On the Global Linear Convergence of the ADMM with MultiBlock Variables

DOI10.1137/140971178zbMATH Open1333.90095arXiv1408.4266OpenAlexW2111076441MaRDI QIDQ5502240FDOQ5502240

Authors: Tian-Yi Lin, Shiqian Ma, Shuzhong Zhang 

Publication date: 18 August 2015

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: The alternating direction method of multipliers (ADMM) has been widely used for solving structured convex optimization problems. In particular, the ADMM can solve convex programs that minimize the sum of $N$ convex functions with $N$-block variables linked by some linear constraints. While the convergence of the ADMM for $N=2$ was well established in the literature, it remained an open problem for a long time whether or not the ADMM for $Nge3$ is still convergent. Recently, it was shown in [3] that without further conditions the ADMM for $Nge3$ may actually fail to converge. In this paper, we show that under some easily verifiable and reasonable conditions the global linear convergence of the ADMM when $Ngeq3$ can still be assured, which is important since the ADMM is a popular method for solving large scale multi-block optimization models and is known to perform very well in practice even when $Nge3$. Our study aims to offer an explanation for this phenomenon.

Full work available at URL: https://arxiv.org/abs/1408.4266

Recommendations

• On the sublinear convergence rate of multi-block ADMM
• Convergence of ADMM for multi-block nonconvex separable optimization models
• Block-wise ADMM with a relaxation factor for multiple-block convex programming
• A multi-parameter parallel ADMM for multi-block linearly constrained separable convex optimization
• Parallel multi-block ADMM with \(o(1/k)\) convergence
• Linearized block-wise alternating direction method of multipliers for multiple-block convex programming
• Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization
• Convergence analysis of L-ADMM for multi-block linear-constrained separable convex minimization problem
• Block-wise alternating direction method of multipliers for multiple-block convex programming and beyond
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent

zbMATH Keywords

alternating direction method of multipliersconvex optimizationglobal linear convergence

Mathematics Subject Classification ID

Convex programming (90C25) Nonlinear programming (90C30)

Cites Work

• Distributed optimization and statistical learning via the alternating direction method of multipliers
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Title not available (Why is that?)
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the global and linear convergence of the generalized alternating direction method of multipliers
• On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
• A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
• Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
• Title not available (Why is that?)
• Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers
• Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs
• Alternating direction method with Gaussian back substitution for separable convex programming
• A note on the alternating direction method of multipliers
• Local Linear Convergence of the Alternating Direction Method of Multipliers for Quadratic Programs
• On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming
• Parallel multi-block ADMM with \(o(1/k)\) convergence
• On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers
• Fast multiple-splitting algorithms for convex optimization
• Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
• Global convergence of unmodified 3-block ADMM for a class of convex minimization problems
• On the convergence analysis of the alternating direction method of multipliers with three blocks
• A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block
• Error Bound and Convergence Analysis of Matrix Splitting Algorithms for the Affine Variational Inequality Problem
• A three-operator splitting scheme and its optimization applications
• Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity
• On the sublinear convergence rate of multi-block ADMM
• Title not available (Why is that?)
• Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions

Cited In (51)

• The statistical rate for support matrix machines under low rankness and row (column) sparsity
• The sparse dynamic factor model: a regularised quasi-maximum likelihood approach
• A class of accelerated GADMM-based method for multi-block nonconvex optimization problems
• Managing randomization in the multi-block alternating direction method of multipliers for quadratic optimization
• On the convergence rate of inexact majorized sGS ADMM with indefinite proximal terms for convex composite programming
• A linear algebra perspective on the random multi-block ADMM: the QP case
• Block-wise ADMM with a relaxation factor for multiple-block convex programming
• Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
• A smooth primal-dual optimization framework for nonsmooth composite convex minimization
• Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
• Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights
• A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming
• On the information-adaptive variants of the ADMM: an iteration complexity perspective
• Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization
• Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization
• On the convergence rate of the augmented Lagrangian-based parallel splitting method
• Convergence rates for an inexact ADMM applied to separable convex optimization
• A proximal alternating direction method for multi-block coupled convex optimization
• Randomized primal-dual proximal block coordinate updates
• On inexact stochastic splitting methods for a class of nonconvex composite optimization problems with relative error
• A generalized inexact Uzawa method for stable principal component pursuit problem with nonnegative constraints
• Title not available (Why is that?)
• An inexact accelerated stochastic ADMM for separable convex optimization
• The augmented Lagrangian method with full Jacobian decomposition and logarithmic-quadratic proximal regularization for multiple-block separable convex programming
• A partial PPA block-wise ADMM for multi-block linearly constrained separable convex optimization
• Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal
• Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization
• Alternating proximal gradient method for convex minimization
• On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming
• Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity
• Image completion and blind deconvolution: model and algorithm
• A proximal fully parallel splitting method with a relaxation factor for separable convex programming
• ADMM for multiaffine constrained optimization
• On the sublinear convergence rate of multi-block ADMM
• An ADMM algorithm for two-stage stochastic programming problems
• Global convergence of unmodified 3-block ADMM for a class of convex minimization problems
• Distributed adaptive dynamic programming for data-driven optimal control
• Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property
• A flexible ADMM algorithm for big data applications
• A two-level distributed algorithm for nonconvex constrained optimization
• On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function
• A survey on some recent developments of alternating direction method of multipliers
• A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
• Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems
• An alternating direction method of multipliers for tensor complementarity problems
• A unified primal-dual algorithm framework for inequality constrained problems
• Estimation of graphical models through structured norm minimization
• Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
• Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
• A modified strictly contractive peaceman-Rachford splitting method for multi-block separable convex programming
• Inexact alternating direction methods of multipliers for separable convex optimization

Uses Software

• Mosek

This page was built for publication: On the Global Linear Convergence of the ADMM with MultiBlock Variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5502240)