A policy iteration algorithm for fixed point problems with nonexpansive operators. (English) Zbl 1171.47051

Summary: The aim of this paper is to solve the fixed point problems:
\[ v = \mathcal{O} v, \quad \text{with}\quad \mathcal{O}v(x) \mathop{=}^{\text{def}} \max (Lv(x), Bv(x) ), \;x \in \mathcal E, \tag{1} \]
where \(\mathcal E\) is a finite set, \(L\) is contractive, \(B\) is a nonexpansive operator, and
\[ v = \mathcal{O} v,\quad \text{with}\quad \mathcal{O}v(x) \mathop{=}^{\text{def}} \max\left(\sup_{w \in \mathcal{W}} L^{w} v(x) ,\sup_{z \in \mathcal{Z}} B^{z} v(x)\right), \;x \in \mathcal E, \tag{2} \]
where \(\mathcal{W}\) and \(\mathcal{Z}\) are general control sets, the operators \(L^{w}\) are contractive and operators \(B^{z}\) are nonexpansive. For these two problems, we give conditions which imply the existence and uniqueness of a solution and provide a policy iteration algorithm which converges to the solution. The proofs are slightly different for the two problems since the set of controls is finite for (1) while that is not necessary the case for problem (2). Equation (2) typically arises in numerical analysis of quasivariational inequalities and variational inequalities associated to impulse or singular stochastic control.


47J25 Iterative procedures involving nonlinear operators
47H09 Contraction-type mappings, nonexpansive mappings, \(A\)-proper mappings, etc.
47H10 Fixed-point theorems
65J15 Numerical solutions to equations with nonlinear operators
49J40 Variational inequalities
Full Text: DOI


[1] Bertsekas DP (2001) Dynamic programming and optimal control, vol I and II. Athena Scientific, Belmont
[2] Chancelier J-Ph, Øksendal B, Sulem A (2002) Combined stochastic control and optimal stopping, and application to numerical approximation of combined stochastic and impulse control. In: Stochastic Financial Mathematics, Proceedings of Steklov Math. Inst., Moscou, vol. 237, editeur A.N. Shiryaev, pp 149 –173 2002 · Zbl 1014.91042
[3] Gaubert S, Gunawardena J (privately circuled draft) Existence of the cycle time for some subtopical functions
[4] Kushner HJ, Dupuis P (2001) Numerical methods for stochastic control problems in continuous time, 2nd edn. Springer, Berlin Heidelberg New York · Zbl 0968.93005
[5] Øksendal B, Sulem A (2005) Applied stochastic control of jump diffusions. Universitext. Springer, Berlin Heidelberg New York · Zbl 1074.93009
[6] Øksendal B, Sulem A (2002) Optimal consumption and portfolio with both fixed and proportional transaction costs. SIAM J Control Optim 40(6): 1765–1790 · Zbl 1102.91054
[7] Puterman ML (1994) Markov decision processes: discrete stochastics markov decision processes: Discrete Stochastics Dynamic Programming. Probability and Mathematical Statistics: applied probability and statistics section. Wiley, New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.