Lemme de Hoffman

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 (voir l'article Borne d'erreur).

Énoncé du lemme

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

$P:=\{x\in {ℝ}^n:Ax⩽b\},$

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

$ℬ(A)$

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

${\mathrm{d}}_P(x):=\underset{y\in P}{\inf }\Vert y-x\Vert ,$

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

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

Discussion

• La constante $h$ n'est pas une constante universelle : elle peut être arbitrairement grande. Ainsi, si pour $\epsilon >0$, on définitModèle:Saut$A_{\epsilon }:=\left(\begin{array}{cc}\epsilon & -1\\ \epsilon & 1\end{array}\right),P\equiv P_{\epsilon }:=\{y\in {ℝ}^2:A_{\epsilon }y⩽0\}\text{et}x:=\left(\begin{array}{c}1\\ 0\end{array}\right),$Modèle:Sautalors $h\to \mathrm{\infty }$ lorsque $\epsilon \downarrow 0$.
• La meilleure constante $h$ est étudiée par Azé et Corvellec (2002).

Annexes

Autres contributions

• Modèle: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.
• Modèle:En A. D. Ioffe (1979). Regular points of Lipschitz functions. Translations of the American Mathematical Society, 251, 61–69.
• Modèle:Mul 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.

Article connexe

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

Bibliographie

• Modèle: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.
• Modèle:En O. Güler (2010). Foundations of Optimization, Graduate Texts in Mathematics 258, Springer, doi.
• Modèle: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.