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

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

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique (2004)

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

Abstract

top
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 m a x ) operations, where p m a x 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.

How to cite

top

Bonnans, 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. [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. [2] G. Barles and E.R. Jakobsen, Error bounds for monotone approximation schemes for Hamilton-Jacobi-Bellman equations (to appear). Zbl1092.65077MR2177879
  3. [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. [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. [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. [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. [7] W.H. Fleming and H.M. Soner, Controlled Markov processes and viscosity solutions. Springer, New York (1993). Zbl0773.60070MR1199811
  8. [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. [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. [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. [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. [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. [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. [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. [15] J.-L. Menaldi, Some estimates for finite difference approximations. SIAM J. Control Optim. 27 (1989) 579–607. Zbl0684.93088

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.