Michel DE LARA (CERMICS-ENPC)
Présentation. Dans un problème d'optimisation déterministe, les valeurs de tous les paramètres sont supposées connues. Comment formuler un problème d'optimisation dans lequel les données sont incertaines (par exemple, les prix des énergies) ? Et quand certaines valeurs des données sont révélées au cours des étapes de décision (par exemple, les demandes en énergie) ? L'optimisation stochastique est un cadre pour répondre à de telles questions et pour formuler des problèmes sous incertitude. C'est également un ensemble de méthodes de résolution.
Dans ce cours, nous présentons
Pré-requis.
Apprentissage. À l'issue du cours, l'étudiant devrait pouvoir concevoir des modèles mathématiques pour l'optimisation sous incertitude et des algorithmes pour les résoudre numériquement.
Langue. Les diapositives de cours (et les travaux pratiques informatiques optionnels) sont en anglais. Le cours oral est assuré en français.
Validation. Examens.
Enseignant responsable. Michel De Lara (CERMICS-ENPC) page web propositions de stages
Enseignants. Michel De Lara (CERMICS-ENPC)
Liens. page web du cours page web du master MPRO planning du master MPRO plan des salles du CNAM
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.
Lecture suggérée : [SDR09, Chap. 1]
Le vendeur de journaux Travail pratique Scicoslab
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 étendons le problème du vendeur de journaux en un problème d'inventaire à une étape. Une compagnie doit commander un produit (en quantité continue) pour satisfaire une demande aléatoire. Elle supporte des coûts d'achat, de backorder et de holding. Dans le cas où la distribution de probabilité de la demande est continue, nous caractérisons la quantité optimale à commander.
Nous montrons comment un programme linéaire déterministe peut être transformé en un problème stochastique avec un nombre fini de scénarios, en introduisant des variables de recours.
Rappels et exercices sur l'optimisation continue [Ber96].
Nous présentons la L-shaped method, méthode de résolution d'un problème linéaire stochastique à deux étapes.
Lectures suggérées : § 2.1, 2.2 et 2.3 de [SDR09, Chap. 2]
Diapositives (VL)
Diapositives (MDL)
Diapositives (VL)
Nous développons la programmation stochastique à deux étapes.
Idée-clef : dans le cas d'un espace de probabilité fini, la programmation stochastique à deux étapes se prête naturellement à des méthodes de décomposition parallèle par scénarios.
Nous présentons la programmation stochastique à deux étapes, avec variables de recours. Nous encadrons la valeur d'un problème stochastique par celles obtenues par un décideur myope (contraintes d'information durcies) et par un décideur clairvoyant (contraintes d'information relachées).
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)
Cet examen porte sur la programmation stochastique à une étape et à deux étapes : formulation de problèmes, résolution (calcul de la solution de première étape), conditions d'utilisation des algorithmes L-shaped et décomposition par scénarios (Progressive Hedging).
Les documents sont autorisés.
Dimensionnement de réserves pour l'équilibrage sur un marché électrique. Travail pratique Scicoslab
Nous soulevons les difficultés du passage de la programmation stochastique à deux étapes vers plusieurs étapes.
Rappels sur les tribus. Rappels de théorie de la mesure — tribu, mesurabilité, théorème de Doob — pour aborder les contraintes d'information et, particulièrement, la contrainte de non-anticipativité.
Bornes supérieure (boucle ouverte) et inférieure (anticipative) d'un problème de minimisation stochastique (à deux étapes). Nous encadrons la valeur d'un problème stochastique par celles obtenues par un décideur myope (contraintes d'information durcies) et par un décideur clairvoyant (contraintes d'information relachées).
Limite numérique à l'optimisation multi-étapes sur un arbre de scénarios.
Nous présentons la programmation dynamique stochastique.
Idée-clef : un état contient les quantités suffisantes pour prendre une décision optimale à une étape donnée ; la programmation dynamique est une méthode de décomposition séquentielle par étapes.
Contrôle optimal stochastique de systèmes dynamiques avec incertitudes.
Programmation dynamique stochastique.
Équation de la programmation dynamique. Politique de Bellman.
Malédiction de la dimension.
Lecture suggérée : [Ber00, Chap. 1]
Diapositives (MDL) Diapositives (VL) Diapositives (JPC)
Problème du sac à dos.
Croissance et reproduction optimales d'une plante.
Diapositives (MDL)
Contrôle optimal stochastique avec coûts quadratiques et dynamique linéaire, sans contraintes sur la commande.
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
Récapitulatif optimisation stochastique multi-étapes.
Programmation stochastique :
cas d'un espace de probabilité fini ;
solutions indicées par un arbre de scénarios ;
explosion combinatoire de l'arbre de
scénarios avec le nombre de pas de temps ;
algorithmes de décomposition par scenarios (L-shaped,
progressive hedging).
Commande optimale stochastique : résolution par
programmation dynamique stochastique sous hypothèse de bruits blancs ;
solutions en feedback sur l'état ;
malédiction de la dimension (explosion du nombre de valeurs de la fonction
de Bellman à stocker, avec la dimension de l'état).
Nous montrons comment la malédiction de la dimension peut être (en partie) levée
sous des hypothèses de coûts convexes et dynamique linéaire,
avec contraintes convexes.
Les fonctions de Bellman peuvent être approchées par dessous par des suprema
de fonctions affines données par l'algorithme Stochastic Dual Dynamic Programming (SDDP).
Idée-clef : la combinaison de méthodes d'analyse convexe et de la programmation dynamique permet de développer un algorithme pouvant traiter des cas avec plusieurs pas de temps et plusieurs dimensions d'état.
Gestion de stocks.
Contrôle optimal stochastique avec coûts convexes et dynamique linéaire,
avec contraintes convexes.
Diapositives (MDL)
Présentation de l'algorithme Stochastic Dual Dynamic Programming (SDDP).
Diapositives (VL)
Rattrapage
DM 2015 DM Corrigé 2015 Sujet 2015 Corrigé 2015 Sujet 2016 Corrigé 2016 Sujet 2018 Sujet 2019-2020 (a) Sujet 2019-2020 (b)