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

Abstract

In this paper, we develop a method for solving a large class of non-convex 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 non-convex 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 2016
Accession Number
AD1014933

Entities

People

  • Jérôme Darbon
  • Stanley Osher
  • Wotao Yin
  • Yat Tin Chow

Organizations

  • University of California

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Computational Fluid Dynamics
  • Computations
  • Convex Sets
  • Differential Equations
  • Equations
  • Grids
  • Hamiltonian Functions
  • Iterations
  • Linear Algebra
  • Mathematics
  • Monotone Functions
  • Optimization
  • Partial Differential Equations
  • Splitting
  • Two Dimensional

Fields of Study

  • Mathematics

Readers

  • Calculus or Mathematical Analysis
  • Operations Research