![$[t+1,T]$](img1.svg)
en une fonction de coût sur ![$[t,T]$](img2.svg)
, ainsi que la politique associée.
Jean-Philippe Chancelier1,
Michel De Lara2,
École nationale des ponts et chaussées, IP Paris
Dans ce cours, nous présentons
Mots-clés : programmation stochastique, arbre de scénarios, commande optimale stochastique, programmation dynamique stochastique, Stochastic Dual Dynamic Programming, décompositions, mesures de risque.
Lieux :
Au cours de la première partie du cours, 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, nous présentons des extensions, telles que l'algorithme Stochastic Dual Dynamic Programming (SDDP), ainsi que 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.
Diapositives * (MDL) (section Working out static examples)
Lecture suggérée : [SDR09, Chap. 1]
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.
Le vendeur de journaux Travail pratique Scicoslab
Nous avançons de la programmation stochastique à une étape vers deux étapes. 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 revisitons le problème du vendeur de journaux dans le cas d'un arbre de scénarios. Nous montrons comment passer d'un problème d'optimisation déterministe d'une fonction polyhédrale sans contraintes à une formulation stochastique.
Nous étendons le problème du vendeur de journaux en un problème d'inventaire à deux étapes. Une compagnie doit commander un produit pour satisfaire une demande aléatoire, mais elle peut effectuer une seconde commande une fois la demande observée. Nous montrons comment passer d'un problème d'optimisation déterministe d'une fonction linéaire sous contraintes (programmation linéaire) à une formulation stochastique avec variables de recours.
Nous développons la programmation stochastique à deux étapes, dans le cas linéaire avec un espace de probabilité fini (scénarios).
Idée-clef : la programmation stochastique linéaire à deux étapes se prête naturellement à une méthode de décomposition temporelle, (L-shaped), qui repose sur la dualité en programmation linéaire.
Diapositives * (MDL) Diapositives * (VL)
Rappels sur convexité et optimisation.
Attention : cette séance aura lieu à l'École nationale des ponts et chaussées, 6 et 8 avenue Blaise Pascal – Cité Descartes – Champs-sur-Marne – 77455 Marne-la-Vallée cedex 2
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é.
Dans le cas d'un espace de probabilité fini, nous montrons comment la contrainte de non-anticipativité peut être prise en compte en indiçant les solutions par un arbre de scénarios.
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.
Nous poursuivons la programmation stochastique à deux étapes et montrons comment la contrainte de non-anticipativité peut être prise en compte
Lectures suggérées : § 2.1, 2.2 et 2.3 de [SDR09, Chap. 2]
Diapositives * (MDL) Diapositives (VL) Diapositives (JPC)
Attention : cette séance aura lieu à l'École nationale des ponts et chaussées, 6 et 8 avenue Blaise Pascal – Cité Descartes – Champs-sur-Marne – 77455 Marne-la-Vallée cedex 2
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) Diapositives (VL)
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
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 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.
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.
Attention : cette séance aura lieu au CNAM, Conservatoire national des arts et métiers, 292 Rue Saint-Martin, 75003 Paris