Termination criteria

Termination conditions

The algorithm is terminated when an approximate optimal solution is found based on its relative primal and dual residuals and relative duality gap. At iteration $\nu$ let ${u}^\nu {}={} ({\chi}^{\nu}, {\psi}^{\nu}, {\tau}^{\nu})$, $\bar{u}^\nu {}={} (\bar{\chi}^{\nu}, \bar{\psi}^{\nu}, \bar{\tau}^{\nu})$ and $\tilde{u}^\nu {}={} (\tilde{\chi}^{\nu}, \tilde{\psi}^{\nu}, \tilde{\tau}^{\nu})$. We compute $\bar{\varsigma}^\nu {}={} \bar{\psi}^{\nu} {}-{} 2\tilde{\psi}^{\nu} {}+{} \psi^\nu.$ Let us also define the triplet $( x^\nu, y^\nu, s^\nu ) {}={} ( \bar{\chi}^{\nu}/\bar{\tau}^{\nu}, \bar{\psi}^{\nu}/\bar{\tau}^{\nu}, \bar{\varsigma}^{\nu}/\bar{\tau}^{\nu} )$, which serves as the candidate primal-dual solution at iteration $\nu$. The relative primal residual is

$$\begin{eqnarray*} \mathrm{pr}^{\nu} {}={} \frac { \| A\bar{x}^\nu + \bar{s}^\nu - b \| } { 1+\|b\| } \end{eqnarray*}$$

The relative dual residual is

$$\begin{eqnarray*} \mathrm{dr}^\nu {}={} \frac { \| A^*\bar{y}^\nu + c \| } { 1+\|c\| } \end{eqnarray*}$$

The relative duality gap is defined as

$$\begin{eqnarray*} \mathrm{gap}^\nu {}={} \frac { |\langle c, \bar{x}^{\nu}\rangle {}+{} \langle b,\bar{y}^{\nu}\rangle| } { 1 + |\langle c, \bar{x}^{\nu}\rangle| + |\langle b, \bar{y}^{\nu}\rangle| } \end{eqnarray*}$$

If $\mathrm{pr}^{\nu}$, $\mathrm{dr}^{\nu}$ and $\mathrm{gap}^{\nu}$ are all below a specified tolerance $\epsilon>0$, then we conclude that that the conic optimization problem is feasible, the algorithm is terminated and the triplet $( x^\nu, y^\nu, s^\nu )$ is an approximate solution.

The unboundedness and infeasibility certificates are derined from the theorem of the alternative. The relative infeasibility certificate is defined as

$$\begin{eqnarray*} \mathrm{ic}^{\nu} {}={} \begin{cases} { \left\|b\right\| \left\|A^*\bar{y}^{\nu}\right\| } / { \langle b, \bar{y}^{\nu}\rangle }, &\text{ if } \langle b, \bar{y}^{\nu}\rangle{}<{}0\\ +\infty,&\text{ else} \end{cases} \end{eqnarray*}$$

Likewise, the relative unboundedness certificate is defined as

$$\begin{eqnarray*} \mathrm{uc}^{\nu} {}={} \begin{cases} { \left\|c\right\| \left\|A\bar{x}^{\nu} + \bar{s}^{\nu}\right\| } / { \langle c, \bar{x}^{\nu}\rangle }, &\text{ if } \langle c, \bar{x}^{\nu}\rangle {}<{} 0\\ +\infty,&\text{ else} \end{cases} \end{eqnarray*}$$

Provided that $\bar{u}^{\nu}$ is not a feasible $\epsilon$-optimal point, it is a certificate of unboundedness if $\mathrm{uc}^{\nu}<\epsilon$ and it is a certificate of infeasibility if $\mathrm{ic}^{\nu}<\epsilon$.

Algorithm termination

SuperSCS is terminated if:

• The above conditions are satisfied up to a given tolerance or
• The maximum number of iterations is reached or
• The maximum execution time is reached