In the last decades, it has been understood that one could solve difficult optimization problems by approximating them, after a suitable "lifting" step, with a semidefinite program (that is, a particular form of convex optimization problem, whose unknown is a matrix). Unfortunately, large-scale semidefinite programs are often slow to numerically solve. 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 about this heuristic, and study their optimality.
Copyright. All Rights Reserved.