(22), proof of Lemma 4, p. 14 — ρ_r(z) ≥ ‖v‖ with v = ((−c + A⊤y)⁺, b − Ax)

Let $A\in\mathbb R^{m\times n}$, $b\in\mathbb R^m$, $c\in\mathbb R^n$ and consider the LP Lagrangian $L(x,y)=c^\top x+y^\top b-y^\top Ax$ on $Z=\{x\ge0\}\times\mathbb R^m$, with the Euclidean norm on $\mathbb R^{n+m}$. For $z=(x,y)\in Z$ set

Then for every $r>0$ the normalized duality gap satisfies

This is the half of Lemma 4 that controls primal infeasibility $\|b-Ax\|$ and dual infeasibility $\|(A^\top y-c)^+\|$ by the normalized duality gap, uniformly in the radius $r$.

Formalization Note The page's assumption that (19) has a solution and the radius $R$ are not needed here and are omitted. When $v=0$ the claim reads $\rho_r(z)\ge0$.