Is ADMM always faster than Average Consensus?. (May 2018)

• Record Type: Journal Article
• Authors: Bof, Nicoletta; Carli, Ruggero; Schenato, Luca
• Is Part Of: Automatica. Volume 91(2018)
• Page Start: 311
• Page End: 315
• Publication Date: 2018-05
• Subjects: Distributed control -- Optimization problems -- Average Consensus -- ADMM; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2018.01.009
• Languages: English
• ISSNs: 0005-1098

Abstract

Abstract: 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.