Tropical linear-fractional programming and parametric mean payoff games

DOI10.1016/J.JSC.2011.12.049MaRDI QIDQ435971zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

linear programmingLagrange multipliersoptimal strategiestropical algebralinear-fractional programmingmean payoff gamesNewton iterations

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(34)

• On tropical fractional linear programming
• Algebraic solutions of tropical optimization problems
• Tropical polar cones, hypergraph transversals, and mean payoff games
• A multidimensional tropical optimization problem with a non-linear objective function and linear constraints
• On the integer max-linear programming problem
• Using matrix sparsification to solve tropical linear vector equations
• Steady states in the scheduling of discrete-time systems
• A note on tropical linear and integer programs
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• Complete solution of tropical vector inequalities using matrix sparsification.
• Minimizing maximum lateness in two-stage projects by tropical optimization
• Locally and globally optimal solutions of global optimisation for max-plus linear systems
• Tropical pseudolinear and pseudoquadratic optimization as parametric mean-payoff games
• Tropicalizing the simplex algorithm
• The level set method for the two-sided max-plus eigenproblem
• On \(2 \times 2\) tropical commuting matrices
• Weak dual residuations applied to tropical linear equations
• On two-sided max-linear equations
• Max-plus approximation for reinforcement learning
• Tropical linear algebra with the Łukasiewicz t-norm
• Tropical polyhedra are equivalent to mean payoff games
• Eigenvalue methods for sparse tropical polynomial systems
• Characterization and algorithm for max-plus supereigenvector problem by parametric programming
• Solution of a tropical optimization problem with linear constraints
• Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
• Tropical Complementarity Problems and Nash Equilibria
• Signed tropicalization of polar cones
• On special cases of the generalized max-plus eigenproblem
• 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
• Weakly robust global optimization of max-plus linear systems with non-negative constraint sets and its application to optimizing time parameters in data transmission systems
• The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average
• 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)