×

zbMATH — the first resource for mathematics

A fast algorithm for the two dimensional HJB equation of stochastic control. (English) Zbl 1130.93433
Summary: 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, 1008–1021 (2003; Zbl 1130.49307)]. 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.

MSC:
93E20 Optimal stochastic control
49L25 Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games
65M06 Finite difference methods for initial value and initial-boundary value problems involving PDEs
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML
References:
[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 · Zbl 0998.65067 · doi:10.1051/m2an:2002002 · numdam:M2AN_2002__36_1_33_0 · eudml:194095
[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 · Zbl 1092.65077 · doi:10.1137/S003614290343815X
[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 · 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 · Zbl 1130.49307 · doi:10.1137/S0036142901387336
[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. · Zbl 1130.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 . Numdam | Zbl 0822.65044 · Zbl 0822.65044 · eudml:193769
[7] W.H. Fleming and H.M. Soner , Controlled Markov processes and viscosity solutions . Springer, New York ( 1993 ). MR 1199811 | Zbl 0773.60070 · 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 · 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 · Zbl 1086.35061 · doi:10.1006/jdeq.2001.4136
[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 · Zbl 0971.65081 · doi:10.1007/s004409900044
[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 · 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 · 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 · Zbl 0716.49023 · doi:10.1080/03605308308820301
[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 · Zbl 0469.65041 · eudml:193367
[15] J.-L. Menaldi , Some estimates for finite difference approximations . SIAM J. Control Optim. 27 ( 1989 ) 579 - 607 . Zbl 0684.93088 · Zbl 0684.93088 · doi:10.1137/0327031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.