burer-monteiro – Optimization Online

Polynomial time guarantees for the Burer-Monteiro method

Published: 2019/12/04

Semi-definite Programming burer-monteiro, low-rank factorization, semidefinite programming

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 … Read more

Burer-Monteiro guarantees for general semidefinite programs

Published: 2019/04/16

Diego Cifuentes

Semi-definite Programming burer-monteiro, global convergence, low-rank factorization, semidefinite programming

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}$, … Read more