On the linear convergence of the alternating direction method of multipliers

DOI10.1007/s10107-016-1034-2zbMath1362.90313arXiv1208.3922OpenAlexW2105693192MaRDI QIDQ517301

Mingyi Hong, Zhi-Quan Luo

Publication date: 23 March 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationerror boundlinear convergenceconvex minimizationdual ascentalternating directions of multipliers

Mathematics Subject Classification ID

Convex programming (90C25)

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, Efficient iterative method for SOAV minimization problem with linear equality and box constraints and its linear convergence, Local R-linear convergence of ADMM-based algorithm for \(\ell_1\)-norm minimization with linear and box constraints, 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, Fast and stable nonconvex constrained distributed optimization: the ELLADA algorithm, Partial Error Bound Conditions and the Linear Convergence Rate of the Alternating Direction Method of Multipliers, On the global and linear convergence of direct extension of ADMM for 3-block separable convex minimization models, Unnamed Item, On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function, Random block coordinate descent methods for linearly constrained optimization over networks, Global convergence of unmodified 3-block ADMM for a class of convex minimization problems, A partially isochronous splitting algorithm for three-block separable convex minimization problems, Distributed algorithms for convex problems with linear coupling constraints, A First-Order Optimization Algorithm for Statistical Learning with Hierarchical Sparsity Structure, Accelerated Bregman operator splitting with backtracking, A generalized inexact Uzawa method for stable principal component pursuit problem with nonnegative constraints, Tight global linear convergence rate bounds for Douglas-Rachford splitting, An estimation approach for the influential-imitator diffusion, Inexact alternating direction methods of multipliers for separable convex optimization, Linearly-convergent FISTA variant for composite optimization with duality, \(O(1/t)\) complexity analysis of the generalized alternating direction method of multipliers, Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization, Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems, Smoothing accelerated proximal gradient method with fast convergence rate for nonsmooth convex optimization beyond differentiability, Consensus-based Dantzig-Wolfe decomposition, Tensor factorization with total variation and Tikhonov regularization for low-rank tensor completion in imaging data, The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates, A two-level distributed algorithm for nonconvex constrained optimization, Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization, Operator Splitting Performance Estimation: Tight Contraction Factors and Optimal Parameter Selection, A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization, A double extrapolation primal-dual algorithm for saddle point problems, Unnamed Item, 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, Sensitivity analysis of the proximal-based parallel decomposition methods, Some results about the isolated calmness of a mixed variational inequality problem, A simple alternating direction method for the conic trust region subproblem, An implementable first-order primal-dual algorithm for structured convex optimization, Distributed model predictive control for continuous‐time nonlinear systems based on suboptimal ADMM, On the Use of ADMM for Imaging Inverse Problems: the Pros and Cons of Matrix Inversions, Douglas-Rachford splitting algorithm for solving state-dependent maximal monotone inclusions, Convergence of the augmented decomposition algorithm, Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property, A general system for heuristic minimization of convex functions over non-convex sets, Distributed optimization and control with ALADIN, The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex, Linear convergence rates for variants of the alternating direction method of multipliers in smooth cases, Convergent prediction-correction-based ADMM for multi-block separable convex programming, Local linear convergence of an ADMM-type splitting framework for equality constrained optimization, Penalized Interaction Estimation for Ultrahigh Dimensional Quadratic Regression, An alternating direction method of multipliers for tensor complementarity problems, A proximal fully parallel splitting method for stable principal component pursuit, Two Symmetrized Coordinate Descent Methods Can Be $O(n^2)$ Times Slower Than the Randomized Version, On Faster Convergence of Cyclic Block Coordinate Descent-type Methods for Strongly Convex Minimization, Estimation of Graphical Models through Structured Norm Minimization, Nonsymmetric proximal point algorithm with moving proximal centers for variational inequalities: convergence analysis, On the convergence analysis of the alternating direction method of multipliers with three blocks, A faster generalized ADMM-based algorithm using a sequential updating scheme with relaxed step sizes for multiple-block linearly constrained separable convex programming, Unnamed Item, A phase-field model of fracture with frictionless contact and random fracture properties: application to thin-film fracture and soil desiccation, Fast algorithms for sparse portfolio selection considering industries and investment styles, Convergence rates for an inexact ADMM applied to separable convex optimization, Convergence study on strictly contractive peaceman-Rachford splitting method for nonseparable convex minimization models with quadratic coupling terms, Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization, Lattice-Based Patterned Fabric Inspection by Using Total Variation with Sparsity and Low-Rank Representations, A partially parallel splitting method for multiple-block separable convex programming with applications to robust PCA, An extended proximal ADMM algorithm for three-block nonconvex optimization problems, On the asymptotic linear convergence speed of Anderson acceleration applied to ADMM, Block-wise Alternating Direction Method of Multipliers for Multiple-block Convex Programming and Beyond, The augmented Lagrangian method with full Jacobian decomposition and logarithmic-quadratic proximal regularization for multiple-block separable convex programming, An objective penalty function method for biconvex programming, Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming, A novel Euler's elastica-based segmentation approach for noisy images using the progressive hedging algorithm, A Block Successive Upper-Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization, Learning a consensus affinity matrix for multi-view clustering via subspaces merging on Grassmann manifold, Accelerated First-Order Primal-Dual Proximal Methods for Linearly Constrained Composite Convex Programming, Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis, A Computational Framework for Multivariate Convex Regression and Its Variants, A proximal alternating direction method for multi-block coupled convex optimization, Randomized primal-dual proximal block coordinate updates, A Proximal Minimization Algorithm for Structured Nonconvex and Nonsmooth Problems, Some characterizations of error bound for non-lower semicontinuous functions, A partial PPA block-wise ADMM for multi-block linearly constrained separable convex optimization, An Uncertainty-Weighted Asynchronous ADMM Method for Parallel PDE Parameter Estimation, Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization, On the Convergence Rate of Inexact Majorized sGS ADMM with Indefinite Proximal Terms for Convex Composite Programming, A Global Dual Error Bound and Its Application to the Analysis of Linearly Constrained Nonconvex Optimization, An inexact accelerated stochastic ADMM for separable convex optimization, A novel augmented Lagrangian method of multipliers for optimization with general inequality constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Fast alternating linearization methods for minimizing the sum of two convex functions
• On the linear convergence of a proximal gradient method for a class of nonsmooth convex minimization problems
• Approximation accuracy, gradient methods, and error bound for structured convex optimization
• On the convergence properties of Hildreth's quadratic programming algorithm
• 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
• A variable-penalty alternating directions method for convex optimization
• On the convergence of the coordinate descent method for convex differentiable minimization
• On the global and linear convergence of the generalized alternating direction method of multipliers
• Alternating proximal gradient method for convex minimization
• 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
• Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
• Iterative Methods for Large Convex Quadratic Programs: A Survey
• Dual Ascent Methods for Problems with Strictly Convex Costs and Linear Constraints: A Unified Approach
• Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• General Projective Splitting Methods for Sums of Maximal Monotone Operators
• Lagrangian dual coordinatewise maximization algorithm for network transportation problems with quadratic costs
• A lagrangean relaxation algorithm for the constrained matrix problem
• Relaxation methods for problems with strictly convex separable costs and linear constraints
• Relaxation Methods for Network Flow Problems with Convex Arc Costs
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Projection methods for variational inequalities with application to the traffic assignment problem
• Computational development of a lagrangian dual approach for quadratic networks
• Relaxation Methods for Problems with Strictly Convex Costs and Linear Constraints
• On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
• On Dual Convergence and the Rate of Primal Convergence of Bregman’s Convex Programming Method
• On the Convergence Rate of Dual Ascent Methods for Linearly Constrained Convex Minimization
• Lipschitz Continuity of Solutions of Linear Inequalities, Programs and Complementarity Problems
• The Linearized Alternating Direction Method of Multipliers for Dantzig Selector
• Fast Alternating Direction Optimization Methods
• 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
• Model Selection and Estimation in Regression with Grouped Variables
• Convex programming in Hilbert space
• Convex Analysis
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent