An Optimal-Storage Approach to Semidefinite Programming using Approximate Complementarity
arXiv:1902.03373
Abstract
This paper develops a new storage-optimal algorithm that provably solves generic semidefinite programs (SDPs) in standard form. This method is particularly effective for weakly constrained SDPs. The key idea is to formulate an approximate complementarity principle: Given an approximate solution to the dual SDP, the primal SDP has an approximate solution whose range is contained in the eigenspace with small eigenvalues of the dual slack matrix. For weakly constrained SDPs, this eigenspace has very low dimension, so this observation significantly reduces the search space for the primal solution. This result suggests an algorithmic strategy that can be implemented with minimal storage: (1) Solve the dual SDP approximately; (2) compress the primal SDP to the eigenspace with small eigenvalues of the dual slack matrix; (3) solve the compressed primal SDP. The paper also provides numerical experiments showing that this approach is successful for a range of interesting large-scale SDPs.
35 pages, 24 pages of main text, 17 figures
References in corpus (6)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
- Low-rank spectral optimization via gauge duality
- A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming
- Efficient First-Order Methods for Linear Programming and Semidefinite Programming
- A Conditional Gradient-Based Augmented Lagrangian Framework
Cited by in corpus (6)
- Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming
- A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
- On the simplicity and conditioning of low rank semidefinite programs
- Lecture notes on non-convex algorithms for low-rank matrix recovery
- Bundle Method Sketching for Low Rank Semidefinite Programming
- Bundle methods for dual atomic pursuit