Burer-Monteiro Low-Rank Semidefinite Programming and Riemannian Staircase

Burer-Monteiro Low-Rank Semidefinite Programming and Riemannian Staircase is a non-convex Riemannian optimization framework analyzed by Boumal, Voroninski, and Bandeira (2016, 2019) that solves linear semidefinite programs min_{X in S^{n x n}} <C, X> subject to A(X) = b, X >= 0 (with m linear constraints) by substituting the rank-p factorization X = Y Y^T with Y in R^{n x p} on the constraint set M_p = {Y in R^{n x p} : A(Y Y^T) = b}. Under regularity assumptions verifying that M_p is a smooth Riemannian submanifold of R^{n x p} with compact quotient M_p / O(p) (such as the Oblique manifold M_p = {Y : (Y Y^T)_{ii} = 1} for Max-Cut, Z_2/SO(d) synchronization, and community detection SDPs), Lemma 2.1 and Lemma 2.2 show that every first-order Riemannian critical point Y has a unique closed-form dual multiplier vector mu(Y) and dual slack matrix S(Y) = C - A^*(mu(Y)) satisfying S(Y) Y = 0 and Riemannian Hessian quadratic form <dot{Y}, Hess g(Y)[dot{Y}]> = <dot{Y}, S(Y) dot{Y}>. Lemma 2.4 proves that any column-rank-deficient second-order critical point (rank(Y) < p, Hess g(Y) >= 0) satisfies S(Y) >= 0 and is therefore globally optimal for the SDP, while Theorem 1.2 and Theorem 1.4 establish via Sard's theorem and dimensional transversality that when p(p+1)/2 > m (the Barvinok-Pataki bound), for generic cost matrices C (outside a set of Lebesgue measure zero) the non-convex landscape on M_p has NO spurious local minima: every second-order Riemannian critical point Y is globally optimal.