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.