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

## Fingerprint Dive into the research topics of 'New characterizations of Hoffman constants for systems of linear constraints'. Together they form a unique fingerprint.

## Cite this

Pena, J. F., Vera, J. C., & Zuluaga, L. F. (2020). New characterizations of Hoffman constants for systems of linear constraints.

*Mathematical Programming*. https://doi.org/10.1007/s10107-020-01473-6