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

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.
Original languageEnglish
JournalMathematical Programming
Early online dateFeb 2020
DOIs
Publication statusE-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