## Algorithm for Overcoming the Curse of Dimensionality for Certain Non-convex Hamilton-Jacobi Equations, Projections and Differential GamesYat Tin Chow, Jerome Darbon, Stanley Osher, and Wotao YinTo appear in ## OverviewIn this paper we develop a method for solving a large class of nonconvex Hamilton-Jacobi partial differential equations (HJ PDE): where is a continuous Hamiltonian and satisfies the initial condition for a convex function . Our method is based on the Hopf formulae, which yields decoupled subproblems, which can be solved in an embarrassingly parallel fashion for different . 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
« Back |