Solving generic nonarchimedean semidefinite programs using stochastic game algorithms

DOI10.1016/j.jsc.2017.07.002zbMath1379.90021arXiv1603.06916OpenAlexW2308402890MaRDI QIDQ2409007

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)

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

zbMATH Keywords

semidefinite programmingPuiseux seriestropical geometryspectrahedranon-Archimedean fieldsstochastic mean payoff gamesnonarchimedean fieldsstochastic zero-sum games

Mathematics Subject Classification ID

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

Related Items (10)

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

Cites Work

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

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