A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints

DOI10.1137/140964357zbMath1328.90083arXiv1404.5378OpenAlexW1982831910MaRDI QIDQ5254992

Kim-Chuan Toh, Defeng Sun, Liuqin Yang

Publication date: 11 June 2015

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

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

zbMATH Keywords

convergenceconic programmingmultiblock ADMMsdpsemiproximal ADMM

Mathematics Subject Classification ID

Semidefinite programming (90C22) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Iterative numerical methods for linear systems (65F10)

Related Items (79)

Fast algorithms for sparse inverse covariance estimation ⋮ Modified hybrid decomposition of the augmented Lagrangian method with larger step size for three-block separable convex programming ⋮ An efficient algorithm for batch images alignment with adaptive rank-correction term ⋮ Linearized symmetric multi-block ADMM with indefinite proximal regularization and optimal proximal parameter ⋮ A proximal quadratic surface support vector machine for semi-supervised binary classification ⋮ A Lipschitzian error bound for convex quadratic symmetric cone programming ⋮ Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems ⋮ An Adaptive Correction Approach for Tensor Completion ⋮ Global Convergence of Splitting Methods for Nonconvex Composite Optimization ⋮ Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity ⋮ A SemiSmooth Newton Method for Semidefinite Programs and its Applications in Electronic Structure Calculations ⋮ Convex Euclidean distance embedding for collaborative position localization with NLOS mitigation ⋮ Unnamed Item ⋮ Global convergence of unmodified 3-block ADMM for a class of convex minimization problems ⋮ An ADMM algorithm for two-stage stochastic programming problems ⋮ Two-stage stochastic variational inequalities: an ERM-solution procedure ⋮ A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications ⋮ On the sublinear convergence rate of multi-block ADMM ⋮ SDP-based branch-and-bound for non-convex quadratic integer optimization ⋮ An exact algorithm for semi-supervised minimum sum-of-squares clustering ⋮ Modified ADMM algorithm for solving proximal bound formulation of multi-delay optimal control problem with bounded control ⋮ Supervised distance preserving projection using alternating direction method of multipliers ⋮ Randomized algorithms for orthogonal nonnegative matrix factorization ⋮ Unnamed Item ⋮ A generalization of linearized alternating direction method of multipliers for solving two-block separable convex programming ⋮ An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization ⋮ Regularized Linear Programming Discriminant Rule with Folded Concave Penalty for Ultrahigh-Dimensional Data ⋮ A proximal-based algorithm for piecewise sparse approximation with application to scattered data fitting ⋮ Asset splitting algorithm for ultrahigh dimensional portfolio selection and its theoretical property ⋮ The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates ⋮ Hybrid Jacobian and Gauss--Seidel Proximal Block Coordinate Update Methods for Linearly Constrained Convex Programming ⋮ A 2-block semi-proximal ADMM for solving the H-weighted nearest correlation matrix problem ⋮ Linearized block-wise alternating direction method of multipliers for multiple-block convex programming ⋮ Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights ⋮ Preconditioned ADMM for a class of bilinear programming problems ⋮ On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming ⋮ Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs ⋮ Alternating iterative methods for solving tensor equations with applications ⋮ A Three-Operator Splitting Perspective of a Three-Block ADMM for Convex Quadratic Semidefinite Programming and Beyond ⋮ 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 ⋮ SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints ⋮ Convergent prediction-correction-based ADMM for multi-block separable convex programming ⋮ Semidefinite programming approach for the quadratic assignment problem with a sparse graph ⋮ Improving ADMMs for solving doubly nonnegative programs through dual factorization ⋮ An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming ⋮ A note on the sufficient initial condition ensuring the convergence of directly extended 3-block ADMM for special semidefinite programming ⋮ An alternating direction method of multipliers for tensor complementarity problems ⋮ A note on the convergence of ADMM for linearly constrained convex optimization problems ⋮ Two Symmetrized Coordinate Descent Methods Can Be $O(n^2)$ Times Slower Than the Randomized Version ⋮ Estimation of Graphical Models through Structured Norm Minimization ⋮ On the conditions for the finite termination of ADMM and its applications to SOS polynomials feasibility problems ⋮ A multi-level ADMM algorithm for elliptic PDE-constrained optimization problems ⋮ Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization ⋮ Fast Algorithms for Large-Scale Generalized Distance Weighted Discrimination ⋮ Best Nonnegative Rank-One Approximations of Tensors ⋮ A Majorized ADMM with Indefinite Proximal Terms for Linearly Constrained Convex Composite Optimization ⋮ An efficient algorithm for sparse inverse covariance matrix estimation based on dual formulation ⋮ Symmetric Gauss-Seidel technique-based alternating direction methods of multipliers for transform invariant low-rank textures problem ⋮ An extended proximal ADMM algorithm for three-block nonconvex optimization problems ⋮ Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs ⋮ ADMM for multiaffine constrained optimization ⋮ Matrix optimization based Euclidean embedding with outliers ⋮ Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming ⋮ SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0) ⋮ An ADMM-based location-allocation algorithm for nonconvex constrained multi-source Weber problem under gauge ⋮ A proximal alternating direction method for multi-block coupled convex optimization ⋮ Randomized primal-dual proximal block coordinate updates ⋮ ADMM-type methods for generalized multi-facility Weber problem ⋮ A symmetric Gauss-Seidel based method for a class of multi-period mean-variance portfolio selection problems ⋮ Non-unique games over compact groups and orientation estimation in cryo-EM ⋮ On the Global Linear Convergence of the ADMM with MultiBlock Variables ⋮ Robust tensor recovery with nonconvex and nonsmooth regularization ⋮ 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 ⋮ Alternating Direction Method of Multipliers for a Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction ⋮ A proximal partially parallel splitting method for separable convex programs ⋮ Two-step fixed-point proximity algorithms for multi-block separable convex problems ⋮ A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems

Uses Software

• QAPLIB
• DIMACS
• 2EBD-HPE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alternating direction augmented Lagrangian methods for semidefinite programming
• Convex analysis and nonlinear optimization. Theory and examples.
• Copositive and semidefinite relaxations of the quadratic assignment problem
• A boundary point method to solve semidefinite programs
• A first-order block-decomposition method for solving two-easy-block structured semidefinite programs
• Lectures on numerical methods for non-linear variational problems
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs
• Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities
• An ADM-based splitting method for separable convex programming
• 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
• Multiplier and gradient methods
• An alternating direction-based contraction method for linearly constrained separable convex programming problems
• Hankel Matrix Rank Minimization with Applications to System Identification and Realization
• Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming
• Regularization Methods for SDP Relaxations in Large-Scale Polynomial Optimization
• Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
• A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
• Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Variational Analysis
• Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
• Frequency planning and ramifications of coloring
• Approximating K‐means‐type Clustering via Semidefinite Programming
• Convex Analysis
• Convergence of a block coordinate descent method for nondifferentiable minimization
• Decomposition method with a variable parameter for a class of monotone variational inequality problems
• 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

This page was built for publication: A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints