# A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics

arXiv: https://arxiv.org/abs/1908.05209 · HTML: https://mlsanity.com/paper/1908.05209/

## Key facts

- Cited by 16 papers in the map (data through 13 Oct 2026).
- First posted on arXiv 14 Aug 2019.

## Built on by (most cited first, 16 of 16)

- [Advances in Inference and Representation for Simultaneous Localization and Mapping](https://mlsanity.com/paper/2103.05041/) (2021)
- [Chordal Sparsity for Lipschitz Constant Estimation of Deep Neural Networks](https://mlsanity.com/paper/2204.00846/) (2022)
- [Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach](https://mlsanity.com/paper/2109.12701/) (2021)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Advances in Trajectory Optimization for Space Vehicle Control](https://mlsanity.com/paper/2108.02335/) (2021)
- [An Overview of the Burer-Monteiro Method for Certifiable Robot Perception](https://mlsanity.com/paper/2410.00117/) (2024)
- [Quantum thermodynamics and semi-definite optimization](https://mlsanity.com/paper/2505.04514/) (2025)
- [Accelerating Certifiable Estimation with Preconditioned Eigensolvers](https://mlsanity.com/paper/2207.05257/) (2022)
- [Higher-Order Newton Methods with Polynomial Work per Iteration](https://mlsanity.com/paper/2311.06374/) (2023)
- [Rebalancing Social Feed to Minimize Polarization and Disagreement](https://mlsanity.com/paper/2308.14486/) (2023)
- [Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part I: Definitions & Basic Properties](https://mlsanity.com/paper/2208.03622/) (2022)
- [Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part II: Theoretical & Computational Results](https://mlsanity.com/paper/2208.03625/) (2022)
- [Grasp Force Optimization as a Bilinear Matrix Inequality Problem: A Deep Learning Approach](https://mlsanity.com/paper/2312.05034/) (2023)
- [Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+](https://mlsanity.com/paper/2406.10407/) (2024)
- [BalLOT: Balanced k-means clustering with optimal transport](https://mlsanity.com/paper/2512.05926/) (2025)
- [Certifiable Factor Graph Optimization](https://mlsanity.com/paper/2603.01267/) (2026)

## Abstract (arXiv)

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.