A semidefinite program (SDP) is an optimization problem where one seeks to minimize a linear function of a positive semidefinite matrix X under linear constraints. SDPs have generated sustained interest since the nineties owing to their powerful expressiveness. Standard algorithms solve SDPs in polynomial time, but they fail in practice for large problems.

To address scaling issues, in the early 2000s, Burer and Monteiro proposed the following heuristic: factorize X as YY*, where Y is a 'tall and narrow' matrix of size n x p. Not only is positive semidefiniteness now mechanically enforced at no cost, but also one gets better control over the dimensionality of the problem through p. However, the optimization problem in Y is non-convex: it is a priori unclear how to solve it.

In this talk, I will show that the Burer-Monteiro heuristic is sound, under certain geometric conditions. Specifically, my collaborators and I proved that if the constraints on Y regularly define a smooth manifold, then, for almost any linear cost function, standard necessary optimality conditions turn out to be sufficient as well: non-convexity is benign. We established this result with optimally small p. I will further mention extensions of such results based on smoothed analysis.

Under the regularity condition, we get an optimization problem in Y on a smooth manifold: I will also mention recent results regarding the complexity of practical algorithms for such problems.

The main parts are joint work with Afonso Bandeira and Vlad Voroninski