Optimal rank for the Burer-Monteiro factorization

Irène Waldspurger
CEREMADE, Université Paris-Dauphine

Date(s) : 19/06/2020   iCal
14 h 00 min - 15 h 00 min

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.

Slides : https://www.i2m.univ-amu.fr/seminaires_signal_apprentissage/Slides/2020_06_19_transpIreneWaldspurger.pdf


Retour en haut 

Secured By miniOrange