Algèbre max-plus et théorie de Perron-Frobenius non-linéaire appliquées au contrôle optimal et aux jeux

S. Gaubert¹

Cours avancé, Parcours OJME, Année 06-07. Volume prévu: 18h (6 séances de 3h).

L'étude de problèmes de contrôle optimal ou de jeux par la méthode de la programmation dynamique fait intervenir des opérateurs qui ont de fortes propriétés de structure, telles que la préservation de l'ordre d'un cône ou la contraction au sens large pour certaines métriques (de Hilbert, de Thompson). Dans le cas particulier des problèmes de contrôle déterministe, ces opérateurs sont même linéaires, à condition de se placer dans des structures algébriques dites max-plus ou tropicales. L'étude de ces opérateurs s'inscrit dans le cadre de la théorie de Perron-Frobenius non-linéaire, qui étend certains des résultats connus pour les opérateurs linéaires positifs préservant un cône. Le but du cours est de présenter cette théorie, en mettant en évidence ses aspects tropicaux, et en l'appliquant à l'analyse des problèmes de contrôle ou de jeux. On s'intéressera particulièrement aux aspects asymptotiques (horizon infini, problèmes ergodiques) et algorithmiques.

Introduction

Semi-anneau max-plus et autres semi-anneaux tropicaux. Problèmes où ces structures interviennent: programmation dynamique; contrôle optimal et équations d'Hamilton-Jacobi; problème d'affectation optimale; problèmes asymptotiques.

Méthodes algébriques en programmation dynamique

Problème déterministe à espace d'état fini. Représentation de l'espace propre. Asymptotique de la fonction valeur et des stratégies optimales lorsque l'horizon tend vers l'infini (théorème ``du Turnpike''). Interprétation des vecteurs propres en termes d'investissement, ou comment éviter l'effet ``après nous le déluge''. Généralisations: cas d'un espace d'état dénombrable (conditions de tension), cas des opérateurs compacts. Application aux semigroupes d'Hamilton-Jacobi.

Cadre de la théorie de Perron-Frobenius non-linéaire

Applications monotones contractantes. Applications monotones homogènes agissant sur un cône. Exemples d'applications: problèmes de décision Markoviens, jeux combinatoires, problèmes de ``scaling'' (maximisation d'entropie), dynamique des populations. Métrique projective de Hilbert, métrique de Thompson. Problème spectral non-linéaire.

Théorème de Perron-Frobenius généralisé

Généralisations non-linéaires du théorème de Perron-Frobenius: questions d'existence et d'unicité du vecteur propre, convergence vers une orbite périodique, structure de l'ensemble des points fixes.

Application en contrôle stochastique

Étude du problème de contrôle stochastique avec critère ergodique.

Algorithmes d'itération sur les politiques pour les jeux

Algorithme d'itération sur les politiques pour les jeux. Cas actualisé. Cas avec gain moyen.

Bibliographie

1

M. Akian and S. Gaubert.
Spectral theorem for convex monotone homogeneous maps, and ergodic control.
Nonlinear Analysis. Theory, Methods & Applications, 52(2):637-679, 2003.

2

M. Akian, R. Bapat, S. Gaubert,
``Max-plus algebras'',
in: Handbook of Linear Algebra, L. Hogben, R. Brualdi, A. Greenbaum, and R. Mathias (editors),
Chapman & Hall, 2006 (in press).

3

F. Baccelli, G. Cohen, G.-J. Olsder, and J.-P. Quadrat.
Synchronization and linearity : an algebra for discrete events systems.
New-York, 1992.

4

G. Cohen, S. Gaubert, and J.-P. Quadrat.
Duality and separation theorems in idempotent semimodules.
Linear Algebra and Appl., 379:395-422, 2004.

5

S. Gaubert and J. Gunawardena.
The Perron-Frobenius theorem for homogeneous, monotone functions.
Trans. of the AMS, 356(12):4931-4950, 2004.

6

V. N. Kolokoltsov and V. P. Maslov.
Idempotent analysis and applications.
Kluwer Acad. Publisher, 1997.

7

V. P. Maslov and S. N. Samborski ${\u{\i\/}}\kern.15em$ .
Idempotent analysis, volume 13 of Advances In Soviet Mathematics.
Amer. Math. Soc., Providence, 1992.

8

R. D. Nussbaum.
Hilbert's projective metric and iterated nonlinear maps.
Memoirs of the AMS, 75(391), 1988.

À propos de ce document...

Algèbre max-plus et théorie de Perron-Frobenius non-linéaire appliquées au contrôle optimal et aux jeux

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

The command line arguments were:
latex2html -split 0 courssg2

The translation was initiated by Stephane Gaubert on 2007-04-22

Notes

... Gaubert ¹: INRIA, Domaine de Voluceau, 78153 Le Chesnay Cédex. Stephane.Gaubert@inria.fr

Stephane Gaubert 2007-04-22