The Mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints

Understand

In this paper, we propose a low-rank coordinate descent approach to structured semidefinite programming with diagonal constraints.

• The approach, which we call the Mixing method, is extremely simple to implement, has no free parameters, and typically attains an order of magnitude or better improvement in optimization performance over the current state of the art.
• We show that the method is strictly decreasing, converges to a critical point, and further that for sufficient rank all non-optimal critical points are unstable.
• Moreover, we prove that with a step size, the Mixing method converges to the global optimum of the semidefinite program almost surely in a locally linear rate under random initialization.