@inproceedings{39d7d8872c1a4096bdff2eea9b05d792,
title = "Solving generic nonarchimedean semidefinite programs using stochastic game algorithms",
abstract = "A general issue in computational optimization is to develop combinatorial algorithms for semidefinite programming. We address this issue when the base field is nonarchimedean. We provide a solution for a class of semidefinite feasibility problems given by generic matrices with a Metzler-Type sign pattern. Our approach is based on tropical geometry. We define tropical spectrahedra as the images by the valuation of nonarchimedean spectrahedra, and provide an explicit description of the tropical spectrahedra arising from the aforementioned class of problems. We deduce that the tropical semidefinite feasibility problems obtained in this way are equivalent to stochastic mean payoff games, which have been well studied in algorithmic game theory. This allows us to solve nonarchimedean semidefinite feasibility problems using algorithms for stochastic games. These algorithms are of a combinatorial nature and work for large instances.",
author = "Xavier Allamigeon and St{\'e}phane Gaubert and Mateusz Skomra",
note = "Publisher Copyright: {\textcopyright} 2016 Copyright held by the owner/author(s).; 41st ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2016 ; Conference date: 20-07-2016 Through 22-07-2016",
year = "2016",
month = jul,
day = "20",
doi = "10.1145/2930889.2930935",
language = "English",
series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",
publisher = "Association for Computing Machinery",
pages = "31--38",
editor = "Markus Rosenkranz",
booktitle = "ISSAC 2016 - Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation",
}