# 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 $\R^n$ relative to a reference polyhedron $R\subseteq\R^n$. The reference polyhedron $R$ represents constraints that are easy to satisfy such as box constraints. In the special case $R = \R^n$, we obtain a novel characterization of the classical Hoffman constant. More precisely, given a reference polyhedron $R\subseteq \R^n$ and $A\in \R^{m\times n}$, we characterize the sharpest constant $H(A\vert R)$ such that for all $b \in A(R) + \R^m_+$ and $u\in R$ $\dist(u, P_{A}(b)\cap R) \le H(A\vert R) \cdot \|(Au-b)_+\|,$ 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.

## Citation

Working Paper, Tepper School of Business, Carnegie Mellon University, May 2019