cuADMM

A CUDA-based implementation of the Alternating Direction Method of Multipliers (ADMM) algorithm to solve Semi-Definite Programming (SDP) problems.

cuADMM solves multi-block SDP problems of the form:

$$\min_X \left\langle C,X\right\rangle \quad\text{s.t.}\quad \begin{cases} \left\langle A_i,X\right\rangle = b_i, \quad i\in [m]\\\ X\in\Omega_+ \end{cases}$$

where $\Omega_+$ is the cartesian product of symmetric cones corresponding to the symmetric blocks.

Dependencies

The following dependencies are required to build and run the project:

• CMake
• CUDA
• BLAS (for basic linear algebra operations)
• SuiteSparse (for CHOLMOD)
• MATLAB (for the bindings)

This project has been tested on Linux.

Execution

Build the project using CMake:

mkdir build
cmake -S . -B build
cmake --build build

Run the project:

./build/cuadmm_exe [dir_name]

where dir_name is the directory containing the input files. See below for the expected input format.

Input format

From TXT

When using the executable, you need to provide a directory containing the input files, in a format close to SDPT3. The expected files are:

• At.txt: the transpose of the constraint matrix in sparse svec COO format
• b.txt: the right-hand side constraint vector in sparse COO format
• blk.txt: a file containing the size of the blocks; if a line contains both a character and a number (e.g. s 3), the block is interpreted using the table below; if it contains only a number (e.g. 2), it indicates a PSD block (identical to s 2)
• C.txt: the cost matrix in sparse svec COO format
• con_num.txt: a file containing the number of constraints (which cannot be inferred from the other files)

Additionally, the following optional files can be provided:

• X.txt: an initial guess for the primal variable in sparse svec COO format
• y.txt: an initial guess for the dual variable in sparse svec COO format
• S.txt: an initial guess for the dual variable in sparse svec COO format

X, C and A use the svec version of the multi-block matrices, obtained by stacking the upper triangular part of each block in a vector, where non-diagonal elements are multiplied by $\sqrt{2}$. The sparse COO format stores the non-zero elements of the svec vector by storing the row indices, column indices, and values on the same line, separated by spaces.

Examples files are provided in the examples directory, in the TXT subfolders. See for instance this example.

Block types

The blk.txt file can contain the following block types:

Character	Description
s	PSD matrix of size n by n
u	WIP: Unconstrained vector of size n

Warning

The support of unconstrained variables (u) is currently a work in progress.

From other formats

We provide in examples a few MATLAB scripts to convert from other formats to the expected TXT format:

• mosek_to_txt.m: converts a problem in MOSEK format to the TXT format
• sedumi_to_txt.m: converts a problem in SeDuMi format to the TXT format

MATLAB Bindings

In the MATLAB directory, you can find the bindings to use cuADMM from MATLAB. To use them, you need to compile the MEX files:

cd MATLAB
mkdir build
cmake -S . -B build
cmake --build build

The signature of the MEX function is the following:

cuadmm_MATLAB(eig_stream_num_per_gpu,...
              max_iter, stop_tol,...
              At_stack, b, C_stack, blk_vec,...
              X_new, y_new, S_new, sig_new,...
              sig_update_threshold, sig_update_stage_1, sig_update_stage_2,...
              switch_admm,switch_proj_iter,switch_proj_tol,...
              sigscale);

The file cuadmm_MATLAB.cu defines the MEX function, and can be used as a reference for the input format when interfacing with other languages or libraries.

A few examples of how to use the bindings are also provided, such as example_mosek.m which shows how to solve a problem in MOSEK format.

Testing

After building, you can execute the unit tests:

cd build && ctest

Note

Some tests require the CUADMM_SOLVER_TEST_PATH environment variable to be set to the path of some test data. You can export it in your terminal session using export CUADMM_SOLVER_TEST_PATH="/path/to/test/data". If the environment variable is not set, the tests will be skipped.