A Discontinuous Galerkin Semi-Lagrangian Scheme for 1D Hamilton-Jacobi-Bellman Equations

Abstract

The Hamilton-Jacobi-Bellman (HJB) equation, due to its nonlinearity, in general does not admit a classical solution, also for regular data. For this reason, the numerical approximation of the solution may pose some additional difficulties, compared to other cases. Over the past four decades, the literature has proposed several numerical approaches. The methods proposed include discontinuous Galerkin (DG) due to its properties of being local, flexible, and robust, but the approach remained underused, due to various technical difficulties, in particular its difficulty in selecting the correct viscosity solution of the problem. In this paper, a numerical method is proposed to solve the evolution HJB equation in one dimension. It consists of the combination of a Semi-Lagrangian (SL) scheme, aimed at reconstructing the characteristic directions, and a DG method, aimed at generating an approximate solution as a linear combination of discontinuous and compactly supported basis functions, defined a priori. In order to evaluate the performance of the proposed method, a collection of numerical experiments with regular, simply continuous, and discontinuous data is presented.

Keywords

Semi-Lagrangian (SL) schemes / Hamilton-Jacobi (HJ) equations / Discontinuous Galerkin (DG) method / 65M25 / 49L25

References

[1] Bardi, M., Capuzzo-Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Systems & Control: Foundations & Applications. Birkhäuser Boston, Inc., Boston (1997). https://doi.org/10.1007/978-0-8176-4755-1 (With appendices by Maurizio Falcone and Pierpaolo Soravia)

[2] Bokanowski O, Simarmata G. Semi-Lagrangian discontinuous Galerkin schemes for some first- and second-order partial differential equations. ESAIM Math. Model. Numer. Anal., 2016, 50(6): 1699-1730

[3] Bryson, S., Levy, D.: High-order semi-discrete central-upwind schemes for multi-dimensional Hamilton-Jacobi equations. J. Comput. Phys. 189(1), 63–87 (2003). https://doi.org/10.1016/S0021-9991(03)00201-8

[4] Carlini, E., Ferretti, R., Russo, G.: A weighted essentially nonoscillatory, large time-step scheme for Hamilton-Jacobi equations. SIAM J. Sci. Comput. 27(3), 1071–1091 (2005). https://doi.org/10.1137/040608787

[5] Cheng, Y., Shu, C.-W.: A discontinuous Galerkin finite element method for directly solving the Hamilton-Jacobi equations. J. Comput. Phys. 223(1), 398–415 (2007). https://doi.org/10.1016/j.jcp.2006.09.012

[6] Cheng, Y., Wang, Z.: A new discontinuous Galerkin finite element method for directly solving the Hamilton-Jacobi equations. J. Comput. Phys. 268, 134–153 (2014). https://doi.org/10.1016/j.jcp.2014.02.041

[7] Courant R, Isaacson E, Rees M. On the solution of nonlinear hyperbolic differential equations by finite differences. Commun. Pure Appl. Math., 1952, 5: 243-255

[8] Crandall, M.G., Evans, L.C., Lions, P.-L.: Some properties of viscosity solutions of Hamilton-Jacobi equations. Trans. Am. Math. Soc. 282(2), 487–502 (1984). https://doi.org/10.2307/1999247

[9] Crandall, M.G., Lions, P.-L.: Viscosity solutions of Hamilton-Jacobi equations. Trans. Am. Math. Soc. 277(1), 1–42 (1983). https://doi.org/10.2307/1999343

[10] Crandall, M.G., Lions, P.-L.: Two approximations of solutions of Hamilton-Jacobi equations. Math. Comput. 43(167), 1–19 (1984). https://doi.org/10.2307/2007396

[11] Evans LC. Partial Differential Equations, 2010, 2Providence. American Mathematical Society: 749 19

[12] Falcone, M., Ferretti, R.: Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations. Society for Industrial and Applied Mathematics, Philadelphia (2013). https://doi.org/10.1137/1.9781611973051

[13] Hu, C., Shu, C.-W.: A discontinuous Galerkin finite element method for Hamilton-Jacobi equations. SIAM J. Sci. Comput. 21(2), 666–690 (1999). https://doi.org/10.1137/S1064827598337282

[14] Inc., T.M.: MATLAB Version 23.2.0 (R2023b). The MathWorks Inc., Natick, Massachusetts, United States (2023). https://www.mathworks.com

[15] Jiang, G.-S., Peng, D.: Weighted ENO schemes for Hamilton-Jacobi equations. SIAM J. Sci. Comput. 21(6), 2126–2143 (2000). https://doi.org/10.1137/S106482759732455X

[16] Ke, G., Guo, W.: An alternative formulation of discontinous Galerkin schemes for solving Hamilton-Jacobi equations. J. Sci. Comput. 78(2), 1023–1044 (2019). https://doi.org/10.1007/s10915-018-0794-7

[17] Kurganov, A., Noelle, S., Petrova, G.: Semidiscrete central-upwind schemes for hyperbolic conservation laws and Hamilton-Jacobi equations. SIAM J. Sci. Comput. 23(3), 707–740 (2001). https://doi.org/10.1137/S1064827500373413

[18] Li, F., Yakovlev, S.: A central discontinuous Galerkin method for Hamilton-Jacobi equations. J. Sci. Comput. 45(1/2/3), 404–428 (2010). https://doi.org/10.1007/s10915-009-9340-y

[19] Osher, S., Shu, C.-W.: High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations. SIAM J. Numer. Anal. 28(4), 907–922 (1991). https://doi.org/10.1137/0728049

[20] Quarteroni A. Modellistica Numerica per Problemi Differenziali, 6th edn. UNITEXT—La Matematica per il 3+2, 2016, Milan. Springer: 651 100

[21] Yan, J., Osher, S.: A local discontinuous Galerkin method for directly solving Hamilton-Jacobi equations. J. Comput. Phys. 230(1), 232–244 (2011). https://doi.org/10.1016/j.jcp.2010.09.022

Funding

Ministero dell’Istruzione, dell’Università e della Ricerca(unds 2022238YY5)

Politecnico di Torino

RIGHTS & PERMISSIONS

The Author(s)