Videos

Rank optimality for the Burer-Monteiro factorization

Presenter
February 12, 2019
Abstract
Irène Waldspurger - Université 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.