CARDAL: A Curvature-Aware Rank-Adaptive Distributed Augmented-Lagrangian Solver for Large-Scale SDPs

CARDAL is an open-source GPU low-rank solver for large-scale semidefinite programs with distributed multi-GPU support. It operates on a Burer-Monteiro low-rank factorization and targets semidefinite programs whose optimal solutions are (or are expected to be) low-rank.

The CARDAL paper is available on arXiv: A Curvature-Aware Rank-Adaptive Distributed Augmented-Lagrangian Solver for Large-Scale SDPs.

Problem Formulation

CARDAL solves standard-form semidefinite programs with block-diagonal PSD variables, an optional nonnegative LP block, and optional unrestricted real variables:

$$\begin{aligned} \min \quad & \sum_{c=1}^p \langle C_c, X_c\rangle + c_{\mathrm{LP}}^\top x_{\mathrm{LP}} + c_{\mathrm{free}}^\top x_{\mathrm{free}} \\\ \text{s.t.} \quad & \sum_{c=1}^p \langle A_{i,c},X_c\rangle + a_{i,\mathrm{LP}}^\top x_{\mathrm{LP}} + a_{i,\mathrm{free}}^\top x_{\mathrm{free}} = b_i, \quad i=1,\dots,m,\\\ & X_c \succeq 0,\quad x_{\mathrm{LP}}\ge 0,\quad x_{\mathrm{free}}\in\mathbb{R}^{d_{\mathrm{free}}}. \end{aligned}$$

$C$ and each $A_i$ are symmetric block-diagonal matrices. Every matrix is stored by its lower triangle only, and off-diagonal entries are not implicitly doubled — the same convention applies to the Python API. Each PSD block $X_c \in \mathbb{R}^{n_c \times n_c}$ is stored as a factor $V_c \in \mathbb{R}^{n_c \times r_c}$ with $X_c = V_c V_c^\top$.

Features

• GPU-native. Most operations are implemented natively on GPUs.
• Multi-GPU. MPI + NCCL parallelization across constraint, rank, and cone axes, enabled by default (-DENABLE_MPI=OFF to opt out).
• Structured matrix data. Objective and constraint blocks may be supplied as signed low-rank or sparse-plus-low-rank matrices without materializing dense matrices.
• Algorithm. Adaptive rank augmentation, negative curvature escape.

Requirements

• Platform: Linux x86_64 with an NVIDIA GPU and CUDA 12.x (12.6 or newer recommended).
• Build tools: CMake 3.20 or newer, a CUDA-compatible C++17 compiler, and Make or Ninja.
• Distributed (optional): MPI-3.1 and NCCL 2.18 or newer for multi-GPU support.

When multiple CUDA versions are installed, select one with CUDACXX, for example CUDACXX=/usr/local/cuda-12.6/bin/nvcc.

Installation

Build from source (C++ CLI)

Multi-GPU support (MPI + NCCL) is enabled by default; add -DENABLE_MPI=OFF for a single-GPU-only binary. If the default nvcc is outdated or missing, prefix the first cmake invocation with CUDACXX=/path/to/nvcc.

git clone https://github.com/Lhongpei/CARDAL.git
cd CARDAL
cmake -S . -B build
cmake --build build --clean-first

The main binary lands at ./build/cardal. A sibling binary ./build/cardal_qubo (built when CARDAL_BUILD_QUBO=ON, default) specializes in QUBO-lifted SDPs, takes the same core CLI flags with a QUBO-specific input parser (./build/cardal_qubo -f model.qubo), and the main cardal binary rejects QUBO inputs. Run ./build/cardal_qubo -h for its full syntax.

Python package

CARDAL ships a NumPy-friendly, single-GPU Python package on PyPI:

pip install cardal

The package compiles its CUDA extension during installation, so a working CUDA 12.x toolchain is required. See python/README.md for optional dependencies, source builds, and the complete Python API.

Quickstart

Solve a problem file

CARDAL auto-detects SDPA, MATLAB, and PDSDP input formats:

./build/cardal -f problem.dat-s -O ./output

The solve summary is printed to the terminal. Passing -O ./output also writes the summary, low-rank primal factor, per-cone rank list, and dual solution to ./output. LP and free primal vectors are included when present.

CLI

# From a file (SDPA, MATLAB, or PDSDP; format auto-detected)
./build/cardal -f problem.dat-s -O ./output

Python Interface

import cardal
import numpy as np

m = cardal.Model()
u = np.array([[1.0], [2.0], [-1.0]])
m.set_problem(
    block_dims=[3],
    b=[1.0],
    C=[cardal.LowRank(u, weights=[-1.0])],
    A=[[cardal.LowRank(np.eye(3))]],
)
result = m.solve(
    time_sec_limit=60.0,
    eps_primal_relative=1e-4,
    eps_dual_relative=1e-4,
    eps_optimal_relative=1e-4,
)
print(result.status, result.primal_objective, result.rel_objective_gap)

