Stéphane Gaubert - Tropical Convexity, Mean Payoff Games and Nonarchimedean Convex Programming
Channel: Institut des Hautes Études Scientifiques (IHÉS)
Date: 04/02/2021

Convex sets can be defined over ordered fields with a non-archimedean valuation. Then, tropical convex sets arise as images by the valuation of non-archimedean convex sets. The tropicalization of polyhedra and spectrahedra are of special in- terest, since they can be described in terms of deterministic and stochastic games with mean payoff. In that way, one gets a correspondence between classes of zero- sum games, with an unsettled complexity, and classes of semilagebraic convex op- timization problems over non-archimedean fields. We shall discuss applications of this correspondence, including a counter example concerning the complexity of interior point methods, and the fact that non-archimedean spectrahedra have precisely the same images by the valuation as convex semi-algebraic sets. This is based on works with Allamigeon, Benchimol, Joswig and Skomra.


Slides :
https://indico.math.cnrs.fr/event/6181/contributions/4956/attachments/2641/3349/slides_Gaubert_CAP20.pdf