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

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

- Volume: 38, Issue: 4, page 723-735
- ISSN: 0764-583X

## Access Full Article

top## Abstract

top## How to cite

topBonnans, J. Frédéric, Ottenwaelter, Élisabeth, and 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 38.4 (2004): 723-735. <http://eudml.org/doc/245261>.

@article{Bonnans2004,

abstract = {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.},

author = {Bonnans, J. Frédéric, Ottenwaelter, Élisabeth, Zidani, Housnaa},

journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique},

keywords = {stochastic control; finite differences; viscosity solutions; consistency; HJB equation; Stern-Brocot tree},

language = {eng},

number = {4},

pages = {723-735},

publisher = {EDP-Sciences},

title = {A fast algorithm for the two dimensional HJB equation of stochastic control},

url = {http://eudml.org/doc/245261},

volume = {38},

year = {2004},

}

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: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique

PY - 2004

PB - EDP-Sciences

VL - 38

IS - 4

SP - 723

EP - 735

AB - 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.

LA - eng

KW - stochastic control; finite differences; viscosity solutions; consistency; HJB equation; Stern-Brocot tree

UR - http://eudml.org/doc/245261

ER -

## References

top- [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. Zbl0998.65067
- [2] G. Barles and E.R. Jakobsen, Error bounds for monotone approximation schemes for Hamilton-Jacobi-Bellman equations (to appear). Zbl1092.65077MR2177879
- [3] G. Barles and P.E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations. Asymptotic Analysis 4 (1991) 271–283. Zbl0729.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. Zbl1130.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. Zbl1130.93433
- [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. Zbl0822.65044
- [7] W.H. Fleming and H.M. Soner, Controlled Markov processes and viscosity solutions. Springer, New York (1993). Zbl0773.60070MR1199811
- [8] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics, A Foundation For Computer Science. Addison-Wesley, Reading, MA (1994). Second edition. Zbl0668.00003MR1397498
- [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. Zbl1086.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. Zbl0971.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. Zbl0547.93076MR469468
- [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. Zbl0968.93005MR1217486
- [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. Zbl0716.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. Zbl0469.65041
- [15] J.-L. Menaldi, Some estimates for finite difference approximations. SIAM J. Control Optim. 27 (1989) 579–607. Zbl0684.93088

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.