检索结果-内蒙古大学图书馆

Accelerated Distributed Dual Averaging Over Evolving Networks of Growing Connectivity

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2018年第7期66卷 1845-1859页

作者： Liu, Sijia Chen, Pin-Yu Hero, Alfred O. Univ Michigan Ann Arbor MI 48109 USA IBM Res MIT IBM Watson AI Lab Cambridge MA 02142 USA IBM Thomas J Watson Res Ctr AI Fdn Learning Grp Yorktown Hts NY 10598 USA

We consider the problem of accelerating distributed optimization in multi-agent networks by sequentially adding edges. Specifically, we extend the distributed dual averaging (DDA) subgradient algorithm to evolving networks of growing connectivity and analyze the corresponding improvement in convergence rate. It is known that the convergence rate of DDA is influenced by the algebraic connectivity of the underlying network, where better connectivity leads to faster convergence. However, the impact of the network topology design on the convergence rate of DDA has not been fully understood. In this paper, we begin by designing network topologies via edge selection and scheduling in an offline manner. For edge selection, we determine the best set of candidate edges that achieves the optimal tradeoff between the growth of network connectivity and the usage of network resources. The dynamics of network evolution is then incurred by edge scheduling. Furthermore, we provide a tractable approach to analyze the improvement in the convergence rate of DDA induced by the growth of network connectivity. Our analysis reveals the connection between network topology design and the convergence rate of DDA, and provides quantitative evaluation of DDA acceleration for distributed optimization that is absent in the existing analysis. Lastly, numerical experiments show that DDA can be significantly accelerated using a sequence of well-designed networks, and our theoretical predictions are well matched to its empirical convergence behavior.

关键词： Distributed dual averaging subgradient algorithm topology design algebraic connectivity multi-agent network

来源：评论

学校读者我要写书评

暂无评论

The matrix pencil nearness problem in structural dynamic model updating

引用

JOURNAL OF ENGINEERING MATHEMATICS 2015年第1期93卷 131-143页

作者： Yuan, Quan Dai, Hua Nanjing Univ Aeronaut & Astronaut Dept Math Nanjing 210016 Peoples R China

This paper considers the problem of finding the least change adjustment to a given matrix pencil. The desired matrix properties, including satisfaction of the characteristic equation, symmetry, positive semidefiniteness, and sparsity, are imposed as side constraints to form the optimal matrix pencil approximation problem. This problem is related to the frequently encountered engineering problem of a structural modification to the dynamic behavior of a structure. Conditions ensuring the feasible region of the matrix pencil nearness problem are analyzed using a matrix decomposition technique. An unconstrained minimization formulation is presented in terms of the Lagrangian multiplier method and solved by a subgradient algorithm. Numerical results are included to illustrate the performance and application of the proposed method.

关键词： Dual problem Matrix pencil nearness problem Model updating subgradient algorithm

来源：评论

学校读者我要写书评

暂无评论

On some difficult linear programs coming from set partitioning

引用

DISCRETE APPLIED MATHEMATICS 2002年第1-2期118卷 3-11页

作者： Barahona, F Anbil, R IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Caleb Technol Corp Austin TX 78759 USA

We deal with the linear programming relaxation of set partitioning problems arising in airline crew scheduling. Some of these linear programs have been extremely difficult to solve with the traditional algorithms, We have used an extension of the subgradient algorithm, the volume algorithm, to produce primal solutions that might violate the constraints by at most 2%, and that are within 1% of the lower bound. This method is fast, requires minimal storage, and can be parallelized in a straightforward way. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： subgradient algorithm volume algorithm large scale linear programming

来源：评论

学校读者我要写书评

暂无评论

Distributed Consensus Optimization in Multiagent Networks With Time-Varying Directed Topologies and Quantized Communication

引用

IEEE TRANSACTIONS ON CYBERNETICS 2017年第8期47卷 2044-2057页

