Abstract
In this paper we develop a new version of the semi-Lagrangian algorithm for first order Hamilton–Jacobi equations. This implementation is well suited to deal with problems in high dimension, i.e. in Rm with m≥3, which typically arise in the study of control problems and differential games. Our model problem is the evolutive Hamilton–Jacobi equation related to the optimal control finite horizon problem. We will give a step-by-step description of the algorithm focusing our attention on two critical routines: the interpolation in high dimension and the search for the global minimum. We present some numerical results on test problems which range from m=3 to m=5 and deal with applications to front propagation, aerospace engineering, ecomomy and biology.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Allen, R.G.D.: Macro-economic theory: a mathematical treatment. Mac Millan 1967
Bardi, M., Capuzzo Dolcetta, I.: Optimal control and viscosity solutions of Hamilton–Jacobi–Bellman equations. Birkhäuser 1997
Bardi, M., Falcone, M., Soravia, P.: Fully discrete schemes for the value function of pursuit-evasion games, Advances in dynamic games and applications. In: Basar, T., Hauriem, A. (eds.). Birkhäuser 1994, pp. 89–105
Bardi, M., Falcone, M., Soravia, P.: Numerical Methods for Pursuit-Evasion Games via Viscosity Solutions. In: Bardi, M., Parthasarathy, T, Raghavan, T.E.S. (eds.). Stochastic and differential games: theory and numerical methods, Annals of the International Society of Differential Games. Vol. 4, Boston: Birkhäuser 2000, pp. 289–303
Barles, G.: Solutions de viscositè des equations d’Hamilton–Jacobi. Springer-Verlag 1998
Brent, R.: Algorithms for minimization without derivatives, Prentice-Hall. Englewood Cliffs 1973
Camilli, F., Falcone, M., Lanucara, P., Seghini, A.: A domain decomposition method for Bellman equations. In: Keyes, D.E., Xu, J. (eds.). Domain Decomposition methods in Scientific and Engineering Computing, Contemporary Mathematics Vol. 180, AMS, 1994, pp. 477–483
Capuzzo Dolcetta, I.: On a discrete approximation of the Hamilton–Jacobi equation of dynamic programming. Appl. Math. Optimization. 10, 367–377 (1983)
Falcone, M.: A numerical approach to the infinite horizon problem of deterministic control theory. Appl. Math. Optimization 15, 1–13 (1987) and 23, 213–214 (1991)
Falcone, M.: Numerical solution of Dynamic Programming equations. Appendix A in the volume Bardi, M., Capuzzo Dolcetta, I., Optimal control and viscosity solutions of Hamilton–Jacobi–Bellman equations. Boston: Birkhäuser 1997
Falcone, M., Ferretti, R.: Discrete-time high-order schemes for viscosity solutions of Hamilton–Jacobi equations. Num. Math. 67, 315–344 (1994)
Falcone, M., Ferretti, R.: Convergence analysis for a class of high-order semi-lagrangian advection schemes. SIAM J. Num. Anal. 35, 909–940 (1998)
Falcone, M., Ferretti, R.: Semi-Lagrangian schemes for Hamilton–Jacobi equations, discrete representation formulae and Godunov methods. J. Comput. Phys. 175, 559–575 (2002)
Falcone, M., Giorgi, T.: An approximation scheme for evolutive Hamilton–Jacobi equations. In: McEneaney, W.M., Yin, G., Zhang, Q. (eds.), Stochastic analysis, Control, optimization and applications: a volume in honor of W.H. Fleming, Birkhäuser 1998
Falcone, M., Lanucara, P., Marinucci, M.: Parallel Algorithms for the Isaacs equation. In: Altman, E., Pourtallier, O. (eds.), Annals of the International Society of Differential Games 6, 203–225 (2001)
Falcone, M., Lanucara, P., Seghini, A.: A splitting algorithm for Hamilton–Jacobi–Bellman equations. Appl. Num. Math. 15, 207–218 (1994)
Falcone, M., Stefani, P.: Advances in Parallel Algorithms for the Isaacs equations. To appear on Annals of the International Society of Differential Games
Falcone, M., Makridakis, Ch. (eds.): Numerical Methods for Viscosity Solutions and Applications. Singapore: World Scientific, 2001
Ferretti, R.: High-order approximations of linear control systems via Runge–Kutta schemes. Computing 58, 351–364 (1997)
Ferretti, R.: Convergence of semi-lagrangian approximations to convex Hamilton–Jacobi equations under (very) large Courant numbers. SIAM J. Num. Anal. 40, 2240–2253 (2003)
Fleming, W.R., Rishel, R.W.: Deterministic and Stochastic Optimal Control. Springer-Verlag 1975
Grüne, L.: An adaptive grid scheme for the discrete Hamilton–Jacobi–Bellman equation. Numer. Math. 75, 319–337 (1997)
Grüne, L., Kato, M., Semmler, W.: Numerical study of an ecological management problem. Working paper Vol. 42, Dept. of Economics, University of Bielefeld, 2002
Grüne, L., Metscher, M., Ohlberger, M.: On numerical algorithm and interactive visualization for optimal control problems. Comput. Vis. Sci. 1, 221–229 (1999)
Grüne, L., Semmler, W.: Using Dynamic Programming with adaptive grid scheme for optimal control problems in economics. Preprint, 2002
Isaacs, R.: Differential games. John Wiley & Sons 1965
Miele: The calculus of variations in applied aerodynamics and flight mechanics. In: Leitman, G. (ed.). Optimization techniques with applications to aerospace systems, New York: Academic Press 1960
Miele: Extremization of linear integrals by Green’s theorem. In: Leitman, G. (ed.), Optimization techniques with applications to aerospace systems, New York: Academic Press 1962
Osher, S., Sethian, J.A.: Fronts propagating with curvature-dependent speed: algorithms based on Hamilton–Jacobi formulations. J. Comput. Phys. 79, 12–49 (1988)
Osher, S., Fedkiw, R.P.: Level-set methods: an overview and some recent results. CAM report, Department of Mathematics, UCLA, 2000
Perelson, A.S., Nelson, P.W.: Mathematical analysis of HIV-1 dynamics in vivo. SIAM Review 41, 3–44 (1999)
Perelson, A.S., Kirschner, D.E., de Boer, R.: Dynamics of HIV infection of CD4+ cells. Math. Biosci. 114, 81–125 (1993)
Sagona, M., Seghini, A.: An adaptive scheme on unstructured grids for the Shape–from–Shading problem. In [18].
Santos, M.S., Vigo-Aguiar, J.: Analysis of a numerical dynamic programming algorithm applied to economic models. Econometrica 66, 409–426 (1998)
Sethian, J.A.: Level Set Method. Evolving interfaces in geometry, fluid mechanics, computer vision, and materials science Cambridge Monographs on Applied and Computational Mathematics, Vol. 3, Cambridge: Cambridge University Press 1996
Sethian, J.A.: Fast marching methods. SIAM Rev. 41, 199–235 (1999)
Sethian, J.A., Vladimirsky, A.: Ordered upwind methods for static Hamilton–Jacobi equations: theory and algorithms. University of California at Berkeley, preprint, June 2001
Sethian, J.A., Vladimirsky, A.: Fast methods for the Eikonal and related Hamilton–Jacobi equations on unstructured meshes. Proc. Natl. Acad. Sci. USA 97, 5699–5703 (2000)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by
K. Mikula
Rights and permissions
About this article
Cite this article
Carlini, E., Falcone, M. & Ferretti, R. An efficient algorithm for Hamilton–Jacobi equations in high dimension. Comput. Visual Sci. 7, 15–29 (2004). https://doi.org/10.1007/s00791-004-0124-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00791-004-0124-5