AI summaryⓘ
The authors introduce CARDAL, a new solver designed to handle very large semidefinite programs (SDPs) across multiple GPUs. Their method adapts the rank of matrix factorizations and uses advanced optimization techniques like augmented Lagrangian and curvature corrections to improve accuracy and efficiency. They also propose a way to distribute the problem across different computing resources to speed up calculations. Tests show that CARDAL is more robust than previous GPU-based methods and achieves significant speed improvements on practical problems from robotics, chemistry, and combinatorial optimization. Their work includes mathematical guarantees about when their method will find globally optimal solutions.
Semidefinite Programming (SDP)Burer-Monteiro factorizationAugmented Lagrangian methodL-BFGS optimizationNegative curvatureKKT conditionsBarvinok-Pataki boundGPU parallel computingRank adaptivityConstraint distribution
Authors
Hongpei Li, Huikang Liu, Dongdong Ge, Yinyu Ye
Abstract
We present CARDAL (Curvature-Aware Rank-Adaptive Distributed Augmented Lagrangian), a distributed multi-GPU solver for large-scale semidefinite programs (SDPs) based on a rank-adaptive Burer-Monteiro factorization and an augmented Lagrangian method. At fixed ranks, a matrix-free L-BFGS method with negative-curvature corrections targets an approximate Euclidean second-order stationary point of the factored augmented Lagrangian. A reverse multiplier shift turns a negative dual-slack direction into exact negative curvature after rank expansion, and a small joint rank-lift problem selects a batched low-rank correction. A verified slack lower bound provides an a posteriori approximate KKT certificate. Our analysis establishes generic global-optimality guarantees for heterogeneous products of PSD cones at per-block ranks near the Barvinok-Pataki scale, together with a finite-accuracy counterpart under blockwise cost smoothing. For scalable execution, CARDAL distributes constraint rows, factor columns, and PSD blocks over a Constraint x Rank x Cone device mesh. The primal residual, gradient, Hessian-vector products, and slack matrix-vector products are evaluated using device-local operations and axis-wise collectives. On the Mittelmann benchmark, CARDAL exhibits stronger robustness than existing low-rank GPU approaches under a uniform accuracy standard. Experiments on large-scale SDP relaxations from robotics, electronic structure, and Max-Cut demonstrate the complementary scaling regimes of the three distribution axes, with observed wall-clock speedups of up to 4x on four H100 GPUs.