×

zbMATH — the first resource for mathematics

Error estimation and adaptive discretization for the discrete stochastic Hamilton-Jacobi-Bellman equation. (English) Zbl 1074.65009
The dynamic programming method is a well known technique for the numerical solution of optimal control problems. Generalizing the technique and results from the deterministic case [cf. the author, ibid. 75, 319–337 (1997; Zbl 0880.65045)], the author obtains a posteriori error estimates for the space discretization of the stochastic Hamilton-Jacobi-Bellman equation. This method gives full global information about the optimal value function of the related stochastic optimal control problem. Therefore a feedback optimal control can be obtained.
It is also demonstrated that the a posteriori error estimates are efficient and reliable for the numerical approximation of PDEs and they allow to derive a bound for the numerical error corresponding to the derivatives. The asymptotic behavior of the error estimates with respect to the size of the grid elements is also investigated. Finally, an adaptive space discretization scheme is developed and numerical examples are presented.

MSC:
65C30 Numerical solutions to stochastic differential and integral equations
60H15 Stochastic partial differential equations (aspects of stochastic analysis)
60H35 Computational methods for stochastic equations (aspects of stochastic analysis)
49J55 Existence of optimal solutions to problems involving randomness
65K10 Numerical optimization and variational techniques
49M25 Discrete approximations in optimal control
65N15 Error bounds for boundary value problems involving PDEs
49L20 Dynamic programming in optimal control and differential games
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bardi, M., Dolcetta, I.C.: Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman equations. Birkh?user, Boston, 1997 · Zbl 0890.49011
[2] Barles, G., Jakobsen, E.R.: On the convergence rate of approximation schemes for Hamilton?Jacobi?Bellman equations. M2AN, Math. Model. Numer. Anal. 36, 33-54 (2002) · Zbl 0998.65067
[3] Bertsekas, D.P.: Dynamic Programming and Optimal Control. Vol. 1 and 2. Athena Scientific, Belmont, MA, 1995 · Zbl 0904.90170
[4] Camilli, F., Falcone, M.: An approximation scheme for the optimal control of diffusion processes. RAIRO, Mod?lisation Math. Anal. Num?r. 29, 97-122 (1995) · Zbl 0822.65044
[5] Camilli, F., Gr?ne, L.: Numerical approximation of the maximal solutions for a class of degenerate Hamilton?Jacobi equations. SIAM J. Numer. Anal. 38, 1540-1560 (2000) · Zbl 0988.65077 · doi:10.1137/S003614299834798X
[6] Camilli, F., Gr?ne, L.: Characterizing attraction probabilities via the stochastic Zubov equation. Discrete Contin. Dyn. Syst. Ser. B 3, 457-468 (2003) · Zbl 1123.60311 · doi:10.3934/dcdsb.2003.3.457
[7] Camilli, F., Gr?ne, L., Wirth, F.: A regularization of Zubov?s equation for robust domains of attraction. In: Nonlinear Control in the Year 2000, Volume 1, A. Isidori, F. Lamnabhi-Lagarrigue, and W. Respondek, eds. Lecture Notes in Control and Information Sciences 258, NCN, Springer Verlag, London, 2000, pp. 277-290
[8] Camilli, F., Gr?ne, L., Wirth, F.: Characterizing controllability probabilities of stochastic control systems via Zubov?s method. In: Proceedings of the 16th International Symposium on Mathematical Theory of Networks and Systems, Leuven, Belgium, 2004, CD-ROM, Paper No. 65
[9] Camilli, F., Loreti, P.: Zubov?s method for stochastic differential equations. NoDEA Nonlinear Differ. Equ. Appl., (2004), To appear · Zbl 1103.60057
[10] Carlini, E., Falcone, M., Ferretti, R.: An efficient algorithm for Hamilton?Jacobi equations in high dimensions. Comput. Vis. Sci. (2004), volume 7, pp. 15-29 · Zbl 1070.65072
[11] Colonius, F., Kliemann, W.: The Dynamics of Control. Birkh?user, Boston, 2000 · Zbl 1020.93500
[12] Crandall, M.G., Lions, P.L.: Viscosity solutions of Hamilton?Jacobi equations. Trans. Amer. Math. Soc. 277, 1-42 (1983) · Zbl 0599.35024 · doi:10.1090/S0002-9947-1983-0690039-8
[13] Daniel, J.W.: Splines and efficiency in dynamic programming. J. Math. Anal. Appl. 54, 402-407 (1976) · Zbl 0345.90041 · doi:10.1016/0022-247X(76)90209-2
[14] Falcone, M.: A numerical approach to the infinite horizon problem of deterministic control theory. Appl. Math. Optim. 15, 1-13 (1987); Corrigenda. ibid. 23, 213-214 (1991) · Zbl 0715.49023 · doi:10.1007/BF01442644
[15] Falcone, M., Ferretti, R., Manfroni, T.: Optimal discretization steps in semi-Lagrangian approximation of first-order PDEs. In: Numerical methods for viscosity solutions and applications, M. Falcone, C. Makridakis (eds.), vol. 59 of Ser. Adv. Math. Appl. Sci. World Scientific, Singapore, 2001, pp. 95-117 · Zbl 0988.65086
[16] Ferretti, R.: Convergence of semi-Lagrangian approximations to convex Hamilton-Jacobi equations under (very) large Courant numbers. SIAM J. Numer. Anal. 40, 2240-2253 (2003) · Zbl 1043.65106 · doi:10.1137/S0036142901388378
[17] Fleming, W.H., Soner, M.H.: Controlled Markov processes and viscosity solutions. Springer?Verlag, New York, 1993 · Zbl 0773.60070
[18] Franke, R., Terwiesch, P., Meyer, M.: Development of an algorithm for the optimal control of trains. In: Proceedings of the 39th IEEE Conference on Decision and Control, Sydney, Australia, 2000, pp. 2123-2128
[19] Gonz?lez, R.L.V., Sagastiz?bal, C.A.: Un algorithme pour la r?solution rapide d??quations discr?tes de Hamilton-Jacobi-Bellman. C. R. Acad. Sci. Paris, S?r. I 311, 45-50 (1990) · Zbl 0719.65053
[20] Gr?ne, L.: An adaptive grid scheme for the discrete Hamilton?Jacobi?Bellman equation. Numer. Math. 75, 319-337 (1997) · Zbl 0880.65045 · doi:10.1007/s002110050241
[21] Gr?ne, L.: Homogeneous state feedback stabilization of homogeneous systems. SIAM J. Control Optim. 38, 1288-1314 (2000) · Zbl 0958.93077 · doi:10.1137/S0363012998349303
[22] Gr?ne, L.: Adaptive grid generation for evolutive Hamilton?Jacobi?Bellman equations. In: Numerical methods for viscosity solutions and applications, M. Falcone and C. Makridakis, eds., vol. 59 of Ser. Adv. Math. Appl. Sci. World Scientific, Singapore, 2001, pp. 153-172 · Zbl 0988.65088
[23] Gr?ne, L.: Asymptotic Behavior of Dynamical and Control Systems under Perturbation and Discretization. Lecture Notes in Mathematics, Vol. 1783, Springer?Verlag, 2002 · Zbl 0991.37001
[24] Gr?ne, L., Metscher, M., Ohlberger, M.: On numerical algorithm and interactive visualization for optimal control problems. Comput. Vis. Sci. 1, 221-229 (1999) · Zbl 0970.65073 · doi:10.1007/s007910050020
[25] Gr?ne, L., Semmler, W.: Using dynamic programming with adaptive grid scheme for optimal control problems in economics. J. Econ. Dyn. Control (2004), To appear · Zbl 1202.49026
[26] Gr?ne, L., Semmler, W., Sieveking, M.: Creditworthyness and thresholds in a credit market model with multiple equilibria. Econ. Theory, (2005), pp. 287-315 · Zbl 1107.91361
[27] Kloeden, P.E., Platen, E.: Numerical Solution of Stochastic Differential Equations. Springer?Verlag, Heidelberg, 1992. (3rd revised and updated printing, 1999) · Zbl 0752.60043
[28] Kushner, H.J., Dupuis, P.G.: Numerical Methods for Stochastic Control Problems in Continuous Time. Applications of Mathematics, 24, Springer-Verlag, New York, 2nd ed. 2001 · Zbl 0968.93005
[29] Lions, P.L.: Generalized solutions of Hamilton-Jacobi equations. Pitman, London, 1982 · Zbl 0497.35001
[30] Menaldi, J.L.: Some estimates for finite difference approximations. SIAM J. Control Optim. 27, 579-607 (1989) · Zbl 0684.93088 · doi:10.1137/0327031
[31] Munos, R., Moore, A.: Variable resolution discretization in optimal control. Mach. Learn. (2002), pp. 291-323 · Zbl 1005.68086
[32] Reiter, M.: Solving higher?dimensional continuous?time stochastic control problems by value function regression. J. Econ. Dyn. Control 23, 1329-1353 (1999) · Zbl 0949.93080 · doi:10.1016/S0165-1889(98)00076-1
[33] Rust, J.: Numerical dynamic programming in economics. In: Handbook of Computational Economics, H.M. Amman, D.A. Kendrick, and J. Rust, eds. Elsevier, Amsterdam, 1996 · Zbl 1126.65316
[34] Rust, J.: Using randomization to break the curse of dimensionality. Econometrica, 65, 487-516 (1997) · Zbl 0872.90107 · doi:10.2307/2171751
[35] Sagona, M., Seghini, A.: An adaptive scheme on unstructured grids for the shape?from?shading problem. In: Numerical methods for viscosity solutions and applications. M. Falcone, C. Makridakis (eds.), vol. 59 of Ser. Adv. Math. Appl. Sci., World Scientific, Singapore, 2001 · Zbl 0988.65101
[36] Santos, M.S., Vigo-Aguiar, J.: Accuracy estimates for a numerical approach to stochastic growth models. Discussion Paper 107, Institute for Empirical Macroeconomics, Federal Reserve Bank of Minneapolis, December 1995
[37] Santos, M.S., Vigo-Aguiar, J.: Analysis of a numerical dynamic programming algorithm applied to economic models. Econometrica 66, 409-426 (1998) · Zbl 1010.90091 · doi:10.2307/2998564
[38] Seeck, A.: Iterative L?sungen der Hamilton-Jacobi-Bellman-Gleichung bei unendlichem Zeithorizont. Diplomarbeit, Universit?t Kiel, 1997
[39] Siebert, K.G.: An a posteriori error estimator for anisotropic refinement. Numer. Math. 73, 373-398 (1996) · Zbl 0873.65098 · doi:10.1007/s002110050197
[40] Trick, M.A., Zin, S.E.: Spline approximations to value functions: a linear programming approach. Macroecon. Dyn. 1, 255-277 (1997) · Zbl 0914.90209 · doi:10.1017/S1365100597002095
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.