×

Algorithm for overcoming the curse of dimensionality for state-dependent Hamilton-Jacobi equations. (English) Zbl 1452.49016

Summary: In this paper, we develop algorithms to overcome the curse of dimensionality in non-convex state-dependent Hamilton-Jacobi partial differential equations (HJ PDEs) arising from optimal control and differential game problems. The subproblems are independent and they can be implemented in an embarrassingly parallel fashion. This is ideal for perfect scaling in parallel computing. The algorithm is proposed to overcome the curse of dimensionality when solving HJ PDE. The major contribution of the paper is to change either the solving of a PDE problem or an optimization problem over a space of curves to an optimization problem of a single vector, which goes beyond the work of [B. Rimoldi, IEEE Trans. Inf. Theory 47, No. 6, 2432–2442 (2001; Zbl 1021.94516)]. We extend the method in [Y. T. Chow et al., Ann. Math. Sci. Appl. 3, No. 2, 369–403 (2018; Zbl 1415.35087); Y. T. Chow et al., J. Sci. Comput. 73, No. 2–3, 617–643 (2017; Zbl 1381.65048); J. Darbon and S. Osher, “Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere”, UCLA CAM report 15-50 (2015)], and conjecture a (Lax-type) minimization principle to solve state-dependent HJ PDE when the Hamiltonian is convex, as well as a (Hopf-type) maximization principle to solve state-dependent HJ PDE when the Hamiltonian is non-convex, as a generalization of the well-known Hopf formula in [L. C. Evans, Partial differential equations. 2nd ed. Providence, RI: American Mathematical Society (AMS) (2010; Zbl 1194.35001); E. Hopf, J. Math. Mech. 14, 951–973 (1965; Zbl 0168.35101); I. V. Rublev, Comput. Math. Model. 11, No. 4, 391–400 (2000; Zbl 1020.49023); translation from Prikl. Mat. Inf. 3, 81–89 (1999)]. We showed the validity of the formula under restricted assumption for the sake of completeness, and would like to bring our readers to [I. Yegorov and P. Dower, “Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations”, Appl. Math. Optim. (to appear)] which validates our conjectures in a more general setting. We conjectured the weakest assumption of our formula to hold is a pseudoconvexity assumption similar to one stated in [I. V. Rublev, Comput. Math. Model. 11, No. 4, 391–400 (2000; Zbl 1020.49023); translation from Prikl. Mat. Inf. 3, 81–89 (1999)]. Our method is expected to have application in control theory, differential game problems and elsewhere.

MSC:

