Algèbre tropicale en optimisation et en jeux
Cours avancé, Majeure OJD, Année 2014-2015
Figure 1:
Un tétraédre tropical.
|
L'algèbre tropicale traite des structures dites de ``caractéristique un'', dans lesquelles l'addition est idempotente. Le semi-corps max-plus, qui est
l'ensemble des réels munis du maximum, vu comme une loi additive,
et de l'addition, vu comme une loi multiplicative, est l'exemple
le plus simple de structure tropicale. L'approche tropicale fournit
des outils de nature combinatoire ou algébrique pour aborder
le contrôle optimal, déterministe ou stochastique, et plus généralement
la théorie des jeux à somme nulle. Elle s'applique particulièrement
aux problèmes dits ``ergodiques'' ou en temps long,
dans lesquels ont s'intéresse
au revenu moyen par unité de temps
où à la croissance du revenu lorsque l'horizon
tend vers l'infini.
L'objet de ce cours est de présenter un certain nombre d'outils
et résultats récents, inspirés de la géométrie tropicale, relatifs aux problèmes de contrôle ou de jeux répétés, déterministes ou stochastiques, avec une attention particulière aux aspects combinatoires et algorithmiques. Certains résultats seront illustrés
par des exemples issus d'applications (optimisation du référencement,
optimisation de la croissance en dynamique de population).
Ce cours fait également appel à l'approche opératorielle
des jeux répétés, dans laquelle les opérateurs journaliers
de la programmation dynamique (opérateurs de Shapley) sont étudiés
du point de vue de la géométrie métrique,
en tant qu'applications non-expansives pour la norme sup.
Il développe enfin des techniques de théorie de Perron-Frobenius
non-linéaire, qui traite des systèmes dynamiques monotones,
les opérateurs de Shapley étant équivalents à des opérateurs
de Perron-Frobenius vus avec des ``lunettes logarithmique''.
Ce cours suppose peu de prè-requis, hormis
les bases d'optimisation (convexité, polyèdres)
ou d'analyse (théorie du point fixe), et les rappels nécessaires
sont systématiquement faits. Le cours est de nature
d'abord mathématique (recherche), cependant, il comprend une
composante notable d'algorithmique et de modélisation, qui peut intéresser les élèves motivés spécifiquement
par des applications de la recherche opérationnelle
(optimisation et jeux stochastiques).
Enfin, les techniques du cours relatives aux systèmes dynamiques monotones
peuvent intéresser les élèves s'orientant en dynamique de populations.
Semi-corps max-plus et autres semi-anneaux tropicaux.
Quelques problèmes où ces structures interviennent:
programmation dynamique; contrôle optimal
et équations d'Hamilton-Jacobi; problème
d'affectation optimale; problème du paiement
moyen pour les jeux répétés déterministes (l'un
des problèmes ayant une bonne caractérisation au sens d'Edmonds, NP coNP, mais non encore décidé); problèmes asymptotiques;
log-convexité de la transformée de Laplace;
tropicalisation de polynômes et généralisation
de la borne de Cauchy.
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.
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), optimisation du référencement,
dynamique des populations.
Opérateurs de Shapley comme limites d'opérateurs
de Perron-Frobenius (lunettes logarithmiques).
Métrique projective de Hilbert,
métrique de Thompson.
Problème spectral non-linéaire.
Généralisations non-linéaires du théorème de Perron-Frobenius:
questions d'existence et d'unicité du vecteur propre ergodique,
formule de Collatz-Wielandt pour le paiement moyen,
généralisations non-linéaires de l'algorithme de la puissance.
Algorithme d'itération sur les politiques pour les jeux.
Cas actualisé. L'itération sur les politiques
est fortement polynômiale si le taux d'actualisation
est fixé.
- ABG06
-
M. Akian, R. Bapat, and S. Gaubert.
Max-plus algebras.
In L. Hogben, editor, Handbook of Linear Algebra (Discrete
Mathematics and Its Applications), volume 39. Chapman & Hall/CRC, 2006.
Chapter 25, Available electronically from
http://www.cmap.polytechnique.fr/~gaubert/PAPERS/hla-preprint.pdf.
- AG03
-
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.
arXiv:math.SP/0110108.
- AG13
-
Marianne Akian and Stéphane Gaubert.
Policy iteration for perfect information stochastic mean payoff games
with bounded first return times is strongly polynomial, 2013.
arXiv:1310.4953.
- AGG12
-
M. Akian, S. Gaubert, and A. Guterman.
Tropical polyhedra are equivalent to mean payoff games.
International of Algebra and Computation, 22(1):125001 (43
pages), 2012.
arXiv:0912.2462,
doi:10.1142/S0218196711006674.
- AGN14
-
M. Akian, S. Gaubert, and R. Nussbaum.
Uniqueness of the fixed point of nonexpansive semidifferentiable
maps.
To appear in Trans. AMS., 2014.
arXiv:1201.1536.
- GG04
-
S. Gaubert and J. Gunawardena.
The Perron-Frobenius theorem for homogeneous, monotone functions.
Trans. of AMS, 356(12):4931-4950, 2004.
arXiv:math.FA/0105091, doi:10.1090/S0002-9947-04-03470-1.
- HMZ11
-
T.D. Hansen, P.B. Miltersen, and U. Zwick.
Strategy iteration is strongly polynomial for 2-player turn-based
stochastic games with a constant discount factor.
In Innovations in Computer Science 2011, pages 253-263.
Tsinghua University Press, 2011.
- IMS07
-
I. Itenberg, G. Mikhalkin, and E. Shustin.
Tropical algebraic geometry.
Oberwolfach seminars. Birkhäuser, 2007.
- Nus88
-
Roger D. Nussbaum.
Hilbert's projective metric and iterated nonlinear maps.
Memoirs of the AMS, 75(391), 1988.
- Vir01
-
O. Viro.
Dequantization of real algebraic geometry on logarithmic paper.
In European Congress of Mathematics, Vol. I (Barcelona, 2000),
volume 201 of Progr. Math., pages 135-146. Birkhäuser, Basel, 2001.
arXiv:math/0005163.
Algèbre tropicale en optimisation et en jeux
This document was generated using the
LaTeX2HTML translator Version 2008 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 coursodj
The translation was initiated by gaubert on 2014-06-27
Notes
- ... Gaubert1
- INRIA and CMAP, École Polytechnique, UMR CNRS 7641, 92128 Palaiseau Cedex. Stephane.Gaubert@inria.fr
gaubert
2014-06-27