On the Burer-Monteiro method for general semidefinite programs

Published in preprint, 2019

Recommended citation: Diego Cifuentes (2021). "On the Burer-Monteiro method for general semidefinite programs." Optimization Letters, https://doi.org/10.1007/s11590-021-01705-4 https://doi.org/10.1007/s11590-021-01705-4

Consider a semidefinite program (SDP) involving an n×n positive semidefinite matrix X. The Burer-Monteiro method consists in solving a nonconvex program in Y, where Y is an n×p matrix such that X = Y Y^T. Despite nonconvexity, Boumal et al. showed that the method provably solves generic equality-constrained SDP’s when p ≳ √2m, where m is the number of constraints. We extend this result to arbitrary SDP’s, possibly involving inequalities or multiple semidefinite constraints. We illustrate applications to matrix sensing and integer quadratic minimization.

Download paper here