Optimal rank for the Burer-Monteiro factorization
Irène Waldspurger
CEREMADE, Université Paris-Dauphine
https://www.ceremade.dauphine.fr/~waldspurger/
Date(s) : 19/06/2020 iCal
14h00 - 15h00
In this talk, we consider semidefinite programs (that is, optimization problems over a matrix subject to a semidefinite positiveness constraint). In large dimension, solving such a program is slow in full generality. However, when the solution is expected tobe low rank, the solving can be sped up with the Burer-Monteiro heuristic: One writes the solution as the product of thinner matrices, and optimizes over the factors instead of over the full matrix. Understanding when this heuristic succeeds is non-trivial,since the factorized problem is non-convex and it is thus unclear when it can be solved exactly. We will discuss which guarantees can be found in the literature, and study their optimality.
Catégories
