# On the Burer-Monteiro method for general semidefinite programs

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2019.

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

- [Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion](https://mlsanity.com/paper/2305.12292/) (2023)
- [Manifold learning and optimization using tangent space proxies](https://mlsanity.com/paper/2501.12678/) (2025)
- [Implicit Bias in Matrix Factorization and its Explicit Realization in a New Architecture](https://mlsanity.com/paper/2501.16322/) (2025)
- [Atlas-based Manifold Representations for Interpretable Riemannian Machine Learning](https://mlsanity.com/paper/2510.17772/) (2025)
- [Maximum a Posteriori Inference of Random Dot Product Graphs via Conic Programming](https://mlsanity.com/paper/2101.02180/) (2021)
- [Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+](https://mlsanity.com/paper/2406.10407/) (2024)
- [A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation](https://mlsanity.com/paper/2507.09148/) (2025)
- [Exact and Heuristic Algorithms for Constrained Biclustering](https://mlsanity.com/paper/2508.05493/) (2025)

## Abstract (arXiv)

Consider a semidefinite program (SDP) involving an n× n positive semidefinite matrix X. The Burer-Monteiro method uses the substitution X=Y YT to obtain a nonconvex optimization problem in terms of an n× p matrix Y. Boumal et al. showed that this nonconvex method provably solves equality-constrained SDPs with a generic cost matrix when p gtrsim √2m, where m is the number of constraints. In this note we extend their result to arbitrary SDPs, possibly involving inequalities or multiple semidefinite constraints. We derive similar guarantees for a fixed cost matrix and generic constraints. We illustrate applications to matrix sensing and integer quadratic minimization.