The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent

DOI10.1007/S10107-014-0826-5zbMath1332.90193OpenAlexW1992841740MaRDI QIDQ5962713

Xiao-Ming Yuan, Bing-sheng He, Yinyu Ye, Caihua Chen

Publication date: 23 February 2016

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

Full work available at URL: https://doi.org/10.1007/s10107-014-0826-5

zbMATH Keywords

convergence analysisconvex programmingsplitting methodsalternating direction method of multipliers

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Nonlinear programming (90C30)

Related Items (only showing first 100 items - show all)

Fast algorithms for sparse inverse covariance estimation ⋮ Alternating direction method of multipliers for linear programming ⋮ Matrix Completion under Low-Rank Missing Mechanism ⋮ A rank-two relaxed parallel splitting version of the augmented Lagrangian method with step size in (0,2) for separable convex programming ⋮ GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning ⋮ On Full Jacobian Decomposition of the Augmented Lagrangian Method for Separable Convex Programming ⋮ An Adaptive Correction Approach for Tensor Completion ⋮ Modified proximal symmetric ADMMs for multi-block separable convex optimization with linear constraints ⋮ On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function ⋮ On the proximal Jacobian decomposition of ALM for multiple-block separable convex minimization problems and its relationship to ADMM ⋮ Alternating proximal gradient method for convex minimization ⋮ Asymmetric forward-backward-adjoint splitting for solving monotone inclusions involving three operators ⋮ Alternating direction method for separable variables under pair-wise constraints ⋮ Background subtraction with Kronecker-basis-representation based tensor sparsity and \(l_{1,1,2}\) norm ⋮ A globally linearly convergent method for pointwise quadratically supportable convex-concave saddle point problems ⋮ A generalized inexact Uzawa method for stable principal component pursuit problem with nonnegative constraints ⋮ Efficient dual ADMMs for sparse compressive sensing MRI reconstruction ⋮ A sequential ADMM algorithm to find sparse LCP solutions using a \(l_2-l_1\) regularization technique with application in bimatrix game ⋮ A unified primal-dual algorithm framework for inequality constrained problems ⋮ Inexact alternating direction methods of multipliers for separable convex optimization ⋮ Regularized Jacobi-type ADMM-methods for a class of separable convex optimization problems in Hilbert spaces ⋮ Sparse Bayesian inference with regularized Gaussian distributions ^* ⋮ Efficient learning rate adaptation based on hierarchical optimization approach ⋮ Inertial proximal ADMM for separable multi-block convex optimizations and compressive affine phase retrieval ⋮ Customized alternating direction methods of multipliers for generalized multi-facility Weber problem ⋮ A proximal fully parallel splitting method with a relaxation factor for separable convex programming ⋮ Fast non-overlapping domain decomposition methods for continuous multi-phase labeling problem ⋮ Block-wise ADMM with a relaxation factor for multiple-block convex programming ⋮ Learning Markov Models Via Low-Rank Optimization ⋮ An efficient semi-proximal ADMM algorithm for low-rank and sparse regularized matrix minimization problems with real-world applications ⋮ A Bregman-style partially symmetric alternating direction method of multipliers for nonconvex multi-block optimization ⋮ A splitting algorithm for constrained optimization problems with parabolic equations ⋮ Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step ⋮ Alternating direction method of multipliers for linear hyperspectral unmixing ⋮ On the Efficiency of Random Permutation for ADMM and Coordinate Descent ⋮ Tensor subspace clustering using consensus tensor low-rank representation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A parallel low rank matrix optimization method for recovering Internet traffic network data via link flow measurement ⋮ Global Complexity Bound of a Proximal ADMM for Linearly Constrained Nonseparable Nonconvex Composite Programming ⋮ A generalized forward-backward splitting operator: degenerate analysis and applications ⋮ A linear algebra perspective on the random multi-block ADMM: the QP case ⋮ A new stopping criterion for Eckstein and Bertsekas's generalized alternating direction method of multipliers ⋮ J‐ADMM for a multi‐contact problem in electro‐elastostatics ⋮ Robust time-of-arrival localization via ADMM ⋮ Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems ⋮ Resolvent splitting for sums of monotone operators with minimal lifting ⋮ Consensus-based Dantzig-Wolfe decomposition ⋮ First-order methods for convex optimization ⋮ A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization ⋮ PCA Sparsified ⋮ A relaxed proximal ADMM method for block separable convex programming ⋮ Localization and approximations for distributed non-convex optimization ⋮ Convergence analysis of an ALF-based nonconvex splitting algorithm with SQP structure ⋮ A survey on operator splitting and decomposition of convex programs ⋮ A two-level distributed algorithm for nonconvex constrained optimization ⋮ Variational image motion estimation by preconditioned dual optimization ⋮ Hybrid Jacobian and Gauss--Seidel Proximal Block Coordinate Update Methods for Linearly Constrained Convex Programming ⋮ A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization ⋮ A 2-block semi-proximal ADMM for solving the H-weighted nearest correlation matrix problem ⋮ Faster convergence of a randomized coordinate descent method for linearly constrained optimization problems ⋮ On the Use of ADMM for Imaging Inverse Problems: the Pros and Cons of Matrix Inversions ⋮ Unnamed Item ⋮ ADMM-Type Methods for Generalized Nash Equilibrium Problems in Hilbert Spaces ⋮ A Three-Operator Splitting Perspective of a Three-Block ADMM for Convex Quadratic Semidefinite Programming and Beyond ⋮ A note on the sufficient initial condition ensuring the convergence of directly extended 3-block ADMM for special semidefinite programming ⋮ Two Symmetrized Coordinate Descent Methods Can Be $O(n^2)$ Times Slower Than the Randomized Version ⋮ Estimation of Graphical Models through Structured Norm Minimization ⋮ Diagonally Dominant Principal Component Analysis ⋮ Lattice-Based Patterned Fabric Inspection by Using Total Variation with Sparsity and Low-Rank Representations ⋮ A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions ⋮ A partially parallel splitting method for multiple-block separable convex programming with applications to robust PCA ⋮ A hybrid splitting method for smoothing Tikhonov regularization problem ⋮ A distributed Douglas-Rachford splitting method for multi-block convex minimization problems ⋮ A Majorized ADMM with Indefinite Proximal Terms for Linearly Constrained Convex Composite Optimization ⋮ ADMM for multiaffine constrained optimization ⋮ 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 ⋮ Low patch-rank image decomposition using alternating minimization algorithms ⋮ Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming ⋮ A Block Successive Upper-Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization ⋮ A sequential updating scheme of the Lagrange multiplier for separable convex programming ⋮ A Computational Framework for Multivariate Convex Regression and Its Variants ⋮ Convergence of ADMM for Three-Block Separable Quadratic Programming Problems with Linear Constraints ⋮ A partial PPA block-wise ADMM for multi-block linearly constrained separable convex optimization ⋮ An alternating minimization method for robust principal component analysis ⋮ Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization ⋮ Efficient and Convergent Preconditioned ADMM for the Potts Models ⋮ Covariate Regularized Community Detection in Sparse Graphs ⋮ On the Global Linear Convergence of the ADMM with MultiBlock Variables ⋮ A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints ⋮ LOW-RANK AND SPARSE MATRIX RECOVERY FROM NOISY OBSERVATIONS VIA 3-BLOCK ADMM ALGORITHM ⋮ On the Convergence Rate of Inexact Majorized sGS ADMM with Indefinite Proximal Terms for Convex Composite Programming ⋮ Alternating Direction Method of Multipliers for a Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction ⋮ Multi-Domain Regularization Based Computed Tomography for High-Speed Rotation Objects ⋮ A proximal partially parallel splitting method for separable convex programs ⋮ Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning ⋮ A partial splitting augmented Lagrangian method for low patch-rank image decomposition ⋮ Two-step fixed-point proximity algorithms for multi-block separable convex problems ⋮ Randomized methods for computing optimal transport without regularization and their convergence analysis

Cites Work

• Unnamed Item
• 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
• Latent variable graphical model selection via convex optimization
• Alternating direction augmented Lagrangian methods for semidefinite programming
• 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
• An \(L _{2}\)-theory for a class of SPDEs driven by Lévy processes
• A note on the alternating direction method of multipliers
• Multiplier and gradient methods
• 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
• Node-Based Learning of Multiple Gaussian Graphical Models
• Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Modified Lagrangians in convex programming and their generalizations
• A splitting method for separable convex programming
• On Alternating Direction Methods of Multipliers: A Historical Perspective
• Convergence Rate Analysis for the Alternating Direction Method of Multipliers with a Substitution Procedure for Separable Convex Programming

This page was built for publication: The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent