Solving Generic Nonarchimedean Semidefinite Programs Using Stochastic Game Algorithms

Xavier Allamigeon 1, 2 Stéphane Gaubert 1, 2 Mateusz Skomra 1, 2
1 TROPICAL - TROPICAL
Inria Saclay - Ile de France
2 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
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.
Type de document :
Communication dans un congrès
ISSAC '16: International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, France. Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC 2017), Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC'16). 〈10.1145/2930889.2930935〉
Liste complète des métadonnées
https://hal.inria.fr/hal-01422638
Contributeur : Stephane Gaubert <>
Soumis le : lundi 26 décembre 2016 - 15:13:46
Dernière modification le : jeudi 10 mai 2018 - 02:04:26

Lien texte intégral

arxiv

Identifiants

Collections

X | INSMI | TDS-MACS | CMAP | INRIA | X-CMAP | PARISTECH | UNIV-PARIS-SACLAY | X-DEP-MATHA

Citation

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, Jul 2016, Waterloo, France. Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC 2017), Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC'16). 〈10.1145/2930889.2930935〉. 〈hal-01422638〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

620

Contact


archive-ouverte@inria.fr