作者： Li, Huaqing Huang, Chicheng Chen, Guo Liao, Xiaofeng Huang, Tingwen Southwest Univ Coll Elect & Informat Engn Chongqing 400715 Peoples R China Univ Newcastle Sch Elect Engn & Comp Sci Sydney NSW 2308 Australia Texas A&M Univ Qatar Doha 23874 Qatar

This paper considers solving a class of optimization problems which are modeled as the sum of all agents' convex cost functions and each agent is only accessible to its individual function. Communication between agents in multiagent networks is assumed to be limited: each agent can only interact information with its neighbors by using time-varying communication channels with limited capacities. A technique which overcomes the limitation is to implement a quantization process to the interacted information. The quantized information is first encoded as a binary sequence at the side of each agent before sending. After the binary sequence is received by the neighboring agent, corresponding decoding scheme is utilized to resume the original information with a certain degree of error which is caused by the quantization process. With the availability of each agent's encoding states (associated with its out-channels) and decoding states (associated with its in-channels), we devise a set of distributed optimization algorithms that generate two iterative sequences, one of which converges to the optimal solution and the other of which reaches to the optimal value. We prove that if the parameters satisfy some mild conditions, the quantization errors are bounded and the consensus optimization can be achieved. How to minimize the number of quantization level of each connected communication channel in fixed networks is also explored thoroughly. It is found that, by properly choosing system parameters, one bit information exchange suffices to ensure consensus optimization. Finally, we present two numerical simulation experiments to illustrate the efficacy of the algorithms as well as to validate the theoretical findings.

关键词： Directed time-varying topology distributed convex optimization multiagent systems quantization communication subgradient algorithm

来源：评论

学校读者我要写书评

暂无评论

subgradient Method for Convex Feasibility on Riemannian Manifolds

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2012年第3期152卷 773-785页

作者： Bento, Glaydston C. Melo, Jefferson G. IME Univ Fed Goias BR-74001970 Goiania Go Brazil

In this paper, a subgradient type algorithm for solving convex feasibility problem on Riemannian manifold is proposed and analysed. The sequence generated by the algorithm converges to a solution of the problem, provided the sectional curvature of the manifold is non-negative. Moreover, assuming a Slater type qualification condition, we analyse a variant of the first algorithm, which generates a sequence with finite convergence property, i.e., a feasible point is obtained after a finite number of iterations. Some examples motivating the application of the algorithm for feasibility problems, nonconvex in the usual sense, are considered.

关键词： Nonsmooth analysis Feasibility problem General convexity subgradient algorithm Riemannian manifolds

来源：评论

学校读者我要写书评

暂无评论

Least-squares estimation of two-ordered monotone regression curves

引用

JOURNAL OF NONPARAMETRIC STATISTICS 2010年第8期22卷 1019-1037页

作者： Balabdaoui, Fadoua Rufibach, Kaspar Santambrogio, Filippo Univ Zurich Biostat Unit Inst Social & Prevent Med CH-8001 Zurich Switzerland Univ Paris 09 CEREMADE F-75775 Paris 16 France Univ Gottingen Inst Math Stochast D-37077 Gottingen Germany

In this paper, we consider the problem of finding the least-squares estimators of two isotonic regression curves [image omitted] and [image omitted] under the additional constraint that they are ordered, for example, [image omitted]. Given two sets of n data points y1, ..., yn and z1, ..., zn observed at (the same) design points, the estimates of the true curves are obtained by minimising the weighted least-squares criterion [image omitted] over the class of pairs of vectors (a, b)nxn such that a1a2 center dot center dot center dot an, b1b2 center dot center dot center dot bn, and aibi, i=1, ..., n. The characterisation of the estimators is established. To compute these estimators, we use an iterative projected subgradient algorithm, where the projection is performed with a 'generalised' pool-adjacent-violaters algorithm, a byproduct of this work. Then, we apply the estimation method to real data from mechanical engineering.

关键词： least squares monotone regression pool-adjacent-violaters algorithm shape constraint estimation subgradient algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimax Feature Selection Problem for Constructing a Classifier Using Support Vector Machines

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2010年第5期50卷 917-925页

作者： Goncharov, Yu. V. Russian Acad Sci Dorodnicyn Comp Ctr Moscow 119333 Russia

