[![INFORMS Journal on Computing Logo](https://INFORMSJoC.github.io/logos/INFORMS_Journal_on_Computing_Header.jpg)](https://pubsonline.informs.org/journal/ijoc)

# LoRADS: A Low-Rank ADMM Splitting Approach for Semidefinite Programming

This archive is distributed in association with the [INFORMS Journal on
Computing](https://pubsonline.informs.org/journal/ijoc) under the [Apache License 2.0](LICENSE).

The software and data in this repository are a snapshot of the software and data
that were used in the research reported on in the paper 
[A Low-Rank ADMM Splitting Approach for
Semidefinite Programming](https://doi.org/10.1287/ijoc.2019.0000) by Han et.al. 

## Cite

To cite the contents of this repository, please cite both the paper and this repo, using their respective DOIs.

https://doi.org/10.1287/ijoc.2024.0701

https://doi.org/10.1287/ijoc.2024.0701.cd

Below is the BibTex for citing this snapshot of the repository.

```
@misc{LoRADS,
  author =        {Han et.al.},
  publisher =     {INFORMS Journal on Computing},
  title =         {{A {L}ow-{R}ank {ADMM} {S}plitting Approach for {S}emidefinite {P}rogramming}},
  year =          {2024},
  doi =           {10.1287/ijoc.2024.07071.cd},
  url =           {https://github.com/INFORMSJoC/2024.0701},
  note =          {Available for download at https://github.com/INFORMSJoC/2024.0701},
}  
```

## Description

LoRADS is an enhanced first-order method solver for low rank Semi-definite programming problems (SDPs). LoRADS is written in ANSI C and is maintained by Cardinal Operations COPT development team. More features are still under active development.

## Code Overview
All algorithms are coded in C. We summarize the main functionalities of the code below:

| File | Description |
|------|-------------|
|src/src_semi/main.c|Main program of LoRADS|
|src/src_semi/lorads.h|Solver constant definitions|
|src/src_semi/lorads_utils.c|Solver utility function definitions, including commonly used memory allocation snippets|
|src/src_semi/lorads_alg/lorads_alm|Solver ALM algorithm implementation|
|src/src_semi/lorads_alg/lorads_admm|Solver ADMM algorithm implementation|
|src/src_semi/lorads_alg/lorads_alg_common|Common code snippets used by both ALM and ADMM solver implementations|
|src/src_semi/lorads_alg/linalg/*|Linear Algebra used in our solver, mostly using BLAS and LAPACK, with some custom implementations|
|src/src_semi/lorads_alg/io/*|Implementation for reading SDPA format files|
|src/src_semi/data/def_*|Various data structure definitions for the solver, including dense (sparse) cone, dense (sparse) SDP coefficients, dense (sparse) vectors, LBFGS node structure, and solver data structures|
|src/src_semi/data/lorads_solver|Solver-level operations: create solver, destroy solver, phase 1 and phase switch, and so on|
|src/src_semi/data/\*conic\*|Conic-level operations: create cone, destroy cone, weighted sum of all coefficients in this cone, cone feature statistics, and so on|
|src/src_semi/data/\*lp_conic\*|Various definitions and operations for LP cone|
|src/src_semi/data/lorads_element|This file implements basic operations for dense and sparse vectors in LoRADS|

Furthermore, if you are interested in the specific functionalities of the code, the following commands can be used to generate the corresponding reference documentation:
```bash
doxygen Doxyfile
cd doc/latex
make
```
The file `refman.pdf` provides detailed descriptions of each function within the codebase.

## Building

### Linux/MacOS
```bash 
cd ./src
mkdir build
cd build
cmake ..
make
```

## Running Experiments

1. **Small Examples**
   Run the interactive demo:
   ```bash
   jupyter notebook ./scripts/demo.ipynb
   ```

2. **Full Experiments**
   - Generate data:
     ```bash
     julia ./data/env.jl
     julia ./data/gen_MatrixCompletion.jl
     julia ./data/gen_MaxCut.jl
     ```
   - Run experiments:
     ```bash
     # Example for small matrix completion problem
     ./src/build/LoRADS_v_2_0_1-alpha ./data/General_SDP/MC_300.dat-s --reoptLevel 0 --timesLogRank 2 --heuristicFactor 10 --timeSecLimit 10000
     ```
   For more parameter settings and experiment configurations, see `./scripts/run.ipynb`.


## Parameters

LoRADS provides users with customizable parameters to fine-tune the solving process according to specific problem requirements (if needed). Below is a detailed description of each parameter:

| **Parameter**   | **Description**                                                                           | **Type** | **Default Value** |
| --------------- | ----------------------------------------------------------------------------------------- | -------- | ----------------- |
| timesLogRank    | Multiplier for the O(log(m)) rank calculation (rank = **timesLogRank** $\times$ log(m)).  | float    | 2.0               |
| phase1Tol       | Tolerance for ending Phase I.                                                             | float    | 1e-3              |
| initRho         | Initial value for the penalty parameter $\rho$.                                           | float    | 1/n               |
| rhoMax          | Maximum value for the penalty parameter $\rho$.                                           | float    | 5000.0            |
| rhoFreq         | Frequency of increasing $\rho$ (increased every **rhoFreq** iterations).                  | int      | 5                 |
| rhoFactor       | Multiplier for increasing $\rho$ ($\rho =$ **rhoFactor** $\times$ $\rho$).                | float    | 1.2               |
| heuristicFactor | Heuristic factor applied when switching to Phase II.                                      | float    | 1.0               |
| maxIter         | Maximum iteration number for the ADMM algorithm.                                          | int      | 10000             |
| timeSecLimit    | Solving time limitation in seconds.                                                       | float    | 10000.0           |

For example, to set **timesLogRank** to 1.0 and solve a problem, we can execute

```
LoRADS_v_1_0_0-alpha SDPAFILE.dat-s --timesLogRank 1.0
```



## Ongoing Development
This code is being developed on an on-going basis at the authors' [Github site](https://github.com/COPT-Public/LoRADS).


## License

This project is licensed under the Apache License 2.0 - see the [LICENSE](LICENSE) file for details.
