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

详细信息    查看全文

• 作者：Assal¨¦ Adj¨¦ ; St¨¦phane Gaubert ; Eric Goubault
• 关键词：Positive stochastic games ; Policy iteration algorithm ; Negative discount ; Static analysis by abstract interpretation ; Nonexpansive mappings ; Semidifferentials ; Nonlinear spectral radius
• 刊名：Journal of Mathematical Analysis and Applications
• 出版年：2014
• 出版时间：1 February, 2014
• 年：2014
• 卷：410
• 期：1
• 页码：227-240
• 全文大小：393 K

文摘

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.