A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
arXiv:1908.05209
Abstract
Historically, scalability has been a major challenge to the successful application of semidefinite programming in fields such as machine learning, control, and robotics. In this paper, we survey recent approaches for addressing this challenge including (i) approaches for exploiting structure (e.g., sparsity and symmetry) in a problem, (ii) approaches that produce low-rank approximate solutions to semidefinite programs, (iii) more scalable algorithms that rely on augmented Lagrangian techniques and the alternating direction method of multipliers, and (iv) approaches that trade off scalability with conservatism (e.g., by approximating semidefinite programs with linear and second-order cone programs). For each class of approaches we provide a high-level exposition, an entry-point to the corresponding literature, and examples drawn from machine learning, control, or robotics. We also present a list of software packages that implement many of the techniques discussed in the paper. Our hope is that this paper will serve as a gateway to the rich and exciting literature on scalable semidefinite programming for both theorists and practitioners.
References in corpus (21)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Manopt, a Matlab toolbox for optimization on manifolds
- Symmetry groups, semidefinite programs, and sums of squares
- Evaluating Robustness of Neural Networks with Mixed Integer Programming
- Global rates of convergence for nonconvex optimization on manifolds
- Low-rank optimization for semidefinite convex problems
- Semidefinite relaxations for certifying robustness to adversarial examples
- Efficient Formal Safety Analysis of Neural Networks
- Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
- Verification for Machine Learning, Autonomy, and Neural Networks Survey
- Robust Stability Analysis of Sparsely Interconnected Uncertain Systems
- Symmetry in semidefinite programs
- Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
- Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
- Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming
- The Mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints
- An Optimal-Storage Approach to Semidefinite Programming using Approximate Complementarity
- A Conditional Gradient-Based Augmented Lagrangian Framework
- Verification of Non-Linear Specifications for Neural Networks
- Engineering and Business Applications of Sum of Squares Polynomials