Communications in Mathematical Sciences
Volume 16 (2018)
A splitting method for overcoming the curse of dimensionality in Hamilton–Jacobi equations arising from nonlinear optimal control and differential games with applications to trajectory generation
Pages: 1933 – 1973
Recent observations have bridged splitting methods arising from optimization, to the Hopf and Lax formulas for Hamilton–Jacobi Equations. This has produced extremely fast algorithms in computing solutions of these PDEs. More recent observations were made in generalizing the Hopf and Lax formulas to state-and-time-dependent cases. In this article, we apply a new splitting method based on the Primal Dual Hybrid Gradient algorithm (a.k.a. Chambolle–Pock) to nonlinear optimal control and differential games problems, based on techniques from the derivation of the new Hopf and Lax formulas, which allow us to compute solutions at specified points directly, i.e. without the use of grids in space. This algorithm also allows us to create trajectories directly. Thus we are able to lift the curse of dimensionality a bit, and therefore compute solutions in much higher dimensions than before. And in our numerical experiments, we actually observe that our computations scale polynomially in time. Furthermore, this new algorithm is embarrassingly parallelizable.
Hamilton–Jacobi equations, optimal control, differential games, optimization, trajectory generation, Hopf–Lax formula, nonconvex Hamiltonian, nonsmooth Hamiltonian, convex-concave games
2010 Mathematics Subject Classification
35F21, 49K20, 49K35, 49L99, 49M99, 49N70, 65M25, 90C26, 90C46, 90C47, 93B40
This work was partially supported by DOE-SC0013838, NGA HM0210410003, and ECCS-1462398.
Received 10 March 2018
Accepted 2 July 2018
Published 7 March 2019