Exploiting low-rank structure in semidefinite programming by approximate operator splitting
From MaRDI portal
Abstract: In contrast with many other convex optimization classes, state-of-the-art semidefinite programming solvers are yet unable to efficiently solve large scale instances. This work aims to reduce this scalability gap by proposing a novel proximal algorithm for solving general semidefinite programming problems. The proposed methodology, based on the primal-dual hybrid gradient method, allows the presence of linear inequalities without the need of adding extra slack variables and avoids solving a linear system at each iteration. More importantly, it does simultaneously compute the dual variables associated with the linear constraints. The main contribution of this work is to achieve a substantial speedup by effectively adjusting the proposed algorithm in order to exploit the low-rank property inherent to several semidefinite programming problems. This proposed modification is the key element that allows the operator splitting method to efficiently scale to larger instances. Convergence guarantees are presented along with an intuitive interpretation of the algorithm. Additionally, an open source semidefinite programming solver, called ProxSDP, is made available and implementation details are discussed. Case studies are presented in order to evaluate the performance of the proposed methodology.
Recommendations
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
- Scalable semidefinite programming
- An optimal-storage approach to semidefinite programming using approximate complementarity
- An efficient approach to solve the large-scale semidefinite programming problems
Cites work
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 3177945 (Why is no real title available?)
- scientific article; zbMATH DE number 53686 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 1342125 (Why is no real title available?)
- scientific article; zbMATH DE number 724202 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1944141 (Why is no real title available?)
- scientific article; zbMATH DE number 4115838 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 3895043 (Why is no real title available?)
- scientific article; zbMATH DE number 3239575 (Why is no real title available?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A new polynomial-time algorithm for linear programming
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A primer on monotone operator methods
- ARPACK Users' Guide
- Alternating direction augmented Lagrangian methods for semidefinite programming
- An Interior-Point Method for Semidefinite Programming
- An approximation theory of matrix rank minimization and its application to quadratic equations
- An implementation of Karmarkar's algorithm for linear programming
- Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational Inequalities
- Applications of semidefinite programming
- Basic Linear Algebra Subprograms for Fortran Usage
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- Computational complexity of optimum multiuser detection
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Convex analysis and monotone operator theory in Hilbert spaces
- Distributed Semidefinite Programming With Application to Large-Scale System Analysis
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Distributionally robust joint chance constraints with second-order moment information
- Efficient semidefinite programming with approximate ADMM
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Interior-Point Algorithms for Semidefinite Programming Problems Derived from the KYP Lemma
- JuMP: a modeling language for mathematical optimization
- Julia: a fresh approach to numerical computing
- Learning the kernel matrix with semidefinite programming
- Linear Matrix Inequalities in System and Control Theory
- Log-determinant relaxation for approximate inference in discrete Markov random fields
- MathOptInterface.jl
- Monotone Operators and the Proximal Point Algorithm
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the power of unique 2-prover 1-round games
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- Phase retrieval via matrix completion
- Practical sketching algorithms for low-rank matrix approximation
- Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
- Problems of distance geometry and convex properties of quadratic maps
- Proximal splitting methods in signal processing
- Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations
- Robust Sparse Analysis Regularization
- Robust Truss Topology Design via Semidefinite Programming
- Robust convex optimization
- SDPLIB 1.2, a library of semidefinite programming test problems
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Semidefinite Programming
- Signal Recovery by Proximal Forward-Backward Splitting
- Solving Euclidean distance matrix completion problems via semidefinite progrmming
- Solving Graph Bisection Problems with Semidefinite Programming
- Solving monotone inclusions via compositions of nonexpansive averaged operators
- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- The Diversity Order of the Semidefinite Relaxation Detector
- Theory of semidefinite programming for sensor network localization
- Towards a proof of the 2-to-1 games conjecture?
Cited in
(9)- An optimal-storage approach to semidefinite programming using approximate complementarity
- Solving low-rank semidefinite programs via manifold optimization
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- An interior point-proximal method of multipliers for linear positive semi-definite programming
- Provably faster gradient descent via long steps
- Scalable low-rank semidefinite programming for certifiably correct machine perception
- An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs
- ProxSDP
- Efficient semidefinite programming with approximate ADMM
Describes a project that uses
Uses Software
This page was built for publication: Exploiting low-rank structure in semidefinite programming by approximate operator splitting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5034932)
