Master EDDEE-EEET
Economie du Développement Durable, de l'Environnement et de l'Energie
  
   2021–2022

Optimisation dans l'incertain

Michel DE LARA, CERMICS-École des Ponts ParisTech

version pdf version de ce document

Pré-requis.

• Compétences mathématiques (capacité à manipuler des concepts abstraits et à effectuer des calculs). Compétences en informatique (avoir déjà programmé).
• Connnaissances en mathématiques de base : algèbre linéaire (vecteurs, matrices, matrices symétriques et symétriques positives) ; topologie sur  $\mathbb{R}^d$ (sous-ensembles ouverts et fermés, sous-ensembles bornés, compacité, continuité des fonctions) ; calcul différentiel sur  $\mathbb{R}^d$ (dérivée, dérivées partielles, gradient, matrice Jacobienne).
• Optimisation continue élémentaire : programmation linéaire, convexité, multiplicateurs de Lagrange et dualité, conditions d'optimalité du premier ordre. [Ber96]
• 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. [Fel68]

Apprentissage. À l'issue du cours, l'étudiant devrait pouvoir

• concevoir des modèles élémentaires de décision pour la gestion de l'énergie et du climat,
• savoir représenter mathématiquement les incertitudes — telles que la production des énergies renouvelables, à la demande d'énergie ou des facteurs climatiques — au moyen de variables aléatoires,
• poser des problèmes de minimisation de l'espérance mathématique de coûts aléatoires (ou d'une mesure de risque appropriée),
• identifier les algorithmes de résolution appropriés — selon que le problème est à une, deux ou plusieurs étapes — et les conditions sous lesquelles ils convergent vers une solution optimale.

Langue. Les diapositives de cours (et les travaux pratiques informatiques optionnels) sont en anglais. Le cours oral est assuré en français.

Contenu du cours. Le cours est découpé en deux grandes parties : cours formel et atelier.

Le cours formel combine des sessions théoriques, des exercices de modélisation et des rappels mathématiques en probabilité et en optimisation. Dans un problème d'optimisation déterministe, les valeurs de tous les paramètres sont censées être connues. Que se passe-t-il lorsque ce n'est plus le cas ? Et quand certaines valeurs sont révélées pendant les étapes de la décision ? Nous présentons l'optimisation stochastique, à la fois comme un cadre mathématique permettant de formuler des problèmes sous incertitude et comme des méthodes pour les résoudre selon la formulation retenue. Plus précisément, nous présentons la programmation stochastique à une étape et la programmation stochastique à deux étapes (et la résolution sur arbre de scénarios ou par scénarios).

Dans la partie atelier, les élèves choisissent eux-mêmes un sujet à traiter soit individuellement, soit par groupes de deux ou trois. Voici des types de sujet possibles :

• rédiger proprement des notes du cours sous la forme de diapositives en beamer L^ATEX ; étendre le problème des tests sanguins à des cas plus complexes ; trouver un exemple pédagogique de comment l'optimisation stochastique est une façon de convexifier un programme linéaire et donc de rendre ses solutions moins “intérieures” (plus robustes) ;
• analyser la façon dont un article économique aborde la décision sous incertitude, puis proposer une reformulation ;
• proposer des formulations mathématiques inspirées du cours pour des problèmes d'allocation économique optimale d'unités de production d'énergie : calcul de réserves d'énergie ;
• proposer des formulations mathématiques inspirées du cours pour des problèmes de mitigation du changement climatique : calcul de hauteurs de digues, analyse de l'utilisation de l'optimisation stochastique ou robuste dans les rapports du GIEC, utilisation de mesures de risque dans la mitigation du changement climatique, conception de politiques robustes de décarbonisation, décentralisation d'une cible globale de réduction d'émissions de gaz à effet de serre ; optimisation sous incertitude sur la fonction de dommages climatiques ;
• formulation de la résilience avec les concepts de l'optimisation stochastique ou robuste ;
• valeur de l'information ;
• préservation de la biodiversité ;
• analyse de l'influence d'un retard d'ordre 1 (modèle de série chronologique AR1) sur les fonctions valeurs et les solutions optimales d'un problème d'optimisation linéaire-quadratique.

J'accompagnerai les élèves le long de l'avancement du sujet, de manière personnalisée (réunions par vidéo).

Validation. La partie atelier conduit à une note.

Enseignant responsable. Michel De Lara (Cermics—École des Ponts ParisTech)      page web          propositions de stages

Liens.    
http://cermics.enpc.fr/~delara/TEACHING/Master_EEET/      page web

Lien Master EDDEE-EEET.    
http://www.master-eddee.fr/      page web du Master EDDEE-EEET

Programme en présentiel

1 / Vendredi 3 décembre 2021 : 16h-18h30,

Vérification des dates et balayage du programme du cours (0h15)

Session de modélisation (2h00)

Mix optimal de production énergétique avec demande déterministe, puis aléatoire.

Stratégies robustes de décarbonation.

diapositives      diapositives

2 / Mardi 7 décembre 2021 : 16h-18h30,

Session de modélisation/ Exercice (1h15)

Le problème des tests sanguins. Nous présentons le problème des tests sanguins comme un exemple de problème d'optimisation stochastique statique (on prend une décision, puis le hasard se réalise). Ceci est une occasion de faire des rappels de calcul des probabilités.

     diapositives

Cours (1h15)

Problème du vendeur de journaux

Nous présentons la programmation stochastique à deux étapes, avec variables de recours, sur 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) et par un décideur clairvoyant (contraintes d'information relachées).

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.

Lectures suggérées : § 2.1, 2.2 et 2.3 de [SDR09, Chap. 2]

     Diapositives (VL)      Diapositives (MDL)

3 / Vendredi 10 décembre 2021 : 16h-18h30,

Cours (0h30)

Rappels de calcul des probabilités : espace de probabilité, tribu, probabilité, variable aléatoire (v.a.), tribu engendrée, loi d'une v.a., espérance mathématique (linéarité, positivité), fonction indicatrice (loi, espérance mathématique), indépendance de v.a., convergence presque sûre et loi forte des grands nombres. [Fel68]

Cours (0h45)

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

• Rappels sur la convexité : ensembles convexes, fonctions convexes, convexité stricte et forte (caractérisation par le Hessien dans le cas régulier), opérations préservant convexité.
• Formulation abstraite d'un problème de minimisation : critère, contraintes. Conditions suffisantes pour l'existence d'un minimum (continuité et compacité/coercivité).
  Condition suffisante pour l'unicité d'un minimum (convexité stricte). Exercices avec une fonction objectif quadratique sur un intervalle.

     Diapositives

Session de modélisation (1h15)

Mix optimal de production énergétique en prenant en compte les incertitudes sur production (renouvelable), demande et coûts des technologies (production, stockage). Analyse du cas linéaire.

Numerical example of a robust solution of a stochastic linear program. Diapositives

4 / Mercredi 15 décembre 2021 : 16h-18h30, salle B208

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)

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.

5 / Vendredi 17 décembre 2021 : 16h-18h30, salle B211

Encadrement de projet.

Programme en distanciel

À l'issue des séances en présentiel, les élèves choisissent, seul ou par binôme, un article à analyser ou un projet à effectuer

Le reste du cours se fait en distanciel à des horaires variés : je fais des réunions avec chaque binôme pour suivre leur avancée.

Références

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.

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.