Large-scale semidefinite programming with graphics processing units

Semidefinite programming (SDP) provides a powerful framework in applied mathematics with applications spanning optimization, machine learning, quantum computing, and beyond. However, the computational cost of solving large-scale SDP problems remains a significant practical limitation. We break this long-standing computational bottleneck through a synergistic codesign of low-rank algorithms and graphics processing unit (GPU) architectures, developing accelerated first-order methods that leverage both algorithmic innovations and hardware-aware implementation to achieve up to 4 orders of magnitude improvements in speed and scalability for large-scale SDPs with sparse and low-rank structure, thereby opening frontiers in large-scale scientific computing. Our solver, GPU-accelerated Low-Rank Alternating Direction Method of Multipliers Splitting (cuLoRADS), exemplifies this approach, combining the Burer-Monteiro method with a splitting scheme to efficiently solve massive-scale SDPs. Specifically, it can solve a set of MaxCut problems whose matrix variables have dimensions of 10 7 × 10 7 in 10 s to 1 min each on an NVIDIA H100 GPU with 80 GB of memory, whereas previously reported central processing unit solvers required dozens of hours. Additionally, cuLoRADS shows exceptional scalability by solving 1) a MaxCut problem with a 170 million × 170 million matrix variable and 2) a Minimum-Rank Matrix Completion problem with a 20 million × 20 million matrix variable and approximately 200 million constraints, both in a matter of minutes. It also resolves a long-standing SDP computational barrier in the quantum ordered search problem, which had remained unsolved for 18 y.