Algèbre tropicale en optimisation et en jeux

Stéphane Gaubert1

Cours avancé, Majeure OJD, Année 2014-2015


Figure 1: Un tétraédre tropical.
Image cyclic-nolabel
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.

Introduction

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 $\cap$ 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.

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

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 ergodique, formule de Collatz-Wielandt pour le paiement moyen, généralisations non-linéaires de l'algorithme de la puissance.

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

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

Examens des années précédentes

Documents

Bibliographie

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.

À propos de ce document...

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