Optimization Online


New characterizations of Hoffman constants for systems of linear constraints

Javier Pena(jfp***at***andrew.cmu.edu)
Juan Vera(j.c.veralizcano***at***uvt.nl)
Luis Zuluaga(luis.zuluaga***at***lehigh.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/2019
Entry Accepted: 05/07/2019
Entry Last Modified: 05/07/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society