A CWENO Large Time-Step Scheme for Hamilton-Jacobi Equations

Abstract

We propose a high-order numerical scheme for time-dependent first-order Hamilton-Jacobi-Bellman (HJB) equations. In particular, we propose to combine a semi-Lagrangian (SL) scheme with a Central Weighted Essentially Non-Oscillatory (CWENO) reconstruction. The CWENO method provides a non-oscillatory, high-order reconstruction polynomial that allows efficient evaluations at multiple reconstruction points, while the SL method ensures stability without any time-step restrictions. Together, they form a particularly effective framework for solving HJB equations. We prove a convergence result in the case of state- and time-independent Hamiltonians. Numerical simulations are presented in space dimensions one and two, also for more general state- and time-dependent Hamiltonians, demonstrating superior performance in terms of CPU time gain compared with a semi-Lagrangian scheme coupled with Weighted Non-Oscillatory reconstructions.

Keywords

Semi-Lagrangian (SL) schemes / Hamilton-Jacobi (HJ) equations / Central Weighted Essentially Non-Oscillatory (CWENO) methods

References

[1] AbgrallR. On essentially non-oscillatory schemes on unstructured meshes: analysis and implementation. J. Comput. Phys., 1994, 114645-48.

[2] BaezaA, BürgerR, MuletP, ZoríoD. Central WENO schemes through a global average weight. J. Sci. Comput., 2019, 781499-530.

[3] BalsaraDS, GarainS, FlorinskiV, BoscheriW. An efficient class of WENO schemes with adaptive order for unstructured meshes. J. Comput. Phys., 2020, 404: 109062.

[4] Bardi, M., Capuzzo-Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Birkhäuser Boston, Inc., Boston (1997)

[5] Bokanowski, O., Falcone, M., Sahu, S.: An efficient filtered scheme for some first order time-dependent Hamilton-Jacobi equations. SIAM J. Sci. Comput. 38(1), 171–195 (2016)

[6] Bokanowski, O., Forcadel, N., Zidani, H.: Reachability and minimal times for state constrained nonlinear problems without any controllability assumption. SIAM J. Control Optim. 48(7), 4292–4316 (2010). https://doi.org/10.1137/090762075

[7] Bonaventura, L., Calzola, E., Carlini, E., Ferretti, R.: Second order fully semi-Lagrangian discretizations of advection-diffusion-reaction systems. J. Sci. Comput. 88, 23 (2021). https://doi.org/10.1007/s10915-021-01518-8

[8] BrysonS, LevyDHouTY, TadmorE. High-order schemes for multi-dimensional Hamilton-Jacobi equations. Hyperbolic Problems: Theory, Numerics, Applications, 2003BerlinSpringer387-396.

[9] Calzola, E., Carlini, E., Dupuis, X., Silva, F.J.: A semi-Lagrangian scheme for Hamilton-Jacobi-Bellman equations with oblique derivatives boundary conditions. Numer. Math. 153(1), 49–84 (2023)

[10] CarliniE, FerrettiR, RussoG. A weighted essentially nonoscillatory, large time-step scheme for Hamilton-Jacobi equations. SIAM J. Sci. Comput., 2006, 2731071-1091.

[11] CastroMJ, SempliceM. Third- and fourth-order well-balanced schemes for the shallow water equations based on the CWENO reconstruction. Int. J. Numer. Methods Fluid, 2019, 898304-325.

[12] CraveroI, PuppoG, SempliceM, ViscontiG. CWENO: uniformly accurate reconstructions for balance laws. Math. Comput., 2018, 873121689-1719.

[13] Cravero, I., Semplice, M., Visconti, G.: Optimal definition of the nonlinear weights in multidimensional Central WENOZ reconstructions. SIAM J. Numer. Anal. 57(5), 2328–2358 (2019)

[14] DumbserM, BoscheriW, SempliceM, RussoG. Central weighted ENO schemes for hyperbolic conservation laws on fixed and moving unstructured meshes. SIAM J. Sci. Comput., 2017, 3962564-2591.

[15] Falcone, M., Ferretti, R.: Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations. Numer. Math. 67(3), 315–344 (1994)

[16] Falcone, M., Ferretti, R.: Semi-Lagrangian schemes for Hamilton-Jacobi equations, discrete representation formulae and Godunov methods. J. Comput. Phys. 175(2), 559–575 (2002)

[17] Falcone, M., Ferretti, R.: Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2014)

[18] Falcone, M., Paolucci, G., Tozza, S.: Convergence of adaptive filtered schemes for first order evolutionary Hamilton-Jacobi equations. Numer. Math. 145(2), 271–311 (2020)

[19] Falcone, M., Paolucci, G., Tozza, S.: Multidimensional smoothness indicators for first-order Hamilton-Jacobi equations. J. Comput. Phys. 409, 109360 (2020). https://doi.org/10.1016/j.jcp.2020.109360

