Lemma 5, p. 15 — the LP primal-dual problem (19) is 1/(H(K)√(1+4R²))-sharp on W_R(0)

Sharpness of linear programming. Let $A\in\mathbb R^{m\times n}$, $b\in\mathbb R^m$, $c\in\mathbb R^n$ and consider the primal-dual problem (19), $\min_{x\ge0}\max_{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}$. Assume (19) has a solution, i.e. its saddle-point set $Z^\star$ is nonempty. Let $H(K)>0$ be a Hoffman constant of the KKT system (20) in the Euclidean norm, i.e. a constant with

Then for every $R\in(0,\infty)$ the problem (19) is $\alpha$-sharp on $W_R(0)=\{z\in Z:\|z\|\le R\}$ with

that is, $\alpha\,\operatorname{dist}(z,Z^\star)\le\rho_r(z)$ for every $z\in W_R(0)$ and every $r\in(0,\operatorname{diam}(W_R(0))]$.

This is the paper's first contribution: it supplies the sharpness hypothesis of its restart theorems for LP, which yields linear convergence of restarted PDHG, extragradient and ADMM on linear programs.

Formalization Note $H(K)$ enters through its defining property (26), quantified over all $z\in\mathbb R^{n+m}$ (not only $z\in Z$); the result is stated for any constant with that property, which includes the Hoffman constant. $H>0$ is assumed (a Hoffman constant is positive). Sharpness is Definition 1, with $r$ ranging over $(0,\operatorname{diam}(W_R(0))]$ and the diameter computed in the extended reals.