Curse-of-Dimensionality Free Method for Bellman PDEs with Semiconvex Hamiltonians

Max-plus methods have been explored for solution of first-order, nonlinear Hamilton-Jacobi-Bellman partial differential equations (HJB PDEs) and corresponding nonlinear control problems. Although earlier, eigenvector-based, max-plus methods could be quite fast, they still suffered from the curse-of-dimensionality. We now consider HJB PDEs where the Hamiltonian takes the form of a (pointwise) maximum of quadratic forms. We obtain a numerical method not subject to the curse-of-dimensionality. The method is based on construction of the dual-space semigroup corresponding to the HJB PDE. This dual-space semigroup is constructed from the dual-space semigroups corresponding to the constituent quadratic Hamiltonians. The actual computations in the algorithm involve repeatedly computing coefficients of quadratics which are obtained as the maxima of two other quadratics. In previous efforts, we considered Hamiltonians which were pointwise maxima of purely quadratic forms. However, such problems corresponded only to HJB PDEs whose solutions were quadratic along straight lines through the origin. By allowing some of the constituent Hamiltonians to have constant and linear terms as well as quadratic, we get the full panoply of behaviors