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: $$\begin{array}{r}Ax-b\in S\\ x\in R\end{array}\text{ and }\begin{array}{r}c-A^{T}y\in R^{\ast }\\ y\in S^{\ast }.\end{array}$$ where $A\in {\mathbb{R}}^{m\times n}$, and $R\subseteq {\mathbb{R}}^n$ and $S\subseteq {\mathbb{R}}^m$ are reference polyhedral cones, with respective dual cones $R^{\ast }\subseteq {\mathbb{R}}^n$ and $S^{\ast }\subseteq {\mathbb{R}}^m$. 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

25 pages. To Appear in SIAM Journal on Optimization