Borne d'erreur

En mathématiques, et plus précisément en analyse et en analyse convexe, une borne d'erreur^[1] est une estimation (le plus souvent une majoration) de la distance à un ensemble par des quantités plus aisément calculables que la distance elle-même (numériquement, celle-ci requiert la résolution d'un problème d'optimisation). Une des premières bornes d'erreur non triviales obtenues concerne la distance à un polyèdre convexe : c'est le lemme de Hoffman, qui date de 1952. Cette estimation a ensuite été généralisée à beaucoup d'autres ensembles.

La borne d'erreur simplissime suivante donnera une première idée de ce que sont ces estimations. Elle concerne l'ensemble singleton $P:=\{{\bar {x}}\}$ formé de l'unique solution ${\bar {x}}$ du système linéaire $Ax=b$ où $A$ est un opérateur linéaire inversible entre deux espaces normés. Pour un point $x$ quelconque, on a $x-{\bar {x}}=A^{-1}(Ax-b)$ , si bien que

$\operatorname {d} _{P}(x)\leqslant \|A^{-1}\|\,\|Ax-b\|.$

On peut donc estimer la distance $\operatorname {d} _{P}(x)$ de $x$ à $P$ par la norme du résidu $\|Ax-b\|$ , souvent plus simple à calculer que la distance $\operatorname {d} _{P}(x)$ puisqu'elle ne requiert pas la connaissance de la solution du système linéaire.

Les bornes d'erreur sont utiles théoriquement (par exemple, pour établir la convergence d'algorithmes d'optimisation, pour établir le conditionnement et la stabilité lipschitzienne d'ensembles) ou numériquement (par exemple, comme test d'arrêt dans des algorithmes d'optimisation). Les bornes d'erreur sont aussi apparentées aux notions de régularité métrique et de minimum saillant en optimisation. Leur écriture requiert une notion de qualification de contraintes qui peut être différente de celle utilisée pour l'obtention des conditions d'optimalité en optimisation.

Cet article fait le point sur les bornes d'erreur les plus connues et renvoie aux articles spécialisés (de Wikipédia ou de revue) pour plus de détails.

Définitions[modifier | modifier le code]

Soient $(\mathbb {E} ,\operatorname {d} )$ un espace métrique et $P$ une partie de $\mathbb {E}$ . Une borne d'erreur pour $P$ est une affirmation de la forme

$\forall \,x\in \mathbb {E} :\quad \operatorname {d} _{P}(x)\leqslant \varphi (x),$

dans laquelle

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

est la distance de $x$ à $P$ et la fonction $\varphi :\mathbb {E} \to \mathbb {R}$ est « plus facile à évaluer que » $\operatorname {d} _{P}$ . Si cette dernière expression est un souhait un peu vague (voir ci-dessous), on requiert en général que $\varphi$ vérifie d'autres propriétés précises, telles que

$\varphi (x)=0$ si, et seulement si, $\operatorname {d} _{P}(x)=0$ ,
$\varphi$ est continue dans un voisinage de $P$ .

Une borne d'erreur peut être globale, comme dans la définition ci-dessus, ou locale si l'estimation $\operatorname {d} _{P}(x)\leqslant \varphi (x)$ n'est vérifiée que pour $x$ voisin de $P$ ou voisin d'un point spécifié de $P$ .

