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.

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(p max ) 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.

DOI : 10.1051/m2an:2004034
Classification : 49L99, 93E20
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] G. Barles and E.R. Jakobsen, On the convergence rate of approximation schemes for Hamilton-Jacobi-Bellman equations. ESAIM: M2AN 36 (2002) 33-54. | Numdam | Zbl

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

[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. | Numdam | Zbl

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

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

[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. | MR | Zbl

[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. | MR | Zbl

[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. | Numdam | Zbl

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

Cité par Sources :