Linearly convergent decentralized consensus optimization with the alternating direction method of multipliers

W. Shi, Q. Ling, K. Yuan, G. Wu, and W. Yin

ICASSP 2013, Vancouver, Canada

Overview

In a decentralized consensus optimization problem, a network of agents minimizes the summation of their local objective functions on a common set of decision variables, allowing only information exchange among neighbors. The alternating direction method of multipliers (ADMM) is a powerful tool for solving the problem with empirically fast convergence.

This paper establishes the linear convergence rate of the ADMM in decentralized consensus optimization assuming that all local objectives are strongly convex. The problem of averaging consensus is a special case. The theoretical convergence rate is a function of the network topology, properties of the local objective functions, and the algorithm parameter. This result not only gives a performance guarantee for the ADMM but also provides a guideline to accelerate its convergence for decentralized consensus optimization problems.

Citation

W. Shi, Q. Ling, K. Yuan, G. Wu, and W. Yin, Linearly convergent decentralized consensus optimization with the alternating direction method of multipliers, in proceedings of International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vancouver, Canada, 2013


« Back