 |
SuperSCS
1.3.2
|
|
SuperSCS
1.3.2
|
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\).
SuperSCS is terminated if:
1.8.6
