nach oben

Journal of Scientific Computing

Erschienen in:

01.06.2013

An Adaptive Sparse Grid Semi-Lagrangian Scheme for First Order Hamilton-Jacobi Bellman Equations

verfasst von: Olivier Bokanowski, Jochen Garcke, Michael Griebel, Irene Klompmaker

Erschienen in: Journal of Scientific Computing | Ausgabe 3/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We propose a semi-Lagrangian scheme using a spatially adaptive sparse grid to deal with non-linear 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.

Vorheriger Artikel Dispersion and Dissipation Errors of Two Fully Discrete Discontinuous Galerkin Methods

Nächster Artikel WENO Schemes and Their Application as Limiters for RKDG Methods Based on Trigonometric Approximation Spaces

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

We call a discrete space \(V_{\underline{k}}\) smaller than a space \(V_{\underline{l}}\) if ∀_t k _t≤l _t and ∃t:k _t<l _t. In the same way a grid \(\varOmega_{\underline{k}}\) is smaller than a grid \(\varOmega_{\underline{l}}\).

Here, also many other approaches exist, which are based on interpolets, prewavelets or wavelets, cf. [12].

Since \(y_{\underline{x}}(-t)\) stays in Ω for all \(\underline{x}\in\varOmega\) the boundary needs no specific consideration and for this example we could use the standard hat basis of Fig. 3(a) as well. Indeed we numerically observed the same accuracy with roughly the same number of points for the standard and modified basis of Fig. 3, respectively.

With \(S_{t}(\underline{x}):=\{\underline{x}\in\mathbb{R}^{d} \mid \|\underline{x}\|_{2}\leq t\}= B(\underline{x},t)\) we can show that \(v(t,\underline{x})= \inf_{y\in S_{t}(\underline{x})} \varphi(y) =\varphi(\underline{x}^{*})\) where \(\underline{x}^{*}\) is a point of ℝ^d such that \(\underline{x}^{*}:=\arg\min_{\underline{y}\in S_{t}(\underline{x})} \| \underline{y}\|\).

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(2), 817–848 (2008) MathSciNetMATHCrossRef

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) MATHCrossRef

Bungartz, H.-J., Griebel, M.: Sparse grids. Acta Numer. 13, 147–269 (2004) MathSciNetCrossRef

Carlini, E., Falcone, M., Ferretti, R.: An efficient algorithm for Hamilton-Jacobi equations in high dimensions. Comput. Vis. Sci. 7, 15–29 (2004) MathSciNetMATHCrossRef

Carlini, E., Ferretti, R., Russo, G.: A weighted essentialy non oscillatory, large time-step scheme for Hamilton Jacobi equations. SIAM J. Sci. Comput. 27(3), 1071–1091 (2005) MathSciNetMATHCrossRef

Crandall, M., Lions, P.-L.: Two approximations of solutions of Hamilton Jacobi equations. Math. Comput. 43, 1–19 (1984) MathSciNetMATHCrossRef

Debrabant, K., Jakobsen, E.: Semi-Lagrangian approximation schemes for linear and Hamilton-Jacobi equations. Preprint

Faber, G.: Über stetige Funktionen. Math. Ann. 66, 81–94 (1909) MathSciNetMATHCrossRef

Falcone, M.: A numerical approach to the infinite horizon problem of deterministic control theory. Appl. Math. Optim. 15, 1–13 (1987). See also Corrigenda: a numerical approach to the infinite horizon problem of deterministic control theory. Appl. Math. Optim. 23, 213–214 (1991) MathSciNetMATHCrossRef

10.

Falcone, M., Ferretti, R.: Semi-Lagrangian approximation schemes for linear and Hamilton-Jacobi equations, in preparation

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(5), 1335–1354 (1994) MathSciNetMATHCrossRef

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) MATH

14.

Griebel, M.: A parallelizable and vectorizable multi-level algorithm on sparse grids. In: Hackbusch, W. (ed.) Parallel Algorithms for Partial Differential Equations. Notes on Numerical Fluid Mechanics, vol. 31, pp. 94–100. Vieweg, Braunschweig (1991)

