This paper analyses the implementation of the generalized finite differences method for the HJB equation of stochastic control, introduced by two of the authors in [Bonnans and Zidani, SIAM J. Numer. Anal. 41 (2003) 1008-1021]. The computation of coefficients needs to solve at each point of the grid (and for each control) a linear programming problem. We show here that, for two dimensional problems, this linear programming problem can be solved in operations, where is the size of the stencil. The method is based on a walk on the Stern-Brocot tree, and on the related filling of the set of positive semidefinite matrices of size two.
Mots clés : stochastic control, finite differences, viscosity solutions, consistency, HJB equation, Stern-Brocot tree
@article{M2AN_2004__38_4_723_0, author = {Bonnans, J. Fr\'ed\'eric and Ottenwaelter, \'Elisabeth and Zidani, Housnaa}, title = {A fast algorithm for the two dimensional {HJB} equation of stochastic control}, journal = {ESAIM: Mod\'elisation math\'ematique et analyse num\'erique}, pages = {723--735}, publisher = {EDP-Sciences}, volume = {38}, number = {4}, year = {2004}, doi = {10.1051/m2an:2004034}, mrnumber = {2087732}, zbl = {1130.93433}, language = {en}, url = {http://www.numdam.org/articles/10.1051/m2an:2004034/} }
TY - JOUR AU - Bonnans, J. Frédéric AU - Ottenwaelter, Élisabeth AU - Zidani, Housnaa TI - A fast algorithm for the two dimensional HJB equation of stochastic control JO - ESAIM: Modélisation mathématique et analyse numérique PY - 2004 SP - 723 EP - 735 VL - 38 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/m2an:2004034/ DO - 10.1051/m2an:2004034 LA - en ID - M2AN_2004__38_4_723_0 ER -
%0 Journal Article %A Bonnans, J. Frédéric %A Ottenwaelter, Élisabeth %A Zidani, Housnaa %T A fast algorithm for the two dimensional HJB equation of stochastic control %J ESAIM: Modélisation mathématique et analyse numérique %D 2004 %P 723-735 %V 38 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/m2an:2004034/ %R 10.1051/m2an:2004034 %G en %F M2AN_2004__38_4_723_0
Bonnans, J. Frédéric; Ottenwaelter, Élisabeth; Zidani, Housnaa. A fast algorithm for the two dimensional HJB equation of stochastic control. ESAIM: Modélisation mathématique et analyse numérique, Tome 38 (2004) no. 4, pp. 723-735. doi : 10.1051/m2an:2004034. http://www.numdam.org/articles/10.1051/m2an:2004034/
[1] On the convergence rate of approximation schemes for Hamilton-Jacobi-Bellman equations. ESAIM: M2AN 36 (2002) 33-54. | Numdam | Zbl
and ,[2] Error bounds for monotone approximation schemes for Hamilton-Jacobi-Bellman equations (to appear). | MR | Zbl
and ,[3] Convergence of approximation schemes for fully nonlinear second order equations. Asymptotic Analysis 4 (1991) 271-283. | Zbl
and ,[4] Consistency of generalized finite difference schemes for the stochastic HJB equation. SIAM J. Numer. Anal. 41 (2003) 1008-1021. | Zbl
and ,[5] A fast algorithm for the two dimensional HJB equation of stochastic control. Technical report, INRIA (2004). Rapport de Recherche 5078.
, and ,[6] An approximation scheme for the optimal control of diffusion processes. RAIRO Modél. Math. Anal. Numér. 29 (1995) 97-122. | Numdam | Zbl
and ,[7] Controlled Markov processes and viscosity solutions. Springer, New York (1993). | MR | Zbl
and ,[8] Concrete Mathematics, A Foundation For Computer Science. Addison-Wesley, Reading, MA (1994). Second edition. | MR | Zbl
, and ,[9] Continuous dependence estimates for viscosity solutions of fully nonlinear degenerate parabolic equations. J. Differ. Equations 183 (2002) 497-525. | Zbl
and ,[10] On the rate of convergence of finite-difference approximations for Bellman's equations with variable coefficients. Probab. Theory Related Fields 117 (2000) 1-16. | Zbl
,[11] Probability methods for approximations in stochastic control and for elliptic equations. Academic Press, New York (1977). Math. Sci. Engrg. 129. | MR | Zbl
,[12] Numerical methods for stochastic control problems in continuous time. Springer, New York, Appl. Math. 24 (2001). Second edition. | MR | Zbl
and ,[13] Optimal control of diffusion processes and Hamilton-Jacobi-Bellman equations. Part 2: Viscosity solutions and uniqueness. Comm. Partial Differential Equations 8 (1983) 1229-1276. | Zbl
,[14] Approximation numérique des équations de Hamilton-Jacobi-Bellman. RAIRO Anal. Numér. 14 (1980) 369-393. | Numdam | Zbl
and ,[15] Some estimates for finite difference approximations. SIAM J. Control Optim. 27 (1989) 579-607. | Zbl
,Cité par Sources :