  We propose a bilinear decomposition for the Burer-Monteiro method and combine
it with the standard Alternating Direction Method of Multipliers algorithm for
semidefinite programming. Bilinear decomposition reduces the degree of the
augmented Lagrangian from four to two, which makes each of the subproblems 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 a first-order stationary point, and
show by exploiting the negative curvature that the algorithm converges to a
point within $O(1-1/r)$ of the optimal objective value. Additionally, the
proximal variant of the algorithm can solve block-diagonally constrained SDPs
with global convergence to a first-order stationary point. Numerical results
show that both our ADMM algorithm and the proximal variant outperform the
state-of-art Riemannian manifold algorithms and can reach the global optimum
empirically.
