Finite-precision reduced-QR KKT solve with certified residual status

Let $K=\left[\begin{array}{cc}H& A^T\\ A& 0\end{array}\right]\in {\mathbb{R}}^{N\times N}$ be an active KKT matrix, where $A$ has full row rank and $H$ is positive definite on $\ker A$, and let $b\in {\mathbb{R}}^N$. By The SQP KKT matrix is nonsingular under positive reduced curvature, $K$ is nonsingular. Also supply a terminating exact-storage routine which, for each requested real entry, either returns that same value with an exact representability certificate in the selected floating-point set or returns unavailable. Before QR, invoke this routine on every entry of the intended $K$ and $b$, in increasing row and column order for $K$ and increasing index for $b$. If any call is unavailable or its equality/representability certificate is not verified, return numerical-failure without a solve certificate. Otherwise use these unchanged stored values, still denoted $K,b$, for both the solve and residual evaluation. No rounded conversion is performed: every successful residual certificate below concerns the original intended data. Assume $Nu<1$, ${\gamma }_{N+3}<1\mathrm{/}8$, and the successful-operation hypotheses of Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add.

Set $R^{(0)}=K$. For $k=0,\dots ,N-1$, call Scaled Householder reflector formation and application on the active column $R_{k:N-1,k}^{(k)}$ and trailing block $R_{k:N-1,k+1:N}^{(k)}$. Set $R^{(k+1)}$ equal to $R^{(k)}$ with the returned active block written into those rows and columns, leaving earlier rows and columns unchanged, and store the returned reflector. If a call fails, return numerical-failure. After the loop set $\widehat{R}=R^{(N)}$. Call the stored reflectors on $b$ in the same order, on the matching active row slices and without column overwrites; call the result $\widehat{y}$. Solve $\widehat{R}\widehat{z}=\widehat{y}$ by descending substitution, for $i=N-1,\dots ,0$: compute the sequential rounded dot $s_i=\mathrm{fl}({\sum }_{j=i+1}^{N-1}{\widehat{R}}_{ij}{\widehat{z}}_j)$, then $t_i=\mathrm{fl}({\widehat{y}}_i-s_i)$ and ${\widehat{z}}_i=\mathrm{fl}(t_i\mathrm{/}{\widehat{R}}_{ii})$, following Forward and backward substitution for triangular linear systems. If reflector application or substitution fails, return numerical-failure. The perturbation bounds for these procedures are supplied by Computed reduced QR least squares is backward stable for full column rank.

For a returned stored vector $\widehat{z}$, compute in the specified order $\widehat{v}=\mathrm{fl}(K\widehat{z})$ and $\widehat{r}=\mathrm{fl}(\widehat{v}-b)$. Use Rounded matrix products give certified linear and normal-equation residual allowances with $A=K$, $x=\widehat{z}$, and $y=b$ to compute $g_N=\frac{1+6u}{1-(N-1)u}-1,W=g_N\mathrm{\parallel }K{\mathrm{\parallel }}_F\mathrm{\parallel }\widehat{z}{\mathrm{\parallel }}_2+u(\mathrm{\parallel }\widehat{v}{\mathrm{\parallel }}_2+\mathrm{\parallel }b{\mathrm{\parallel }}_2),$ where the product and subtraction use successful sequential dot products and $(N-1)u<1$. Let ${\kappa }_N$ be the local coefficient specified by The scaled computed Householder step satisfies the local backward error premise, and set ${\beta }_Q=(1+{\kappa }_N{)}^N-1,{\beta }_b={\beta }_Q,{\beta }_K={\beta }_Q+{\gamma }_{N+3}(1+{\beta }_Q),$ where ${\gamma }_j=ju\mathrm{/}(1-ju)$ is defined by the operationwise model. The QR theorem supplies an exactly orthonormal $\widehat{Q}$, a triangular $\widehat{R}$, and perturbations satisfying $K+{\mathrm{\Delta }}_Q=\widehat{Q}\widehat{R},(\widehat{R}+{\mathrm{\Delta }}_R)\widehat{z}={\widehat{Q}}^T(b+\delta b),$ with $\mathrm{\parallel }{\mathrm{\Delta }}_Q{\mathrm{\parallel }}_F\le {\beta }_Q\mathrm{\parallel }K{\mathrm{\parallel }}_F$, $\mathrm{\parallel }{\mathrm{\Delta }}_R{\mathrm{\parallel }}_F\le {\gamma }_{N+3}\mathrm{\parallel }\widehat{R}{\mathrm{\parallel }}_F$, and $\mathrm{\parallel }\delta b{\mathrm{\parallel }}_2\le {\beta }_b\mathrm{\parallel }b{\mathrm{\parallel }}_2$. Define ${\mathrm{\Delta }}_K={\mathrm{\Delta }}_Q+\widehat{Q}{\mathrm{\Delta }}_R$. Return $\eta =\min \{\mathrm{\parallel }\widehat{r}{\mathrm{\parallel }}_2+W,{\beta }_K\mathrm{\parallel }K{\mathrm{\parallel }}_F\mathrm{\parallel }\widehat{z}{\mathrm{\parallel }}_2+{\beta }_b\mathrm{\parallel }b{\mathrm{\parallel }}_2\}$ using exact norms or certified upward bounds. If residual evaluation or a certified bound fails, return numerical-failure. A successful return certifies a residual upper bound, not a small residual or an accurate exact solution by itself.