Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+

Semidefinite programs (SDPs) and their solvers are powerful tools with many applications in machine learning and data science. Designing scalable SDP solvers is challenging because by standard the positive semidefinite decision variable is an n × n dense matrix, even though the input is often an n × n sparse matrix. However, the solution may not require a full-rank matrix, as shown by Barvinok and Pataki. Two decades ago, Burer and Monteiro developed an SDP solver textttSDPLR that optimizes over a low-rank factorization instead of the full matrix. This greatly decreases the storage cost and works well for many problems. The original solver textttSDPLR tracks only the primal infeasibility of the solution, preventing early termination at moderate accuracy. We use a suboptimality bound for trace-bounded SDP problems that enables us to track the progress better and perform early termination. We then develop textttSDPLR+, which starts the optimization with an extremely low-rank factorization and dynamically updates the rank based on the primal infeasibility and suboptimality. This further speeds up the computation and saves storage. Numerical comparisons on Max Cut, Minimum Bisection, Cut Norm, and Lov'asz Theta problems with many recent memory-efficient scalable SDP solvers demonstrate the scalability of textttSDPLR+ up to problems with million-by-million decision variables. It is often the fastest solver to a moderate accuracy of 10-2. Further experiments on μ-conductance, matrix completion, and k-means clustering show the potential of textttSDPLR+ on a broader range of data science applications.