Mathematics Computer Science Seminar
INRIA and CMAP, Echole Polytechinique
Condition numbers in nonarchimedean semidefinite programming and what they say about stochastic mean payoff games
Abstract: Semidefinite programming consists in optimizing a linear form over a spectrahedron, the latter being a cross section of the cone of positive semidefinite matrices. This makes sense over any real closed field, and in particular, over fields of real Puiseux series, equipped with their non archimedean valuation. In this way, a tropical spectrahedron can be defined as the image by the valuation of a nonarchimedean spectrahedron. The nonarchimedean semidefinite feasibility problem, with generic valuations of the input matrices, turns out to be equivalent to stochastic mean payoff games with perfect information. Solving the latter is a known problem in algorithmic game theory. It has an unsettled complexity, but a number of experimentally efficient algorithms have been developed. We used such stochastic games algorithms to solve generic nonarchimedean semidefinite problems. We will show that, conversely, one can infer complexity bounds for stochastic games from their tropical formulation. To do so, we develop a metric geometry approach of nonarchimedean semidefinite programming. We use the value of a stochastic mean payoff game to define a nonarchimedean condition number. The latter measures the distance to unfeasibility, for a feasible instance, and vice versa. This condition number coincides with the inverse of the maximal radius of a ball included in the primal or dual feasible set. Here, the radius is measured in Hilbert's projective metric, the canonical metric of tropical convexity. The time needed to decide the winner of a stochastic mean payoff game can be bounded in terms of the condition number and of an auxiliary metric estimate. In this way, we obtain parametrized complexity bounds for several classes of games. The results on nonarchimedean conditions numbers are from a current work with Allamigeon, Katz, and Skomra, arXiv:1802.07712, based on earlier work with Allamigeon and Skomra, arXiv:1603.06916 (J. Symb. Comp.), arXiv:1610.06746 and arXiv:1801.02089.
Wednesday May 23, 2018 at 2:00 PM in SEO 427