Solving Low-Rank Semidefinite Programs via Manifold Optimization

Understand

We propose a manifold optimization approach to solve linear semidefinite programs (SDP) with low-rank solutions, with an emphasis on SDP relaxations for polynomial optimization problems.

• This approach incorporates the inexact augmented Lagrangian method (ALM) and the Burer-Monteiro factorization, and features the self-adaptive strategies for updating the factorization size and the penalty parameter.
• We establish global convergence of the inexact ALM, despite the non-convexity brought by the Burer-Monteiro factorization.
• We further provide a practical algorithm building on the inexact ALM, and along with the algorithm we release an open-source SDP solver ManiSDP.