Polynomial time guarantees for the Burer-Monteiro method

Understand

The Burer-Monteiro method is one of the most widely used techniques for solving large-scale semidefinite programs (SDP).

• The basic idea is to solve a nonconvex program in $Y$, where $Y$ is an $n \times p$ matrix such that $X = Y Y^T$.
• In this paper, we show that this method can solve SDPs in polynomial time in a smoothed analysis setting.
• More precisely, we consider an SDP whose domain satisfies some compactness and smoothness assumptions, and slightly perturb the cost matrix and the constraints.