An easily computable upper bound on the Hoffman constant for homogeneous inequality systems
Let $A\in \mathbb{R}^{m\times n}\setminus \{0\}$ and $P:=\{x:Ax\le 0\}$. This paper provides a procedure to compute an upper bound on the following {\em homogeneous Hoffman constant} \[ H_0(A) := \sup_{u\in \mathbb{R}^n \setminus P} \frac{\text{dist}(u,P)}{\text{dist}(Au, \mathbb{R}^m_-)}. \] In sharp contrast to the intractability of computing more general Hoffman constants, the procedure described in this paper is entirely … Read more