Search papers, labs, and topics across Lattice.
CARDAL is a novel distributed multi-GPU solver designed for large-scale semidefinite programs (SDPs), utilizing a rank-adaptive Burer-Monteiro factorization combined with an augmented Lagrangian method. The solver achieves enhanced robustness and speed by implementing a matrix-free L-BFGS method with negative-curvature corrections and a reverse multiplier shift, which optimally manages rank expansion and low-rank corrections. Experimental results on the Mittelmann benchmark show that CARDAL outperforms existing low-rank GPU methods, achieving speedups of up to 4x on four H100 GPUs while maintaining a uniform accuracy standard.
CARDAL achieves up to 4x speedups in solving large-scale SDPs while ensuring robust performance across various applications.
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.
