Rank optimality for the Burer-Monteiro factorization

Irène Waldspurger
Université de Paris IX (Paris-Dauphine)

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.

Back to Operator Theoretic Methods in Dynamic Data Analysis and Control