A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
From MaRDI portal
Publication:5254992
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.
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
Cites work
- scientific article; zbMATH DE number 3833218 (Why is no real title available?)
- scientific article; zbMATH DE number 3177945 (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 boundary point method to solve semidefinite programs
- A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- A first-order block-decomposition method for solving two-easy-block structured semidefinite programs
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Alternating direction method with Gaussian back substitution for separable convex programming
- Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities
- An ADM-based splitting method for separable convex programming
- An alternating direction-based contraction method for linearly constrained separable convex programming problems
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Convex Analysis
- Convex analysis and nonlinear optimization. Theory and examples.
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Decomposition method with a variable parameter for a class of monotone variational inequality problems
- Frequency planning and ramifications of coloring
- Hankel matrix rank minimization with applications to system identification and realization
- Lectures on numerical methods for non-linear variational problems
- Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming
- Multiplier and gradient methods
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
- Regularization methods for SDP relaxations in large-scale polynomial optimization
- Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
- Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
- 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
(84)- An Adaptive Correction Approach for Tensor Completion
- A SemiSmooth Newton Method for Semidefinite Programs and its Applications in Electronic Structure Calculations
- 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
- Modified hybrid decomposition of the augmented Lagrangian method with larger step size for three-block separable convex programming
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
- A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
- GRPDA revisited: relaxed condition and connection to Chambolle-Pock's primal-dual algorithm
- An efficient partial parallel method with scaling step size strategy for three-block convex optimization problems
- Linearized symmetric multi-block ADMM with indefinite proximal regularization and optimal proximal parameter
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
- Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
- The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates
- On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming
- Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
- 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
- A Three-Operator Splitting Perspective of a Three-Block ADMM for Convex Quadratic Semidefinite Programming and Beyond
- 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
- Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction
- 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
- A proximal quadratic surface support vector machine for semi-supervised binary classification
- Improving ADMMs for solving doubly nonnegative programs through dual factorization
- An efficient algorithm for sparse inverse covariance matrix estimation based on dual formulation
- Fast algorithms for sparse inverse covariance estimation
- Randomized algorithms for orthogonal nonnegative matrix factorization
- Global convergence of splitting methods for nonconvex composite optimization
- Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- A note on the sufficient initial condition ensuring the convergence of directly extended 3-block ADMM for special semidefinite programming
- 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 Lipschitzian error bound for convex quadratic symmetric cone programming
- A generalization of linearized alternating direction method of multipliers for solving two-block separable convex programming
- 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
- A 2-block semi-proximal ADMM for solving the H-weighted nearest correlation matrix problem
- Matrix optimization based Euclidean embedding with outliers
- Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization
- SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
- Asset splitting algorithm for ultrahigh dimensional portfolio selection and its theoretical property
- High-dimensional interactions detection with sparse principal Hessian matrix
- 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
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Convex Euclidean distance embedding for collaborative position localization with NLOS mitigation
- Robust tensor recovery with nonconvex and nonsmooth regularization
- On the Global Linear Convergence of the ADMM with MultiBlock Variables
- scientific article; zbMATH DE number 7370538 (Why is no real title available?)
- Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming
- Nonconvex Dantzig selector and its parallel computing algorithm
- An exact algorithm for semi-supervised minimum sum-of-squares clustering
- ADMM for multiaffine constrained optimization
- On the sublinear convergence rate of multi-block ADMM
- An ADMM algorithm for two-stage stochastic programming problems
- 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
- Modified ADMM algorithm for solving proximal bound formulation of multi-delay optimal control problem with bounded control
- A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block
- A proximal-based algorithm for piecewise sparse approximation with application to scattered data fitting
- Best nonnegative rank-one approximations of tensors
- An extended proximal ADMM algorithm for three-block nonconvex optimization problems
- Supervised distance preserving projection using alternating direction method of multipliers
- A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications
- A proximal alternating direction method of multipliers with a substitution procedure
- SDP-based branch-and-bound for non-convex quadratic integer optimization
- 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
- A note on the convergence of ADMM for linearly constrained convex optimization problems
- QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
- A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
- An alternating direction method of multipliers for tensor complementarity problems
- Preconditioned ADMM for a class of bilinear programming problems
- Estimation of graphical models through structured norm minimization
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)
