Duality of Hoffman Constants

Abstract. We show that a suitable Slater condition implies a duality inequality between the Hoffman constants of the following feasibility problems: [Formula: see text] where [Formula: see text], and [Formula: see text] and [Formula: see text] are reference polyhedral cones, with respective dual cones [Formula: see text] and [Formula: see text]. Our approach relies on an exact characterization of Hoffman constants and introduces a novel Hoffman duality inequality for polyhedral set-valued mappings. These two fundamental results also yield a striking identity between the Hoffman constants of box-constrained feasibility problems, which feature a similar primal-dual structure with a box and a linear subspace as reference sets. Additionally, we establish a surprising identity between the Hoffman constants of box-constrained feasibility problems and the chi condition measures for weighted least-squares problems.