La plupart des bornes d'erreur peuvent se rassembler en deux familles, que nous décrivons ci-après, celle où $P$ est l'image réciproque d'un ensemble simple et celle où $P$ est un ensemble de sous-niveau d'une fonction à valeurs dans ${\bar {\mathbb {R} }}$ (cas particulier du précédent dans lequel l'image réciproque est associée à une fonction à valeurs dans $\mathbb {R}$ et où l'ensemble simple est un intervalle $[\nu ,+\infty [$ ). Nous verrons dans chaque cas ce que l'on entend par une fonction $\varphi$ « plus facile à évaluer que » $\operatorname {d} _{P}$ .

Images réciproques[modifier | modifier le code]

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

$P:=c^{-1}(Q).$

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

$\varphi (x)=\beta \,\operatorname {d} _{Q}(c(x)),$

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

Contraintes affines[modifier | modifier le code]

Sous-espace affine[modifier | modifier le code]

Demi-espace affine[modifier | modifier le code]

Polyèdre convexe[modifier | modifier le code]

Article détaillé : Lemme de Hoffman.

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 $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)$ le cône convexe 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 cherche à estimer la distance de $x$ à $P$ , qui est définie par

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

Pour $v\in \mathbb {R} ^{m}$ , on note $v^{+}$ le vecteur de $\mathbb {R} ^{m}$ dont la composante $i$ est $\max(0,v_{i})$ . On introduit également une norme $\|\cdot \|'$ sur $\mathbb {R} ^{m}$ .

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

Lemme de Hoffman — Il existe une constante $h$ (ne dépendant que de $A$ , de $\|\cdot \|$ et de $\|\cdot \|'$ ) telle que

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

Contraintes convexes[modifier | modifier le code]

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

$P:=\{x\in \mathbb {R} ^{n}:c(x)\leqslant 0\},$

où $c:\mathbb {R} ^{n}\to \mathbb {R} ^{m}$ est $\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

$\exists \,\beta >0,\quad \forall \,x\in P:\qquad \operatorname {d} _{P}(x)\leqslant \beta \,\|c(x)^{+}\|,$

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 $P:=\{x\in \mathbb {R} ^{2}:c_{1}(x)\leqslant 0$ , $c_{2}(x)\leqslant 0\}$ , avec $c_{1}(x)=(x_{1}-1)^{2}+x_{2}^{2}-1$ et $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 $x_{t}=(0,t)$ , car $\operatorname {d} _{P}(x_{t})=|t|$ et $\|c(x_{t})^{+}\|_{2}={\sqrt {2}}t^{2}$ , si bien qu'il faudrait trouver un $\beta >0$ tel que $|t|\leqslant {\sqrt {2}}\beta t^{2}$ , ce qui ne peut pas avoir lieu pour des $|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 $\beta \,\|c(x)^{+}\|^{\alpha }$ , avec un $\alpha >0$ .

Contraintes quadratiques convexes[modifier | modifier le code]

Bornes d'erreur de Robinson[modifier | modifier le code]

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 $\mathbb {E}$ et $\mathbb {F}$ , dont les normes sont toutes les deux notées $\|\cdot \|$ , un ensemble convexe $C\subset \mathbb {E}$ , un cône convexe fermé non vide $K\subset \mathbb {F}$ et une fonction $K$ -convexe $c:C\to \mathbb {F}$ . On s'intéresse à une borne d'erreur pour l'ensemble

$P:=\{x\in C:c(x)\in -K\}=C\cap \left(c^{-1}(-K)\right).$

On suppose que $P$ satisfait la condition de Slater suivante :

$\exists \,{\check {x}}\in P,\quad \exists \,\rho >0:\quad c({\check {x}})+\rho B_{\mathbb {F} }\in -K,$

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

$\delta _{x}:=\operatorname {d} _{(-K)}c(x)$

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

Bornes d'erreur de Robinson — Dans les conditions et avec les notations ci-dessus, on a

$\forall \,x\in C:\qquad \operatorname {d} _{P}(x)\leqslant \left({\frac {\delta _{x}}{\delta _{x}+\rho }}\right)\|x-{\check {x}}\|\leqslant {\frac {\|x-{\check {x}}\|}{\rho }}\,\delta _{x}.$

Si, de plus, $P$ est borné de diamètre $\Delta$ , alors

$\forall \,x\in C:\qquad \operatorname {d} _{P}(x)\leqslant {\frac {\Delta }{\rho }}\,\delta _{x}.$

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

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

Contraintes algébriques convexes[modifier | modifier le code]

Voir Guoyin Li (2013^[4]).

Autres bornes d'erreur[modifier | modifier le code]

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

Contraintes SDP[modifier | modifier le code]

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

Contraintes non convexes[modifier | modifier le code]

Borne d'erreur de Robinson[modifier | modifier le code]

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

P:=\{x\in \mathbb {E} :c(x)\in C\}=c^{-1}(C).

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

({\mbox{QC-R}})\qquad 0\in \operatorname {int} \{c(x)+c'(x)\mathbb {E} -C\},

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

Borne d'erreur de Robinson^[9] — Si la condition de qualification de Robinson (QC-R) a lieu en $x\in P$ , alors il existe une constante positive $\rho$ , telle que pour tout $x'$ voisin de $x$ , on a

\operatorname {d} _{P}(x')\leqslant \rho \,\operatorname {d} _{C}{\bigl (}c(x'){\bigr )}.

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

Ensembles de sous-niveau[modifier | modifier le code]

Une autre famille de bornes d'erreur concerne l'ensemble de sous-niveau d'une fonction $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 :

$P:=\{x\in \mathbb {E} :f(x)\leqslant 0\}.$

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

$\varphi (x)=\beta \,(f(x)^{+})^{\alpha },$

où $\alpha$ et $\beta$ sont des constantes positives indépendantes de $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 $f$ et l'ensemble $Q$ est l'intervalle $\mathbb {R} _{-}:={]-\infty ,0]}$ .

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

