Curse-of-Dimensionality Free Method for Bellman PDEs with Hamiltonian Written as Maximum of Quadratic Forms

摘要

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. These methods exploit the max-plus linearity of the associated semigroups. Although these methods provide advantages, they still suffer from the curse-of-dimensionality. Here we 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.