Algèbre tropicale en optimisation et en jeux

S. Gaubert École Polytechnique

Pour obtenir des informations plus détaillées, merci de vous connnecter à http://www.cmap.polytechnique.fr/~gaubert/coursodjups/index.html

Support de cours :

Divers documents disponibles

Prérequis :

Analyse fonctionnelle élémentaire, analyse convexe

Objectifs de l'UE :

Ce cours présente 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 pour les problèmes de paiement moyen ou en temps long ainsi que pour les aspects combinatoires et algorithmiques. Certains résultats sont illustrés par des exemples issus d'applications (optimisation du référencement, optimisation de la croissance en dynamique de population).

Thèmes abordés :

Algèbre tropicale et structures de ``caractéristique un'' (semi-corps max-plus). Résolution de problèmes avec paiement moyen via des problèmes spectraux non-linéaires. Représentation des opérateurs de Shapley. Théorie de Perron-Frobenius non-linéaire, dynamiques monotones ou non-expansives. Existence du paiement moyen. Certificats de Collatz-Wielandt. Généralisation non-linéaire de l'algorithme de la puissance. Algorithmes d'itération sur les politiques. Résultats de complexité pour les jeux répétés.