Optimisation stochastique (OS)
2017-2018
Master Parisien de Recherche Opérationnelle
(MPRO)

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

Des travaux pratiques informatiques -- avec le logiciel scientifique Scicoslab [CCN10] -- 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 utiliser le logiciel scientifique Scicoslab pour résoudre numériquement des problèmes de petite taille.


Matériel informatique.
\fbox{Ordinateur portable personnel aux sťances de travaux pratiques informatiques.}
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 MPRO               planning du master MPRO               plan des salles du CNAM


Programme

1 / 14h00-17h30, jeudi 28 septembre 2017
(Vincent Leclère), salle 21.2.31 (Rue Saint-Martin)

Nous présentons diverses problématiques posées par la présence de variables incertaines dans un problème d'optimisation :
traitement des contraintes (presque sûrement, en probabilité, etc.) ; construction d'un critère (en espérance, pire des cas, etc.).
Nous étudierons la programmation stochastique à une étape, au travers d'exemples.

Nous ferons des rappels de résultats de théorie des probabilités, utiles pour la suite du cours.      slides

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


2 / 14h00-17h30, jeudi 5 octobre 2017
(Vincent Leclère), salle 17.2.07 (Rue Saint-Martin)

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

Travaux pratiques      slides


3 / 14h00-17h30, jeudi 12 octobre 2017
(Vincent Leclère), salle 30.-1.05 (Rue Conté)

Méthode de résolution d'un problème stochastique à deux étapes (L-shaped method).
Extension à la programmation stochastique à plusieurs étapes. Discussion sur la taille du problème.

Exercices.


4 / 14h00-17h30, jeudi 19 octobre 2017
(Michel De Lara), salle 30.-1.05 (Rue Conté)

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.
     slides [Bel57,Put94,Ber00,Whi82,DD08,CCCD15]

Exercice : croissance et reproduction optimales d'une plante.      slides
Lecture suggérée : [Ber00, Chap. 1]


5 / 14h00-17h30, jeudi 26 octobre 2017
(Michel De Lara), salle 17.2.07 (Rue Saint-Martin)

Exercices : problème du sac à dos, gestion de stock.

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

\fbox{Ordinateur portable personnel}

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


6 / 14h00-17h30, jeudi 9 novembre 2017
(Michel De Lara), salle 17.2.14 (Rue Saint-Martin)

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

16h00-17h30 : Examen (90 minutes).


7 / 9h00-12h00, jeudi ??? décembre 2017
(Michel De Lara)/(Vincent Leclère),

Rattrapage.


Annales

     DM 2015      DM Corrigé 2015      Sujet 2015      Corrigé 2015      Sujet 2016      Corrigé 2016


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.