Burer-Monteiro ADMM for Large-scale Diagonally Constrained SDPs

We propose a bilinear decomposition for the Burer-Monteiro method for semidefinite programming and combine it with the Alternating Direction Method of Multipli-ers. Bilinear decomposition reduces the degree of the augmented Lagrangian from four to two, which makes each of the sub-problems a quadratic programming and hence computationally efficient. Our approach is able to solve a class of large-scale SDPs with diagonal constraints. We prove that our ADMM algorithm converges globally to the set of first-order stationary points, and show empirically that the algorithm returns a globally optimal solution for diagonally constrained SDPs.