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.076zbMATH Open1309.47057arXiv0806.1160OpenAlexW2076783467MaRDI QIDQ2260413FDOQ2260413

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)

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.

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

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

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)

Cites Work

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