Lemme de Hoffman

On considère un polyèdre convexe ${\displaystyle P}$ de ${\displaystyle \mathbb {R} ^{n}}$, écrit sous la forme suivante

où ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ est une matrice réelle et ${\displaystyle b\in \mathbb {R} ^{m}}$. On note

l'ensemble des vecteurs ${\displaystyle b\in \mathbb {R} ^{m}}$ tels que ${\displaystyle P\neq \varnothing }$. Pour une norme ${\displaystyle \|\cdot \|}$ sur ${\displaystyle \mathbb {R} ^{n}}$ (pas nécessairement la norme euclidienne), on note

la distance de ${\displaystyle x}$ à ${\displaystyle P}$. Pour ${\displaystyle v\in \mathbb {R} ^{m}}$, on note ${\displaystyle v^{+}}$ le vecteur de ${\displaystyle \mathbb {R} ^{m}}$ dont la composante ${\displaystyle i}$ est ${\displaystyle \max(0,v_{i})}$.

Le lemme de Hoffman permet donc d'estimer la distance de ${\displaystyle x}$ à ${\displaystyle P}$ par la norme du résidu ${\displaystyle (Ax-b)^{+}}$.

• La constante ${\displaystyle h}$ n'est pas une constante universelle : elle peut être arbitrairement grande. Ainsi, si pour ${\displaystyle \varepsilon >0}$, on définit
  ${\displaystyle A_{\varepsilon }:={\begin{pmatrix}\varepsilon &-1\\\varepsilon &1\end{pmatrix}},\qquad P\equiv P_{\varepsilon }:=\{y\in \mathbb {R} ^{2}:A_{\varepsilon }y\leqslant 0\}\qquad {\mbox{et}}\qquad x:={\begin{pmatrix}1\\0\end{pmatrix}},}$
  alors ${\displaystyle h\to \infty }$ lorsque ${\displaystyle \varepsilon \downarrow 0}$.

• La meilleure constante ${\displaystyle h}$ est étudiée par Azé et Corvellec (2002).