View article

We give a characterization of the Hoffman constant of a system of linear constraints in relative to a reference polyhedron . The reference polyhedron R represents constraints that are easy to satisfy such as box constraints. In the special case , we obtain a novel characterization of the classical Hoffman constant. More precisely, suppose is a reference polyhedron, and . We characterize the sharpest constant such that for all and $$\begin{aligned} {\mathrm {dist}}(u, P_{A}(b)\cap R) \le H(A\vert R) \cdot \Vert (Au-b)_+\Vert , \end{aligned}$$where . 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.