Approximation d'espérances conditionnelles guidée par le problème en optimisation stochastique multi-étapes

Dans cette thèse, nous considérons d'une façon générale la résolution de problèmes d'optimisation stochastique multi-étapes. Ces derniers apparaissent dans de nombreux domaines d'application tels que la finance, l'énergie, la logistique, le transport, la santé, etc. Ils sont généralement insolubles de façon exacte car ils contiennent des espérances mathématiques qui ne peuvent pas être calculées analytiquement. Il est donc nécessaire de considérer pour cela des méthodes numériques. Nous nous intéressons particulièrement aux méthodes de génération d'arbres de scénarios. Ceux-ci remplacent le processus stochastique sous-jacent au problème afin de ramener ce dernier à une taille raisonnable permettant sa résolution pratique. Numériquement, cela permet de remplacer les opérateurs d'espérance qui apparaissent dans la formulation originale du problème (et qui tiennent compte de toutes les scénarios possibles en les pondérant avec une certaine densité de probabilité), par des sommes finies qui, pour leur part, ne prennent en compte qu'un sous-ensemble de scénarios seulement. Cette approximation permet ensuite à un ordinateur de résoudre le problème discrétisé à l'aide de solveurs classiques d'optimisation. L'arbre de scénarios doit satisfaire un compromis entre la qualité d'approximation, qui voudrait que l'arbre soit le plus grand possible, et la complexité de résolution du problème discrétisé qui, à l'inverse, voudrait qu'il soit le plus petit possible. Alors que ce compromis est relativement facile à satisfaire pour les problèmes à deux étapes, il l'est beaucoup moins pour les problèmes multi-étapes (c.-à-d. à partir de trois étapes). Ceci est dû à la nécessité de considérer des structures d'arbres dont la taille (le nombre de noeuds) croît exponentiellement avec le nombre d'étapes. Dans ce contexte multi-étapes, la recherche d'un compromis satisfaisant entre qualité et complexité a mené la communauté d'optimisation stochastique à développer de nombreuses approches de génération d'arbres de scénarios basées sur des justifications théoriques ou pratiques différentes. Ces justifications portent essentiellement sur la qualité d'approximation du processus stochastique par l'arbre de scénarios. Pour cette raison, ces approches sont dites guidées par la distribution, étant donné qu'elles souhaitent reproduire le mieux possible –suivant leur propre critère de qualité– la distribution du processus stochastique (ou certaines propriétés de celle-ci). Prendre en compte la distribution permet sous certaines conditions assez faibles d'assurer la consistance de la méthode de résolution. Pour cette raison, ces méthodes sont utilisées avec succès dans de nombreux problèmes. Cependant, cette stratégie ne permet pas de tirer profit de la structure même du problème d'optimisation, par exemple la variabilité de sa fonction objectif ou l'influence de ses contraintes, qui joue aussi un rôle important dans la qualité d'approximation. La prise en compte de ces caractéristiques permettrait de construire des arbres de scénarios plus adaptés aux problèmes et ainsi de satisfaire un meilleur compromis entre qualité et complexité. En pratique, cela permettrait de pouvoir résoudre des problèmes avec un plus grand nombre d'étapes.