Annals of Mathematical Sciences and Applications

Volume 3 (2018)

Number 2

Algorithm for overcoming the curse of dimensionality for certain non-convex Hamilton–Jacobi equations, projections and differential games

Pages: 369 – 403

DOI: https://dx.doi.org/10.4310/AMSA.2018.v3.n2.a1

Authors

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

Jérôme Darbon (Division of Applied Mathematics, Brown University, Providence, Rhode Island, U.S.A.)

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

Wotao Yin (Department of Mathematics, University of California at Los Angeles)

Abstract

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 [6] 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.

Keywords

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.

Full Text (PDF format)

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