Solving generic nonarchimedean semidefinite programs using stochastic game algorithms

DOI10.1145/2930889.2930935zbMATH Open1379.90021arXiv1603.06916OpenAlexW2308402890MaRDI QIDQ2409007FDOQ2409007

Mateusz Skomra, Stéphane Gaubert, Xavier Allamigeon

Publication date: 10 October 2017

Published in: Journal of Symbolic Computation, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1603.06916

zbMATH Keywords

semidefinite programmingtropical geometryPuiseux seriesspectrahedranon-Archimedean fieldsstochastic mean payoff gamesnonarchimedean fieldsstochastic zero-sum games

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Semidefinite programming (90C22) Stochastic games, stochastic differential games (91A15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of stochastic games
• The complexity of mean payoff games on graphs
• Max-linear Systems: Theory and Algorithms
• Ergodicity conditions for zero-sum games
• Linear independence over tropical semirings and beyond
• Geometric algorithms and combinatorial optimization.
• An exact duality theory for semidefinite programming and its complexity implications
• Tropical polyhedra are equivalent to mean payoff games
• Lattice-ordered Rings and Modules
• The real field with convergent generalized power series
• Semidefinite Optimization and Convex Algebraic Geometry
• Tropicalizing the positive semidefinite cone
• The hyperring of adèle classes
• On the Generation of Positivstellensatz Witnesses in Degenerate Cases
• The algebraic degree of semidefinite programming
• Convexity and log convexity for the spectral radius
• The Complexity of Solving Stochastic Games on Graphs
• Stochastic Games with Perfect Information and Time Average Payoff
• Approximation Algorithms and Semidefinite Programming
• Invariant Half-Lines of Nonexpansive Piecewise-Linear Transformations
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Optimal search for rationals
• Sums of squares of polynomials with rational coefficients
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
• Finding Optimal Strategies of Almost Acyclic Simple Stochastic Games
• Exact algorithms for linear matrix inequalities
• Solving generic nonarchimedean semidefinite programs using stochastic game algorithms
• Tropical spectrahedra
• On the Turing model complexity of interior point methods for semidefinite programming
• Solving rank-constrained semidefinite programs in exact arithmetic

Cited In (10)

• Tropical spectrahedra
• The tropical analogue of the Helton-Nie conjecture is true
• Exact algorithms for semidefinite programs with degenerate feasible set
• Symmetric polynomials in tropical algebra semirings
• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• Solving generic nonarchimedean semidefinite programs using stochastic game algorithms
• Spectral inequalities for nonnegative tensors and their tropical analogues
• Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect information
• Tropical totally positive matrices
• Tropical Complementarity Problems and Nash Equilibria

This page was built for publication: Solving generic nonarchimedean semidefinite programs using stochastic game algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409007)