On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming
From MaRDI portal
Publication:2220656
DOI10.1007/S10107-019-01423-XzbMATH Open1458.90509arXiv1803.10803OpenAlexW2971348295WikidataQ127331854 ScholiaQ127331854MaRDI QIDQ2220656FDOQ2220656
Liang Chen, Xudong Li, Defeng Sun, Kim-Chuan Toh
Publication date: 25 January 2021
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: In this paper, we show that for a class of linearly constrained convex composite optimization problems, an (inexact) symmetric Gauss-Seidel based majorized multi-block proximal alternating direction method of multipliers (ADMM) is equivalent to an {em inexact} proximal augmented Lagrangian method (ALM). This equivalence not only provides new perspectives for understanding some ADMM-type algorithms but also supplies meaningful guidelines on implementing them to achieve better computational efficiency. Even for the two-block case, a by-product of this equivalence is the convergence of the whole sequence generated by the classic ADMM with a step-length that exceeds the conventional upper bound of , if one part of the objective is linear. This is exactly the problem setting in which the very first convergence analysis of ADMM was conducted by Gabay and Mercier in 1976, but, even under notably stronger assumptions, only the convergence of the primal sequence was known. A collection of illustrative examples are provided to demonstrate the breadth of applications for which our results can be used. Numerical experiments on solving a large number of linear and convex quadratic semidefinite programming problems are conducted to illustrate how the theoretical results established here can lead to improvements on the corresponding practical implementations.
Full work available at URL: https://arxiv.org/abs/1803.10803
Recommendations
- A linearly convergent majorized ADMM with indefinite proximal terms for convex composite programming and its applications
- A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
- On the convergence rate of inexact majorized sGS ADMM with indefinite proximal terms for convex composite programming
- Inexact proximal \(\epsilon\)-subgradient methods for composite convex optimization problems
- An inexact version of the symmetric proximal ADMM for solving separable convex optimization
- Inexact generalized proximal alternating direction methods of multipliers and their convergence rates
- The convergence properties of infeasible inexact proximal alternating linearized minimization
- An inexact proximal generalized alternating direction method of multipliers
- An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems
- A partially inexact proximal alternating direction method of multipliers and its iteration-complexity analysis
alternating direction method of multipliersaugmented Lagrangian methodsymmetric Gauss-Seidel decompositionproximal term
Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Decomposition methods (49M27)
Cites Work
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Fast Algorithms for Large-Scale Generalized Distance Weighted Discrimination
- QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
- 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
- Title not available (Why is that?)
- Robust Estimation of a Location Parameter
- A Newton-CG augmented Lagrangian method for semidefinite programming
- Regularization methods for semidefinite programming
- Noisy low-rank matrix completion with general sampling distribution
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Convex Analysis
- Hankel matrix rank minimization with applications to system identification and realization
- Another Look at Distance-Weighted Discrimination
- An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming
- A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
- Multiplier and gradient methods
- Title not available (Why is that?)
- Optimization and nonsmooth analysis
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Implicit Functions and Solution Mappings
- Title not available (Why is that?)
- Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic Signals
- Distributed Sparse Linear Regression
- Bundle methods for regularized risk minimization
- Title not available (Why is that?)
- A boundary point method to solve semidefinite programs
- Atomic decomposition by basis pursuit
- Weighted Complementarity Problems---A New Paradigm for Computing Equilibria
- An inexact primal-dual path following algorithm for convex quadratic SDP
- Practical Aspects of the Moreau--Yosida Regularization: Theoretical Preliminaries
- Lectures on numerical methods for non-linear variational problems
- A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
- Semidefinite Relaxations for Best Rank-1 Tensor Approximations
- A rank-corrected procedure for matrix completion with fixed basis coefficients
- Frequency planning and ramifications of coloring
- Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
- Spectral operators of matrices
- Regularization methods for SDP relaxations in large-scale polynomial optimization
- Approximating K‐means‐type Clustering via Semidefinite Programming
- A note on the convergence of ADMM for linearly constrained convex optimization problems
- Algorithms for Fitting the Constrained Lasso
- Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming
- An Adaptive Correction Approach for Tensor Completion
- Penalized and Constrained Optimization: An Application to High-Dimensional Website Advertising
- Semidefinite programming approach for the quadratic assignment problem with a sparse graph
- A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications
- Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction
- A linearly convergent majorized ADMM with indefinite proximal terms for convex composite programming and its applications
Cited In (14)
- A scale-invariant relaxation in low-rank tensor recovery with an application to tensor completion
- An Asymptotically Superlinearly Convergent Semismooth Newton Augmented Lagrangian Method for Linear Programming
- Douglas-Rachford splitting and ADMM for pathological convex optimization
- A linear algebra perspective on the random multi-block ADMM: the QP case
- A Three-Operator Splitting Perspective of a Three-Block ADMM for Convex Quadratic Semidefinite Programming and Beyond
- Understanding the convergence of the preconditioned PDHG method: a view of indefinite proximal ADMM
- Poissonian image restoration via the \(L_1/L_2\)-based minimization
- Majorized iPADMM for Nonseparable Convex Minimization Models with Quadratic Coupling Terms
- An inexact majorized proximal alternating direction method of multipliers for diffusion tensors
- Title not available (Why is that?)
- A proximal fully parallel splitting method with a relaxation factor for separable convex programming
- On proximal augmented Lagrangian based decomposition methods for dual block-angular convex composite programming problems
- An algorithm for matrix recovery of high-loss-rate network traffic data
- A Corrected Inexact Proximal Augmented Lagrangian Method with a Relative Error Criterion for a Class of Group-Quadratic Regularized Optimal Transport Problems
Uses Software
This page was built for publication: On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220656)
