A fast algorithm for the two dimensional HJB equation of stochastic control
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 38 (2004) no. 4, p. 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\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.

DOI : https://doi.org/10.1051/m2an:2004034
Classification:  49L99,  93E20
Keywords: 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: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
publisher = {EDP-Sciences},
volume = {38},
number = {4},
year = {2004},
pages = {723-735},
doi = {10.1051/m2an:2004034},
zbl = {1130.93433},
mrnumber = {2087732},
language = {en},
url = {http://www.numdam.org/item/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: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 38 (2004) no. 4, pp. 723-735. doi : 10.1051/m2an:2004034. http://www.numdam.org/item/M2AN_2004__38_4_723_0/

[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 0998.65067

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

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

[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 1130.49307

[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 0822.65044

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

[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 1397498 | Zbl 0668.00003

[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 1086.35061

[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 0971.65081

[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 469468 | Zbl 0547.93076

[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 1217486 | Zbl 0968.93005

[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 0716.49023

[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 0469.65041

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