![$[t+1,T]$](img2.svg)
en une fonction de coût sur ![$[t,T]$](img3.svg)
, ainsi que la politique associée.
P. Carpentier1,
J.-P. Chancelier2,
M. De Lara3,
V. Leclère4
École des Ponts ParisTech
Dans ce cours, nous présentons
Mots-clés : programmation stochastique, arbre de scénarios, Progressive Hedging, commande optimale stochastique, programmation dynamique stochastique, Stochastic Dual Dynamic Programming, décomposition.
Au cours de la première partie du cours (séances 1 à 5), nous présentons les deux approches mathématiques standards traitant des problèmes d'optimisation stochastique multi-étapes, c'est-à-dire la programmation stochastique et la commande optimale stochastique.
Dans la deuxième partie du cours (séances 6 à 8), nous présentons des extensions. Comme les problèmes d'optimisation stochastique multi-étapes sont souvent trop difficiles pour être résolus d'une manière directe, nous détaillons des méthodes avancées permettant de résoudre ces problèmes par décomposition — c'est-à-dire d'itérativement (en parallèle ou séquentiellement) résoudre des sous-problèmes de taille raisonnable, plutôt que l'ensemble. Nous présentons également les mesures de risque et comment les incorporer dans des problèmes d'optimisation stochastique.
La formation alterne séances de cours, de modélisation et d'exercices. Des diapositives correspondantes (en Anglais) sont mises en ligne sur le site web (un astérisque * dénote un support de cours particulièrement adapté à la séance courante).
Nous étudions la programmation stochastique à une étape au travers d'exemples.
Idée-clef : le résultat d'un problème d'optimisation stochastique est la distribution des valeurs aléatoires prises par le critère ; c'est au décideur de choisir entre plusieurs distributions selon son type d'aversion au risque.
Nous commençons par un exercice de modélisation de tests sanguins groupés. Nous formulerons un problème d'optimisation stochastique de minimisation du nombre moyen de tests en fonction de la taille des groupes. Nous comparerons la taille optimale obtenue à celle correspondant au problème d'optimisation robuste de minimisation du pire nombre de tests. Nous comparerons les distributions du nombre de tests selon la taille des groupes.
Nous ferons des rappels de calcul des probabilités : espace de probabilité, probabilité, variable aléatoire (v.a.), loi d'une v.a., fonction indicatrice, espérance mathématique, indépendance, loi forte des grands nombres.
Nous poursuivons en étudiant le problème dit du vendeur de journaux. Le vendeur doit décider le matin du nombre (déterministe) de journaux qu'il va commander, alors que la demande est aléatoire (de distribution supposée connue). Nous montrons comment le nombre optimal de journaux dépend de la distribution de probabilité de la demande.
Diapositives * (MDL) (section Working out static examples)
Lecture suggérée : [SDR09, Chap. 1]
Nous avançons de la programmation stochastique à une étape vers deux étapes.
Idée-clef : quand une première décision est prise avant la réalisation d'un aléa et une seconde décision est prise après la réalisation d'un aléa, la façon mathématique de représenter cela est par le biais d'une contrainte de non-anticipativité ; formuler un problème d'optimisation stochastique sur un arbre de scénarios est une façon de coder directement une contrainte de non-anticipativité.
Nous encadrons la valeur d'un problème stochastique par celles obtenues par un décideur myope (contraintes d'information durcies - boucle ouverte) et par un décideur clairvoyant (contraintes d'information relâchées - anticipative).
Nous discutons ensuite de l'extension au cas multi-étape sur un arbre de scénario et des limites numériques associées.
Lectures suggérées : § 2.1, 2.2 et 2.3 de [SDR09, Chap. 2]
Diapositives (MDL) Diapositives (VL)
Rappels sur convexité et optimisation.
Diapositives * (MDL) Diapositives (JPC)
Nous développons la programmation stochastique à deux étapes, particulièrement dans le cas d'un espace de probabilité fini (scénarios).
Idée-clef : la programmation stochastique à deux étapes se prête naturellement à des méthodes de décomposition, soit par scénario (Progressive Hedging) soit temporelle (L-shaped).
Nous montrons comment passer d'un problème d'optimisation mono-étape — soit déterministe polyhédral sans contraintes soit lineaire — à un problème d'optimisation stochastique linéaire à deux étapes.
Nous poursuivons la programmation stochastique à deux étapes et montrons comment la contrainte de non-anticipativité peut être prise en compte
Diapositives* (MDL) Diapositives (VL) Diapositives (JPC)
Après avoir présenté les notions de recours complet ou relativement complet, nous nous intéressons particulièrement au cas des problèmes stochastique linéaires (avec éventuelles variables entières pour la première étape). Après avoir décomposé le problème en deux pas de temps, nous exploitons la dualité linéaire pour introduire la L-shaped method, qui est une méthode standard de résolution de tel problèmes.
Diapositives* (VL) Diapositives (VL)
Nous soulevons les difficultés du passage de la programmation stochastique à deux étapes vers plusieurs étapes. À l'aide d'une hypothèse de bruits temporellement indépendant, nous présentons la programmation dynamique stochastique. L'idée clef étant l'existence d'un état qui contient les informations suffisantes pour prendre une décision optimale à une étape donnée. La programmation dynamique stochastique consistant alors à décomposer le problème global en une suite de problèmes à une étape.
Nous introduisons le formalisme des opérateurs de Bellman qui tranfère une fonction de coût futur sur en une fonction de coût sur , ainsi que la politique associée.
Finalement nous soulignons les malédictions de la dimension, inhérentes aux méthodes de programmation dynamique.
Lecture suggérée : [Ber00, Chap. 1]
Diapositives (MDL) Diapositives (JPC)
Croissance et reproduction optimales d'une plante.
Contrôle optimal stochastique avec coûts quadratiques et dynamique linéaire, sans contraintes sur la commande.
Programmation de l'algorithme de programmation dynamique. Travail pratique Scicoslab
de gestion de stocks. Mise en perspective
des méthodes. Mesures de risque
Politique dans le problème du vendeur de journaux multi-étapes.
Diapositives* (JPC) Diapositives* (JPC)
Quelle méthode de résolution pour quel problème ? Après avoir avoir évoqué la difficulté de l'évaluation d'une solution pour un problème d'optimisation stochastique, nous rappellerons les principales caractéristiques des deux grandes classes de méthodes servant à résoudre les problèmes stochastiques multi-étapes, à savoir la programmation stochastique et la programmation dynamique, et nous mettrons en lumière leurs forces et leurs faiblesses respectives. Enfin nous discuterons sur quelques problèmes typiques du meilleur choix de la méthode de résolution.
Au delà de l'espérance et du pire des cas — comme forme d'agrégation des incertitudes dans une fonction objectif — nous présentons les mesures de risque.
Exemples : Sun'R, achat optimal de bruts.
SDDP (Stochastic Dual Dynamic Programming) est un algorithme à l'intersection de la programmation dynamique et de la méthode L-Shaped. En s'appuyant sur des hypothèses de linéarité et de convexité, SDDP va itérativement construire des approximations (inférieures) des fonctions de Bellman. Cette approche permet de repousser, pour une certaine classe de problèmes, les limites des malédictions de la dimension.
Pour cela:
Au cours de cette séance, nous explorerons différents schémas de décomposition permettant de diviser un problème de contrôle stochastique optimal — impliquant un grand nombre d'unités — afin d'obtenir plusieurs sous-problèmes à petite échelle. Ces méthodes permettent de résoudre les sous-problèmes par la programmation dynamique ou par SDDP.
Mélange de techniques de décomposition et de programmation dynamique. Nous donnerons tout d'abord quelques exemples classiques de problèmes d'optimisation de grande taille et nous rappellerons les concepts d'optimisation nécessaires pour mettre en oeuvre les méthodes de décomposition. Puis, nous rappellerons deux méthodes classiques de décomposition et coordination, dans un cadre très général (Hilbertien). Nous nous interrogerons enfin sur les particularités de la décomposition dans le cadre des problèmes d'optimisation stochastique dynamique et sur la difficulté en stochastique du mélange de la décomposition et de la programmation dynamique
“Dual Approximate Dynamic Programming” et méthodes connexes. Nous présenterons tout d'abord l'application de la méthode de décomposition par les prix à un problème d'optimisation stochastique dynamique de grande taille et l'approximation permettant de mettre effectivement en oeuvre la décomposition (Dual Approximate Dynamic Programming). Puis nous généraliserons l'approche précédente et nous montrerons comment obtenir des bornes inférieure et supérieure pour la valeur optimale de ces problèmes, par utilisation des méthodes de décomposition par les prix et par les resources. Nous présenterons enfin les résultats obtenus par application de ces méthodes de décomposition spatiale et temporelle sur deux exemples, à savoir la gestion journalière de vallées hydrauliques et la gestion de micro-grilles à l'échelle d'un quartier urbain.
Décomposition par blocs temporels. Sur l'exemple d'un problème de gestion pluri-annuelle d'une batterie, pour lequel il faut prendre en compte à la fois des décisions opérationnelles (charge de la batterie) à une échelle de temps rapide (minute) et des décisions d'investissement (renouvellement de la batterie) à une échelle de temps lente (journée), nous montrerons comment décomposer le problème par blocs temporels afin de découpler les échelles de temps lente et rapide. Nous utiliserons de nouveau les méthodes de décomposition par les prix et par les ressources et nous montrerons comment elles permettent d'écrire et de mettre en oeuvre de manière efficace la programmation dynamique à l'échelle de temps lente.
En conclusion, nous esquisserons la manière dont les méthodes de décomposition spatiale vues dans le courant de la matinée peuvent se mélanger avec les méthodes de décomposition temporelle par blocs.
Diapositives* (PC) Diapositives* (PC)
Nous présentons comment incorporer les mesures de risque dans des problèmes d'optimisation stochastique.
Diapositives * (MDL) (section Two-stage stochastic programs with risk)