×

zbMATH — the first resource for mathematics

An adaptive sparse grid semi-Lagrangian scheme for first order Hamilton-Jacobi Bellman equations. (English) Zbl 1269.65076
Summary: We propose a semi-Lagrangian scheme using a spatially adaptive sparse grid to deal with nonlinear time-dependent Hamilton-Jacobi Bellman equations. We focus in particular on front propagation models in higher dimensions which are related to control problems. We test the numerical efficiency of the method on several benchmark problems up to space dimension \(d=8\), and give evidence of convergence towards the exact viscosity solution. In addition, we study how the complexity and precision scale with the dimension of the problem.

MSC:
65M06 Finite difference methods for initial value and initial-boundary value problems involving PDEs
35F21 Hamilton-Jacobi equations
49L25 Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games
65M50 Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akian, M.; Gaubert, S.; Lakhoua, A., The MAX-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis, SIAM J. Control Optim., 47, 817-848, (2008) · Zbl 1157.49034
[2] Bardi, M., Capuzzo-Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Systems and Control: Foundations and Applications. Birkhäuser, Boston (1997) · Zbl 0890.49011
[3] Bungartz, H.-J.; Griebel, M., Sparse grids, Acta Numer., 13, 147-269, (2004) · Zbl 1122.65405
[4] Carlini, E.; Falcone, M.; Ferretti, R., An efficient algorithm for Hamilton-Jacobi equations in high dimensions, Comput. Vis. Sci., 7, 15-29, (2004) · Zbl 1070.65072
[5] Carlini, E.; Ferretti, R.; Russo, G., A weighted essentialy non oscillatory, large time-step scheme for Hamilton Jacobi equations, SIAM J. Sci. Comput., 27, 1071-1091, (2005) · Zbl 1105.65090
[6] Crandall, M.; Lions, P.-L., Two approximations of solutions of Hamilton Jacobi equations, Math. Comput., 43, 1-19, (1984) · Zbl 0556.65076
[7] Debrabant, K., Jakobsen, E.: Semi-Lagrangian approximation schemes for linear and Hamilton-Jacobi equations. Preprint · Zbl 1276.65050
[8] Faber, G.: Über stetige Funktionen. Math. Ann. 66, 81-94 (1909) · JFM 39.0455.02
[9] Falcone, M., A numerical approach to the infinite horizon problem of deterministic control theory, Appl. Math. Optim., 15, 1-13, (1987) · Zbl 0715.49023
[10] Falcone, M., Ferretti, R.: Semi-Lagrangian approximation schemes for linear and Hamilton-Jacobi equations, in preparation · Zbl 1335.65001
[11] Falcone, M.; Giorgi, T.; Loreti, P., Level sets of viscosity solutions: some applications to fronts and rendez-vous problems, SIAM J. Appl. Math., 54, 1335-1354, (1994) · Zbl 0808.49029
[12] Feuersänger, C.: Sparse grid methods for higher dimensional approximation. Dissertation, Institut für Numerische Simulation, Universität Bonn (2010)
[13] Godlewski, E., Raviart, P.-A.: Hyperbolic Systems of Conservation Laws. SMAI, Ellipses (1991) · Zbl 0768.35059
[14] Griebel, M.; Hackbusch, W. (ed.), A parallelizable and vectorizable multi-level algorithm on sparse grids, No. 31, 94-100, (1991), Braunschweig · Zbl 0741.65090
[15] Griebel, M., Adaptive sparse grid multilevel methods for elliptic PDEs based on finite differences, Computing, 61, 151-179, (1998) · Zbl 0918.65078
[16] Grüne, L., An adaptive grid scheme for the discrete Hamilton-Jacobi-Bellman equation, Numer. Math., 75, 319-337, (1997) · Zbl 0880.65045
[17] Heinecke, A.; Pflüger, D., Multi- and many-core data mining with adaptive sparse grids, 29:1-29:10, (2011), New York
[18] Hu, C.; Shu, S.-W., A discontinuous Galerkin finite element method for Hamilton-Jacobi equations, SIAM J. Sci. Comput., 21, 666-690, (1999) · Zbl 0946.65090
[19] Maslov, V.P.: Operational Methods. Mir, Moscow (1976). Translated from the Russian by V. Golo, N. Kulman and G. Voropaeva · Zbl 0449.47002
[20] Mitchell, I.; Bayen, A.; Tomlin, C., A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games, IEEE Trans. Autom. Control, 50, 947-957, (2005) · Zbl 1366.91022
[21] Mitchell, I.; Tomlin, C.; Krogh, B. (ed.); Lynch, E.N. (ed.), Level set methods for computation in hybrid systems, No. 1790, 310-323, (2000), New York · Zbl 0952.93006
[22] Osher, S.; Sethian, J.A., Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys., 79, 12-49, (1988) · Zbl 0659.65132
[23] Osher, S.; Shu, C.-W., High order essentially non-oscillatory schemes for Hamilton-Jacobi equations, SIAM J. Numer. Anal., 28, 907-922, (1991) · Zbl 0736.65066
[24] Pareigis, S.; Jordan, M.I. (ed.); Kearns, M.J. (ed.); Solla, S.A. (ed.), Adaptive choice of grid and time in reinforcement learning, (1997)
[25] Pflüger, D.: Spatially adaptive sparse grids for high-dimensional problems. Dissertation TU, München, Verlag Dr. Hut, München (Aug. 2010) · Zbl 1157.49034
[26] Smolyak, S.A., Quadrature and interpolation formulas for tensor products of certain classes of functions, Dokl. Akad. Nauk SSSR, 148, 1042-1043, (1963) · Zbl 0202.39901
[27] Yserentant, H., On the multi-level splitting of finite element spaces, Numer. Math., 49, 379-412, (1986) · Zbl 0608.65065
[28] Zenger, C.; Hackbusch, W. (ed.), Sparse grids, Kiel, 1990, Wiesbaden · Zbl 0763.65091
[29] Zhang, Y.-T.; Shu, C.-W., High order WENO schemes for Hamilton-Jacobi equations on triangular meshes, SIAM J. Sci. Comput., 24, 1005-1030, (2003) · Zbl 1034.65051
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.