Lemma 4, p. 14 — ‖(h − Kz)⁺‖ ≤ ρ_r(z)√(1 + R²) for z ∈ W_R(0), r ∈ (0, R]

Let $A\in\mathbb R^{m\times n}$, $b\in\mathbb R^m$, $c\in\mathbb R^n$, let $L(x,y)=c^\top x+y^\top b-y^\top Ax$ be the Lagrangian (19) on $Z=\{x\ge0\}\times\mathbb R^m$, equipped with the Euclidean norm, and let $K,h$ be the KKT data (20). Suppose (19) has a saddle point. Then for all $R\in(0,\infty)$, $r\in(0,R]$ and $z\in W_R(0)$,

The KKT residual, a standard stopping criterion for LP, is thus bounded by the normalized duality gap; combined with Hoffman's bound this gives sharpness of LP (Lemma 5).

Formalization Note The inequality is stated in the extended reals, with $\sqrt{1+R^2}>0$ coerced. The hypothesis that a solution exists is kept as on the page, although it is not needed for the inequality.