Skip to Main content Skip to Navigation
Conference papers

Solving Generic Nonarchimedean Semidefinite Programs Using Stochastic Game Algorithms

Xavier Allamigeon 1, 2 Stéphane Gaubert 1, 2 Mateusz Skomra 1, 2
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
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.
Complete list of metadata
Contributor : Stephane Gaubert <>
Submitted on : Monday, December 26, 2016 - 3:13:46 PM
Last modification on : Tuesday, December 8, 2020 - 9:46:48 AM

Links full text




Xavier Allamigeon, Stéphane Gaubert, Mateusz Skomra. Solving Generic Nonarchimedean Semidefinite Programs Using Stochastic Game Algorithms. ISSAC '16: International Symposium on Symbolic and Algebraic Computation, ACM, Jul 2016, Waterloo, France. ⟨10.1145/2930889.2930935⟩. ⟨hal-01422638⟩



Record views