Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems

By Euhanna Ghadimi, André M. H. Teixeira, Iman Shames, Mikael Johansson. IEEE Transactions on Automatic Control, 2013

569 citations recorded by the source corpus.

The alternating direction method of multipliers (ADMM) has emerged as a powerful technique for large-scale structured optimization. Despite many recent results on the convergence properties of ADMM, a quantitative characterization of the impact of the algorithm parameters on the convergence times of the method is still lacking. In this paper we find the optimal algorithm parameters that minimize the convergence factor of the ADMM iterates in the context of ℓ2-regularized minimization and constrained quadratic programming. Numerical examples show that our parameter selection rules significantly outperform existing alternatives in the literature.

Subfields: Artificial Intelligence, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/14c0cd1288ecc2f8e388cf3fc105034fd6e651ef

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Signal Processing

Citations in the corpus

Multi-label Learning with Missing Labels Using Mixed Dependency Graphs (2018, background): “To Q and (cid:4) The updates for Q t + 1 and (cid:4) t + 1 are closed form, According to the analysis in Ghadimi et al. (2015), Raghu-nathan and Di Cairano (2014), the above ADMM algorithm is guaranteed to converge to the global minimum of Problem (28).”
Graph Learning Based on Total Variation Minimization (2018, methodology): “However, due to the advantages provided by the varying penalty strategy [31, Section 2.3] and the reasonable stopping criterion, we rather advocate using the augmented ADMM method from [31] with the closed form expressions for the proximal operators elaborated in [10] and the scaling matrix [31] cho”
Understanding Traffic Density from Large-Scale Web Camera Data (2017, methodology): “The loss function is optimized via batch-based ADMM[14] and backpropagation.”
Tight global linear convergence rate bounds for Douglas–Rachford splitting (2015, background): “In [16] it is shown that the linear convergence rate bounds in [17] (which are generalizations of the bounds in [15]) are tight for composite convex optimization problems where one function is strongly convex and smooth.”
Reference and command governors for systems with constraints: A survey on theory and applications (2017, methodology): “The methods in [99,107] require the QP to be strongly convex.”
A General Analysis of the Convergence of ADMM (2015, unknown): “The construction of the lower bound in this section is similar to a construction given in Ghadimi et al. (2015).”
DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers (2015, methodology): “Among dual descent methods, decentralized implementation of the alternating directions method of multipliers (ADMM), known as DADMM, is proven to be very efficient with respect to convergence time [8], [20]–[23], [28].”
Adaptive Consensus ADMM for Distributed Optimization (2017, methodology): “To improve practical convergence of ADMM, fixed optimal parameters are discussed in (Raghunathan & Di Cairano, 2014; Ghadimi et al., 2015; Nishihara et al., 2015; França & Bento, 2016).”
Quantized consensus ADMM for multi-agent distributed optimization (2015, methodology): “We refer readers to [18, 20, 29] for discussions on the effect of ρ on the ADMM.”
Plug-and-Play Priors for Bright Field Electron Tomography and Sparse Interpolation (2015, background): “High quality reconstruction of these samples from tomographic projections is possible by exploiting the redundancy caused by repeating structures.”
Multi-Agent Distributed Optimization via Inexact Consensus ADMM (2014, unknown): “, see [33].”