Ricerc@Sapienza

The classical dynamic programming (DP) approach to optimal control problems is based on the characterization of the value function as the unique viscosity solution of a Hamilton-Jacobi-Bellman equation. The DP scheme for the numerical approximation of viscosity solutions of Bellman equations is typically based on a time discretization which is projected on a fixed state-space grid. The time discretization can be done by a one-step scheme for the dynamics and the projection on the grid typically uses a local interpolation.

We present a tree structure algorithm for optimal control problems with state constraints. We prove a convergence result for a discrete time approximation of the value function based on a novel formulation in the case of convex constraints. Then the Dynamic Programming approach is developed by a discretization in time leading to a tree structure in space derived by the controlled dynamics, taking into account the state constraints to cut several branches of the tree. Moreover, an additional pruning allows for the reduction of the tree complexity as for the case without state constraints.