Appears in collection : 2019 - T1 - WS3 - Imaging and machine learning

In the last decades, semidefinite programs have emerged as a a powerful way to solve difficult combinatorial optimization problems in polynomial time. Unfortunately, they are difficult to numerically solve in high dimensions. This talk will discuss a classical heuristic used to speed up the solving, namely the Burer-Monteiro formulation. We will review the main correctness guarantees that have been established for this heuristic, and study their optimality.