Optimisation dans l’incertain et structure d’information

Optimisation dans l’incertain et structure d’information

 Optimisation et incertain

Les problèmes d’optimisation dans l’incertain sont caractérisés par la nécessité de prendre des décisions sans savoir précisément qu’elles seront leurs conséquences. De tels problèmes apparaissent dans différents domaines d’application et soulèvent des questions aussi bien théoriques que pratiques. Commen¸cons par définir la terminologie employée. Optimisation : nous faisons référence à l’étude d’un problème et de sa solution, dans lequel nous devons faire un choix admissible. Les décisions admissibles sont modélisées comme les éléments d’un ensemble admissible. Le but est de trouver le “meilleur” choix (pas nécessairement unique). Les choix possibles sont comparés en fonction de la valeur que leur attribue une certaine fonction, le critère. Incertain : le terme fait référence au fait que les données entrant en jeu dans le problème d’optimisation peuvent éventuellement être aléatoires.

Scénarios et structure d’information

Supposons que l’on souhaite minimiser un critère économique déterminé par l’application J : R m × Ξ → R, et que ce critère dépende d’événements qui ne seront connus que progressivement. Nous dirons qu’une suite d’événements possibles est un scénario et, pour fixer les idées, ξ désignera un scénario. Par ailleurs supposons également que, même si les événements n’ont pas encore eu lieu, il faut quand même prendre une décision. Il n’est pas raisonnable de minimiser pour tous les scénarios ξ possibles la fonction x 7→ J(x, ξ). En effet, supposons que les événements possibles se résument à une succession de + et de −. Considérons les scénarios suivants ξ1 = + + + + +, ξ2 = +− − − − et ξ3 = +−+−+. Si à l’étape 1 du processus on observe +, comment déterminer s’il faut appliquer la décision associée à ξ1, celle associée à ξ2, ou celle associée à ξ3. Si l’interprétation du signe + est 1 Optimisation dans l’incertain et structure d’information 2 Compte rendu de la littera ´ ture I.1 “abondance” et celle du signe − est “pénurie”, alors les décisions associées au premier événement des scénarios ξ1 et ξ2 peuvent être très différentes : il est légitime de penser qu’on ne ferait pas la même chose selon que l’on se prépare une période de pénurie ou une période d’abondance. C’est la raison pour laquelle le critère d’un problème d’optimisation stochastique classique est généralement la valeur moyenne des couts ˆ associés à tous les scénarios possibles. Les décisions sont supposées être prises sur la base de l’observation d’événements passés : cette contrainte se traduit mathématiquement par une contrainte de mesurabilité sur les variables de décision. Plus généralement, nous parlerons de structure d’information pour faire référence aux contraintes de mesurabilité auxquelles sont assujetties les variables de décision. 

Arbres de scénarios

