Primal Recovery from Consensus-Based Dual Decomposition for Distributed Convex Optimization

详细信息    查看全文

• 作者：Andrea Simonetto ; Hadi Jamali-Rad
• 关键词：Distributed convex optimization ; Dual decomposition ; Primal recovery ; Consensus algorithm ; Subgradient optimization ; Epsilon ; subgradient ; Ergodic convergence
• 刊名：Journal of Optimization Theory and Applications
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：168
• 期：1
• 页码：172-197
• 全文大小：761 KB
• 刊物主题：Calculus of Variations and Optimal Control; Optimization; Optimization; Theory of Computation; Applications of Mathematics; Engineering, general; Operations Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2878

文摘

Dual decomposition has been successfully employed in a variety of distributed convex optimization problems solved by a network of computing and communicating nodes. Often, when the cost function is separable but the constraints are coupled, the dual decomposition scheme involves local parallel subgradient calculations and a global subgradient update performed by a master node. In this paper, we propose a consensus-based dual decomposition to remove the need for such a master node and still enable the computing nodes to generate an approximate dual solution for the underlying convex optimization problem. In addition, we provide a primal recovery mechanism to allow the nodes to have access to approximate near-optimal primal solutions. Our scheme is based on a constant stepsize choice, and the dual and primal objective convergence are achieved up to a bounded error floor dependent on the stepsize and on the number of consensus steps among the nodes.