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 formé de l'unique solution du système linéaire est un opérateur linéaire inversible entre deux espaces normés. Pour un point quelconque, on a , si bien que

On peut donc estimer la distance de à par la norme du résidu , souvent plus simple à calculer que la distance 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éfinitionsModifier

Soient   un espace métrique et   une partie de  . Une borne d'erreur pour   est une affirmation de la forme

 

dans laquelle

 

est la distance de   à   et la fonction   est « plus facile à évaluer que »  . Si cette dernière expression est un souhait un peu vague (voir ci-dessous), on requiert en général que   vérifie d'autres propriétés précises, telles que

  •   si, et seulement si,  ,
  •   est continue dans un voisinage de  .

Une borne d'erreur peut être globale, comme dans la définition ci-dessus, ou locale si l'estimation   n'est vérifiée que pour   voisin de   ou voisin d'un point spécifié de  .

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

Images réciproquesModifier

Dans la première famille, l'ensemble   est l'image réciproque par une application  , une contrainte, d'une partie   d'un autre espace métrique   (même notation pour les métriques de   et  ), ce qui s'écrit

 

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

 

  est une constante positive indépendante de  . Cette fonction   est en effet souvent plus facilement calculable que  , en tout cas si l'on peut évaluer   et si la distance à   se calcule plus facilement que la distance à  . La borne d'erreur de Hoffman et les bornes d'erreur de Robinson obéissent à ce modèle.

Contraintes affinesModifier

Sous-espace affineModifier

Demi-espace affineModifier

Polyèdre convexeModifier

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   de  , écrit sous la forme suivante

 

  est une matrice réelle et  . On note   le cône convexe des vecteurs   tels que  . Pour une norme   sur   (pas nécessairement la norme euclidienne), on cherche à estimer la distance de   à  , qui est définie par

 

Pour  , on note   le vecteur de   dont la composante   est  . On introduit également une norme   sur  .

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

Lemme de Hoffman — Il existe une constante   (ne dépendant que de  , de   et de  ) telle que

 

Contraintes convexesModifier

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

 

  est  -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  ,  , avec   et  , qui est l'intersection de deux disques tangents extérieurement. L'estimation ci-dessus ne peut avoir lieu en des points de la forme  , car   et  , si bien qu'il faudrait trouver un   tel que  , ce qui ne peut pas avoir lieu pour des   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  , avec un  .

Contraintes quadratiques convexesModifier

Bornes d'erreur de RobinsonModifier

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   et  , dont les normes sont toutes les deux notées  , un ensemble convexe  , un cône convexe fermé non vide   et une fonction  -convexe  . On s'intéresse à une borne d'erreur pour l'ensemble

 

On suppose que   satisfait la condition de Slater suivante :

 

  est la boule unité fermée de  . La borne d'erreur de Robinson majore la distance   d'un point   à   dans l'espace   par un multiple de la distance

 

de   à   dans l'espace  .

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

 

Si, de plus,   est borné de diamètre  , alors

 

La première borne d'erreur de Robinson ne fait intervenir   dans la définition de  , ni par la distance de   à  , ni par le rayon  , mais par l'intermédiaire du point de Slater  . Dans la seconde borne d'erreur, c'est le diamètre   qui prend en compte la présence de   dans  . Un intérêt de la seconde borne d'erreur est de ne plus faire intervenir le point de Slater  .

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

Contraintes algébriques convexesModifier

Voir Guoyin Li (2013[4]).

Autres bornes d'erreurModifier

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

Contraintes SDPModifier

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

Contraintes non convexesModifier

Borne d'erreur de RobinsonModifier

Le cadre est le suivant. On suppose que   et   sont deux espaces de Banach, que   est une fonction Fréchet différentiable et que   un convexe fermé non vide de  . On s'intéresse à une borne d'erreur pour l'ensemble (non nécessairement convexe) suivant

 

La condition de qualification de Robinson en   s'écrit

 

  est l'opérateur prenant l'intérieur. On note ci-dessous   la distance de   à   et   la distance de   à  .

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

 

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

Ensembles de sous-niveauModifier

Une autre famille de bornes d'erreur concerne l'ensemble de sous-niveau d'une fonction  . Sans perte de généralité, on peut supposer qu'il s'agit de l'ensemble sous le niveau zéro :

 

Le fait que   puisse prendre des valeurs infinies permet de prendre en compte la contrainte implicite   (le domaine effectif de  ). Il est alors courant d'obtenir des bornes d'erreur de la forme   avec

 

  et   sont des constantes positives indépendantes de  . Cette seconde famille peut être considérée comme un cas particulier de la première dans laquelle la contrainte est la fonction scalaire   et l'ensemble   est l'intervalle  .

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

 

 .

AnnexesModifier

État de l'artModifier

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

NotesModifier

  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 » (no 27), , 75–110 p.
  3. (en) S. M. Robinson, « An application of error bounds for convex programming in a linear space », SIAM Journal on Control, no 13,‎ , 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, no 13,‎ , p. 243–253.
  6. (en) S. Deng, « Computable error bounds for convex inequality systems in reflexive Banach spaces », SIAM Journal on Optimization, no 7,‎ , p. 274–279.
  7. (en) S. Deng et H. Hu, « Computable error bounds for semidefinite programming », Journal of Global Optimization, no 14,‎ , 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, no 24,‎ , p. 133–147.
  9. Robinson (1976)

Article connexeModifier

BibliographieModifier

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