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.

Abstract

In this thesis, we consider solution methods for general multistage stochastic optimization problems. Such problems arise in many fields of application, including finance, energy, logistic, transportation, health care, etc. They generally do not have closed-form solutions since they feature mathematical expectations, which cannot be computed exactly in most applications. For this reason, it is necessary to consider solutions through numerical methods. One of them, which is the focus of this thesis, is the scenario-tree generation approach. Its aim is to substitute the underlying stochastic process with a finite subset of scenarios so as to replace the conditional expectations with their finite sum estimators. This reduces the size of the problem, which is then solved using some generic optimization solvers. The generation of scenario trees is subject to a trade-off between the approximation accuracy and the complexity of the resulting discretized problem. The former tends to increase the number of scenarios, whereas the latter tends to decrease it. This trade-off turns out to be fairly easy to satisfy when dealing with two-stage problems. However, it becomes much more difficult when problems are multistage, that is, when they have 3 stages of more. This stems from the fact that multistage problems require specific tree structures whose size (the number of nodes) grow exponentially as the number of stages increases. For this reason, a lot of attention has been drawn on generating scenario trees in the multistage setting. Many methods have been developed based on different theoretical or practical grounds. Most of them can be described as distribution-driven, as they aim at approximating the distribution of the stochastic process (or some features of it), according to their own idea of what a good approximation is. The distribution-driven strategy allows to have consistent scenario-tree estimators under some weak conditions. For this reason, these methods have been successfully applied to many problems. However, it does not allow to capitalize on some specific features of the multistage problem (e.g., the variability of its revenue function or the influence of its constraints), although they play an important role in the scenario-tree approximation quality as well. Taking them into account would lead to more suitable scenario trees that may satisfy a better trade-off between accuracy and complexity. This, in turn, may allow to consider problems with more stages. In this thesis, we introduce a new problem-driven scenario-tree generation approach. It takes into account the whole structure of the optimization problem through its stochastic process, revenue (or cost) function and sets of constraints. This approach is developed in a general setting of multistage problems, hence it is not tied to a particular application or field of applications. The conditions that are introduced along the lines of this thesis about the revenue function, constraints, or probability distribution essentially aims at making sure that the problems is mathematically well-defined.