### 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).