Département d'informatique et de recherche opérationnelle (IRO)
Hiver 2011
Objectif général
Ce cours vise à étudier les algorithmes et outils mathématiques servant à analyser ou à optimiser
des processus de décision séquentiels, pour lesquels il y a interaction entre les décisions, dans un
environnement certain ou incertain. On verra comment implanter les algorithmes de calcul et on
étudiera leur performance. Dans plusieurs cas on pourra démontrer certaines propriétés caractérisant
la forme d'une politique optimale. On examinera aussi des exemples d'applications tirées de différents
domaines, incluant la gestion et la finance.
Contenu
- Introduction.
Processus de décision séquentiels. Modèles déterministes et stochastiques.
Définition de l'état. équations de récurrence. Horizons finis et infinis, avec et sans actualisation. La malédiction des grandes dimensions. Exemples.
- Modèles déterministes en temps discret.
Prototype: recherche du plus court chemin dans un réseau. Modèle déterministe sur horizon fini. équations de récurrence. Différents algorithmes et comparaisons. Commande optimale en temps continu: aperçu.
- Modèles stochastiques sur horizon fini et en temps discret.
Processus de décision Markoviens sur horizon fini. équations de récurrence et résolution. Modèles à état partiellement observé. Approximations et stratégies sous-optimales. Examples divers.
- Horizon infini avec actualisation.
Modèles en temps discret et en temps continu (renouvellement Markovien). Algorithmes de calcul: itération des valeurs, itérations des politiques, méthodes hybrides, programmation linéaire. Applications contractantes. Conditions de convergence et vitesses de convergence.
- Horizon infini avec coût moyen.
Modèles et hypothèses. Stabilité. Conditions d'optimalité. Algorithmes de calcul.
- Autres aspects.
Méthodes d'aggrégation adaptatives. Algorithmes parallèles. Discrétisations
et approximations pour les espaces d'états ou les espaces de décisions continus. Méthodes utilisant la simulation. Jeux dynamiques. Etc. (selon le temps disponible)
Référence de base
-
D. P. Bertsekas, Dynamic Programming and Optimal Control, Vol. 1 et 2, Athena Scientific, Belmont, Mass., 2005 et 2007. Disponible à la librairie de l'U. de M. au pavillon principal.
Autres références
-
E. V. Denardo, Dynamic Programming: Models and Applications, Prentice-Hall, 1982.
-
M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, New York, 1994.
- W. B. Powell, Approximate Dynamic Programming, Wiley, New York, 2007.
Evaluation
Examen partiel: 20%, 16 mars 2009
Travail final: 30%
Devoirs (4): 50%
Plagiat
Vous êtes priés de lire bien attentivement le règlement sur le plagiat.
Il sera appliqué rigoureusement dans ce cours. En particulier, les
solutions copiées (ou presque) sur le voisin, ou sur des
solutionnaires trouvés sur internet ou ailleurs, ou tirés de livres ou
articles sans donner la référence, constituent du plagiat.