Optimisation stochastique (OS)
2021–2022
Master Parisien de Recherche Opérationnelle
(MPRO)

Michel DE LARA (CERMICS-ENPC)


pdf version of this document


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

Des travaux pratiques informatiques optionnels et des exercices complètent le cours.


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


Programme


1 / Lundi 20 septembre 2021, 14h00–17h30
(Michel De Lara), CNAM av. St Martin, salle 21.2.37

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.

Exercice (1h00)

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.

    Diapositives

Cours (1h00)

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.

Exercice (1h00)

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]

Travail pratique informatique (optionnel)

Le vendeur de journaux Travail pratique Scicoslab


2 / Lundi 27 septembre 2021, 14h00–17h30
(Michel De Lara), CNAM av. St Martin, salle 21.2.37

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é.

Exercice (1h00)

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.

    Diapositives

Cours (0h30)

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 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).

Cours (1h30)

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.

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)     


3 / Lundi 4 octobre 2021, 14h00–17h30
(Michel De Lara), CNAM av. St Martin, salle 21.2.31

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.

Rappels et exercices (0h15)

Rappels et exercices sur l'optimisation continue [Ber96].

    Diapositives

Cours (1h15)

Nous poursuivons la programmation stochastique à deux étapes et montrons comment la contrainte de non-anticipativité peut être prise en compte

Avec cette deuxième façon de faire, nous introduisons la décomposition par scénarios, puis le Progressive Hedging [RW91].

     Diapositives (MDL)      Diapositives (VL)      Diapositives (JPC)

    

Examen (1h30)

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.

Travail pratique informatique (optionnel)

Dimensionnement de réserves pour l'équilibrage sur un marché électrique.      Travail pratique Scicoslab

Exercices (optionnel)

     Diapositives


4 / Lundi 11 octobre 2021, 14h00–17h30
(Michel De Lara), CNAM av. St Martin, salle 21.1.16

Correction de l'examen (0h45)

Cours (0h45)

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.

Cours (1h30)

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)


5 / Lundi 18 octobre 2021, 14h00–17h30
(Michel De Lara), CNAM av. St Martin, salle 21.1.37

Exercice (0h45)

Problème du sac à dos.

Exercice (0h45)

Croissance et reproduction optimales d'une plante.      Diapositives (MDL)

Cours (0h45)

Contrôle optimal stochastique avec coûts quadratiques et dynamique linéaire, sans contraintes sur la commande.

Exercice (0h45)

Contrôle optimal stochastique avec coûts quadratiques et dynamique linéaire, sans contraintes sur la commande.

Travail pratique informatique (optionnel)

Programmation de l'algorithme de programmation dynamique.      Travail pratique Scicoslab


6 / Lundi 8 novembre 2021, 14h00–17h30
(Michel De Lara), CNAM av. St Martin, salle 30.1.20

Cours (1h30)

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)

Examen (1h30)


7 / Vendredi 28 janvier 2022, 9h00–12h00
(Michel De Lara),

Rattrapage

Annales

     DM 2015      DM Corrigé 2015      Sujet 2015      Corrigé 2015      Sujet 2016      Corrigé 2016      Sujet 2018      Sujet 2019-2020 (a)      Sujet 2019-2020 (b)


Bibliographie

Ber96
D. P. Bertsekas.
Constrained Optimization and Lagrange Multiplier Methods.
Athena Scientific, Belmont, Massachusetts, 1996.
Ber00
D. P. Bertsekas.
Dynamic Programming and Optimal Control.
Athena Scientific, Belmont, Massachusetts, second edition, 2000.
Volumes 1 and 2.
Fel68
W. Feller.
An Introduction to Probability Theory and its Applications, volume 1.
Wiley, New York, third edition, 1968.
RW91
R.T. Rockafellar and R. J-B. Wets.
Scenarios and policy aggregation in optimization under uncertainty.
Mathematics of operations research, 16(1):119–147, 1991.
SDR09
A. Shapiro, D. Dentcheva, and A. Ruszczynski.
Lectures on stochastic programming: modeling and theory.
The society for industrial and applied mathematics and the mathematical programming society, Philadelphia, USA, 2009.