LOCAL MINIMIZATION ALGORITHMS FOR DYNAMIC PROGRAMMING EQUATIONS

The application of the dynamic programming principle in continuous-time optimal control prob-lems leads to nonlinear Hamilton-Jacobi-Bellman equations which require the minimization of a nonlinear mapping over the set of admissible controls. In the context of the numerical approxima-tion of such equations, this minimization is often performed by comparison between a finite number of elements of the control set. In this paper we demonstrate the importance of an accurate realization of these minimization problems and propose algorithms by which this can be achieved effectively. The considered class of equations includes nonsmooth control problems with ℓ1 penalizations. Key words. dynamic programming, Hamilton-Jacobi-Bellman equations, semi-Lagrangian schemes, first order primal-dual methods, semi-smooth Newton methods AMS subject classifications