Computing the smallest fixed point of order-preserving nonexpansive mappings arising in positive stochastic games and static analysis of programs - Centre de mathématiques appliquées (CMAP) Accéder directement au contenu
Article Dans Une Revue Journal of Mathematical Analysis and Applications Année : 2014

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

Résumé

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.
Fichier principal
Vignette du fichier
0806.1160.pdf (468.23 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-00940804 , version 1 (11-02-2024)

Identifiants

Citer

Assalé Adjé, Stéphane Gaubert, Eric Goubault. Computing the smallest fixed point of order-preserving nonexpansive mappings arising in positive stochastic games and static analysis of programs. Journal of Mathematical Analysis and Applications, 2014, 410, pp.227-240. ⟨10.1016/j.jmaa.2013.07.076⟩. ⟨hal-00940804⟩
229 Consultations
2 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More