An efficient inexact ABCD method for least squares semidefinite programming
From MaRDI portal
Publication:2805705
DOI10.1137/15M1021799zbMATH Open1346.90658arXiv1505.04278OpenAlexW1499687860MaRDI QIDQ2805705FDOQ2805705
Authors: Defeng Sun, Kim-Chuan Toh, Liuqin Yang 
Publication date: 13 May 2016
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: We consider least squares semidefinite programming (LSSDP) where the primal matrix variable must satisfy given linear equality and inequality constraints, and must also lie in the intersection of the cone of symmetric positive semidefinite matrices and a simple polyhedral set. We propose an inexact accelerated block coordinate descent (ABCD) method for solving LSSDP via its dual, which can be reformulated as a convex composite minimization problem whose objective is the sum of a coupled quadratic function involving four blocks of variables and two separable non-smooth functions involving only the first and second block, respectively. Our inexact ABCD method has the attractive iteration complexity if the subproblems are solved progressively more accurately. The design of our ABCD method relies on recent advances in the symmetric Gauss-Seidel technique for solving a convex minimization problem whose objective is the sum of a multi-block quadratic function and a non-smooth function involving only the first block. Extensive numerical experiments on various classes of over 600 large scale LSSDP problems demonstrate that our proposed ABCD method not only can solve the problems to high accuracy, but it is also far more efficient than (a) the well known BCD (block coordinate descent) method, (b) the eARBCG (an enhanced version of the accelerated randomized block coordinate gradient) method, and (c) the APG (accelerated proximal gradient) method.
Full work available at URL: https://arxiv.org/abs/1505.04278
Recommendations
- Solving large-scale least squares semidefinite programming by alternating direction methods
- An accelerated active-set algorithm for a quadratic semidefinite program with general constraints
- Block coordinate descent methods for semidefinite programming
- An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP
- Calibrating Least Squares Semidefinite Programming with Equality and Inequality Constraints
Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Semidefinite programming (90C22) Iterative numerical methods for linear systems (65F10)
Cites Work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Smooth minimization of non-smooth functions
- Introductory lectures on convex optimization. A basic course.
- Title not available (Why is that?)
- A Newton-CG augmented Lagrangian method for semidefinite programming
- Convex Analysis
- A coordinate gradient descent method for nonsmooth separable minimization
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
- On the convergence of the block nonlinear Gauss-Seidel method under convex constraints
- Title not available (Why is that?)
- Monotone Operators and the Proximal Point Algorithm
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- An Inexact Accelerated Proximal Gradient Method for Large Scale Linearly Constrained Convex SDP
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Accelerated, Parallel, and Proximal Coordinate Descent
- On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
- 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
- The Theory of Max-Min, with Applications
- A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions
- On the Convergence of Block Coordinate Descent Type Methods
- Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data
- Frequency planning and ramifications of coloring
- On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
- Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
- Dual coordinate ascent methods for non-strictly convex minimization
- Approximating K‐means‐type Clustering via Semidefinite Programming
- An Accelerated Randomized Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
Cited In (14)
- An efficient duality-based approach for PDE-constrained sparse optimization
- An FE-inexact heterogeneous ADMM for elliptic optimal control problems with \(L^1\)-control cost
- Numerical solution for sparse PDE constrained optimization
- An inexact proximal DC algorithm with sieving strategy for rank constrained least squares semidefinite programming
- Solving large-scale least squares semidefinite programming by alternating direction methods
- An efficient augmented Lagrangian method for support vector machine
- A proximal augmented method for semidefinite programming problems
- An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs
- Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
- A Euclidean distance matrix model for protein molecular conformation
- A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications
- 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
- Computing the Best Approximation over the Intersection of a Polyhedral Set and the Doubly Nonnegative Cone
Uses Software
This page was built for publication: An efficient inexact ABCD method for least squares semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805705)
