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 Rn em relative to a em reference polyhedron RsubseteqRn. The reference polyhedron R represents constraints that are easy to satisfy such as box constraints. In the special case R = Rn, we obtain a novel characterization of the classical Hoffman constant. More precisely, suppose Rsubseteq ℝn is a reference polyhedron, A∈ Rm× n, and A(R):=Ax: x∈ R. We characterize the sharpest constant H(A|R) such that for all b ∈ A(R) + Rm_+ and u∈ R [ dist(u, PA(b)cap R) ≤ H(A|R) · |(Au-b)_+|, ] where PA(b) = x∈ Rn:Ax≤ 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.