• Time: Thursday, May 3rd, 2018 at 5:30pm
  • Place: Wean Hall 8220

Abstract

A classical result of Hoffman (1952) shows that the distance from a point $u$ to a non-empty polyhedron defined by the system of inequalities $Ax \le b$ can be bounded above in terms of the “error” or “residual” $(Au-b)_+ = max(0,Au-b)$. More precisely, the distance from $u$ to the polyhedron ${x: Ax \le b}$ is bounded above by $H(A)\cdot |(Au-b)_+|$ for some Hoffman constant $H(A)$ that depends only on the matrix $A$. This type of “error bound” plays a fundamental role for establishing convergence properties of a wide variety of algorithms for optimization problems.

This talk will give a novel and constructive proof of existence and characterization of the Hoffman constant $H(A)$. We highlight the striking similarity between the Hoffman constant $H(A)$ and the smallest singular value of $A$. The new characterization of the Hoffman constant yields some interesting new insights and an algorithm to compute $H(A)$ – a notoriously difficult computational problem.

The talk will be entirely self-contained and easily accessible. The only required prior knowledge is basic matrix algebra.

Pizza will be served.