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

Po-Wei Wang, Wei-Cheng Chang, J. Zico Kolter

Abstract

In this paper, we propose a low-rank coordinate descent approach to structured semidefinite programming (SDP) 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 solving the maximum cut semidefinite relaxation and a maximum satisfiability relaxation. In all settings, we demonstrate substantial improvement over the existing state of the art, expanding the scope and scale of problems that can be solved using semidefinite programming methods.

Introduction

Semidefinite programming (SDP) is a powerful mathematical tool used to solve convex relaxations of notoriously hard combinatorial problems, such as MAXCUT or MAXSAT. However, standard SDPs optimize over an $n \times n$ matrix, meaning the number of variables grows quadratically with the problem size. For large-scale datasets, traditional exact solvers—such as interior point methods—quickly become computationally prohibitive due to memory and time constraints.

To address this, researchers often employ the "Burer-Monteiro factorization," which replaces the massive $n \times n$ matrix $X$ with a low-rank factorization $V^T V$. While this drastically reduces the number of variables, it introduces a non-convex optimization landscape. Algorithms operating in this space risk getting stuck in local minima. While existing low-rank solvers, such as Riemannian manifold methods, work well in practice, they often require meticulous step-size tuning and lack strong theoretical guarantees for finding the true global optimum without restrictive assumptions.

The Mixing Method

We introduce the Mixing method, a low-rank coordinate descent approach specifically designed for SDPs with unit diagonal constraints. These constraints effectively require the columns of the factorized matrix $V$ to lie on a unit sphere.

Instead of taking complex gradient steps, the Mixing method updates one vector $v_i$ at a time using a closed-form solution. To update $v_i$, the algorithm calculates a weighted sum of all other vectors—weighted by the problem's cost matrix—and projects the result back onto the unit sphere. The method is named for this "mixing" and normalization process. Key advantages include:

  • Extreme Simplicity: The core algorithm is parameter-free, requiring no learning rates or manual tuning.
  • Efficiency: The closed-form updates allow for rapid iterations compared to gradient-based manifold optimization.

Theoretical Guarantees

Despite the non-convexity introduced by the low-rank factorization, we provide rigorous theoretical support for the Mixing method. We prove that if the rank $k$ is sufficiently large ($k > \sqrt{2n}$), all non-optimal critical points are unstable saddle points. This geometric property ensures that the algorithm naturally diverges from sub-optimal points and moves toward the global optimum.

Furthermore, we prove that a variant of the Mixing method (incorporating a step size) converges to the global optimum of the original convex SDP almost surely. This represents the first low-rank SDP method shown to achieve a global optimum on the spherical manifold without heavy external assumptions.

Experimental Results

We evaluated the Mixing method across several domains to demonstrate its scalability and speed.

MAXCUT and Scalability

On standard MAXCUT benchmark graphs ranging from 1,000 nodes to nearly 2 million nodes (e.g., roadNet-CA), the Mixing method is 10 to 100 times faster than competing state-of-the-art solvers like DSDP, SDPLR, and Manopt. It maintains this order-of-magnitude advantage even as the problem size scales to millions of variables.

MAXSAT

We introduced a novel SDP relaxation for general MAXSAT problems, extending the classic Goemans-Williamson relaxation. On 525 instances from the 2016 MAXSAT competition, the Mixing method achieved an average approximation ratio of 0.978. It found higher-quality solutions faster than standard Linear Programming (LP) approximations and remained competitive with specialized heuristic solvers.

Word Embeddings

In the context of learning word embeddings (using the GloVe objective), the Mixing method converged substantially faster to a lower function value than standard Stochastic Gradient Descent (SGD), demonstrating its utility beyond traditional combinatorial optimization.

Conclusion

The Mixing method provides a highly efficient, parameter-free alternative for solving large-scale structured SDPs. By leveraging the geometry of the spherical manifold and coordinate descent, it bypasses the traditional trade-offs between computational speed and theoretical convergence. Future work includes bridging the gap between the step-size-free version used in practice and the theoretical proofs, as well as extending the method to handle more general affine constraints.

Summary updated

Abstract

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.
BibTeX
@misc{wang2017mixing,
  author = {Po-Wei Wang and Wei-Cheng Chang and J. Zico Kolter},
  title = {{The Mixing method: coordinate descent for low-rank semidefinite programming}},
  year = {2017},
  eprint = {1706.00476},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1706.00476},
}
Figure