New characterizations of Hoffman constants for systems of linear constraints

J.F. Pena, J. C. Vera, Luis F. Zuluaga

Research output: Contribution to journalArticleScientificpeer-review

9 Citations (Scopus)


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

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 languageEnglish
Pages (from-to)79-109
JournalMathematical Programming
Issue number1-2
Publication statusPublished - May 2021


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

Cite this