BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Optimisation and Numerical Analysis Seminars
SUMMARY:Condition numbers in nonarchimedean semidefinite p
rogramming and what they say about stochastic mean
payoff games - Stephane Gaubert (INRIA and Ecole
Polytechnique\, France)
DTSTART:20190124T160000Z
DTEND:20190124T170000Z
UID:TALK3479AT
URL:/talk/index/3479
DESCRIPTION:Semidefinite programming consists in optimizing a
linear form over a spectrahedron\, the latter bein
g a cross section of the cone of positive semidefi
nite matrices. This makes sense over any real clos
ed field\, and in particular\, over fields of real
Puiseux series\, equipped with their non archimed
ean valuation. In this way\, a tropical spectrahed
ron can be defined as the image by the valuation o
f a nonarchimedean spectrahedron. The nonarchimede
an semidefinite feasibility problem\, with generic
valuations of the input matrices\, turns out to b
e equivalent to stochastic mean payoff games with
perfect information. We use this correspondence to
define a condition number for stochastic mean pay
off games\, which controls the ``rotundity'' of th
e associated tropical spectrahedra. We bound the c
omplexity of value iteration in terms of this cond
ition number\, and derive fixed parameter tractabi
lity results for stochastic mean payoff games\nwit
h perfect information. \n\nThis is a joint work wi
th Xavier Allamigeon\, Ricardo Katz and Mateusz Sk
omra.\n
LOCATION:Nuffield G17
CONTACT:Sergey Sergeev
END:VEVENT
END:VCALENDAR