15.

Griebel, M.: Adaptive sparse grid multilevel methods for elliptic PDEs based on finite differences. Computing 61(2), 151–179 (1998) MathSciNetMATHCrossRef

16.

Grüne, L.: An adaptive grid scheme for the discrete Hamilton-Jacobi-Bellman equation. Numer. Math. 75(3), 319–337 (1997) MathSciNetMATHCrossRef

17.

Heinecke, A., Pflüger, D.: Multi- and many-core data mining with adaptive sparse grids. In: Proceedings of the 8th ACM International Conference on Computing Frontiers, CF’11, pp. 29:1–29:10. ACM, New York (2011)

18.

Hu, C., Shu, S.-W.: A discontinuous Galerkin finite element method for Hamilton-Jacobi equations. SIAM J. Sci. Comput. 21, 666–690 (1999) MathSciNetMATHCrossRef

19.

Maslov, V.P.: Operational Methods. Mir, Moscow (1976). Translated from the Russian by V. Golo, N. Kulman and G. Voropaeva MATH

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(7), 947–957 (2005) MathSciNetCrossRef

21.

Mitchell, I., Tomlin, C.: Level set methods for computation in hybrid systems. In: Krogh, B., Lynch, E.N. (eds.) Hybrid Systems: Computation and Control. Lecture Notes in Computer Science, vol. 1790, pp. 310–323. Springer, New York (2000) CrossRef

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) MathSciNetMATHCrossRef

23.

Osher, S., Shu, C.-W.: High order essentially non-oscillatory schemes for Hamilton-Jacobi equations. SIAM J. Numer. Anal. 28, 907–922 (1991) MathSciNetMATHCrossRef

24.

Pareigis, S.: Adaptive choice of grid and time in reinforcement learning. In: Jordan, M.I., Kearns, M.J., Solla, S.A. (eds.) NIPS (1997)

25.

Pflüger, D.: Spatially adaptive sparse grids for high-dimensional problems. Dissertation TU, München, Verlag Dr. Hut, München (Aug. 2010)

26.

Smolyak, S.A.: Quadrature and interpolation formulas for tensor products of certain classes of functions. Dokl. Akad. Nauk SSSR 148, 1042–1043 (1963). Russian, Engl. Transl.: Soviet Math. Dokl. 4, 240–243 (1963) MathSciNetMATH

27.

Yserentant, H.: On the multi-level splitting of finite element spaces. Numer. Math. 49, 379–412 (1986) MathSciNetMATHCrossRef

28.

Zenger, C.: Sparse grids. In: Hackbusch, W. (ed.) Parallel Algorithms for Partial Differential Equations, Proceedings of the Sixth GAMM-Seminar, Kiel, 1990. Notes on Numer. Fluid Mech., vol. 31, pp. 241–251. Vieweg, Wiesbaden (1991)

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) MathSciNetMATHCrossRef

Titel: An Adaptive Sparse Grid Semi-Lagrangian Scheme for First Order Hamilton-Jacobi Bellman Equations
verfasst von: Olivier Bokanowski
Jochen Garcke
Michael Griebel
Irene Klompmaker
Publikationsdatum: 01.06.2013
Verlag: Springer US
Erschienen in: Journal of Scientific Computing / Ausgabe 3/2013
Print ISSN: 0885-7474
Elektronische ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-012-9648-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2013

An Adaptive P 1 Finite Element Method for Two-Dimensional Maxwell’s Equations

Numerical Modeling of Degenerate Equations in Porous Media Flow

C 0-Nonconforming Triangular Prism Elements for the Three-Dimensional Fourth Order Elliptic Problem

Reduced Collocation Methods: Reduced Basis Methods in the Collocation Framework

WENO Schemes and Their Application as Limiters for RKDG Methods Based on Trigonometric Approximation Spaces

Dispersion and Dissipation Errors of Two Fully Discrete Discontinuous Galerkin Methods

Premium Partner