Solving generic nonarchimedean semidefinite programs using stochastic game algorithms
arXiv:1603.06916 · doi:10.1016/j.jsc.2017.07.002
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. Our approach is based on tropical geometry. It relies on tropical spectrahedra, which are defined as the images by the valuation of nonarchimedean spectrahedra. We establish a correspondence between generic tropical spectrahedra and zero-sum stochastic games with perfect information. The latter 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.
arXiv commentv1: 25 pages, 4 figures; v2: 27 pages, 4 figures, minor revisions + benchmarks added; v3: 30 pages, 6 figures, generalization to non-Metzler sign patterns + some results have been replaced by references to the companion work arXiv:1610.06746
References in corpus (7)
- Tropical polyhedra are equivalent to mean payoff games
- Tropicalizing the simplex algorithm
- Hyperfields for Tropical Geometry I. Hyperfields and dequantization
- Minimal half-spaces and external representation of tropical polyhedra
- On the Turing model complexity of interior point methods for semidefinite programming
- Tropical spectrahedra
- Tropicalizing the positive semidefinite cone
Cited by in corpus (7)
- Tropical spectrahedra
- Tropical totally positive matrices
- The tropical analogue of the Helton-Nie conjecture is true
- Symmetric Polynomials in Tropical Algebra Semirings
- Spectral inequalities for nonnegative tensors and their tropical analogues
- Convex geometry over ordered hyperfields
- Condition numbers of stochastic mean payoff games and what they say about nonarchimedean semidefinite programming