La résolution des problèmes d’optimisation stochastique est difficile pour deux raisons : 1. d’une part il faut calculer les espérances de fonctions aléatoires relativement des lois continues, ou des lois dicrètes sur un grand nombre d’atomes; 2. d’autre part il faut discrétiser les contraintes de mesurabilité du problème d’origine. Une approche classique pour tenir compte de ces deux contraintes repose sur la technique des arbres de scénarios. L’idée est la suivante : on commence par se donner un nombre fini de scénarios, leur rˆole étant de permettre l’évaluation du critère, puis on organise ces scénarios en arbre,1 l’idée sous-jacente étant qu’un arbre est l’approximation naturelle d’une filtration2 . Ce faisant, la discrétisation du critère et de la structure d’information est réalisée avec l’aide de l’unique structure qu’est l’arbre de scénarios. Cette technique réalise donc un compromis entre la discrétisation de la structure d’information et celle du cout.   Il n’existe pas notre connaissance de moyen permettant de distinguer la contribution de l’arbre de scénarios la discrétisation du cout ˆ de celle allouée la discrétisation de la structure d’information. Ce manque de clarté concernant l’apport de l’arbre de scénarios l’une ou l’autre des discrétisations peut expliquer les difficultés rencontrées lorsque l’on souhaite juger de la qualité d’un arbre de scénarios. En fait il paraˆıt difficile de mesurer directement la qualité de l’arbre de scénarios, étant donné qu’il cherche réaliser un compromis entre deux problèmes très différents : un problème de nature numérique, “approcher des lois de probabilité” et un problème de nature algébrique, “approcher des σ-algèbres”. Compte tenu des difficultés liées l’évaluation de ces phénomènes, les questions liées la qualité de l’arbre des scénarios ne trouvent pas dans la littérature de réponses directes. Le problème est contourné en considérant qu’un “bon arbre de scénarios” est une structure permettant d’obtenir une bonne approximation du cout ˆ optimal3 [60] : ce point de vue a l’inconvénient de limiter la possibilité d’obtenir des résultats généraux sur la manière d’obtenir des arbres 1Un arbre est simplement une filtration discrète ou bien associée à un processus discret. 2Une filtration est une suite croissante de sous-tribus. 3Le critère de qualité aurait pu porter sur la qualité des contrˆoles calculés, mais cela ne donne pas un instrument de mesure “univoque” étant donné que l’unicité des solutions n’est pas garantie en général. I.2 Les categories ´ de problemes ` 3 de scénarios, étant donné que la qualité de l’arbre est directement liée aux propriétés du problème étudié. 

Les catégories de problèmes

Nous étudierons dans ce mémoire la discrétisation des contraintes de mesurabilité dans un problème d’optimisation stochastique, c’est la raison pour laquelle il nous parait nécessaire de déterminer précisément les différentes catégories de structure d’information, ce qui nous permettra de classer chaque problème d’optimisation dans une catégorie en fonction de sa contrainte de mesurabilité

Boucle ouverte

Les problèmes d’optimisation en boucle ouverte sont les problèmes de la forme : min x∈Rn E[J(x, ξ(ω))] . (I.1) La variable de décision x ∈ R n est prise avant l’observation d’une quelconque variable aléatoire. Ce type de problème est largement étudié [97, 98], et bien qu’en apparence très simple, il ne peut pas être abordé par des techniques classiques d’optimisation non linéaire. La difficulté principale de ce type de problème est liée l’évaluation de E[J(x, ξ(ω))] ou d’un (sous) gradient. Il existe cependant quelques cas favorables (notamment lorsque la loi de ξ est discrète) le calcul de l’espérance se résume alors une simple somme : E[J(x, ξ(ω))] = X N i=1 piJ(x, ξi). Dans ce cas, évaluer l’espérance ou le gradient du critère consiste simplement évaluer J(x, ξi) ou J 0 x (x, ξi) pour tout i. Cette constatation est la base des techniques dite de chroniques de scénarios qui consistent remplacer la variable aléatoire ξ par une loi discrète sur un nombre fini de scénarios dans le but d’obtenir un problème discret plus facile résoudre. Cette approche soulève le problème du nombre de scénarios nécessaires afin de respecter une marge d’erreur fixée a priori [96, 95]. Parmi les différents angles d’approche du problème (I.1), il faut également citer celles de type gradient stochastique [76] qui sont basées sur l’idée de mener conjointement et progressivement la minimisation du critère et le calcul de l’espérance. Les problèmes en boucle ouverte pouvant être de grande taille, les techniques de décomposition [27] sont naturellement un aspect important. 

Structure d’information statique

Les problèmes statiques sont ceux dont la particularité est de posséder une structure d’information indépendante de toute loi de commande. Nous dirons des problèmes statiques 4 Compte rendu de la littérature I.3 qu’ils possèdent une structure d’information fixe. La décision optimale est prise après l’observation d’une variable aléatoire définie indépendamment de toute variable de décision. Un exemple de problème statique est : V (B) def = min {E[J(γ(ξ), ξ)] | γ est B-mesurable} . (I.2) On montrera plus loin que si la tribu B est engendrée par une partition finie, alors V (B) peut se ramener un problème en boucle ouverte. Il arrive souvent en pratique que la tribu B soit engendrée par une variable aléatoire h, nous appellerons une telle fonction h une fonction d’observation. Nous insistons sur le fait que le problème d’optimisation (I.2) est seulement un exemple de problème statique ; il suffit simplement de remarquer que deux contraintes de mesurabilité disons “γ1 est A-mesurable et γ2 est B-mesurable”, ne peuvent pas en général s’écrire comme une seule contrainte de mesurabilité sur le couple (γ1, γ2).

Structure d’information dynamique ou avec effet dual

Les problèmes dynamiques sont ceux qui ne font pas partie de la catégorie problèmes statiques. On trouve notamment dans cette catégorie les problèmes pour lesquels les fonctions d’observations dépendent des variables de décision. Dans certains cas, la dépendance relativement aux variables de décision s’exprime uniquement travers les valeurs prises par la fonction d’observation et pas travers la σalgèbre engendrée. Il s’agit alors de faux problèmes dynamiques : on dit alors qu’il n’y a pas d’effet dual. Un exemple de problème dynamique est : min {E[J(γ(ξ), ξ)] | γ est B γ -mesurable} . (I.3) Pour des développements récents au sujet de l’absence d’effet dual voir [19] et le chapitre II de ce mémoire.