Distributed Optimization: Convergence Conditions from a Dynamical System Perspective
Preprint
Abstract
This paper explores the fundamental properties of distributed minimization of a sum of functions with each function only known to one node, and a pre-specified level of node knowledge and computational capacity. We define the optimization information each node receives from its objective function, the neighboring information each node receives from its neighbors, and the computational capacity each node can take advantage of in controlling its state. It is proven that there exist a neighboring information way and a control law that guarantee global optimal consensus if and only if the solution sets of the local objective functions admit a nonempty intersection set for fixed strongly connected graphs. Then we show that for any tolerated error, we can find a control law that guarantees global optimal consensus within this error for fixed, bidirectional, and connected graphs under mild conditions. For time-varying graphs, we show that optimal consensus can always be achieved as long as the graph is uniformly jointly strongly connected and the nonempty intersection condition holds. The results illustrate that nonempty intersection for the local optimal solution sets is a critical condition for successful distributed optimization for a large class of algorithms.Keywords
All Related Versions
This publication has 33 references indexed in Scilit:
- Randomized optimal consensus of multi-agent systemsAutomatica, 2012
- Multi-agent robust consensus-Part I: Convergence analysis2011
- Zero-gradient-sum algorithms for distributed convex optimization: The continuous-time case2011
- Global target aggregation and state agreement of nonlinear multi-agent systems with switching topologiesAutomatica, 2009
- Distributed Consensus in Multi-vehicle Cooperative Control2008
- Algebraic Graph Theory2001
- Incremental Gradient Algorithms with Stepsizes Bounded Away from ZeroComputational Optimization and Applications, 1998
- Nonsmooth Analysis and Control Theory1998
- Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problemsLinear Algebra and its Applications, 1991
- Stability Theory by Liapunov’s Direct Method1977