Bounds on the fixed point of a monotone contraction operator (Q579144)

From MaRDI portal
Revision as of 17:21, 1 July 2023 by Importer (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
Bounds on the fixed point of a monotone contraction operator
scientific article

    Statements

    Bounds on the fixed point of a monotone contraction operator (English)
    0 references
    0 references
    1987
    0 references
    This paper considers the solution to the following fixed point equation governing infinite horizon Markovian decision processes: \[ x^*_ i=\max_{k\in A(i)}[a^ k_ i+\sum^{N}_{t=1}M^ k_{it}x^*_ t]=f(x^*)_ i,\quad 1\leq i\leq N. \] The generally imposed condition is that \(\rho ([M_{ij}^{k(i)}])<1\), for all the possible probability transition matrices obtainable for any stationary pure Markov decision rule, and \(\rho\) is the spectral radius of the probability transition matrix. The main results are in Theorem 1. These results include the following: (i) The set \[ Y=\{y\in E^ N: y_ i>\sum^{N}_{t=1}M^ k_{it}y_ t,\quad \forall \quad k\in A(i),\quad 1\leq i\leq N\} \] is nonempty, and \(y>0\), \(\forall\) \(y\in Y\). (ii) f is a contraction mapping with modulus \(\lambda\) (y) for each norm \(\| u\|_ y\equiv \max_{1\leq i\leq N}[| u_ i| /y_ i]\), where \[ \lambda (y)\equiv \max_{i,k}[\Sigma_ tM^ k_{it}\quad y_ t/y_ i]<1. \] (iii) If \(x\in E^ N\), \(y\in Y\), then: \[ ^ y_ i\min_{1\leq j\leq N}\max_{k\in A(j)}\frac{P(j,k)}{Q(j,k)}\leq x^*_ i-x_ i\leq y_ i\max_{1\leq j\leq N}\max_{k\in A(j)}\frac{P(j,k)}{Q(j,k)},\quad where \] \[ P(j,k)=a^ k_ j+\sum^{N}_{t=1}M^ k_{jt}x_ t-x_ j\quad and\quad Q(j,k)=y_ j-\sum^{N}_{t=1}M_{jt}y_ t. \] The paper also introduces subgradient ideas. Thus y is a subgradient for f, if there exist numbers \(\{c_{ti}\}\), \(0\leq c_{ti}<1\), for all t, i, such that for all w, \(z\in E^ N\) \[ f(w+z)_ i\leq f(w)_ i+c_{ti}y_ i\max_{1\leq k\leq N}[z_ k/y_ k],\quad 1\leq i\leq N \] where \(t=1\) if \(\max_{k}[z_ k]\geq 0\), \(t=2\) if \(\max [z_ k]<0\). The paper then shows that if \(x\in E^ N\) \(y_ i\min_{1\leq j\leq N}\min_{t=1,2}\frac{R(j,t)}{S(j,t)}\leq x^*_ i-x_ i\leq y_ i\max_{1\leq j\leq N}\max_{t=1,2}\frac{R(j,t)}{S(j,t)},\) where \[ R(j,t)=f(x_ j)-x_ j\quad and\quad S(j,t)=y_ j(1-c_{tj}). \] Special cases of \(\{c_{tj}\}\) exist in terms of \(y\in Y\). The remainder of the paper gives some specializations, additional properties, some consideration of semi-Markov decision processes, and nonsymmetric bounds.
    0 references
    upper and lower variational bounds
    0 references
    fixed point
    0 references
    monotone contraction operator
    0 references
    infinite horizon Markovian decision processes
    0 references

    Identifiers