On the Linear Convergence of the Alternating Direction Method of Multipliers
arXiv:1208.3922
Abstract
We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global linear convergence of the ADMM for minimizing the sum of any number of convex separable functions. This result settles a key question regarding the convergence of the ADMM when the number of blocks is more than two or if the strong convexity is absent. It also implies the linear convergence of the ADMM for several contemporary applications including LASSO, Group LASSO and Sparse Group LASSO without any strong convexity assumption. Our proof is based on estimating the distance from a dual feasible solution to the optimal dual solution set by the norm of a certain proximal residual, and by requiring the dual stepsize to be sufficiently small.
References in corpus (2)
Cited by in corpus (36)
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- Communication Efficient Distributed Optimization using an Approximate Newton-type Method
- D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization
- Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
- Distributed Optimal Power Flow Algorithm for Balanced Radial Distribution Networks
- Bregman Alternating Direction Method of Multipliers
- Distributed Optimization With Local Domains: Applications in MPC and Network Flows
- A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization
- Quantized Consensus ADMM for Multi-Agent Distributed Optimization
- Quantized Consensus by the ADMM: Probabilistic versus Deterministic Quantizers
- Online Alternating Direction Method (longer version)
- Learning the Conditional Independence Structure of Stationary Time Series: A Multitask Learning Approach
- Distributed recovery of jointly sparse signals under communication constraints
- Parallel Direction Method of Multipliers
- On the Sublinear Convergence Rate of Multi-Block ADMM
- Towards A Deeper Geometric, Analytic and Algorithmic Understanding of Margins
- Distributed Multi-Task Learning with Shared Representation
- Randomized Primal-Dual Proximal Block Coordinate Updates
- On the Global Linear Convergence of the ADMM with Multi-Block Variables
- A Randomized Nonmonotone Block Proximal Gradient Method for a Class of Structured Nonlinear Programming
- A distributed primal-dual interior-point method for loosely coupled problems using ADMM
- Playing with Duality: An Overview of Recent Primal-Dual Approaches for Solving Large-Scale Optimization Problems
- Extended ADMM and BCD for Nonseparable Convex Minimization Models with Quadratic Coupling Terms: Convergence Analysis and Insights
- Iteration complexity analysis of dual first order methods for conic convex programming
- An Alternating Direction Method Approach to Cloud Traffic Management
- Graded quantization for multiple description coding of compressive measurements
- Inexact alternating direction multiplier methods for separable convex optimization
- A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
- On Faster Convergence of Cyclic Block Coordinate Descent-type Methods for Strongly Convex Minimization
- On the Duality Gap Convergence of ADMM Methods
- Parallel Statistical Multi-resolution Estimation
- Stochastic Parallel Block Coordinate Descent for Large-scale Saddle Point Problems
- Decomposition of Longitudinal Deformations via Beltrami Descriptors
- A Scalable Frank-Wolfe based Augmented Lagrangian Method for Linearly Constrained Composite Convex Programming
- ADMM for Distributed Dynamic Beamforming
- On linear convergence of a distributed dual gradient algorithm for linearly constrained separable convex problems