# Algorithm

SCS applies Douglas-Rachford splitting to a homogeneous embedding of the quadratic cone program. The high level algorithm is as follows, from an initial \(w^0\) for \(k=0,1,\ldots\) do

which yields \(w^k \rightarrow u^\star + \mathcal{Q}(u^\star)\) where \(0 \in \mathcal{Q}(u^\star) + N_{\mathcal{C}_+}(u^\star)\), and \(u^k \rightarrow u^\star\) from which we can recover the optimal solution or a certificate of infeasibility (such a \(u^\star\) is guaranteed to exist). Note that this is slightly different to the formulation in the original paper, and corresponds to the latest algorithm described here. The algorithm consists of three steps. The first step involves solving a linear system of equations:

The second step is the Euclidean projection onto a convex cone, ie,

over variable \(z\). Many cones of interest have relatively simple projection operators.

## Optimality conditions

SCS solves problems of the form:

When strong duality holds, the Karush-Kuhn-Tucker (KKT) conditions are necessary and sufficient for optimality. They are given by

These are primal feasibility, dual feasibility, primal and dual cone membership,
and complementary slackness. The complementary slackness condition is
equivalent to a zero *duality gap* condition at any optimal point, that is
for \((x,y,s)\) that satisfy the KKT conditions we have

## Certificate of infeasibility

On the other hand, if no optimal solution exists then SCS is able to robustly detect primal or dual infeasibility. Any \(y \in \mathbf{R}^m\) that satisfies

acts a certificate that the quadratic cone program is primal infeasible (dual unbounded). On the other hand, if we can find \(x \in \mathbf{R}^n\) such that

then this is a certificate that the problem is dual infeasible (primal unbounded).

## Termination criteria

### Optimality

The iterates produced by SCS *always* satisfy the conic constraints \(s \in
\mathcal{K}, y \in \mathcal{K}^*, s \perp y\). Therefore to say that a problem
is solved we need to check if the primal residual, dual residual, and duality
gap are all below a certain tolerance. Specifically, SCS terminates when it has
found \(x \in \mathbf{R}^n\), \(s \in \mathbf{R}^m\), and \(y \in
\mathbf{R}^m\) that satisfy the following residual bounds.

Primal residual:

Dual residual:

Duality gap:

where \(\epsilon_\mathrm{abs}>0\) and \(\epsilon_\mathrm{rel}>0\) are
user defined settings. The \(\ell_\infty\) norm
here can be changed to other norms by changing the definition of `NORM`

in
the `include/glbopts.h`

file.

### Infeasibility

Since the conic constraints are always guaranteed by the iterates (\(s \in
\mathcal{K}, y \in \mathcal{K}^*, s \perp y\)), SCS
declares a problem **primal infeasible (dual unbounded)** when it finds \(y \in
\mathbf{R}^m\) that satisfies

Similarly, SCS declares a problem **dual infeasible (primal unbounded)** when it finds
\(x \in \mathbf{R}^n\), \(s \in \mathbf{R}^m\) that satisfy

where \(\epsilon_\mathrm{infeas} > 0\) is a user-defined setting. The \(\ell_\infty\) norm here can be changed to other norms by
changing the definition of `NORM`

in the `include/glbopts.h`

file.

In some rare cases a problem is both primal and dual infeasible. In this case SCS will return one of the two above certificates, whichever one it finds first. However, in that case the interpretation of infeasibility in one space being equivalent to unboundedness in the dual space does not hold.