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.
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 11 janvier 2018 - 06:22:34

Lien texte intégral

Identifiants

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〉

Partager

Métriques

Consultations de la notice

531