Title: New Suboptimality Bounds for Trace-Bounded SDPs Facilitate the Development of a High-Performance, Scalable Low-Rank Solver: SDPLR+

Abstract:

Semidefinite programming (SDP) and its associated computational tools have become indispensable assets across machine learning and data science disciplines. However, creating solvers that scale effectively remains a significant hurdle. Standard SDP formulations treat the positive semidefinite decision variable as a dense $n \times n$ matrix, which creates a bottleneck even when the input data is sparse. Fortunately, as demonstrated by Barvinok and Pataki, the optimal solution often does not necessitate a full-rank matrix. Capitalizing on this insight, Burer and Monteiro introduced the SDPLR solver two decades ago. By optimizing over a low-rank factorization rather than the complete matrix, SDPLR significantly reduced memory requirements and proved effective for a wide array of problems.

Despite its advantages, the original SDPLR algorithm had a limitation: it monitored only the primal infeasibility, which hindered the ability to terminate the optimization process early when achieving moderate accuracy levels. To address this, we introduce a suboptimality bound tailored for trace-bounded SDP problems. This innovation allows for more precise tracking of optimization progress and supports early termination strategies. Building on this, we present SDPLR+, a new solver that initiates optimization with a very low-rank factorization and dynamically adjusts the rank according to both primal infeasibility and suboptimality metrics. This approach accelerates computation and further conserves storage resources.

Extensive numerical evaluations on problems such as Max Cut, Minimum Bisection, Cut Norm, and Lov\'{a}sz Theta, comparing SDPLR+ against several recent memory-efficient and scalable SDP solvers, highlight its superior scalability. SDPLR+ successfully handles decision variables in the million-by-million range and frequently emerges as the fastest solver for achieving moderate accuracy (specifically $10^{-2}$). Additional tests involving $\mu$-conductance, matrix completion, and $k$-means clustering underscore the solver's versatility and potential applicability across a diverse spectrum of data science tasks.

Source: arXiv Generated at: 2026-06-03 00:00:00 UTC