Irène Waldspurger (CEREMADE, Université Paris-Dauphine): Correction guarantees for the Burer-Monteiro heuristic on MaxCut-type problems

We consider semidefinite optimization problems, that is, where one has to minimize a convex function on the set of semidefinite positive matrices. Sometimes, we know a priori that the solution will be of low rank (for instance, rank 1). This information can be used to make numerical solvers faster. This is the goal of the Burer-Monteiro factorization: we represent the unknown matrix as a product of "thin" matrices (i.e. with few columns); then, we optimize the factors instead of the whole square matrix. Since it reduces the dimensionality of the problem, this method allows for significant speedups. However, it makes the problem non-convex, thereby possibly introducing non-optimal critical points which can cause the solver to fail.

With Faniriana Rakoto Endor, we have considered the specific category of so-called "MaxCut-type" semidefinite problems. We have exhibited a simple property which guarantees that the Burer-Monteiro factorization associated with one of these problems has no non-optimal critical point.