Optimisation stochastique
Master Université Cadi Ayyad, Marrakech, Maroc
27-30 novembre 2017

Michel DE LARA, Vincent LECLÈRE (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

• l'optimisation stochastique statique (à une étape),
• la programmation stochastique à deux étapes (et la résolution sur arbre de scénarios ou par scénarios),
• le contrôle stochastique à temps discret (et la résolution par programmation dynamique stochastique).

Des travaux pratiques informatiques -- avec le logiciel scientifique Scicoslab [CCN10] -- et des exercices complètent le cours.

Pré-requis.

• Optimisation continue élémentaire : programmation linéaire, convexité, conditions d'optimalité du premier ordre. [Ber96]
• Calcul des probabilités : espace de probabilité, probabilité, variable aléatoire, espérance mathématique, indépendance, loi des grands nombres, théorème central limite. [Fel68,Bre93,Pit93]
• Logiciel Scicoslab [CCN10] : téléchargement Scicoslab et auto-formation travaux pratiques Scicoslab
  

Apprentissage. À l'issue du cours l'étudiant devrait pouvoir concevoir des modèles mathématiques pour l'optimisation sous incertitude et utiliser le logiciel scientifique Scicoslab pour résoudre numériquement des problèmes de petite taille.

Matériel informatique.

Logiciel (gratuit) Scicoslab.

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

Validation. Notation des travaux pratiques. Examens.

Enseignant responsable. Michel De Lara (CERMICS-ENPC)      page web          propositions de stages

Enseignants. Michel De Lara (CERMICS-ENPC), Vincent LECLÈRE (CERMICS-ENPC)

Liens.      page web du cours               page web du master Modélisation et calcul scientifique pour l'ingénierie mathématique

Programme

1 /     8h30-12h00, lundi 27 novembre 2017
(Michel De Lara)

Exercice

Nous commençons par formuler un problème de commande optimale d'un produit pour satisfaire une demande, avec des coûts d'achat, de backorder et de holding. Nous montrons comment parvenir à un programme linéaire, d'abord en déterministe puis avec un nombre fini de scénarios de demande.      slides

Travaux pratiques informatiques

Introduction au logiciel de calcul scientifique Scicoslab.      Travaux pratiques Scicoslab

2 /     14h30-17h30, lundi 27 novembre 2017
(Michel De Lara)

Travaux pratiques informatiques

The newsvendor problem

Cours

Dans le cas d'un espace de probabilité fini, nous présentons la programmation stochastique à deux étapes, avec variables de recours [SDR09,KW12]. Nous montrons comment la contrainte de non-anticipativité peut être prise en compte en indiçant les solutions par un arbre de scénarios.      slides Lecture suggérée : [SDR09, Chap. 1]

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

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

Exercices      slides

3 /     8h30-12h00, mardi 28 novembre 2017
(Michel De Lara)

Cours

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

• 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.
• Définition d'un minimiseur local ; condition nécessaire dans le cas différentiable. Formulation d'un problème de minimisation sous contraintes d'égalité explicites. Conditions nécessaires d'optimalité du premier ordre dans le cas de contraintes d'égalité régulières ou affines ; Lagrangien, dualité, multiplicateurs. Conditions suffisantes d'optimalité du premier ordre dans le cas convexe-affine. Exercices.

Cours

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

• en indiçant les solutions par un arbre de scénarios,
• ou en indiçant les solutions par un peigne, puis en écrivant des égalités entre composantes de la solution.

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

Travaux pratiques informatiques

Dimensionnement de réserves pour l'équilibrage sur un marché électrique.      Two Stage Stochastic Optimization for Fixing Energy Reserves

4 /     14h30-17h30, mardi 27 novembre 2017
(Michel De Lara)

Cours

Limite numérique à l'optimisation multi-étapes sur un arbre de scénarios.
Exemples de problèmes d'optimisation multi-étapes : gestion de stocks.
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. [Bel57,Put94,Ber00,Whi82,DD08,CCCD15]

Exercice

Croissance et reproduction optimales d'une plante.

Problème du sac à dos, gestion de stock.      slides

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

     slides     
Lecture suggérée : [Ber00, Chap. 1]

5 /     8h30-12h00, mercredi 29 novembre 2017
(Vincent Leclère, Michel De Lara)

Travaux pratiques informatiques

Travaux pratiques informatiques. Programmation de l'algorithme de programmation dynamique.      Travaux pratiques Scicoslab

6 /     14h30-17h30, mercredi 29 novembre 2017
(Vincent Leclère, Michel De Lara)

Contrôle optimal stochastique avec coûts convexes et dynamique linéaire, avec contraintes convexes.      slides
Présentation de l'algorithme Stochastic Dual Dynamic Programming (SDDP).      slides

7 /     8h30-12h00, jeudi 30 novembre 2017
(Vincent Leclère, Michel De Lara)

Exemples d'application au pilotage de micro-grids.

Discussion de possibles sujets de stage et de thèses.

Bibliographie

Bel57

R. E. Bellman.
Dynamic Programming.
Princeton University Press, Princeton, N.J., 1957.

Ber96

D. P. Bertsekas.
Constrained Optimization and Lagrange Multiplier Methods.
Athena Scientific, Belmont, Massachusets, 1996.

Ber00

D. P. Bertsekas.
Dynamic Programming and Optimal Control.
Athena Scientific, Belmont, Massachusets, second edition, 2000.
Volumes 1 and 2.

Bre93

L. Breiman.
Probability.
Classics in applied mathematics. SIAM, Philadelphia, second edition, 1993.

CCCD15

P. Carpentier, J.-P. Chancelier, G. Cohen, and M. De Lara.
Stochastic Multi-Stage Optimization. At the Crossroads between Discrete Time Stochastic Control and Stochastic Programming.
Springer-Verlag, Berlin, 2015.

CCN10

Stephen Campbell, Jean-Philippe Chancelier, and Ramine Nikoukhah.
Modeling and Simulation in Scilab/Scicos with ScicosLab 4.4.
Springer-Verlag, New York, 2 edition, 2010.

DD08

Michel De Lara and Luc Doyen.
Sustainable Management of Natural Resources. Mathematical Models and Methods.
Springer-Verlag, Berlin, 2008.

Fel68

W. Feller.
An Introduction to Probability Theory and its Applications, volume 1.
Wiley, New York, third edition, 1968.

KW12

Alan J. King and Stein W. Wallace.
Modeling with Stochastic Programming.
Springer Series in Operations Research and Financial Engineering. Springer New York, 2012.

Pit93

J. Pitman.
Probability.
Springer-Verlag, New-York, 1993.

Put94

M. L. Puterman.
Markov Decision Processes.
Wiley, New York, 1994.

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.

Whi82

P. Whittle.
Optimization over Time: Dynamic Programming and Stochastic Control, volume 1 and 2.
John Wiley & Sons, New York, 1982.