Hopf-type representation formulas and efficient algorithms for certain high-dimensional optimal control problems

Abstract

Two key challenges in optimal control include efficiently solving high-dimensional problems and handling optimal control problems with state-dependent running costs. In this paper, we consider a class of optimal control problems whose running costs consist of a quadratic on the control variable and a convex, non-negative, piecewise affine function on the state variable. We provide the analytical solution for this class of optimal control problems as well as a Hopf-type representation formula for the corresponding Hamilton-Jacobi partial differential equations. Finally, we propose efficient numerical algorithms based on our Hopf-type representation formula, convex optimization algorithms, and min-plus techniques. We present several high-dimensional numerical examples, which demonstrate that our algorithms overcome the curse of dimensionality. We also describe a field-programmable gate array (FPGA) implementation of our numerical solver whose latency scales linearly in the spatial dimension and that achieves approximately a 40 times speedup compared to a parallelized central processing unit (CPU) implementation. Thus, our numerical results demonstrate the promising performance boosts that FPGAs are able to achieve over CPUs. As such, our proposed methods have the potential to serve as a building block for solving more complicated high-dimensional optimal control problems in real-time.

arXiv commentarXiv admin note: text overlap with arXiv:2109.14849

References in corpus (18)

• DGM: A deep learning algorithm for solving partial differential equations
• Solving high-dimensional partial differential equations using deep learning
• The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis
• Deep neural networks algorithms for stochastic control problems on finite horizon: convergence analysis
• On some neural network architectures that can represent viscosity solutions of certain high dimensional Hamilton--Jacobi partial differential equations
• Reachability-Based Safety and Goal Satisfaction of Unmanned Aerial Platoons on Air Highways
• Actor-Critic Method for High Dimensional Static Hamilton--Jacobi--Bellman Partial Differential Equations based on Neural Networks
• Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms
• Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations
• QRnet: optimal regulator design with LQR-augmented neural networks
• Rectified deep neural networks overcome the curse of dimensionality for nonsmooth value functions in zero-sum games of nonlinear stiff systems
• A new scalable algorithm for computational optimal control under uncertainty
• Deep neural networks algorithms for stochastic control problems on finite horizon: numerical applications
• Using Neural Networks to Compute Approximate and Guaranteed Feasible Hamilton-Jacobi-Bellman PDE Solutions
• Deep backward schemes for high-dimensional nonlinear PDEs
• Game representations for state constrained continuous time linear regulator problems
• Lax-Oleinik-type formulas and efficient algorithms for certain high-dimensional optimal control problems
• A Computationally Efficient Hamilton-Jacobi-based Formula for State-Constrained Optimal Control Problems