A unitary distributed subgradient method for multi-agent optimization with different coupling sources
Preprint
Abstract
In this work, we first consider distributed convex constrained optimization problems where the objective function is encoded by multiple local and possibly nonsmooth objectives privately held by a group of agents, and propose a distributed subgradient method with double averaging (abbreviated as ${\rm DSA_2}$) that only requires peer-to-peer communication and local computation to solve the global problem. The algorithmic framework builds on dual methods and dynamic average consensus; the sequence of test points is formed by iteratively minimizing a local dual model of the overall objective where the coefficients, i.e., approximated subgradients of the objective, are supplied by the dynamic average consensus scheme. We theoretically show that ${\rm DSA_2}$ enjoys non-ergodic convergence properties, i.e., the local minimizing sequence itself is convergent, a distinct feature that cannot be found in existing results. Specifically, we establish a convergence rate of $O(\frac{1}{\sqrt{t}})$ in terms of objective function error. Then, extensions are made to tackle distributed optimization problems with coupled functional constraints by combining ${\rm DSA_2}$ and dual decomposition. This is made possible by Lagrangian relaxation that transforms the coupling in constraints of the primal problem into that in cost functions of the dual, thus allowing us to solve the dual problem via ${\rm DSA_2}$. Both the dual objective error and the quadratic penalty for the coupled constraint are proved to converge at a rate of $O(\frac{1}{\sqrt{t}})$, and the primal objective error asymptotically vanishes. Numerical experiments and comparisons are conducted to illustrate the advantage of the proposed algorithms and validate our theoretical findings.
Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Dual subgradient method with averaging for optimal resource allocationEuropean Journal of Operational Research, 2018
- Network Topology and Communication-Computation Tradeoffs in Decentralized OptimizationProceedings of the IEEE, 2018
- Dual decomposition for multi-agent distributed optimization with coupling constraintsAutomatica, 2017
- Primal Recovery from Consensus-Based Dual Decomposition for Distributed Convex OptimizationJournal of Optimization Theory and Applications, 2015
- Quasi-monotone Subgradient Methods for Nonsmooth Convex MinimizationJournal of Optimization Theory and Applications, 2014
- Constrained Consensus and Optimization in Multi-Agent NetworksIEEE Transactions on Automatic Control, 2010
- Discrete-time dynamic average consensusAutomatica, 2010
- Distributed average consensus with least-mean-square deviationJournal of Parallel and Distributed Computing, 2007
- Collective dynamics of ‘small-world’ networksNature, 1998
- Distributed asynchronous deterministic and stochastic gradient optimization algorithmsIEEE Transactions on Automatic Control, 1986