C/C++
In this example we shall solve the following small quadratic program:
\[\begin{split}\begin{array}{ll}
\mbox{minimize} & (1/2) x^T \begin{bmatrix}3 & -1\\ -1 & 2 \end{bmatrix}
x + \begin{bmatrix}-1 \\ -1\end{bmatrix}^T x \\
\mbox{subject to} & \begin{bmatrix} -1 \\ 1 \end{bmatrix}^T x = -1 \\
& \begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix} x \leq \begin{bmatrix}0.3 \\ -0.5\end{bmatrix}
\end{array}\end{split}\]
over variable \(x \in \mathbf{R}^2\). This problem corresponds to data:
\[\begin{split}\begin{array}{cccc}
P = \begin{bmatrix}3 & -1\\ -1 & 2 \end{bmatrix}, &
A = \begin{bmatrix}-1 & 1\\ 1 & 0\\ 0 & 1\end{bmatrix}, &
b = \begin{bmatrix}-1 \\ 0.3 \\ -0.5\end{bmatrix}, &
c = \begin{bmatrix}-1 \\ -1\end{bmatrix}.
\end{array}\end{split}\]
And the cone \(\mathcal{K}\) consists of a zero cone (z) of length 1
and a positive cone (l) of dimension 2. Note that the order of the
rows in \(A\) and \(b\) corresponds to the order in Cones, so
the row corresponding to the zero cone comes first, followed by the rows for the
positive cone.
C code to solve this is below.
#include "scs.h" /* SCS API */
#include <stdio.h> /* printf */
#include <stdlib.h> /* memory allocation */
/* Set up and solve basic qp */
int main(int argc, char **argv) {
/* Set up the problem data */
/* A and P must be in compressed sparse column format */
double P_x[3] = {3., -1., 2.}; /* Upper triangular of P only */
int P_i[3] = {0, 0, 1};
int P_p[3] = {0, 1, 3};
double A_x[4] = {-1., 1., 1., 1.};
int A_i[4] = {0, 1, 0, 2};
int A_p[3] = {0, 2, 4};
double b[3] = {-1., 0.3, -0.5};
double c[2] = {-1., -1.};
/* data shapes */
int n = 2; /* number of variables */
int m = 3; /* number of constraints */
/* Allocate SCS structs */
ScsCone *k = (ScsCone *)calloc(1, sizeof(ScsCone));
ScsData *d = (ScsData *)calloc(1, sizeof(ScsData));
ScsSettings *stgs = (ScsSettings *)calloc(1, sizeof(ScsSettings));
ScsSolution *sol = (ScsSolution *)calloc(1, sizeof(ScsSolution));
ScsInfo *info = (ScsInfo *)calloc(1, sizeof(ScsInfo));
/* Fill in data struct */
d->m = m;
d->n = n;
d->b = b;
d->c = c;
d->A = &(ScsMatrix){A_x, A_i, A_p, m, n};
d->P = &(ScsMatrix){P_x, P_i, P_p, n, n};
/* Cone */
k->z = 1;
k->l = 2;
/* Utility to set default settings */
scs_set_default_settings(stgs);
/* Modify tolerances */
stgs->eps_abs = 1e-9;
stgs->eps_rel = 1e-9;
/* Initialize SCS workspace */
ScsWork *scs_work = scs_init(d, k, stgs);
/* Solve! */
int exitflag = scs_solve(scs_work, sol, info, 0);
/*
* If we wanted to solve many related problems with different
* b / c vectors we could update the SCS workspace as follows:
*
* int success = scs_update(scs_work, new_b, new_c)
* int new_exitflag = scs_solve(scs_work, sol, info, 1);
*
*/
/* Free SCS workspace */
scs_finish(scs_work);
/* Verify that SCS solved the problem */
printf("SCS solved successfully: %i\n", exitflag == SCS_SOLVED);
/* Print some info about the solve */
printf("SCS took %i iters, using the %s linear solver.\n", info->iter,
info->lin_sys_solver);
/* Print solution x */
printf("Optimal solution vector x*:\n");
for (int i = 0; i < n; ++i) {
printf("x[%i] = %4f\n", i, sol->x[i]);
}
/* Print dual solution y */
printf("Optimal dual vector y*:\n");
for (int i = 0; i < m; ++i) {
printf("y[%i] = %4f\n", i, sol->y[i]);
}
/* Free allocated memory */
free(k);
free(d);
free(stgs);
free(info);
/* SCS allocates sol->x,y,s if NULL on entry, need to be freed */
free(sol->x);
free(sol->y);
free(sol->s);
free(sol);
return 0; /* returning exitflag will set bash exit code to 1 */
}
After following the CMake install instructions, we can
compile the code (assuming the library was installed in /usr/local/ and
the gcc compiler is available) using:
gcc -I/usr/local/include/scs -L/usr/local/lib/ qp.c -o qp.out -lscsdir
Then running the binary yields output:
------------------------------------------------------------------
SCS v3.2.1 - Splitting Conic Solver
(c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem: variables n: 2, constraints m: 3
cones: z: primal zero / dual free vars: 1
l: linear vars: 2
settings: eps_abs: 1.0e-09, eps_rel: 1.0e-09, eps_infeas: 1.0e-07
alpha: 1.50, scale: 1.00e-01, adaptive_scale: 1
max_iters: 100000, normalize: 1, rho_x: 1.00e-06
acceleration_lookback: 10, acceleration_interval: 10
lin-sys: sparse-direct-amd-qdldl
nnz(A): 4, nnz(P): 3
------------------------------------------------------------------
iter | pri res | dua res | gap | obj | scale | time (s)
------------------------------------------------------------------
0| 1.51e+00 1.00e+00 4.91e+00 1.14e+00 1.00e-01 1.19e-04
75| 4.09e-10 7.93e-10 1.07e-09 1.24e+00 1.00e-01 2.10e-04
------------------------------------------------------------------
status: solved
timings: total: 2.11e-04s = setup: 9.88e-05s + solve: 1.13e-04s
lin-sys: 1.48e-05s, cones: 3.92e-06s, accel: 5.06e-05s
------------------------------------------------------------------
objective = 1.235000
------------------------------------------------------------------
SCS solved successfully: 1
SCS took 75 iters, using the sparse-direct-amd-qdldl linear solver.
Optimal solution vector x*:
x[0] = 0.300000
x[1] = -0.700000
Optimal dual vector y*:
y[0] = 2.700000
y[1] = 2.100000
y[2] = 0.000000