[20] Ferretti, R.: Convergence of semi-Lagrangian approximations to convex Hamilton-Jacobi equations under (very) large Courant numbers. SIAM J. Numer. Anal. 40(6), 2240–2253 (2002). https://doi.org/10.1137/S0036142901388378

[21] Galántai, A.: The Nelder-Mead simplex algorithm is sixty years old: new convergence results and open questions. Algorithms 17(11), 523 (2024). https://doi.org/10.3390/a17110523

[22] Ha, Y., Kim, C.H., Yang, H., Yoon, J.: A sixth-order weighted essentially non-oscillatory schemes based on exponential polynomials for Hamilton-Jacobi equations. SIAM J. Sci. Comput. 75, 1675–1700 (2018). https://doi.org/10.1007/s10915-017-0603-8

[23] HartenA, EngquistB, OsherS, ChakravarthySR. Uniformly high-order accurate essentially nonoscillatory schemes III. J. Comput. Phys., 1987, 712231-303.

[24] Hu, C., Shu, C.-W.: Weighted essentially non-oscillatory schemes on triangular meshes. J. Comput. Phys. 150(1), 97–127 (1999). https://doi.org/10.1006/jcph.1998.6165

[25] 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

[26] Jiang, G.-S., Shu, C.-W.: Efficient implementation of weighted ENO schemes. J. Comput. Phys. 126, 202–228 (1996)

[27] Kim, C.H., Ha, Y., Yang, H., Yoon, J.: A third-order WENO scheme based on exponential polynomials for Hamilton-Jacobi equations. Appl. Numer. Math. 165, 167–183 (2021). https://doi.org/10.1016/j.apnum.2021.01.020

[28] LevyD, PuppoG, RussoG. Compact central WENO schemes for multidimensional conservation laws. SIAM J. Sci. Comput., 2000, 222656-672.

[29] Lin, C.T., Tadmor, E.: High-resolution nonoscillatory central schemes for Hamilton-Jacobi equations. SIAM J. Sci. Comput. 21(6), 2163–2186 (2000)

[30] LiuXD, OsherS, ChanT. Weighted essentially non-oscillatory schemes. J. Comput. Phys., 1994, 1151200-212.

[31] Nelder, J.A., Mead, R.: A simplex method for function minimization. The Computer Journal 7(4), 308–313 (1965)

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

[33] Samala, R.: L1\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$L^1$$\end{document}-type smoothness indicators based weighted essentially nonoscillatory scheme for Hamilton-Jacobi equations. Int. J. Numer. Methods Fluid 92(12), 1927–1947 (2020). https://doi.org/10.1002/fld.4855

[34] Samala, R., Biswas, B.: Arc length-based WENO scheme for Hamilton-Jacobi equations. Commun. Appl. Math. Comput. 3, 481–496 (2021). https://doi.org/10.1007/s42967-020-00091-5

[35] SempliceM, CocoA, RussoG. Adaptive mesh refinement for hyperbolic systems based on third-order compact WENO reconstruction. J. Sci. Comput., 2016, 66: 692-724.

[36] Semplice, M., Visconti, G.: Efficient implementation of adaptive order reconstructions. J. Sci. Comput. 83, 6 (2020). https://doi.org/10.1007/s10915-020-01156-6

[37] Zennaro, M.: Natural continuous extensions of Runge-Kutta methods. Math. Comput. 46(173), 119–133 (1986). https://doi.org/10.1090/S0025-5718-1986-0815835-1

[38] Zheng, F., Shu, C.-W., Qiu, J.: High order finite difference Hermite WENO schemes for the Hamilton-Jacobi equations on unstructured meshes. Comput. Fluids 183, 53–65 (2019). https://doi.org/10.1016/j.compfluid.2019.02.010

[39] ZhouJ, CaiL, ZhouF-Q. New high-resolution scheme for three-dimensional nonlinear hyperbolic conservation laws. Appl. Math. Comput., 2008, 1982770-786.

[40] ZhuJ, QiuJ. A new fifth order finite difference WENO scheme for solving hyperbolic conservation laws. J. Comput. Phys., 2016, 318: 110-121.

[41] Zhu, J., Qiu, J.: A new fifth order finite difference WENO scheme for Hamilton-Jacobi equations. Numer. Methods PDEs 33(4), 1095–1113 (2017). https://doi.org/10.1002/num.22133

[42] Zhu, J., Qiu, J.: A new type of high-order WENO schemes for Hamilton-Jacobi equations on triangular meshes. Commun. Comput. Phys. 27(3), 897–920 (2020). https://doi.org/10.4208/cicp.OA-2018-0156

Funding

Ministero dell’Università e della Ricerca(PRIN Project 2022, #2022238YY5 - “Optimal control problems: analysis, approximation”)

Università degli Studi Roma Tre

RIGHTS & PERMISSIONS

The Author(s)