Efficient Higher Order Time Discretization Schemes for Hamilton-Jacobi-Bellman Equations Based on Diagonally Implicit Symplectic Runge-Kutta Methods

We consider a semi-Lagrangian approach for the computation of the value function of a Hamilton-Jacobi-Bellman equation. This problem arises when one solves optimal feedback control problems for evaluationary partial differential equations. A time discretization with Runge-Kutta methods leads in general to a complexity of the optimization problem for the control which is exponential in the number of stages of the time scheme. Motivated by this, we introduce a time discretization based on Runge-Kutta composition methods, which achieves higher order approximation with respect to time, but where the overall optimization costs increase only linearly with respect to the number of stages of the employed Runge-Kutta method. In numerical tests we can empirically confirm an approximately linear complexity with respect to the number of stages. The presented algorithm is in particular of interest for those optimal control problems which do involve a costly minimization over the control set.