Borne d'erreur

Dans la première famille, l'ensemble ${\displaystyle P}$ est l'image réciproque par une application ${\displaystyle c:\mathbb {E} \to \mathbb {F} }$, une contrainte, d'une partie ${\displaystyle Q}$ d'un autre espace métrique ${\displaystyle (\mathbb {F} ,\operatorname {d} )}$ (même notation pour les métriques de ${\displaystyle \mathbb {E} }$ et ${\displaystyle \mathbb {F} }$), ce qui s'écrit

En général, ${\displaystyle Q}$ est « plus simple » que ${\displaystyle P}$. Alors, on aimerait pouvoir prendre

où ${\displaystyle \beta }$ est une constante positive indépendante de ${\displaystyle x}$. Cette fonction ${\displaystyle \varphi }$ est en effet souvent plus facilement calculable que ${\displaystyle \operatorname {d} _{P}}$, en tout cas si l'on peut évaluer ${\displaystyle c(x)}$ et si la distance à ${\displaystyle Q}$ se calcule plus facilement que la distance à ${\displaystyle P}$. La borne d'erreur de Hoffman et les bornes d'erreur de Robinson obéissent à ce modèle.

La première borne d'erreur non triviale a été obtenue pour la distance à un polyèdre convexe. On suppose donc donné 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 ${\displaystyle {\mathcal {B}}(A)}$ le cône convexe 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 cherche à estimer la distance de ${\displaystyle x}$ à ${\displaystyle P}$, qui est définie par

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})}$. On introduit également une norme ${\displaystyle \|\cdot \|'}$ sur ${\displaystyle \mathbb {R} ^{m}}$.

En 1952, Hoffman a démontré le résultat suivant.

Si l'ensemble considéré est donné par

où ${\displaystyle c:\mathbb {R} ^{n}\to \mathbb {R} ^{m}}$ est ${\displaystyle \mathbb {R} _{+}^{m}}$-convexe, en général, on ne peut pas avoir une borne d'erreur du type de celle de Hoffman, c'est-à-dire

sans hypothèses supplémentaires. Des contre-exemples sont donnés par Lewis et Pang (1997^[2]), mais on peut aussi considérer le cas du singleton ${\displaystyle P:=\{x\in \mathbb {R} ^{2}:c_{1}(x)\leqslant 0}$, ${\displaystyle c_{2}(x)\leqslant 0\}}$, avec ${\displaystyle c_{1}(x)=(x_{1}-1)^{2}+x_{2}^{2}-1}$ et ${\displaystyle c_{2}(x)=(x_{1}+1)^{2}+x_{2}^{2}-1}$, qui est l'intersection de deux disques tangents extérieurement. L'estimation ci-dessus ne peut avoir lieu en des points de la forme ${\displaystyle x_{t}=(0,t)}$, car ${\displaystyle \operatorname {d} _{P}(x_{t})=|t|}$ et ${\displaystyle \|c(x_{t})^{+}\|_{2}={\sqrt {2}}t^{2}}$, si bien qu'il faudrait trouver un ${\displaystyle \beta >0}$ tel que ${\displaystyle |t|\leqslant {\sqrt {2}}\beta t^{2}}$, ce qui ne peut pas avoir lieu pour des ${\displaystyle |t|}$ arbitrairement petits.

Il s'avère donc nécessaire d'avoir une hypothèse de qualification de contraintes pour avoir une borne d'erreur linéaire, c'est-à-dire de la forme ci-dessus, ou de prendre une borne d'erreur non linéaire, de la forme ${\displaystyle \beta \,\|c(x)^{+}\|^{\alpha }}$, avec un ${\displaystyle \alpha >0}$.

La borne d'erreur de Robinson (1975^[3]) concerne un ensemble convexe défini par des contraintes (ou fonctions) convexes et satisfaisant une condition de Slater. Le cadre est très général, en particulier, la dimension des espaces vectoriels n'est pas supposée finie.

De manière plus précise, on suppose donnés deux espaces normés ${\displaystyle \mathbb {E} }$ et ${\displaystyle \mathbb {F} }$, dont les normes sont toutes les deux notées ${\displaystyle \|\cdot \|}$, un ensemble convexe ${\displaystyle C\subset \mathbb {E} }$, un cône convexe fermé non vide ${\displaystyle K\subset \mathbb {F} }$ et une fonction ${\displaystyle K}$-convexe ${\displaystyle c:C\to \mathbb {F} }$. On s'intéresse à une borne d'erreur pour l'ensemble

On suppose que ${\displaystyle P}$ satisfait la condition de Slater suivante :

où ${\displaystyle B_{\mathbb {F} }}$ est la boule unité fermée de ${\displaystyle \mathbb {F} }$. La borne d'erreur de Robinson majore la distance ${\displaystyle \operatorname {d} _{P}(x)}$ d'un point ${\displaystyle x\in C}$ à ${\displaystyle P}$ dans l'espace ${\displaystyle \mathbb {E} }$ par un multiple de la distance

de ${\displaystyle c(x)}$ à ${\displaystyle -K}$ dans l'espace ${\displaystyle \mathbb {F} }$.

La première borne d'erreur de Robinson ne fait intervenir ${\displaystyle C}$ dans la définition de ${\displaystyle P}$, ni par la distance de ${\displaystyle c(x)}$ à ${\displaystyle -K}$, ni par le rayon ${\displaystyle \rho }$, mais par l'intermédiaire du point de Slater ${\displaystyle {\check {x}}}$. Dans la seconde borne d'erreur, c'est le diamètre ${\displaystyle \Delta }$ qui prend en compte la présence de ${\displaystyle C}$ dans ${\displaystyle P}$. Un intérêt de la seconde borne d'erreur est de ne plus faire intervenir le point de Slater ${\displaystyle {\check {x}}}$.

Ces bornes d'erreur ont été étendues au cas d'ensembles non convexes (voir ci-dessous).

Voir Guoyin Li (2013^[4]).

Voir Auslender et Crouzeix (1988^[5]). Extension à un Banach réflexif par S. Deng (1997^[6]).

Voir S. Deng et H. Hu (1999^[7]), Azé et Hiriart-Urruty (2002^[8]).

Le cadre est le suivant. On suppose que ${\displaystyle \mathbb {E} }$ et ${\displaystyle \mathbb {F} }$ sont deux espaces de Banach, que ${\displaystyle c:\mathbb {E} \to \mathbb {F} }$ est une fonction Fréchet différentiable et que ${\displaystyle C}$ un convexe fermé non vide de ${\displaystyle \mathbb {F} }$. On s'intéresse à une borne d'erreur pour l'ensemble (non nécessairement convexe) suivant

La condition de qualification de Robinson en ${\displaystyle x\in P}$ s'écrit

où ${\displaystyle \operatorname {int} }$ est l'opérateur prenant l'intérieur. On note ci-dessous ${\displaystyle \operatorname {d} _{P}(x)}$ la distance de ${\displaystyle x}$ à ${\displaystyle P}$ et ${\displaystyle \operatorname {d} _{C}(c(x))}$ la distance de ${\displaystyle c(x)}$ à ${\displaystyle C}$.

Cette borne d'erreur est locale (estimation de la distance pour ${\displaystyle x'}$ voisin de ${\displaystyle x}$), du fait de la non convexité potentielle de l'ensemble ${\displaystyle P.}$

