Calendar

Semidefinite programming (SDP) is a fundamental tool in convex and polynomial optimization. It consists in minimizing linear functions over spectrahedra (sets defined by linear matrix inequalities). In particular, SDP is a generalization of linear programming. In this talk, we discuss the nonarchimedean analogue of SDP, replacing the field of real numbers by the field of Puiseux series. Our methods rely on tropical geometry and, in particular, on the study of tropicalization of spectrahedra. We show that, under genericity conditions, tropical spectrahedra encode Shapley operators associated with stochastic mean payoff games. As a result, a large class of semidefinite feasibility problems defined over Puiseux series can be solved efficiently using combinatorial algorithms designed for stochastic games. Conversely, we use tropical spectrahedra to introduce a condition number for stochastic mean payoff games. We show that this conditioning controls the number of value iterations needed to decide whether a mean payoff game is winning. In particular, we obtain a pseudopolynomial bound for the complexity of value iteration provided that the number of random positions is fixed.
The talk is based on joint works with X. Allamigeon, S. Gaubert, and R. Katz.