Tropical linear-fractional programming and parametric mean payoff games

DOI10.1016/J.JSC.2011.12.049zbMATH Open1270.90081arXiv1101.3431OpenAlexW2088418904MaRDI QIDQ435971FDOQ435971

Authors: Stéphane Gaubert, Ricardo D. Katz, Sergey M. Sergeev 

Publication date: 13 July 2012

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: Tropical polyhedra have been recently used to represent disjunctive invariants in static analysis. To handle larger instances, tropical analogues of classical linear programming results need to be developed. This motivation leads us to study the tropical analogue of the classical linear-fractional programming problem. We construct an associated parametric mean payoff game problem, and show that the optimality of a given point, or the unboundedness of the problem, can be certified by exhibiting a strategy for one of the players having certain infinitesimal properties (involving the value of the game and its derivative) that we characterize combinatorially. We use this idea to design a Newton-like algorithm to solve tropical linear-fractional programming problems, by reduction to a sequence of auxiliary mean payoff game problems.

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

Recommendations

• Tropical polyhedra are equivalent to mean payoff games
• Tropical polar cones, hypergraph transversals, and mean payoff games
• The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average
• On tropical fractional linear programming
• Linear Programming Polytope and Algorithm for Mean Payoff Games

zbMATH Keywords

linear programmingLagrange multipliersoptimal strategiestropical algebralinear-fractional programmingmean payoff gamesNewton iterations

Mathematics Subject Classification ID

Fractional programming (90C32) 2-person games (91A05)

Cites Work

• The complexity of mean payoff games on graphs
• Tropical convexity
• Max-linear systems. Theory and algorithms.
• Title not available (Why is that?)
• The tropical analogue of polar cones
• Tropical polar cones, hypergraph transversals, and mean payoff games
• Linear and combinatorial optimization in ordered algebraic structures
• The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
• Tropical polyhedra are equivalent to mean payoff games
• Introduction to max-linear programming
• Max-Plus $(A,B)$-Invariant Spaces and Control of Timed Discrete-Event Systems
• Duality and separation theorems in idempotent semimodules.
• Tropical halfspaces
• Idempotent functional analysis: An algebraic approach
• Title not available (Why is that?)
• Methods and applications of (max,+) linear algebra
• Positional strategies for mean payoff games
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Scheduling with AND/OR Precedence Constraints
• Stochastic Games with Perfect Information and Time Average Payoff
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Invariant Half-Lines of Nonexpansive Piecewise-Linear Transformations
• The duality theorem for min-max functions
• A constructive fixed point theorem for min-max functions
• Computer Aided Verification
• Static Analysis by Policy Iteration on Relational Domains
• -convexity
• Title not available (Why is that?)
• Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations
• Inferring Min and Max Invariants Using Max-Plus Polyhedra
• Coupling policy iteration with semi-definite relaxation to compute accurate numerical invariants in static analysis
• Precise Relational Invariants Through Strategy Iteration
• Title not available (Why is that?)
• The Max-Atom Problem and Its Relevance
• Title not available (Why is that?)
• Verification, Model Checking, and Abstract Interpretation
• Verification, Model Checking, and Abstract Interpretation
• The number of extreme points of tropical polyhedra
• Hard problems in max-algebra, control theory, hypergraphs and other areas

Cited In (27)

• On tropical fractional linear programming
• Algebraic solutions of tropical optimization problems
• A multidimensional tropical optimization problem with a non-linear objective function and linear constraints
• On the integer max-linear programming problem
• Steady states in the scheduling of discrete-time systems
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• A note on tropical linear and integer programs
• Minimizing maximum lateness in two-stage projects by tropical optimization
• Complete solution of tropical vector inequalities using matrix sparsification.
• Locally and globally optimal solutions of global optimisation for max-plus linear systems
• Tropical pseudolinear and pseudoquadratic optimization as parametric mean-payoff games
• The level set method for the two-sided max-plus eigenproblem
• Weak dual residuations applied to tropical linear equations
• On \(2 \times 2\) tropical commuting matrices
• On two-sided max-linear equations
• Max-plus approximation for reinforcement learning
• Tropical linear algebra with the Łukasiewicz t-norm
• Eigenvalue methods for sparse tropical polynomial systems
• Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
• Solution of a tropical optimization problem with linear constraints
• Tropical Complementarity Problems and Nash Equilibria
• On special cases of the generalized max-plus eigenproblem
• Tropicalizing the Simplex Algorithm
• Approximately global optimal control for max-plus linear systems and its application on load distribution
• Tropical optimization problems with application to project scheduling with minimum makespan
• On integer images of max-plus linear mappings
• A strongly polynomial method for solving integer max-linear optimization problems in a generic case

This page was built for publication: Tropical linear-fractional programming and parametric mean payoff games

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