En mathématiques, et plus précisément en analyse convexe, le lemme de Hoffman est ce que l'on appelle une borne d'erreur, c'est-à-dire une estimation (ou majoration) de la distance à un ensemble (en l'occurrence, un polyèdre convexe) par des quantités aisément calculables, alors que la distance elle-même requiert la résolution d'un problème d'optimisation (quadratique convexe lorsque l'ensemble est un polyèdre convexe). Il s'agit d'une des premières bornes d'erreur non triviales.

Le résultat a été démontré par Alan J. Hoffman en 1952 et a conduit à de nombreux développements en optimisation^[1] (voir l'article Borne d'erreur).

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).

• (en) O. Güler, A. J. Hoffman, U. G. Rothblum (1995). Approximations to solutions to systems of linear inequalities. SIAM Journal on Matrix Analysis and Applications, 16, 688–696.
• (en) A. D. Ioffe (1979). Regular points of Lipschitz functions. Translations of the American Mathematical Society, 251, 61–69.
• (ru + en) A. D. Ioffe (2000). Metric regularity and subdifferential calculus. Uspekhi Mat. Nauk, 55, 103–162. En russe, traduit dans Russian Mathematical Surveys, 55, 501-558.

• Borne d'erreur : fait le point sur les généralisations du lemme de Hoffman à des ensembles plus complexes qu'un polyèdre convexe

• (en) D. Azé, J.-N. Corvellec (2002). On the sensitivity analysis of Hoffman constants for systems of linear inequalities. SIAM Journal on Optimization, 12, 913–927.
• (en) O. Güler (2010). Foundations of Optimization, Graduate Texts in Mathematics 258, Springer, doi.
• (en) A. J. Hoffman (1952). On approximate solutions of systems of linear inequalities, Journal of Research of the National Bureau of Standard 49, 263-265.

• Portail des mathématiques
• Portail de l'analyse