A bit of smooth geometry and a bit of smoothed analysis for semidefinite programs in low-rank form (Nicolas Boumal - Princeton University)

22.03.2019 10:30 – 11:30

Semidefinite programs are optimization problems of the form: minimize a linear function of X, where X is a positive semidefinite matrix subject to linear constraints. Enforcing positive semidefiniteness can be computationally challenging. A popular heuristic is to factor X as YY*, where Y is a tall and narrow matrix. This ensures semidefiniteness for free, but breaks convexity. I will describe why, if the search space in Y is a smooth manifold, then the non-convexity is almost never an issue. Then, I will argue through smoothed analysis that the zero-measure set of bad problems is not a serious threat even for algorithms which have to terminate in finite time. As these concepts involve optimization on smooth manifolds, I will touch upon recent complexity bounds in this domain.

Lieu

Room 17, Séminaire d'analyse numérique

entrée libre