- New characterizations of Hoffman constants for systems of linear constraints Javier Pena(jfpandrew.cmu.edu) Juan Vera(j.c.veralizcanouvt.nl) Luis Zuluaga(luis.zuluagalehigh.edu) Abstract: We give a characterization of the Hoffman constant of a system of linear constraints in $\R^n$ relative to a reference polyhedron $R\subseteq\R^n$. The reference polyhedron $R$ represents constraints that are easy to satisfy such as box constraints. In the special case $R = \R^n$, we obtain a novel characterization of the classical Hoffman constant. More precisely, given a reference polyhedron $R\subseteq \R^n$ and $A\in \R^{m\times n}$, we characterize the sharpest constant $H(A\vert R)$ such that for all $b \in A(R) + \R^m_+$ and $u\in R$ $\dist(u, P_{A}(b)\cap R) \le H(A\vert R) \cdot \|(Au-b)_+\|,$ where $P_A(b) = \{x\in \R^n:Ax\le 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. Keywords: Hoffman constant, set-valued mappings, norms Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Combinatorial Optimization (Polyhedra ) Citation: Working Paper, Tepper School of Business, Carnegie Mellon University, May 2019 Download: [PDF]Entry Submitted: 05/07/2019Entry Accepted: 05/07/2019Entry Last Modified: 05/07/2019Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.