Communications in Mathematical Sciences

Volume 16 (2018)

Number 7

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

DOI: https://dx.doi.org/10.4310/CMS.2018.v16.n7.a9

Authors

Alex Tong Lin (Department of Mathematics, University of California at Los Angeles)

Yat Tin Chow (Department of Mathematics, University of California at Los Angeles)

Stanley J. Osher (Department of Mathematics, University of California at Los Angeles)

Abstract

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.

Keywords

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

Full Text (PDF format)

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