49L12 Hamilton-Jacobi equations in optimal control and differential games
65K10 Numerical optimization and variational techniques
35F21 Hamilton-Jacobi equations
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bellman, R., Adaptive Control Processes, a Guided Tour (1961), Princeton University Press · Zbl 0103.12901
[2] Bellman, R., Dynamic Programming (1957), Princeton University Press · Zbl 0077.13605
[3] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press · Zbl 1058.90049
[4] Bernard, P., The Lax-Oleinik semi-group: a Hamiltonian point of view (2012), preprint · Zbl 1400.70027
[5] Bernardi, O.; Cardin, F., Minimax and viscosity solutions of Hamilton-Jacobi equations in the convex case, Commun. Pure Appl. Anal., 5, 4, 793-812 (2006) · Zbl 1135.35005
[6] Capitanio, G., Generic singularities of minimax solutions to Hamilton-Jacobi equations (2004), preprint · Zbl 1080.53075
[7] Chow, Y. T.; Darbon, J.; Osher, S.; Yin, W., Algorithm for Overcoming the Curse of Dimensionality for Certain Non-convex Hamilton-Jacobi Equations, Projections and Differential Games, (Annals of Mathematical Sciences and Applications, vol. 3 (2018)), 369-403, UCLA CAM Report 16-27 · Zbl 1415.35087
[8] Chow, Y. T.; Darbon, J.; Osher, S.; Yin, W., Algorithm for overcoming the curse of dimensionality for state-dependent Hamilton-Jacobi equations (2017), preprint
[9] Chow, Y. T.; Darbon, J.; Osher, S.; Yin, W., Algorithm for overcoming the curse of dimensionality for time-dependent non-convex Hamilton-Jacobi equations arising from optimal control and differential games problems, J. Sci. Comput., 73, 2-3, 617-643 (2017) · Zbl 1381.65048
[10] Clarke, F. H.; Vinter, R. B., The relationship between the maximum principle and dynamic programming, SIAM J. Control Optim., 25, 5, 1291-1311 (1987) · Zbl 0642.49014
[11] Cohn-Vossen, S. E., Some Problems of Differential Geometry in the Large (1959), Fizmatgiz: Fizmatgiz Moscow
[12] Crandall, M. G.; Lions, P.-L., Some properties of viscosity solutions of Hamilton-Jacobi equations, Trans. Am. Math. Soc., 282, 2, 487-502 (1984) · Zbl 0543.35011
[13] Crandall, M. G.; Lions, P.-L., Viscosity solutions of Hamilton-Jacobi equations, Trans. Am. Math. Soc., 277, 1, 1-42 (1983) · Zbl 0599.35024
[14] Darbon, J., On convex finite-dimensional variational methods in imaging sciences, and Hamilton-Jacobi equations, SIAM J. Imaging Sci., 8, 4, 2268-2293 (2015) · Zbl 1330.35076
[15] Darbon, J.; Osher, S., Algorithms for Overcoming the Curse of Dimensionality for Certain Hamilton-Jacobi Equations Arising in Control Theory and Elsewhere (2015), preprint, UCLA CAM report 15-50
[16] Dijkstra, E. W., A note on two problems in connexion with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002
[17] E, W.; Ren, W.; Vanden-Eijnden, E., Minimum action method for the study of rare events, Commun. Pure Appl. Math., 57, 5, 637-656 (2004) · Zbl 1050.60068
[18] Evans, L. C., Partial Differential Equations, Grad. Studies in Math., vol. 19 (2010), AMS · Zbl 1194.35001
[19] Evans, L. C., Envelopes and nonconvex Hamilton-Jacobi equations, Calc. Var. Partial Differ. Equ., 50, 1, 257-282 (2014) · Zbl 1302.49038
[20] Evans, L. C.; Souganidis, P. E., Differential games and representation formulas for solutions of Hamilton-Jacobi Isaacs equations, Indiana Univ. Math. J., 38, 773-797 (1984) · Zbl 1169.91317
[21] Friedlander, M. P.; Macedo, I.; Pong, T. K., Gauge optimization and duality, SIAM J. Optim., 24, 4, 1999-2022 (2014) · Zbl 1333.90083
[22] Grafke, T.; Schaefer, T.; Vanden-Eijnden, E., Long term effects of small random perturbations on dynamical systems: theoretical and computational tools, preprint · Zbl 1383.37035
[23] Heymann, M.; Vanden-Eijnden, E., The geometric minimum action method: a least action principle on the space of curves, Commun. Pure Appl. Math., 61, 8, 1052-1117 (2008) · Zbl 1146.60046
[24] Hiriart-Urruty, J.-B.; Lemaréchal, C., Fundamentals of Convex Analysis (2001), Springer · Zbl 0998.49001
[25] Hopf, E., Generalized solutions of nonlinear equations of the first order, J. Math. Mech., 14, 951-973 (1965) · Zbl 0168.35101
[26] Hopf, H.; Rinow, W., Ueber den Begriff der vollstandigen differentialgeometrischen Flachen, Comment. Math. Helv., 3, 209-225 (1931) · JFM 57.0871.04
[27] Horowitz, M. B.; Damle, A.; Burdick, J. W., Linear Hamilton Jacobi Bellman equations in high dimensions (2014)
[28] Kang, W.; Wilcox, L. C., Mitigating the curse of dimensionality: sparse grid characteristics method for optimal feedback control and HJB equations (2015), preprint · Zbl 1383.49045
[29] Komiya, H., Elementary proof for Sion’s minimax theorem, Kodat Math. J., 11, 5-7 (1988) · Zbl 0646.49004
[30] Krasovskii, N. N.; Subbotin, A. I., Game-Theoretical Control Problems (1988), Springer-Verlag: Springer-Verlag New York · Zbl 0649.90101
[31] Krasovskii, N. N.; Subbotin, A. I., Positional Differential Games (1974), Nauka: Nauka Moscow · Zbl 0298.90067
[32] Mirica, S., Extending Cauchy’s method of characteristics for Hamilton-Jacobi equations, Stud. Cercet. Mat., 37, 6, 555-565 (1985)
[33] Mitchell, I. M.; Bayen, A. M.; Tomlin, C. J., A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games. Automatic Control, IEEE Trans. Autom. Control, 50, 7, 947-957 (2005) · Zbl 1366.91022
[34] Mitchell, I. M.; Tomlin, C. J., Overapproximating reachable sets by Hamilton-Jacobi projections, J. Sci. Comput., 19, 1-3, 323-346 (2003) · Zbl 1045.93008
[35] Moreau, J. J., Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. Fr., 93, 273-299 (1965) · Zbl 0136.12101
[36] Mordukhovich, B. S., Maximum principle in problems of time optimal control with nonsmooth constraints, J. Appl. Math. Mech., 40, 960-969 (1976) · Zbl 0362.49017
[37] Mordukhovich, B. S., Variational Analysis and Generalized Differentiation, I: Basic Theory, Grundlehren Math. Wiss., vol. 330 (2006), Springer-Verlag: Springer-Verlag Berlin
[38] Mordukhovich, B. S., Variational Analysis and Generalized Differentiation, II: Applications, Grundlehren Math. Wiss., vol. 331 (2006), Springer-Verlag: Springer-Verlag Berlin
[39] von Neumann, J., Zur theorie der gesellschaftsspiele, Math. Ann., 100, 295-320 (1928) · JFM 54.0543.02
[40] O’Donoghue, B.; Stathopoulos, G.; Boyd, S., A splitting method for optimal control, IEEE Trans. Control Syst. Technol., 21, 6, 2432-2442 (2013)
[41] Osher, S.; Chu, C.-W., High order essentially non-oscillatory schemes for Hamilton-Jacobi equations, SIAM J. Numer. Anal., 28, 4, 907-922 (1991) · Zbl 0736.65066
[42] Osher, S.; Sethian, J. A., Fronts propagating with curvature dependent speech: algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys., 79, 1, 12-49 (1988) · Zbl 0659.65132
[43] Osher, S.; Merriman, B., The Wulff shape as the asymptotic limit of a growing crystalline interface, Asian J. Math., 1, 3, 560-571 (1997) · Zbl 0891.49023
[44] Polyak, B. T., Some methods of speeding up the convergence of iteration methods, USSR Comput. Math. Math. Phys., 4, 5, 1-17 (1964) · Zbl 0147.35301
[45] Pontryagin, L. S.; Boltyansky, V. G.; Gamkrelidze, R. V.; Mishchenko, E. F., The Mathematical Theory of Optimal Processes (1964), Macmillan: Macmillan New York · Zbl 0117.31702
[46] Rockafellar, R. T., A general correspondence between dual minimax problems and convex programs, Pac. J. Math., 25, 3, 597-611 (1968) · Zbl 0162.23103
[47] Rockafellar, R. T., Convex Analysis, Princeton Landmarks in Mathematics (1997), Princeton University Press · Zbl 0932.90001
[48] Rockafellar, R.; Wolenski, P., Convexity in Hamilton-Jacobi theory I: Dynamics and duality, SIAM J. Control Optim., 39, 5, 1323-1350 (2000) · Zbl 0998.49018
[49] Rockafellar, R.; Wolenski, P., Convexity in Hamilton-Jacobi theory II: Envelope representations, SIAM J. Control Optim., 39, 5, 1351-1372 (2000) · Zbl 0998.49019
[50] Rublev, I. V., Generalized Hopf formulas for the nonautonomous Hamilton-Jacobi equation, Comput. Math. Model., 11, 4, 391-400 (2000) · Zbl 1020.49023
[51] Rutishauser, H., Theory of gradient methods, (Refined Iterative Methods for Computation of the Solution and the Eigenvalues of Self-Adjoint Boundary Value Problems (1959)), 24-49
[52] Sion, M., On general minimax theorems, Pac. J. Math., 8, 171-176 (1958) · Zbl 0081.11502
[53] Subbotin, A. I.; Chentsov, A. G., Optimization of Guaranteed Result in Control Problems (1981), Nauka: Nauka Moscow · Zbl 0542.90106
[54] Subbotina, N. N., Method of Cauchy characteristics and generalized solutions of Hamilton-Jacobi-Bellman equations, Dokl. Akad. Nauk SSSR, 320, 556-561 (1991) · Zbl 0793.35015
[55] Subbotina, N. N., Necessary and Sufficient Optimality Conditions in Terms of Characteristics of the Hamilton-Jacobi-Bellman Equation (1992), Institut für Angewandte Mathematik und Statistic, Universität Würzburg: Institut für Angewandte Mathematik und Statistic, Universität Würzburg Würzburg, Report 393
[56] Subbotina, N. N., The method of characteristics for Hamilton-Jacobi equations and applications to dynamical optimization, J. Math. Sci., 135, 3, 2955-3091 (2006) · Zbl 1184.49032
[57] Sutskever, I.; Martens, J.; Dahl, G. E.; Hinton, G. E., On the importance of initialization and momentum in deep learning, Int. Conf. Mach. Learn., 28, 3, 1139-1147 (2013)
[58] Tsai, Y. H.R.; Cheng, L. T.; Osher, S.; Zhao, H. K., Fast sweeping algorithms for a class of Hamilton-Jacobi equations, SIAM J. Numer. Anal., 41, 2, 673-694 (2003) · Zbl 1049.35020
[59] Tsitsiklis, J. N., Efficient algorithms for globally optimal trajectories, IEEE Trans. Autom. Control, 40, 9, 1528-1538 (1995) · Zbl 0831.93028
[60] Vanden-Eijnden, E.; Weare, J., Rare event simulation of small noise diffusions, Commun. Pure Appl. Math., 65, 12, 1770-1803 (2012) · Zbl 1268.65015
[61] Wei, Q., Viscosity solution of the Hamilton-Jacobi equation by a limiting minimax method, Nonlinearity, 27, 1, 17-42 (2013) · Zbl 1284.35120
[62] Yegorov, I.; Dower, P., Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations, preprint · Zbl 1461.49028
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.