Prochain Séminaire

A+ A- Aa
Partager cette page :

le 28 mars 2019


Stéphane Gaubert

Jeudi 28 mars 2019 à 11h15
Stéphane Gaubert
CMAP, Ecole Polytechnique, Palaiseau, France
Titre : Nonarchimedean Convex Programming and Its Relation to Mean-Payoff Games

Résumé : Linear programming, and more generally convex semialgebraic programming, makes sense over any ordered nonarchimedean field, like a field of real Puiseux series. Nonarchimedean instances encode classical parametric instances of convex programs with a suitably large parameter. Tropical geometry allows one to study such instances by combinatorial means. In particular, it reveals that, under a genericity condition, solving a nonarchimedean feasibility problem is equivalent to deciding who the winner is in a mean payoff game. Indeed, nonarchimedean linear programs correspond to deterministic mean payoff games, whereas nonarchimedean semidefinite programs correspond to perfect information stochastic mean payoff games. In this way, one can apply methods from convex programming to mean payoff games, and vice versa. We will present here the main ideas and tools from tropical geometry developed in this approach, and illustrate them by two results: a counter example, with a family of linear programs, with large coefficients, for which log-barrier interior point methods have a non strongly polynomial behavior (they make a number of iterations exponential in the number of constraints and variables); a theorem transferring complexity results concerning pivoting methods in linear programming to mean payoff games.
This is based on a series of works with Allamigeon, Benchimol and Joswig, concerning the tropicalization of the central path and of pivoting methods, and with Allamigeon and Skomra, for the tropicalization of semidefinite programming.

Partager cette page :

Mise à jour le 25 mars 2019