Mathematics Computer Science Seminar
Stephane Gaubert
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