March 11, 2016, Webb 1100

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