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. This is the first low-rank semidefinite programming method that
has been shown to achieve a global optimum on the spherical manifold without
assumption. We apply our algorithm to two related domains: solving the maximum
cut semidefinite relaxation, and solving a maximum satisfiability relaxation
(we also briefly consider additional applications such as learning word
embeddings). In all settings, we demonstrate substantial improvement over the
existing state of the art along various dimensions, and in total, this work
expands the scope and scale of problems that can be solved using semidefinite
programming methods.

本文提出了一种低秩坐标下降方法，用于结构半定规划，该方法是极其简单易于实现的，没有自由参数，并且通常比现有技术的优化性能提高一个数量级或更好的性能。我们证明该算法是严格下降的，收敛到一个临界点，并且对于足够秩的情况，所有非最优临界点都是不稳定的。此外，我们证明了通过选择合适的步长，该算法几乎可以在局部线性速率下以随机初始化收敛到半定规划的全局最优解，这是第一个证明在不做任何假设的情况下，在球形流形上达到全局最优的低秩半定规划方法。我们将算法应用于两个相关领域：解决最大割半定松弛和解决最大可满足性松弛（我们还简要考虑了其他应用，如学习单词嵌入）。在所有设置中，我们都在各个方面展示了比现有技术的实质性改进，从而扩大了可以使用半定规划方法解决的问题范围和规模。