## 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 |
---|---|

Pages (from-to) | 79-109 |

Journal | Mathematical Programming |

Volume | 187 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - May 2021 |