A minimax feature selection problem for constructing a classifier using support vector machines is considered. Properties of the solutions of this problem are analyzed. An improvement of the saddle point search algorithm based on extending the bound for the step parameter is proposed. A new nondifferential optimization algorithm is developed that, together with the saddle point search algorithm, forms a hybrid feature selection algorithm. The efficiency of the algorithm for computing Dykstra's projections as applied for the feature selection problem is experimentally estimated.

关键词： feature selection problem minimax problem support vector machine saddle point searching algorithm subgradient algorithm

来源：评论

学校读者我要写书评

暂无评论

A variable target value method for nondifferentiable optimization

引用

OPERATIONS RESEARCH LETTERS 2000年第1期26卷 1-8页

作者： Sherali, HD Choi, G Tuncbilek, CH Virginia Polytech Inst & State Univ Dept Ind & Syst Engn Blacksburg VA 24061 USA

This paper presents a new Variable target value method (VTVM) that can be used in conjunction with pure or deflected subgradient strategies. The proposed procedure assumes no a priori knowledge regarding bounds on the optimal value. The target values are updated iteratively whenever necessary, depending on the information obtained in the process of the algorithm. Moreover, convergence of the sequence of incumbent solution values to a near-optimum is proved using popular, practically desirable step-length rules. In addition, the method also allows a wide flexibility in designing subgradient deflection strategies by imposing only mild conditions on the deflection parameter. Some preliminary computational results are reported on a set of standard test problems in order to demonstrate the viability of this approach. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： nondifferentiable optimization subgradient algorithm conjugate subgradient methods deflected subgradient directions variable target value method

来源：评论

学校读者我要写书评

暂无评论

Lifetime Maximization in Wireless Sensor Networks with Network Coding

Lifetime Maximization in Wireless Sensor Networks with Netwo...

引用

3rd International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM 2007)

作者： Hong, Yongfa Xu, Juan Jiang, Changjun Tongji Univ Coll Elect & Informat Engn Shanghai 200092 Peoples R China Shandong Univ Sci & Technol Coll Informat Sci & Technol Qingdao Peoples R China

ISBN: (纸本)9781424413119

The lifetime is a critical parameter for wireless sensor networks, which is defined as the maximum time of delivering certain data to the sink node before sensor node runs out of energy under an initial energy is given. In this paper, we propose a distributed algorithm for data gathering in wireless sensor networks with the assistance of network coding, such that the network lifetime is maximized. We prove rigorously that the proposed algorithm converge to the optimal solution of regularized problem.

关键词： network lifetime wireless sensor networks subgradient algorithm distributed algorithm network coding

来源：评论

学校读者我要写书评

暂无评论

On ascending Vickrey auctions for heterogeneous objects

引用

JOURNAL OF ECONOMIC THEORY 2007年第1期132卷 95-118页

作者： de Vries, Sven Schummer, James Vohra, Rakesh V. Northwestern Univ JL Kellogg Grad Sch Management Dept Managerial Econ & Decis Sci Evanston IL 60208 USA Tech Univ Munich Zentrum Math D-85747 Garching Germany

We construct an ascending auction for heterogeneous objects by applying a primal-dual algorithm to a linear program that represents the efficient-allocation problem for this setting. The auction assigns personalized prices to bundles, and asks bidders to report their preferred bundles in each round. A bidder's prices are increased when he belongs to a "minimally undersupplied" set of bidders. This concept generalizes the notion of "overdemanded" sets of objects introduced by Demange, Gale, and Sotomayor for the one-to-one assignment problem. Under a submodularity condition, the auction implements the Vickrey-Clarke-Groves outcome;we show that this type of condition is somewhat necessary to do so. When classifying the ascending-auction literature in terms of their underlying algorithms, our auction fills a gap in that literature. We relate our results to various ascending auctions in the literature. (c) 2005 Elsevier Inc. All rights reserved.

关键词： Vickrey auctions combinatorial auctions duality primal-dual algorithm subgradient algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：