Annals of Mathematical Sciences and Applications
Volume 3 (2018)
Algorithm for overcoming the curse of dimensionality for certain non-convex Hamilton–Jacobi equations, projections and differential games
Pages: 369 – 403
In this paper we develop a method for solving a large class of nonconvex Hamilton–Jacobi partial differential equations (HJ PDE). The method yields decoupled subproblems, which can be solved in an embarrassingly parallel fashion. The complexity of the resulting algorithm is polynomial in the problem dimension; hence, it overcomes the curse of dimensionality [1, 2]. We extend previous work in  and apply the Hopf formula to solve HJ PDE involving nonconvex Hamiltonians.We propose an ADMM approach for finding the minimizer associated with the Hopf formula. Some explicit formulae of proximal maps, as well as newly-defined stretch operators, are used in the numerical solutions of ADMM subproblems. Our approach is expected to have wide applications in continuous dynamic games, control theory problems, and elsewhere.
Hamilton–Jacobi equations, viscosity solution, Hopf formula, nonconvex Hamiltonian, nonconvex ADMM, differential games, optimal control
2010 Mathematics Subject Classification
Primary 35F21, 46N10, 49N70, 49N90. Secondary 90C90, 91A23, 93C95.
The research of Y. T. Chow, S. Osher and W. Yin is supported by ONR N000141612157, DOE DE-SC00183838, NSF EAGER-1462397, DMS-1317602, and ECCS-1462397.
Received 18 May 2016
Published 9 August 2018