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

\[\begin{split}\tilde u^{k+1} &= (I + \mathcal{Q})^{-1} w^k\\ u^{k+1} &= \Pi_{\mathcal{C}_+}(2\tilde u^{k+1} - w^k)\\ w^{k+1} &= w^k + u^{k+1} - \tilde u^{k+1}\end{split}\]

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:

\[\begin{split}\begin{bmatrix} I + P & A^T \\ A & -I \end{bmatrix}\begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} \mu_x \\ -\mu_y \end{bmatrix}\end{split}\]

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

\[\begin{split}\begin{array}{ll} \mbox{minimize} & \| z - z_0\|_2^2 \\ \mbox{subject to } & z \in \mathcal{K} \end{array}\end{split}\]

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

Optimality conditions

SCS solves problems of the form:

\[\begin{split}\begin{array}{lcr} \begin{array}{ll} \mbox{minimize} & (1/2)x^\top P x + c^\top x\\ \mbox{subject to} & Ax + s = b\\ & s \in \mathcal{K} \end{array} &\quad& \begin{array}{ll} \mbox{maximize} & -(1/2)x^\top P x - b^\top y\\ \mbox{subject to} & Px + A^\top y + c = 0\\ & y \in \mathcal{K}^* \end{array} \end{array}\end{split}\]

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

\[Ax + s = b, \quad Px + A^\top y + c = 0,\quad s \in \mathcal{K}, \quad y \in \mathcal{K}^*,\quad s \perp y.\]

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

\[s\perp y \ \Leftrightarrow \ c^\top x + b^\top y + x^\top P x = 0.\]

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

\[A^\top y = 0,\ y \in \mathcal{K}^*,\ b^\top y < 0\]

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

\[Px = 0,\ -Ax\in \mathcal{K},\ c^\top x < 0\]

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:

\[r_p := \|Ax + s - b\|_\infty \leq \epsilon_\mathrm{abs} + \epsilon_\mathrm{rel} \max(\|Ax\|_\infty, \|s\|_\infty, \|b\|_\infty)\]

• Dual residual:

\[r_d := \|Px + A^\top y + c \|_\infty \leq \epsilon_\mathrm{abs} + \epsilon_\mathrm{rel} \max(\|Px\|_\infty, \|A^\top y\|_\infty, \|c\|_\infty)\]

• Duality gap:

\[r_g := |x^\top Px + c^\top x + b^\top y| \leq \epsilon_\mathrm{abs} + \epsilon_\mathrm{rel} \max(|x^\top P x|, |c^\top x|, |b^\top y|),\]

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

\[b^\top y = -1, \quad \|A^\top y\|_\infty < \epsilon_\mathrm{infeas} \cdot \min\left(1, \frac{\max_{ij} |A_{ij}|}{\|b\|_\infty}\right).\]

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

\[c^\top x = -1, \quad \|P x\|_\infty < \epsilon_\mathrm{infeas}, \quad \|A x + s\|_\infty < \epsilon_\mathrm{infeas} \cdot \min\left(1, \frac{\max_{ij} |A_{ij}|}{\|c\|_\infty}\right)\]

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 (the \(\max_{ij} |A_{ij}|\) factor is always the largest entry magnitude of \(A\)).

The \(\min(1, \cdot)\) factors make the tests invariant to a rescaling of \(b\) (resp. \(c\)) relative to \(A\). The certificate normalizations \(b^\top y = -1\) and \(c^\top x = -1\) otherwise bake the data magnitudes into the effective tolerance: with, e.g., \(\|c\|_\infty \sim 10^6\), a normalized certificate \(x\) has norm \(\sim 10^{-6}\) and the unscaled test becomes six orders of magnitude looser than intended, which can produce false infeasibility declarations on badly scaled feasible problems. The factors only ever tighten the tests, never loosen them.

To guard against transient iterates that momentarily pass the residual tests (for example iterates produced by acceleration steps), SCS additionally requires the certificate conditions to hold at two consecutive residual checks before declaring infeasibility or unboundedness.

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.