A fast algorithm for the two dimensional HJB equation of stochastic control

Bonnans, J. Frédéric  ; Ottenwaelter, Élisabeth ; Zidani, Housnaa

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 38 (2004) no. 4, pp. 723-735.

Résumé

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 $O\left(p_{max}\right)$ operations, where $p_{max}$ 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.

Détail

DOI : 10.1051/m2an:2004034

Classification : 49L99, 93E20
Keywords: stochastic control, finite differences, viscosity solutions, consistency, HJB equation, Stern-Brocot tree

Bibliographie

[1] G. Barles and E.R. Jakobsen, On the convergence rate of approximation schemes for Hamilton-Jacobi-Bellman equations. ESAIM: M2AN 36 (2002) 33-54. | Zbl | mathdoc-id

[2] G. Barles and E.R. Jakobsen, Error bounds for monotone approximation schemes for Hamilton-Jacobi-Bellman equations (to appear). | Zbl | MR

[3] G. Barles and P.E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations. Asymptotic Analysis 4 (1991) 271-283. | Zbl

[4] J.F. Bonnans and H. Zidani, Consistency of generalized finite difference schemes for the stochastic HJB equation. SIAM J. Numer. Anal. 41 (2003) 1008-1021. | Zbl

[5] J.F. Bonnans, E. Ottenwaelter and H. Zidani, A fast algorithm for the two dimensional HJB equation of stochastic control. Technical report, INRIA (2004). Rapport de Recherche 5078.

[6] F. Camilli and M. Falcone, An approximation scheme for the optimal control of diffusion processes. RAIRO Modél. Math. Anal. Numér. 29 (1995) 97-122. | Zbl | mathdoc-id

[7] W.H. Fleming and H.M. Soner, Controlled Markov processes and viscosity solutions. Springer, New York (1993). | Zbl | MR

[8] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics, A Foundation For Computer Science. Addison-Wesley, Reading, MA (1994). Second edition. | Zbl | MR

[9] E.R. Jakobsen and K.H. Karlsen, Continuous dependence estimates for viscosity solutions of fully nonlinear degenerate parabolic equations. J. Differ. Equations 183 (2002) 497-525. | Zbl

[10] N.V. Krylov, 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] H.J. Kushner, Probability methods for approximations in stochastic control and for elliptic equations. Academic Press, New York (1977). Math. Sci. Engrg. 129. | Zbl | MR

[12] H.J. Kushner and P.G. Dupuis, Numerical methods for stochastic control problems in continuous time. Springer, New York, Appl. Math. 24 (2001). Second edition. | Zbl | MR

[13] P.-L. Lions, 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] P.-L. Lions and B. Mercier, Approximation numérique des équations de Hamilton-Jacobi-Bellman. RAIRO Anal. Numér. 14 (1980) 369-393. | Zbl | mathdoc-id

[15] J.-L. Menaldi, Some estimates for finite difference approximations. SIAM J. Control Optim. 27 (1989) 579-607. | Zbl