Une autre famille de bornes d'erreur concerne l'ensemble de sous-niveau d'une fonction ${\displaystyle f:\mathbb {E} \to \mathbb {R} \cup \{+\infty \}}$. Sans perte de généralité, on peut supposer qu'il s'agit de l'ensemble sous le niveau zéro :

Le fait que ${\displaystyle f}$ puisse prendre des valeurs infinies permet de prendre en compte la contrainte implicite ${\displaystyle x\in \operatorname {dom} f:=\{x\in \mathbb {E} :f(x)<+\infty \}}$ (le domaine effectif de ${\displaystyle f}$). Il est alors courant d'obtenir des bornes d'erreur de la forme ${\displaystyle \operatorname {d} _{P}(x)\leqslant \varphi (x)}$ avec

où ${\displaystyle \alpha }$ et ${\displaystyle \beta }$ sont des constantes positives indépendantes de ${\displaystyle x}$. Cette seconde famille peut être considérée comme un cas particulier de la première dans laquelle la contrainte est la fonction scalaire ${\displaystyle f}$ et l'ensemble ${\displaystyle Q}$ est l'intervalle ${\displaystyle \mathbb {R} _{-}:={]-\infty ,0]}}$.

Un cas particulier de cette famille est celui où ${\displaystyle P}$ est l'ensemble formé par les solutions d'un problème d'optimisation :

où ${\displaystyle f:\mathbb {E} \to \mathbb {R} \cup \{+\infty \}}$.

On pourra consulter les livres de Zalinescu (2002) et de Auslender et Teboulle (2003), ainsi que les articles de synthèse de Pang (1997) et de Lewis et Pang (1998).

• Lemme de Hoffman

• (en) A. Auslender, M. Teboulle (2003). Asymptotic Cones and Functions in Optimization and Variational Inequalities. Springer Monographs in Mathematics. Springer, New York.
• (en) A. S. Lewis, J. S. Pang (1998). Error bounds for convex inequality systems generalized convexity, generalized monotonicity. In: Crouzeix, J.P., Martinez-Legaz, J.E., Volle, M. (eds.), p. 75–110.
• (en) J. S. Pang (1997). Error bounds in mathematical programming. Mathematical Programming, 79, 299–332.
• (en) S.M. Robinson (1976). Stability theory for systems of inequalities, part II: differentiable nonlinear systems. SIAM Journal on Numerical Analysis, 13, 497-513.
• (en) C. Zalinescu (2002). Convex Analysis in General Vector Spaces. World Scientific, Singapore.

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