SIAM Journal on Control and Optimization, Vol.48, No.4, 2651-2685, 2009
CONVERGENCE RATE FOR A CURSE-OF-DIMENSIONALITY-FREE METHOD FOR HAMILTON-JACOBI-BELLMAN PDEs REPRESENTED AS MAXIMA OF QUADRATIC FORMS
In previous work of the author and others, 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 max-plus basis expansion and max-plus finite-element methods provide computational-speed advantages, they still generally suffer from the curse-of-dimensionality. Here we consider HJB PDEs where the Hamiltonian takes the form of a (pointwise) maximum of linear/quadratic forms. The approach to a solution will be rather general, but in order to ground the work, we consider only constituent Hamiltonians corresponding to long-run average-cost-per-unit-time optimal control problems for the development. We consider a previously obtained 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 linear/quadratic Hamiltonians. The dual-space semigroup is particularly useful due to its form as a max-plus integral operator with kernel obtained from the originating semigroup. One employs repeated application of the dual-space semigroup to obtain the solution. Here, we consider constituent Hamiltonians which contain linear and constant terms as well as purely quadratic terms. This greatly expands the allowable class of problems. However, there are solution existence issues, and the error bounds are more difficult.
Keywords:partial differential equations;curse-of-dimensionality;dynamic programming;max-plus algebra;Legendre transform;Fenchel transform;semiconvexity;Hamilton-Jacobi-Bellman equations;idempotent analysis