## Abstract

We give a characterization of the Hoffman constant of a system of linear constraints in Rnrelative to a reference polyhedronR⊆Rn. 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 R⊆Rn 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)∩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.

dist(u,PA(b)∩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.

Original language | English |
---|---|

Journal | Mathematical Programming |

Early online date | Feb 2020 |

DOIs | |

Publication status | E-pub ahead of print - Feb 2020 |