On the Global Linear Convergence of the ADMM with MultiBlock Variables

DOI10.1137/140971178zbMath1333.90095arXiv1408.4266OpenAlexW2111076441MaRDI QIDQ5502240

Tian-Yi Lin, Shu-Zhong Zhang, Shi-Qian Ma

Publication date: 18 August 2015

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

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

zbMATH Keywords

convex optimizationalternating direction method of multipliersglobal linear convergence

Mathematics Subject Classification ID

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

Related Items

On inexact stochastic splitting methods for a class of nonconvex composite optimization problems with relative error, Managing randomization in the multi-block alternating direction method of multipliers for quadratic optimization, A survey on some recent developments of alternating direction method of multipliers, 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, On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function, Alternating proximal gradient method for convex minimization, Global convergence of unmodified 3-block ADMM for a class of convex minimization problems, On the information-adaptive variants of the ADMM: an iteration complexity perspective, Image completion and blind deconvolution: model and algorithm, An ADMM algorithm for two-stage stochastic programming problems, A generalized inexact Uzawa method for stable principal component pursuit problem with nonnegative constraints, On the sublinear convergence rate of multi-block ADMM, A unified primal-dual algorithm framework for inequality constrained problems, Inexact alternating direction methods of multipliers for separable convex optimization, A proximal fully parallel splitting method with a relaxation factor for separable convex programming, Unnamed Item, A linear algebra perspective on the random multi-block ADMM: the QP case, Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems, A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization, A flexible ADMM algorithm for big data applications, A two-level distributed algorithm for nonconvex constrained optimization, Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization, Hybrid Jacobian and Gauss--Seidel Proximal Block Coordinate Update Methods for Linearly Constrained Convex Programming, A modified strictly contractive peaceman-Rachford splitting method for multi-block separable convex programming, Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights, On the convergence rate of the augmented Lagrangian-based parallel splitting method, Distributed adaptive dynamic programming for data-driven optimal control, Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs, Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property, A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming, An alternating direction method of multipliers for tensor complementarity problems, 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, Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization, Estimation of Graphical Models through Structured Norm Minimization, Convergence rates for an inexact ADMM applied to separable convex optimization, Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization, Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal, A Majorized ADMM with Indefinite Proximal Terms for Linearly Constrained Convex Composite Optimization, ADMM for multiaffine constrained optimization, The augmented Lagrangian method with full Jacobian decomposition and logarithmic-quadratic proximal regularization for multiple-block separable convex programming, A proximal alternating direction method for multi-block coupled convex optimization, Randomized primal-dual proximal block coordinate updates, On the Convergence Rate of Inexact Majorized sGS ADMM with Indefinite Proximal Terms for Convex Composite Programming, An inexact accelerated stochastic ADMM for separable convex optimization

Uses Software

• Mosek

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity
• A three-operator splitting scheme and its optimization applications
• On the sublinear convergence rate of multi-block ADMM
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• Global convergence of unmodified 3-block ADMM for a class of convex minimization problems
• Parallel multi-block ADMM with \(o(1/k)\) convergence
• A note on the alternating direction method of multipliers
• On the convergence analysis of the alternating direction method of multipliers with three blocks
• On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers
• 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
• Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming
• Fast Multiple-Splitting Algorithms for Convex Optimization
• A Convergent $3$-Block Semi-Proximal ADMM for Convex Minimization Problems with One Strongly Convex Block
• Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• On Full Jacobian Decomposition of the Augmented Lagrangian Method for Separable Convex Programming
• Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Error Bound and Convergence Analysis of Matrix Splitting Algorithms for the Affine Variational Inequality Problem
• A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints
• Iteration-Complexity of Block-Decomposition Algorithms and the Alternating Direction Method of Multipliers
• Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions
• Local Linear Convergence of the Alternating Direction Method of Multipliers for Quadratic Programs
• Local Linear Convergence of the Alternating Direction Method of Multipliers on Quadratic or Linear Programs
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent