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

Énoncé du lemme

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

$P:=\{x\in \mathbb {R} ^{n}:Ax\leqslant b\},$

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

${\mathcal {B}}(A)$

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

$\operatorname {d} _{P}(x):=\inf _{y\in P}\,\|y-x\|,$

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

Lemme de Hoffman — Il existe une constante $h$ (ne dépendant que de $A$ , de $\|\cdot \|$ et d'une norme $\|\cdot \|'$ sur $\mathbb {R} ^{m}$ ) telle que

$\forall \,b\in {\mathcal {B}}(A),~~\forall \,x\in \mathbb {R} ^{n}:\quad \operatorname {d} _{P}(x)\leqslant h\,\|(Ax-b)^{+}\|'.$

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 $\varepsilon >0$ , on définit
$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 $h\to \infty$ lorsque $\varepsilon \downarrow 0$ .
La meilleure constante $h$ est étudiée par Azé et Corvellec (2002).

Annexes

Autres contributions

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

Note

↑ Voir par exemple l'article de O. Guler, 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.

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

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

[1] Voir par exemple l'article de O. Guler, 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.

[1]