Algorithm for Overcoming the Curse of Dimensionality for Certain Non-convex Hamilton-Jacobi Equations, Projections and Differential Games

Yat Tin Chow, Jerome Darbon, Stanley Osher, and Wotao Yin

To appear in Annals of Mathematical Sciences and Applications

Overview

In this paper we develop a method for solving a large class of nonconvex Hamilton-Jacobi partial differential equations (HJ PDE):

 frac{partial}{partial t}phi(x,t) + Hbig(nabla_xphi (x,t)big) = 0quadmbox{in}~mathbf{R}^dtimes (0,infty)

where H is a continuous Hamiltonian and phi satisfies the initial condition

 phi(x,0)=J(x),quad xinmathbf{R}^d

for a convex function J.

Our method is based on the Hopf formulae, which yields decoupled subproblems,

 phi(x,t):= -min_{vinmathbf{R}^d} big{ J^*(v)+tH(v)-langle x,v ranglebig},

which can be solved in an embarrassingly parallel fashion for different (x,t). The complexity of the resulting algorithm is polynomial in the problem dimension; hence, it overcomes the curse of dimensionality. We extend previous work in [6] (see our report) 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

Citation

Y.T. Chow, J. Darbon, S. Osher, and W. Yin, Algorithm for Overcoming the Curse of Dimensionality for Certain Non-convex Hamilton-Jacobi Equations, Projections and Differential Games, UCLA CAM 16-27, to appear in Annals of Mathematical Sciences and Applications, 2016.


« Back