Is ADMM always faster than Average Consensus?

There is a common belief that the ADMM, a popular algorithm employed for distributed convex optimization over graphs, is faster than another distributed algorithm typically referred as the Average Consensus. This belief is based on the observation that the ratio of the number of iterations necessary...

Full description

Saved in:
Bibliographic Details
Published in:Automatica (Oxford) 2018-05, Vol.91, p.311-315
Main Authors: Bof, Nicoletta, Carli, Ruggero, Schenato, Luca
Format: Article
Language:English
Subjects:
ADMM
Average Consensus
Distributed control
Optimization problems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:There is a common belief that the ADMM, a popular algorithm employed for distributed convex optimization over graphs, is faster than another distributed algorithm typically referred as the Average Consensus. This belief is based on the observation that the ratio of the number of iterations necessary to achieve a desired error with respect to the optimal solution of the ADMM vs the Average Consensus goes to zero as the graph becomes larger or less connected. In this work, we provide a closed form expression for the rate of ADMM as a function of the essential spectral radius of the graph, which is a measure of connectivity of the graph, for scalar quadratic cost functions with identical curvature, and we show that its rate of convergence can be slower than the Average Consensus when the graph is highly connected. Moreover, via extensive simulations, we show that ADMM performance, differently from the average consensus, rapidly degrade as the cost functions become skewed, thus making the latter approach competitive also for sparse graphs.
ISSN:0005-1098
1873-2836
DOI:10.1016/j.automatica.2018.01.009