Brown University shieldBrown University

Abstract; On fast algorithms for solving certain Hamilton-Jacobi equations arising in control theory

On fast algorithms for solving certain Hamilton-Jacobi
equations arising in control theory


It is well known that certain Hamilton-Jacobi (HJ) PDE's play an
important role in analyzing control theory problems. The cost of
standard algorithms, and, in fact all PDE grid based approximations is
exponential in the space dimension and time, with huge memory
requirements. Here we propose and test methods for solving a large
class of HJ PDE relevant to optimal control without the
use of grids or numerical approximations. Rather we use the classical
Hopf-Lax formulas for solving initial value problems for HJ PDE. We
have noticed that if the Hamiltonian is convex and positively
homogeneous of degree one that very fast methods (related to those
used in compressed sensing) exist to solve the resulting optimization
problem. We seem to obtain methods which are polynomial in dimension.
We can evaluate the solution in very high dimensions in between
10^(-4) and 10^(-8) seconds per evaluation on a laptop. The method
requires very limited memory and is almost perfectly parallelizable.
In addition, as a step often needed in this procedure, we have
developed a new, equally fast and efficient method to find, in very
high dimensions, the projection of a point onto a compact set. We can
also compute the distance to such sets much faster than fast marching
or fast sweeping algorithms. This is a joint work with Stanley Osher
(UCLA).