Condition numbers in nonarchimedean semidefinite programming and what they say about stochastic mean payoff games

Add to your list(s) Download to your calendar using vCal

• Stephane Gaubert (INRIA and Ecole Polytechnique, France)
• Thursday 24 January 2019, 16:00-17:00
• Nuffield G17.

If you have a question about this talk, please contact Sergey Sergeev.

This talk is a part of the LMS Workshop on Tropical Mathematics and its Applications

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. We use this correspondence to define a condition number for stochastic mean payoff games, which controls the ``rotundity’’ of the associated tropical spectrahedra. We bound the complexity of value iteration in terms of this condition number, and derive fixed parameter tractability results for stochastic mean payoff games with perfect information.

This is a joint work with Xavier Allamigeon, Ricardo Katz and Mateusz Skomra.

This talk is part of the Optimisation and Numerical Analysis Seminars series.

This talk is included in these lists:

• Nuffield G17
• Optimisation and Numerical Analysis Seminars
• School of Mathematics events

Note that ex-directory lists are not shown.