On the Burer-Monteiro method for general semidefinite programs

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.