Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming
From MaRDI portal
(Redirected from Publication:5219557)
Abstract: In this paper, we aim to provide a comprehensive analysis on the linear rate convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex composite optimization problems. Under a certain error bound condition, we establish the global linear rate of convergence for a more general semi-proximal ADMM with the dual steplength being restricted to be in the open interval . In our analysis, we assume neither the strong convexity nor the strict complementarity except an error bound condition, which holds automatically for convex composite quadratic programming. This semi-proximal ADMM, which includes the classic ADMM, not only has the advantage to resolve the potentially non-solvability issue of the subproblems in the classic ADMM but also possesses the abilities of handling multi-block convex optimization problems efficiently. We shall use convex composite quadratic programming and quadratic semi-definite programming as important applications to demonstrate the significance of the obtained results. Of its own novelty in second-order variational analysis, a complete characterization is provided on the isolated calmness for the nonlinear convex semi-definite optimization problem in terms of its second order sufficient optimality condition and the strict Robinson constraint qualification for the purpose of proving the linear rate convergence of the semi-proximal ADMM when applied to two- and multi-block convex quadratic semi-definite programming.
Recommendations
- Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems
- Linear convergence rate of the generalized alternating direction method of multipliers for a class of convex minimization problems
- Linear convergence rates for variants of the alternating direction method of multipliers in smooth cases
- On convergence rates of linearized proximal algorithms for convex composite optimization with applications
- On the linear convergence of the alternating direction method of multipliers
- Optimally linearizing the alternating direction method of multipliers for convex programming
- On convergence rates of proximal alternating direction method of multipliers
- Convergence Rate Analysis for the Alternating Direction Method of Multipliers with a Substitution Procedure for Separable Convex Programming
- On the rate of convergence of the proximal alternating linearized minimization algorithm for convex problems
- On the iterative complexity of the linearized alternating direction method of multipliers
Cites work
- A class of linearized proximal alternating direction methods
- 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 majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
- A new inexact alternating directions method for monotone variational inequalities
- A note on the convergence of ADMM for linearly constrained convex optimization problems
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
- An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming
- Asymptotic Convergence Analysis of the Proximal Point Algorithm
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Characterization of the robust isolated calmness for a class of conic programming problems
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Hankel matrix rank minimization with applications to system identification and realization
- scientific article; zbMATH DE number 3833218 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 1502618 (Why is no real title available?)
- Implicit Functions and Solution Mappings
- Lectures on numerical methods for non-linear variational problems
- Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems
- Local Duality of Nonlinear Programs
- Local Duality of Nonlinear Semidefinite Programming
- Local Linear Convergence of the Alternating Direction Method of Multipliers for Quadratic Programs
- Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs
- Monotone Operators and the Proximal Point Algorithm
- On alternating direction methods of multipliers: a historical perspective
- On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the global and linear convergence of the generalized alternating direction method of multipliers
- On the linear convergence of the alternating direction method of multipliers
- Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
- Some continuity properties of polyhedral multifunctions
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
- Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives
- Variational Analysis
Cited in
(85)- A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming
- QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
- An inexact PAM method for computing Wasserstein barycenter with unknown supports
- Double fused Lasso penalized LAD for matrix regression
- Convergence rates for an inexact ADMM applied to separable convex optimization
- A parallel operator splitting algorithm for solving constrained total-variation retinex
- A multi-level ADMM algorithm for elliptic PDE-constrained optimization problems
- A dual symmetric Gauss-Seidel alternating direction method of multipliers for hyperspectral sparse unmixing
- A dual based semismooth Newton-type algorithm for solving large-scale sparse Tikhonov regularization problems
- Double fused Lasso regularized regression with both matrix and vector valued predictors
- Sparse estimation of high-dimensional inverse covariance matrices with explicit eigenvalue constraints
- A fundamental proof of convergence of alternating direction method of multipliers for weakly convex optimization
- A superlinearly convergent splitting feasible sequential quadratic optimization method for two-block large-scale smooth optimization
- An inexact symmetric ADMM algorithm with indefinite proximal term for sparse signal recovery and image restoration problems
- An inexact ADMM with proximal-indefinite term and larger stepsize
- An inexact accelerated stochastic ADMM for separable convex optimization
- A survey on some recent developments of alternating direction method of multipliers
- Augmented Lagrangian methods for convex matrix optimization problems
- On the linear convergence of the general first order primal-dual algorithm
- A double extrapolation primal-dual algorithm for saddle point problems
- On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming
- An incremental aggregated proximal ADMM for linearly constrained nonconvex optimization with application to sparse logistic regression problems
- A first-order inexact primal-dual algorithm for a class of convex-concave saddle point problems
- Local linear convergence of an ADMM-type splitting framework for equality constrained optimization
- The alternating direction method of multipliers for finding the distance between ellipsoids
- Sparsity reconstruction using nonconvex TGpV-shearlet regularization and constrained projection
- Optimally linearizing the alternating direction method of multipliers for convex programming
- On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming
- A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications
- General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems
- Unified linear convergence of first-order primal-dual algorithms for saddle point problems
- Efficient color image segmentation via quaternion-based \(L_1/L_2\) Regularization
- Linearized proximal algorithms with adaptive stepsizes for convex composite optimization with applications
- Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems
- A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
- On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions
- Quadratic growth conditions for convex matrix optimization problems associated with spectral functions
- A linearly convergent majorized ADMM with indefinite proximal terms for convex composite programming and its applications
- Discerning the linear convergence of ADMM for structured convex optimization through the lens of variational analysis
- A fast globally linearly convergent algorithm for the computation of Wasserstein barycenters
- An efficient linearly convergent regularized proximal point algorithm for fused multiple graphical Lasso problems
- An image sharpening operator combined with framelet for image deblurring
- On the convergence rate of inexact majorized sGS ADMM with indefinite proximal terms for convex composite programming
- Edge adaptive hybrid regularization model for image deblurring
- Image segmentation via Fischer-Burmeister total variation and thresholding
- A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP
- Operator splitting performance estimation: tight contraction factors and optimal parameter selection
- A note on the convergence of ADMM for linearly constrained convex optimization problems
- A three-stage variational image segmentation framework incorporating intensity inhomogeneity information
- Convergence Rate Analysis for the Alternating Direction Method of Multipliers with a Substitution Procedure for Separable Convex Programming
- On the characterizations of solutions to perturbed l₁ conic optimization problem
- Portfolio selection with regularization
- On degenerate doubly nonnegative projection problems
- Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem
- Fast Algorithms for LS and LAD-Collaborative Regression
- A partially inexact generalized primal-dual hybrid gradient method for saddle point problems with bilinear couplings
- Complexity analysis of a stochastic variant of generalized alternating direction method of multipliers
- Sparse precision matrix estimation with missing observations
- A new stopping criterion for Eckstein and Bertsekas's generalized alternating direction method of multipliers
- A weighted gradient model with total variation regularization for multi-focus image fusion
- Inexact generalized ADMM with relative error criteria for linearly constrained convex optimization problems
- A Round Trip Time Weighting Model for One-way Delay Estimation
- A Bregman-style improved ADMM and its linearized version in the nonconvex setting: convergence and rate analyses
- Regret analysis of an online majorized semi-proximal ADMM for online composite optimization
- An efficient smoothing and thresholding image segmentation framework with weighted anisotropic-isotropic total variation
- Accelerated primal-dual methods with adaptive parameters for composite convex optimization with linear constraints
- Optimality conditions and numerical algorithms for a class of linearly constrained minimax optimization problems
- An overview of SaT segmentation methodology and its applications in image processing
- Quaternion-aware low-rank prior for blind color image deblurring
- Stochastic linearized generalized alternating direction method of multipliers: expected convergence rates and large deviation properties
- The exact worst-case convergence rate of the alternating direction method of multipliers
- A quadratically convergent semismooth Newton method for nonlinear semidefinite programming without generalized Jacobian regularity
- The robust isolated calmness of spectral norm regularized convex matrix optimization problems
- A linearized proximal ADMM for stochastic and large-scale convex optimization
- An accelerated semi-proximal ADMM with applications to multi-block sparse optimization problems
- Linear convergence rate analysis of proximal generalized ADMM for convex composite programming
- Feature-splitting algorithms for ultrahigh dimensional quantile regression
- Accelerating preconditioned ADMM via degenerate proximal point mappings
- Convergence of three-block ADMM for weakly convex optimization problems
- HPR-LP: an implementation of an HPR method for solving linear programming
- Online alternating direction method of multipliers for online composite optimization
- An efficient algorithm for the weighted elastic net penalized quantile regression
- A Gauss-Seidel type inertial proximal stochastic alternating direction method of multipliers for nonconvex finite sum optimization
- Fused lasso penalized Huber regression with nonasymptotic property and numerical implementations
- A symmetric Gauss-Seidel based method for a class of multi-period mean-variance portfolio selection problems
This page was built for publication: Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219557)
