Weighted ADMM for Fast Decentralized Network Optimization
Authors:
Open Access
- 25 August 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 64 (22) , 5930-5942
Abstract
In this paper, we propose a weighted alternating direction method of multipliers (ADMM) to solve the consensus optimization problem over a decentralized network. In the proposed algorithm, every node holds its local objective function, exchanges its current iterate with a subset of neighbors, carries on local computation, and eventually reaches an optimal and consensual solution that minimizes the summation of the local objective functions. Compared with the conventional ADMM that is popular in decentralized network optimization, the weighted ADMM is able to reduce the communication cost spent in the optimization process through tuning the weight matrices, which assign beliefs on the neighboring iterates. We first prove convergence and establish linear convergence rate of the weighted ADMM. Second, we maximize the derived convergence speed and obtain the best weight matrices on a given topology. Third, observing that exchanging information with all the neighbors is expensive, we maximize the convergence speed while limit the number of communication arcs. This strategy finds a subset of arcs within the underlying topology to fulfill the optimization task while leads to a favorable tradeoff between the number of iterations and the communication cost per iteration. Numerical experiments demonstrate advantages of the weighted ADMM over its conventional counterpart in expediting the convergence speed and reducing the communication cost.Keywords
Funding Information
- China NSF (61573331)
- Anhui NSF (1608085QF130)
- CAS (XDA06011203)
- US NSF (AST-1547329)
This publication has 36 references indexed in Scilit:
- On the Global and Linear Convergence of the Generalized Alternating Direction Method of MultipliersJournal of Scientific Computing, 2015
- Global Convergence of Splitting Methods for Nonconvex Composite OptimizationSIAM Journal on Optimization, 2015
- Outage Constrained Robust Transmit Optimization for Multiuser MISO Downlinks: Tractable Approximations by Conic OptimizationIEEE Transactions on Signal Processing, 2014
- Decentralized Dynamic Optimization Through the Alternating Direction Method of MultipliersIEEE Transactions on Signal Processing, 2013
- Distributed computation of the Fiedler vector with application to topology inference in ad hoc networksSignal Processing, 2012
- On the $O(1/n)$ Convergence Rate of the Douglas–Rachford Alternating Direction MethodSIAM Journal on Numerical Analysis, 2012
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of MultipliersFoundations and Trends in Machine Learning, 2011
- Distributed Subgradient Methods for Multi-Agent OptimizationIEEE Transactions on Automatic Control, 2009
- Convex Optimization2004
- Fastest Mixing Markov Chain on a GraphSIAM Review, 2004