Computing the smallest fixed point of order-preserving nonexpansive mappings arising in positive stochastic games and static analysis of programs

DOI10.1016/J.JMAA.2013.07.076MaRDI QIDQ2260413zbMATH OpenOpenAlexFDO

Authors Assalé Adjé, Stéphane Gaubert, Éric Goubault

Publication date 10 March 2015

Published in Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

nonexpansive mappingspolicy iteration algorithmsemidifferentialsnegative discountnonlinear spectral radiuspositive stochastic gamesstatic analysis by abstract interpretation

Mathematics Subject Classification ID

Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Fixed-point theorems (47H10) Iterative procedures involving nonlinear operators (47J25) Stochastic games, stochastic differential games (91A15) Monotone and positive operators on ordered Banach spaces or other ordered topological vector spaces (47H07)

Abstract: The problem of computing the smallest fixed point of an order-preserving map arises in the study of zero-sum positive stochastic games. It also arises in static analysis of programs by abstract interpretation. In this context, the discount rate may be negative. We characterize the minimality of a fixed point in terms of the nonlinear spectral radius of a certain semidifferential. We apply this characterization to design a policy iteration algorithm, which applies to the case of finite state and action spaces. The algorithm returns a locally minimal fixed point, which turns out to be globally minimal when the discount rate is nonnegative.

Recommendations

• Computer Aided Verification
• scientific article; zbMATH DE number 18885
• Computing the least fixed point of positive polynomial systems
• Uniqueness of the fixed point of nonexpansive semidifferentiable maps
• COMPUTING LEAST FIXED POINTS OF PROBABILISTIC SYSTEMS OF POLYNOMIALS

Cites work

• scientific article; zbMATH DE number 1134975 (Why is no real title available?)
• scientific article; zbMATH DE number 2067976 (Why is no real title available?)
• A first course on zero-sum repeated games
• Abstract interpretation meets convex optimization
• Accelerated Data-Flow Analysis
• Acceleration in Convex Data-Flow Analysis
• An operator approach to zero-sum repeated games
• Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations
• Computer Aided Verification
• Computing relaxed abstract semantics w.r.t. quadratic zones precisely
• Convexity and log convexity for the spectral radius
• Eigenvalues for a class of homogeneous cone maps arising from max-plus operators
• Eigenvalues of dynamic max-min systems
• Evolution equations in discrete and continuous time for nonexpansive operators in Banach spaces
• Hilbert’s projective metric and iterated nonlinear maps
• Max-min representation of piecewise linear functions
• Min-max functions
• On the existence of a limit value in some nonexpansive optimal control problems
• Precise Fixpoint Computation Through Strategy Iteration
• Spectral theorem for convex monotone homogeneous maps, and ergodic control
• Stability and convergence in discrete convex monotone dynamical systems
• Static Analysis by Policy Iteration on Relational Domains
• The Perron-Frobenius theorem for homogeneous, monotone functions
• Tropical polyhedra are equivalent to mean payoff games
• Uniqueness of the fixed point of nonexpansive semidifferentiable maps
• Variational Analysis

Cited in

(5)

• Policy iteration in finite templates domain
• Template-based unbounded time verification of affine hybrid automata
• Template polyhedra and bilinear optimization
• Static analysis by abstract interpretation: a mathematical programming approach
• Improving strategies via SMT solving

This page was built for publication: Computing the smallest fixed point of order-preserving nonexpansive mappings arising in positive stochastic games and static analysis of programs

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