New characterizations of Hoffman constants for systems of linear constraints

We give a characterization of the Hoffman constant of a system of linear constraints in ${\mathbb{R}}^n$ {\em relative} to a {\em reference polyhedron} $R\subseteq {\mathbb{R}}^n$. The reference polyhedron $R$ represents constraints that are easy to satisfy such as box constraints. In the special case $R={\mathbb{R}}^n$, we obtain a novel characterization of the classical Hoffman constant. More precisely, suppose $R\subseteq {\mathbb{R}}^n$ is a reference polyhedron, $A\in {\mathbb{R}}^{m\times n},$ and $A(R):=\{Ax:x\in R\}$. We characterize the sharpest constant $H(A\mathrm{\mid }R)$ such that for all $b\in A(R)+{\mathbb{R}}_{+}^m$ and $u\in R$ $$\text{dist}(u,P_A(b)\cap R)\le H(A\mathrm{\mid }R)\cdot \mathrm{\parallel }(Au-b{)}_{+}\mathrm{\parallel },$$ where $P_A(b) = {x\in \R^n:Ax\le b}$. Our characterization is stated in terms of the largest of a canonical collection of easily computable Hoffman constants. Our characterization in turn suggests new algorithmic procedures to compute Hoffman constants.