On the sublinear convergence rate of multi-block ADMM

DOI10.1007/s40305-015-0092-0zbMath1323.90052arXiv1408.4265OpenAlexW2161823659MaRDI QIDQ888303

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

Publication date: 30 October 2015

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationalternating direction method of multiplierssublinear convergence rate

Mathematics Subject Classification ID

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

Related Items

A survey on some recent developments of alternating direction method of multipliers, 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, Alternating direction method of multipliers for separable convex optimization of real functions in complex variables, 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, A generalized inexact Uzawa method for stable principal component pursuit problem with nonnegative constraints, A unified primal-dual algorithm framework for inequality constrained problems, Inertial proximal ADMM for separable multi-block convex optimizations and compressive affine phase retrieval, On convergence rates of proximal alternating direction method of multipliers, \(O(1/t)\) complexity analysis of the generalized alternating direction method of multipliers, Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems, A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization, Parallel multi-block ADMM with \(o(1/k)\) convergence, A two-level distributed algorithm for nonconvex constrained 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, Linearized block-wise alternating direction method of multipliers for multiple-block 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, 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, 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, An extragradient-based alternating direction method for convex minimization, Efficient alternating minimization methods for variational edge-weighted colorization models, A Simple Parallel Algorithm with an $O(1/t)$ Convergence Rate for General Convex Programs, ON THE CONVERGENCE RATE OF THE ALTERNATING DIRECTION METHOD OF MULTIPLIERS IN A COMPLEX DOMAIN, Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization, A Majorized ADMM with Indefinite Proximal Terms for Linearly Constrained Convex Composite Optimization, A parallel line search subspace correction method for composite convex optimization, An extended proximal ADMM algorithm for three-block nonconvex optimization problems, ADMM for multiaffine constrained optimization, The augmented Lagrangian method with full Jacobian decomposition and logarithmic-quadratic proximal regularization for multiple-block separable convex programming, Randomized primal-dual proximal block coordinate updates, On the Global Linear Convergence of the ADMM with MultiBlock Variables, Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization, Proximal ADMM for nonconvex and nonsmooth optimization, An efficient partial parallel method with scaling step size strategy for three-block convex optimization problems, Two-step fixed-point proximity algorithms for multi-block separable convex problems

Uses Software

• RASL

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
• 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
• A Convergent $3$-Block Semi-Proximal ADMM for Convex Minimization Problems with One Strongly Convex Block
• Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
• The Numerical Solution of Parabolic and Elliptic Differential Equations
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• A Block Successive Upper-Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization
• 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
• 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 on Quadratic or Linear Programs
• On the Global Linear Convergence of the ADMM with MultiBlock Variables
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent