A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
From MaRDI portal
Publication:5254992
DOI10.1137/140964357zbMATH Open1328.90083arXiv1404.5378OpenAlexW1982831910MaRDI QIDQ5254992FDOQ5254992
Authors: Defeng Sun, Kim-Chuan Toh, Liuqin Yang 
Publication date: 11 June 2015
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: The objective of this paper is to design an efficient and convergent alternating direction method of multipliers (ADMM) for finding a solution of medium accuracy to conic programming problems whose constraints consist of linear equalities, linear inequalities, a non-polyhedral cone and a polyhedral cone. For this class of problems, one may apply the directly extended ADMM to their dual, which can be written in the form of convex programming with four separable blocks in the objective function and a coupling linear equation constraint. Indeed, the directly extended ADMM, though may diverge in theory, often performs much better numerically than many of its variants with theoretical convergence guarantee. Ideally, one should find a convergent variant which is at least as efficient as the directly extended ADMM in practice. We achieve this goal by designing a convergent semi-proximal ADMM (called sPADMM3c for convenience) for convex programming problems having three separable blocks in the objective function with the third part being linear. At each iteration, the proposed sPADMM3c takes one special block coordinate descent (BCD) cycle with the order , instead of the usual Gauss-Seidel BCD cycle used in the non-convergent directly extended -block ADMM, for updating the variable blocks. Our extensive numerical tests on the important class of doubly non-negative semidefinite programming (SDP) problems with linear equality and/or inequality constraints demonstrate that our convergent method is at least faster than the directly extended ADMM with unit step-length for the vast majority of about large scale problems tested.
Full work available at URL: https://arxiv.org/abs/1404.5378
Recommendations
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
- 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
- Convergence of ADMM for Three-Block Separable Quadratic Programming Problems with Linear Constraints
- A note on the sufficient initial condition ensuring the convergence of directly extended 3-block ADMM for special semidefinite programming
Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Semidefinite programming (90C22) Iterative numerical methods for linear systems (65F10)
Cites Work
- A first-order block-decomposition method for solving two-easy-block structured semidefinite programs
- Convergence of a block coordinate descent method for nondifferentiable minimization
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities
- Title not available (Why is that?)
- Variational Analysis
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- A Newton-CG augmented Lagrangian method for semidefinite programming
- Convex Analysis
- Hankel matrix rank minimization with applications to system identification and realization
- 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
- Multiplier and gradient methods
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Decomposition method with a variable parameter for a class of monotone variational inequality problems
- Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Copositive and semidefinite relaxations of the quadratic assignment problem
- A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs
- An alternating direction-based contraction method for linearly constrained separable convex programming problems
- Alternating direction method with Gaussian back substitution for separable convex programming
- Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
- Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives
- A boundary point method to solve semidefinite programs
- Convex analysis and nonlinear optimization. Theory and examples.
- Lectures on numerical methods for non-linear variational problems
- Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
- Frequency planning and ramifications of coloring
- Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
- An ADM-based splitting method for separable convex programming
- Regularization methods for SDP relaxations in large-scale polynomial optimization
- Approximating K‐means‐type Clustering via Semidefinite Programming
Cited In (84)
- Modified hybrid decomposition of the augmented Lagrangian method with larger step size for three-block separable convex programming
- GRPDA revisited: relaxed condition and connection to Chambolle-Pock's primal-dual algorithm
- A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
- Linearized symmetric multi-block ADMM with indefinite proximal regularization and optimal proximal parameter
- The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates
- Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
- Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
- A Three-Operator Splitting Perspective of a Three-Block ADMM for Convex Quadratic Semidefinite Programming and Beyond
- Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights
- Linearized block-wise alternating direction method of multipliers for multiple-block convex programming
- A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming
- Convergent prediction-correction-based ADMM for multi-block separable convex programming
- An efficient algorithm for batch images alignment with adaptive rank-correction term
- Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction
- Semidefinite programming approach for the quadratic assignment problem with a sparse graph
- On the conditions for the finite termination of ADMM and its applications to SOS polynomials feasibility problems
- Two-stage stochastic variational inequalities: an ERM-solution procedure
- Symmetric Gauss-Seidel technique-based alternating direction methods of multipliers for transform invariant low-rank textures problem
- Fast algorithms for sparse inverse covariance estimation
- A proximal quadratic surface support vector machine for semi-supervised binary classification
- An efficient algorithm for sparse inverse covariance matrix estimation based on dual formulation
- Global convergence of splitting methods for nonconvex composite optimization
- A note on the sufficient initial condition ensuring the convergence of directly extended 3-block ADMM for special semidefinite programming
- Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
- Alternating iterative methods for solving tensor equations with applications
- A proximal alternating direction method for multi-block coupled convex optimization
- Randomized primal-dual proximal block coordinate updates
- Two-step fixed-point proximity algorithms for multi-block separable convex problems
- A multi-level ADMM algorithm for elliptic PDE-constrained optimization problems
- ADMM-type methods for generalized multi-facility Weber problem
- A generalization of linearized alternating direction method of multipliers for solving two-block separable convex programming
- A Lipschitzian error bound for convex quadratic symmetric cone programming
- A 2-block semi-proximal ADMM for solving the H-weighted nearest correlation matrix problem
- SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
- Matrix optimization based Euclidean embedding with outliers
- Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization
- Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity
- Fast Algorithms for Large-Scale Generalized Distance Weighted Discrimination
- On the Global Linear Convergence of the ADMM with MultiBlock Variables
- Convex Euclidean distance embedding for collaborative position localization with NLOS mitigation
- Title not available (Why is that?)
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming
- Robust tensor recovery with nonconvex and nonsmooth regularization
- ADMM for multiaffine constrained optimization
- On the sublinear convergence rate of multi-block ADMM
- Global convergence of unmodified 3-block ADMM for a class of convex minimization problems
- A symmetric Gauss-Seidel based method for a class of multi-period mean-variance portfolio selection problems
- A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block
- Best nonnegative rank-one approximations of tensors
- An extended proximal ADMM algorithm for three-block nonconvex optimization problems
- A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications
- An ADMM-based location-allocation algorithm for nonconvex constrained multi-source Weber problem under gauge
- A proximal partially parallel splitting method for separable convex programs
- An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming
- QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
- A note on the convergence of ADMM for linearly constrained convex optimization problems
- A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
- An alternating direction method of multipliers for tensor complementarity problems
- Estimation of graphical models through structured norm minimization
- A SemiSmooth Newton Method for Semidefinite Programs and its Applications in Electronic Structure Calculations
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
- An Adaptive Correction Approach for Tensor Completion
- Preconditioned ADMM for a class of bilinear programming problems
- An efficient partial parallel method with scaling step size strategy for three-block convex optimization problems
- On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming
- Improving ADMMs for solving doubly nonnegative programs through dual factorization
- Randomized algorithms for orthogonal nonnegative matrix factorization
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- Sequential inertial linear ADMM algorithm for nonconvex and nonsmooth multiblock problems with nonseparable structure
- Regularized Linear Programming Discriminant Rule with Folded Concave Penalty for Ultrahigh-Dimensional Data
- Asset splitting algorithm for ultrahigh dimensional portfolio selection and its theoretical property
- High-dimensional interactions detection with sparse principal Hessian matrix
- Nonconvex Dantzig selector and its parallel computing algorithm
- An exact algorithm for semi-supervised minimum sum-of-squares clustering
- An ADMM algorithm for two-stage stochastic programming problems
- Modified ADMM algorithm for solving proximal bound formulation of multi-delay optimal control problem with bounded control
- A proximal-based algorithm for piecewise sparse approximation with application to scattered data fitting
- Supervised distance preserving projection using alternating direction method of multipliers
- A proximal alternating direction method of multipliers with a substitution procedure
- SDP-based branch-and-bound for non-convex quadratic integer optimization
- Non-unique games over compact groups and orientation estimation in cryo-EM
- Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
Uses Software
This page was built for publication: A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5254992)
