Nonarchimedean Convex Programming and Its Relation to Mean-Payoff Games

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

Authors

• Stéphane Gaubert

Keywords

No keywords are indexed for this paper.