LowRank(U, weights=d) represents (U\mathrm{diag}(d)U^\top); weights may be negative. SparseLowRank(S, U, weights=d) represents (S+U\mathrm{diag}(d)U^\top). A small symmetric core=D may be provided instead of diagonal weights. File-based loading remains available through cardal.Model.read_file(...).

Advanced Usage

CLI reference

./build/cardal -f <PATH> [OPTIONS]

• -f, --file <path> reads a problem file (SDPA .dat-s / .dat-s.gz, MATLAB .mat, PDSDP .npz; auto-detected).

Solver parameters

Option	Type	Description	Default
-e, --eps	float	Set the primal, dual, and objective-gap tolerances together.	1e-4
--eps-primal	float	Relative primal residual tolerance.	1e-4
--eps-dual	float	Relative dual residual tolerance.	1e-4
--eps-gap	float	Relative objective-gap tolerance.	1e-4
-r, --rank	int	Initial Burer-Monteiro rank.	ceil(2 log m)
-R, --max-rank	int	Maximum rank of each PSD block.	Pataki bound
--augmentation-mode	string	Rank augmentation backend: random, qp, closed-form, or sdp.	random
-i, --inner-iters	int	L-BFGS iteration limit per outer step.	30000
-o, --outer-iters	int	Augmented-Lagrangian outer iteration limit.	20000000
-p, --penalty-fac	float	Penalty coefficient multiplier.	3.3
-c, --init-penalty	float	Initial penalty coefficient.	2 / sqrt(N)
-M, --max-penalty	float	Maximum penalty coefficient.	5e5
-L, --lbfgs-hist	int	L-BFGS history size.	5
-T, --time-limit	float	Wall-clock limit in seconds; 0 disables it.	3600
-v, --verbose	int	Log level: 0 silent, 1 summary, 2 iterations, 3 debug.	2
-O, --output-dir	path	Write the summary and primal/dual solution files.	None

Distributed and scaling parameters

Option	Type	Description	Default
-z, --grid-size	string	MPI grid as row,rank,cone; dimensions must multiply to the MPI process count.	Auto
--shuffle	string	Distributed constraint ordering: none, uniform, block, or col.	col
--l-inf-ruiz-iter	int	Number of L-infinity Ruiz scaling iterations; 0 disables them.	10
--pock-chambolle-alpha	float	Pock-Chambolle scaling exponent.	1.0
--no-pock-chambolle	flag	Disable Pock-Chambolle scaling.	Off
--no-bound-obj-rescaling	flag	Disable bound-objective rescaling.	Off
--psd-scale-mode	string	PSD scaling mode: per-element or per-cone.	per-element
--no-scaling	flag	Disable all scaling stages.	Off

Run ./build/cardal -h for the authoritative CLI help. The Python interface uses the same solver defaults; its keyword parameters are documented in python/README.md.

Multi-GPU with MPI + NCCL

The same binary auto-detects an MPI launch and switches to the distributed solver — MPI for control-plane messaging, NCCL for on-device collectives:

# 4 GPUs, process grid auto-selected
mpirun -n 4 ./build/cardal -f problem.dat-s -O ./output

# Explicit row x rank x cone grid
mpirun -n 4 ./build/cardal -f problem.dat-s --grid-size 2,2,1
mpirun -n 8 ./build/cardal -f problem.dat-s --grid-size 1,1,8

Troubleshooting

• nvcc: command not found, or CUDA too old. Export CUDACXX=/usr/local/cuda-12.6/bin/nvcc before invoking cmake.
• CLI build fails with missing MPI. MPI is on by default; reconfigure with -DENABLE_MPI=OFF for a single-GPU build.
• QUBO input rejected. The main cardal binary refuses QUBO instances; use cardal_qubo (./build/cardal_qubo -h).

Contributing

Contributions and pull requests are welcome.

Citation

If you use CARDAL in academic work, please cite the companion paper:

@misc{li2026curvatureawarerankadaptivedistributedaugmentedlagrangian,
  title        = {A Curvature-Aware Rank-Adaptive Distributed Augmented-Lagrangian Solver for Large-Scale SDPs},
  author       = {Hongpei Li and Huikang Liu and Dongdong Ge and Yinyu Ye},
  year         = {2026},
  eprint       = {2607.17933},
  archivePrefix = {arXiv},
  primaryClass = {math.OC},
  url          = {https://arxiv.org/abs/2607.17933}
}

Machine-readable citation metadata is also available in CITATION.cff.

License

Copyright 2026 Hongpei Li.

Licensed under the Apache License, Version 2.0. See the LICENSE file for details.