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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

Autres contributions[modifier | modifier le code]

(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[modifier | modifier le code]

↑ 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[modifier | modifier le code]

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[modifier | modifier le code]

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