  


New characterizations of Hoffman constants for systems of linear constraints
Javier Pena(jfpandrew.cmu.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 \(Aub)_+\, \] 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, setvalued 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/2019 Modify/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  