Optimisation dans l'Incertain (OI)

dernière modif : le 18/12/2023 à 16:44:37
Titre :
Optimisation dans l'Incertain (OI)
Section :
Obligatoire
État pour cette année :
OPEN
Mots clés :
Programmation Stochastique, Programmation Dynamique
Ects :
3
Responsable :
Vincent Leclère (ENPC ParisTech / CERMICS)
Intervenants :
Vincent Leclère (ENPC ParisTech / CERMICS)
Prérequis :

bases de probabilité, programmation et dualité linéaire, décomposition de Benders

Objectif :

Objectif à préciser

Contenu / Plan :

Séance 1 Introduction à l’optimisation sous incertitude.

  • Grandes classes de problème d’optimisation sous incertitude parmis lesquels l’optimisation stochas- tique et robuste. Importance de la simulation dans l’évaluation des problèmes d’optimisation sous incertitude.
  • Principe de l’optimisation stochastique. Formulation extensive sur un arbre de scénarios. Notion de structure d’information, VSS et EVPI.
  • Principe de Sample Average Approximation.

Séance 2 Méthodes numériques de décomposition des problèmes stochastiques

  • Décomposition L-Shaped.
  • Progressive-Hedging.
  • Extension au cas multistage.

Séance 3 Méthodes de résolution à base de programmation dynamique.

  • Principe de la programmation dynamique. Opérateur de Bellman. Application à un problème de gestion de stock.
  • Extension du cadre d’application de la programmation dynamique à l’aide d’état étendu : exemples et exercices.
  • Algorithme SDDP pour le cas linéaire convexe.

Séance 4 Introduction à l’optimisation robuste.

  • Principe de l’optimisation robuste. Motivation par le cas linéaire.
  • Classes de méthodes de résolution : génération de contraintes ou reformulation. Exemple du cas linéaire.
  • Classification des problèmes robustes. Notion de garantie probabiliste.

Séance 5 Optimisation robuste avancée.

  • Problèmesd’optimisationrobustesouscontraintesdebudget.ModèledeSoyster.Modèleaveccontraintes de budget (Bertsimas-Sim). Méthode de reformulation et garanties théoriques.
  • Problèmes d’optimisation robuste avec recours. Règles de décision affines. Recours K-adaptable.

Séance 6 Examen

Compétences visées

  • Savoir modéliser un problème d’optimisation sous incertitude ;
  • savoir mettre en place des méthodes de résolution d’un problème stochastique à deux étapes ;
Bibliographie :
  • Lectures on Stochastic Programming, Dentcheva, Ruszczynski, Shapiro

  • Dynamic Programming and Optimal Control, Bertsekas

  • Theory and applications of robust optimization, Bertsimas, Brown, Caramis

  • The Price of Robustness, Bertsimas Sim

  • Distributionally robust optimization : A review, Rahimian, Mehrotra

  • A survey of adjustable robust optimization Yanıkoğlu, Gorissen, den Hertog

Liens :
(aucun)
Compétences visées :
  • Savoir modéliser un problème d'optimisation sous incertitude;

  • savoir mettre en place des méthodes de résolution d'un problème stochastique à deux étapes;

  • savoir mettre en place des méthodes de résolution d'un problème d'optimisation robuste linéaire ;

  • savoir utiliser un algorithme de programmation dynamique dans un cadre Markovien simple.

Modalités de contrôle :

TP à faire hors séance + Examen final