Basic QP

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.

Python code to solve this is below.

import scipy
import scs
import numpy as np

# Set up the problem data
P = scipy.sparse.csc_matrix([[3.0, -1.0], [-1.0, 2.0]])
A = scipy.sparse.csc_matrix([[-1.0, 1.0], [1.0, 0.0], [0.0, 1.0]])
b = np.array([-1, 0.3, -0.5])
c = np.array([-1.0, -1.0])

# Populate dicts with data to pass into SCS
data = dict(P=P, A=A, b=b, c=c)
cone = dict(z=1, l=2)

# Initialize solver
solver = scs.SCS(data, cone, eps_abs=1e-9, eps_rel=1e-9)
# Solve!
sol = solver.solve()

print(f"SCS took {sol['info']['iter']} iters")
print("Optimal solution vector x*:")
print(sol["x"])

print("Optimal dual vector y*:")
print(sol["y"])

After following the python install instructions, we can run the code yielding output:

------------------------------------------------------------------
	       SCS v3.2.0 - 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
	  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  8.39e-05 
    75| 4.09e-10  7.93e-10  1.07e-09  1.24e+00  1.00e-01  3.93e-04 
------------------------------------------------------------------
status:  solved
timings: total: 5.30e-04s = setup: 1.31e-04s + solve: 3.98e-04s
	 lin-sys: 1.55e-05s, cones: 4.71e-06s, accel: 2.72e-04s
------------------------------------------------------------------
objective = 1.235000
------------------------------------------------------------------
SCS took 75 iters
Optimal solution vector x*:
[ 0.3 -0.7]
Optimal dual vector y*:
[2.7 2.1 0. ]