Ouvrir le menu principal

L'optimisation robuste est une branche de l'optimisation mathématique qui cherche à résoudre un problème d'optimisation en prenant en compte les différentes sources d'incertitude de celui-ci.

Sommaire

HistoireModifier

Les origines de l'optimisation robuste remontent aux débuts de la théorie de la décision moderne dans les années 1950. Des « analyses des cas les plus défavorables » ont été réalisées pour faire face aux fortes incertitudes. L'optimisation robuste devient dans les années 1970 une discipline à elle-seule avec des applications dans des domaines tels que la recherche opérationnelle[1], la théorie du contrôle[2], les statistiques, l'économie

ExempleModifier

Considérons le problème de type optimisation linéaire suivant :

 

  est un sous-ensemble de  .

La ligne   fait de ce programme linéaire un problème d'optimisation robuste. En effet, pour qu'une solution   soit réalisable, la contrainte   doit être satisfaite par la pire paire  , c'est-à-dire la paire   qui maximise la valeur de   pour la valeur donnée de  .

Si l'espace de paramètre   est fini (composé d'un nombre fini d'éléments), alors le problème d'optimisation robuste est lui-même un problème d'optimisation linéaire : pour chaque   il existe une contrainte linéaire.

Si l'espace de paramètre   n'est pas fini, alors ce problème est un problème de programmation linéaire semi-infinie (en), c'est-à-dire un problème de programmation linéaire avec un nombre fini de variables de décision et un nombre infini de contraintes.

ClassificationModifier

Il existe de nombreux critères de classification des problèmes/modèles d'optimisation robuste. En particulier, on peut faire la distinction entre les problèmes traitant de modèles robustes locaux ou globaux, et entre les modèles robustes probabilistes et non-probabilistes. L'optimisation robuste moderne traite d'abord de modèles robustes non-probabilistes qui cherchent à résoudre le pire des cas.

Robustesse localeModifier

Il existe des cas dans lesquels la robustesse travaille sur de petites perturbations sur une valeur nominale d'un paramètre. Un modèle populaire de robustesse locale est le modèle du rayon de stabilité :

 

  représente la valeur nominale du paramètre,   représente une boule de rayon   centrée en   et   représente l'ensemble des valeurs de   qui satisfont le problème dans les conditions de stabilité et de performance associées à la décision  .

Robustesse globaleModifier

Soit le problème d'optimisation présenté ci-dessous :

 

dans lequel  désigne l'ensemble des valeurs possibles de  .

Ce problème est un problème d'optimisation robuste globale dans le sens où la contrainte de robustesse   représente toutes les valeurs possibles de  .

La difficulté est qu'une telle contrainte globale peut être trop contraignante dans le sens où il n'y a pas de   qui satisfasse cette contrainte. Mais même si un tel   existe, la contrainte peut être trop "conservatrice" dans le sens où une solution   génère un très petit objectif   qui n'est pas représentatif de la performance des autres décisions dans  . Par exemple, il pourrait y avoir un   qui ne viole que légèrement la contrainte de robustesse, mais qui donne un très bon objectif  . Dans de tels cas, il peut être nécessaire de relâcher un peu la contrainte de robustesse et/ou de modifier l'énoncé du problème.

ExempleModifier

Considérons le cas où l'objectif est de satisfaire la contrainte  , où   représente la variable de décision et   est un paramètre dont l'ensemble des valeurs possibles est dans  . S'il n'existe pas de   tel que  , alors la mesure de robustesse suivante est intuitive :

 

  est une mesure appropriée de la "taille" de l'ensemble  . Par exemple, si   est un ensemble fini, alors   peut être défini par la cardinalité de l'ensemble  .

En bref, la robustesse d'une décision est la taille du plus grand sous-ensemble de   pour lequel la contrainte   est satisfaite pour chaque   dans cet ensemble. Une décision optimale est alors une décision dont la robustesse est la plus importante.

On en déduit le problème d'optimisation robuste suivant :

 

Cette notion intuitive de robustesse globale n'est pas souvent utilisée en pratique. En effet, les problèmes d'optimisation robuste qu'elle induit sont souvent (mais pas toujours) très difficiles à résoudre.

Notes et référencesModifier

  1. (en) Dimitris Bertsimas et Melvin Sim, « The Price of Robustness », Operations Research, vol. 52, no 1,‎ , p. 35-53
  2. (en) P.P. Khargonekar, I.R. Petersen et K. Zhou, « Robust stabilization of uncertain linear systems : quadratic stabilizability and H/sup infinity/control theory », IEEE Transactions on Automatic Control, vol. 35, no 3,‎ , p. 356–361

AnnexesModifier

Liens externesModifier

BibliographieModifier