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}\begin{align} \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{align}\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}.\]

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 \max(\|P x\|_\infty, \|A x + s\|_\infty) < \epsilon_\mathrm{infeas}\]

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.