On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming
From MaRDI portal
Publication:2220656
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.
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
Cites work
- scientific article; zbMATH DE number 6508162 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 3309655 (Why is no real title available?)
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
- A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications
- A boundary point method to solve semidefinite programs
- A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- 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
- A note on the convergence of ADMM for linearly constrained convex optimization problems
- A rank-corrected procedure for matrix completion with fixed basis coefficients
- Algorithms for Fitting the Constrained Lasso
- An Adaptive Correction Approach for Tensor Completion
- An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming
- An inexact primal-dual path following algorithm for convex quadratic SDP
- Another look at distance-weighted discrimination
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Atomic decomposition by basis pursuit
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Bundle methods for regularized risk minimization
- Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic Signals
- Convex Analysis
- Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction
- Distributed Sparse Linear Regression
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Fast Algorithms for Large-Scale Generalized Distance Weighted Discrimination
- Frequency planning and ramifications of coloring
- Hankel matrix rank minimization with applications to system identification and realization
- Implicit Functions and Solution Mappings
- Lectures on numerical methods for non-linear variational problems
- Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming
- Multiplier and gradient methods
- Noisy low-rank matrix completion with general sampling distribution
- Optimization and nonsmooth analysis
- Penalized and Constrained Optimization: An Application to High-Dimensional Website Advertising
- Practical Aspects of the Moreau--Yosida Regularization: Theoretical Preliminaries
- QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
- Regularization methods for SDP relaxations in large-scale polynomial optimization
- Regularization methods for semidefinite programming
- Restricted strong convexity and weighted matrix completion: optimal bounds with noise
- Robust Estimation of a Location Parameter
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Semidefinite programming approach for the quadratic assignment problem with a sparse graph
- Semidefinite relaxations for best rank-1 tensor approximations
- Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
- Spectral operators of matrices
- Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives
- Weighted complementarity problems -- A new paradigm for computing equilibria
Cited in
(14)- Douglas-Rachford splitting and ADMM for pathological convex optimization
- An Asymptotically Superlinearly Convergent Semismooth Newton Augmented Lagrangian Method for Linear Programming
- A scale-invariant relaxation in low-rank tensor recovery with an application to tensor completion
- 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
- scientific article; zbMATH DE number 7370538 (Why is no real title available?)
- A proximal fully parallel splitting method with a relaxation factor for separable convex programming
- An algorithm for matrix recovery of high-loss-rate network traffic data
- On proximal augmented Lagrangian based decomposition methods for dual block-angular convex composite programming problems
- A Corrected Inexact Proximal Augmented Lagrangian Method with a Relative Error Criterion for a Class of Group-Quadratic Regularized Optimal Transport Problems
Describes a project that uses
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)
