Distributed Coordination for Nonsmooth Convex Optimization via Saddle-Point Dynamics
Distributed Coordination for Nonsmooth Convex Optimization via Saddle-Point Dynamics
复制标题
DOI：
10.1007/s00332-018-9516-4
复制
发表时间：
2016-06
影响因子：
3
通讯作者：
J. Cortés;Simon K. Niederländer
中科院分区：
文献类型：
--
作者：
J. Cortés;Simon K. Niederländer
本文研究了一类具有内在分布式结构的非光滑凸优化问题的连续时间协调算法。我们的算法设计建立在非光滑凸规划的解被刻画为增广拉格朗日的鞍点的基础上。我们证明了相关的鞍点动力学是渐近正确的，但通常由于全局惩罚参数的存在而不是分布的。这促使设计了一种不连续的鞍点类算法，该算法具有相同的收敛特性，并且完全服从于分布式实现。我们的收敛证明依赖于鞍点动力学的一个新的全局Lyapunov函数的辨识。这种新颖性还允许我们识别目标函数的温和凸性和正则性条件，这些条件保证了所提出的算法在等式约束下的凸优化问题的指数收敛速度。各种例子说明了我们的讨论。
This paper considers continuous-time coordination algorithms for networks of agents that seek to collectively solve a general class of nonsmooth convex optimization problems with an inherent distributed structure. Our algorithm design builds on the characterization of the solutions of the nonsmooth convex program as saddle points of an augmented Lagrangian. We show that the associated saddle-point dynamics are asymptotically correct but, in general, not distributed because of the presence of a global penalty parameter. This motivates the design of a discontinuous saddle-point-like algorithm that enjoys the same convergence properties and is fully amenable to distributed implementation. Our convergence proofs rely on the identification of a novel global Lyapunov function for saddle-point dynamics. This novelty also allows us to identify mild convexity and regularity conditions on the objective function that guarantee the exponential convergence rate of the proposed algorithms for convex optimization problems subject to equality constraints. Various examples illustrate our discussion.