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.