P:=\operatorname {*} {arg\,min}_{x\in \mathbb {E} }\,f(x),

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

Annexes[modifier | modifier le code]

État de l'art[modifier | modifier le code]

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

Notes[modifier | modifier le code]

↑ Error bound en anglais.
↑ (en) A.S. Lewis et J.-S. Pang, « Error bounds for convex inequality systems », dans Generalized convexity, generalized monotonicity: recent results, Kluwer Academic Publishers, Dordrecht, coll. « Nonconvex Optimization and its Applications » (n^o 27), 1998, 75–110 p.
↑ (en) S. M. Robinson, « An application of error bounds for convex programming in a linear space », SIAM Journal on Control, n^o 13,‎ 1975, p. 271–273.
↑ (en) Guoyin Li (2013). Global error bounds for piecewise convex polynomials. Mathematical Programming.
↑ (en) A. Auslender et J.-P. Crouzeix, « Global regularity theorems », Mathematics of Operations Research, n^o 13,‎ 1988, p. 243–253.
↑ (en) S. Deng, « Computable error bounds for convex inequality systems in reflexive Banach spaces », SIAM Journal on Optimization, n^o 7,‎ 1997, p. 274–279.
↑ (en) S. Deng et H. Hu, « Computable error bounds for semidefinite programming », Journal of Global Optimization, n^o 14,‎ 1999, p. 105-115.
↑ (en) D. Azé et J.-B. Hiriart-Urruty, « Optimal Hoffman-type estimates in eigenvalue and semidefinite inequality constraints », Journal of Global Optimization, n^o 24,‎ 2002, p. 133–147.
↑ Robinson (1976)

Article connexe[modifier | modifier le code]

Lemme de Hoffman

Bibliographie[modifier | modifier le code]

(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.), pp. 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.

[1] Error bound en anglais.

[2] (en) A.S. Lewis et J.-S. Pang, « Error bounds for convex inequality systems », dans Generalized convexity, generalized monotonicity: recent results, Kluwer Academic Publishers, Dordrecht, coll. « Nonconvex Optimization and its Applications » (n^o 27), 1998, 75–110 p.

[3] (en) S. M. Robinson, « An application of error bounds for convex programming in a linear space », SIAM Journal on Control, n^o 13,‎ 1975, p. 271–273.

[4] (en) Guoyin Li (2013). Global error bounds for piecewise convex polynomials. Mathematical Programming.

[5] (en) A. Auslender et J.-P. Crouzeix, « Global regularity theorems », Mathematics of Operations Research, n^o 13,‎ 1988, p. 243–253.

[6] (en) S. Deng, « Computable error bounds for convex inequality systems in reflexive Banach spaces », SIAM Journal on Optimization, n^o 7,‎ 1997, p. 274–279.

[7] (en) S. Deng et H. Hu, « Computable error bounds for semidefinite programming », Journal of Global Optimization, n^o 14,‎ 1999, p. 105-115.

[8] (en) D. Azé et J.-B. Hiriart-Urruty, « Optimal Hoffman-type estimates in eigenvalue and semidefinite inequality constraints », Journal of Global Optimization, n^o 24,‎ 2002, p. 133–147.

[9] Robinson (1976)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]