![$[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,
Cermics, École nationale des ponts et chaussées, IP Paris
Dans ce cours, nous présentons
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).
Mots-clés : programmation stochastique, arbre de scénarios, commande optimale stochastique, programmation dynamique stochastique, Stochastic Dual Dynamic Programming, mesures de risque.
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.
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)
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.