Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations
Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations
复制标题
最小-最大-多项式方程组的单调逼近方法
DOI：
10.1007/978-3-540-70575-8_57
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
H. Seidl
中科院分区：
文献类型：
--
作者：
J. Esparza;Thomas Gawlitza;S. Kiefer;H. Seidl
研究了变量X1，…，X2，…，X3上的单调极小极大多项式方程组（min-max-MSPE），Xn始终具有形式为Xi= fi（X1，...，Xn），其中eachfi（X1，...，Xn）是由具有非负系数的多项式、最小和最大算子建立的表达式。计算min-max-MSPE的最小解的问题在递归随机博弈分析中自然存在[5，6，14]。Min-max-MSPE推广了文献[11，3]中牛顿法的收敛速度结果。本文提出了第一种近似计算min-max-MSPE最小解的方法，它们至少线性收敛，而第一种方法收敛快，第二种方法只需一步就可以得到最小解。此外，我们还计算了在递归随机博弈中希望最大化结果的局中人的最优位置策略。
A monotone system of min-max-polynomial equations(min-max-MSPE) over the variablesX1,...,Xnhas forevery iexactly one equation of the form Xi= fi(X1,...,Xn) where eachfi(X1,...,Xn) is an expression built up from polynomialswith non-negative coefficients, minimum- and maximum-operators. Thequestion of computing least solutions of min-max-MSPEs arisesnaturally in the analysis of recursive stochastic games[5,6,14]. Min-max-MSPEs generalize MSPEs for which convergencespeed results of Newton's method are established in [11,3]. Wepresent the first methods for approximatively computing leastsolutions of min-max-MSPEs which converge at least linearly.Whereas the first one converges faster, a single step of the secondmethod is cheaper. Furthermore, we computee-optimal positional strategies for the player whowants to maximize the outcome in a recursive stochastic game.