A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization

DOI10.1137/140999025zbMATH Open1338.90305arXiv1412.1911OpenAlexW2963647795MaRDI QIDQ2802143FDOQ2802143

Kim-Chuan Toh, Defeng Sun, Min Li

Publication date: 25 April 2016

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: This paper presents a majorized alternating direction method of multipliers (ADMM) with indefinite proximal terms for solving linearly constrained $2$-block convex composite optimization problems with each block in the objective being the sum of a non-smooth convex function and a smooth convex function, i.e., $mi{n}_{xincalX,;yincalY}p(x)+f(x)+q(y)+g(y)mid{A}^{*}x+B^{*}y=c$. By choosing the indefinite proximal terms properly, we establish the global convergence and $O(1/k)$ ergodic iteration-complexity of the proposed method for the step-length $auin(0,(1+sqrt5)/2)$. The computational benefit of using indefinite proximal terms within the ADMM framework instead of the current requirement of positive semidefinite ones is also demonstrated numerically. This opens up a new way to improve the practical performance of the ADMM and related methods.

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

Recommendations

• A linearly convergent majorized ADMM with indefinite proximal terms for convex composite programming and its applications
• Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization
• A new accelerated positive-indefinite proximal ADMM for constrained separable convex optimization problems
• On the convergence rate of inexact majorized sGS ADMM with indefinite proximal terms for convex composite programming
• Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming

zbMATH Keywords

alternating direction method of multipliersmajorizationconvex composite optimizationiteration-complexityindefinite proximal terms

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Cites Work

• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• Title not available (Why is that?)
• 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 \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
• Title not available (Why is that?)
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Convex Analysis
• Hankel matrix rank minimization with applications to system identification and realization
• A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
• A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
• Title not available (Why is that?)
• On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean
• Iteration-Complexity of Block-Decomposition Algorithms and the Alternating Direction Method of Multipliers
• A new inexact alternating directions method for monotone variational inequalities
• Title not available (Why is that?)
• On the $O(1/t)$ Convergence Rate of Alternating Direction Method with Logarithmic-Quadratic Proximal Regularization
• A note on the alternating direction method of multipliers
• Lectures on numerical methods for non-linear variational problems
• Parallel multi-block ADMM with \(o(1/k)\) convergence
• On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions
• Convergence Rate Analysis of Several Splitting Schemes
• On the convergence analysis of the alternating direction method of multipliers with three blocks
• A Convergent $3$-Block Semi-Proximal ADMM for Convex Minimization Problems with One Strongly Convex Block
• On the Global Linear Convergence of the ADMM with MultiBlock Variables
• On the sublinear convergence rate of multi-block ADMM
• An extragradient-based alternating direction method for convex minimization
• An Accelerated Linearized Alternating Direction Method of Multipliers

Cited In (48)

• An alternating direction method of multipliers with the BFGS update for structured convex quadratic optimization
• Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization
• Linearized symmetric multi-block ADMM with indefinite proximal regularization and optimal proximal parameter
• Regret analysis of an online majorized semi-proximal ADMM for online composite optimization
• On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming
• A proximal point analysis of the preconditioned alternating direction method of multipliers
• Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights
• A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming
• Improved proximal ADMM with partially parallel splitting for multi-block separable convex programming
• A linearly convergent majorized ADMM with indefinite proximal terms for convex composite programming and its applications
• An image sharpening operator combined with framelet for image deblurring
• Understanding the convergence of the preconditioned PDHG method: a view of indefinite proximal ADMM
• Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization
• Majorized iPADMM for Nonseparable Convex Minimization Models with Quadratic Coupling Terms
• On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions
• An accelerated proximal augmented Lagrangian method and its application in compressive sensing
• LINEARIZED ALTERNATING DIRECTION METHOD OF MULTIPLIERS FOR SEPARABLE CONVEX OPTIMIZATION OF REAL FUNCTIONS IN COMPLEX DOMAIN
• Fixing and extending some recent results on the ADMM algorithm
• Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems
• The augmented Lagrangian method with full Jacobian decomposition and logarithmic-quadratic proximal regularization for multiple-block separable convex programming
• A generalization of linearized alternating direction method of multipliers for solving two-block separable convex programming
• An indefinite proximal subgradient-based algorithm for nonsmooth composite optimization
• An inexact majorized proximal alternating direction method of multipliers for diffusion tensors
• The indefinite proximal point algorithms for maximal monotone operators
• High-Dimensional Gaussian Sampling: A Review and a Unifying Approach Based on a Stochastic Proximal Point Algorithm
• On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming
• Analysis of fully preconditioned alternating direction method of multipliers with relaxation in Hilbert spaces
• Customized alternating direction methods of multipliers for generalized multi-facility Weber problem
• Edge adaptive hybrid regularization model for image deblurring
• A proximal ADMM with the Broyden family for convex optimization problems
• On the Convergence Rate of Inexact Majorized sGS ADMM with Indefinite Proximal Terms for Convex Composite Programming
• Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming
• ADMM for multiaffine constrained optimization
• Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization
• Inertial proximal strictly contractive peaceman-Rachford splitting method with an indefinite term for convex optimization
• Convergence study of indefinite proximal ADMM with a relaxation factor
• Linearized proximal algorithms with adaptive stepsizes for convex composite optimization with applications
• Learning Markov Models Via Low-Rank Optimization
• A nonconvex ADMM for a class of sparse inverse semidefinite quadratic programming problems
• Inertial-relaxed splitting for composite monotone inclusions
• Variational image motion estimation by preconditioned dual optimization
• Efficient and Convergent Preconditioned ADMM for the Potts Models
• Subgroup analysis in the heterogeneous Cox model
• An inexact symmetric ADMM algorithm with indefinite proximal term for sparse signal recovery and image restoration problems
• An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming
• The developments of proximal point algorithms
• Title not available (Why is that?)
• A primal majorized semismooth Newton-CG augmented Lagrangian method for large-scale linearly constrained convex programming

Uses Software

• BADMM

This page was built for publication: A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802143)