An efficient inexact ABCD method for least squares semidefinite programming
From MaRDI portal
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.
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
Cites work
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3465097 (Why is no real title available?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
- A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs
- A coordinate gradient descent method for nonsmooth separable minimization
- A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions
- Accelerated, parallel, and proximal coordinate descent
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP
- 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
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Dual coordinate ascent methods for non-strictly convex minimization
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Frequency planning and ramifications of coloring
- Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data
- Introductory lectures on convex optimization. A basic course.
- Monotone Operators and the Proximal Point Algorithm
- On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
- On the convergence of block coordinate descent type methods
- On the convergence of the block nonlinear Gauss-Seidel method under convex constraints
- On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
- On the copositive representation of binary and continuous nonconvex quadratic programs
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Smooth minimization of non-smooth functions
- Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
- The Theory of Max-Min, with Applications
Cited in
(17)- An accelerated active-set algorithm for a quadratic semidefinite program with general constraints
- 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
- Computing the best approximation over the intersection of a polyhedral set and the doubly nonnegative cone
- An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP
- 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
- Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
- An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs
- 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
- Block coordinate descent methods for semidefinite programming
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)
