Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDPs

Understand

Semidefinite programming (SDP) with diagonal constraints arise in many optimization problems, such as Max-Cut, community detection and group synchronization.

• Although SDPs can be solved to arbitrary precision in polynomial time, generic convex solvers do not scale well with the dimension of the problem.
• In order to address this issue, Burer and Monteiro proposed to reduce the dimension of the problem by appealing to a low-rank factorization and solve the subsequent non-convex problem instead.
• In this paper, we present coordinate ascent based methods to solve this non-convex problem with provable convergence guarantees.