Burer-Monteiro guarantees for general semidefinite programs

Consider a semidefinite program (SDP) involving an $n\times n$ positive semidefinite matrix $X$. The Burer-Monteiro method consists in solving a nonconvex program in $Y$, where $Y$ is an $n\times 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 > \sqrt{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 sensor network localization and to matrix sensing.

Citation

arXiv:1904.07147

Article

Download

View Burer-Monteiro guarantees for general semidefinite programs