A Primal-dual hybrid gradient method for solving optimal control problems and the corresponding Hamilton-Jacobi PDEs

Optimal control problems are crucial in various domains, including path planning, robotics, and humanoid control, demonstrating their broad applicability. The connection between optimal control and Hamilton-Jacobi (HJ) partial differential equations (PDEs) underscores the need for solving HJ PDEs to address these control problems effectively. While numerous numerical methods exist for tackling HJ PDEs across different dimensions, this paper introduces an innovative optimization-based approach that reformulates optimal control problems and HJ PDEs into a saddle point problem using a Lagrange multiplier. Our method, based on the preconditioned primal-dual hybrid gradient (PDHG) method, offers a solution to HJ PDEs with first-order accuracy and numerical unconditional stability, enabling larger time steps and avoiding the limitations of explicit time discretization methods. Our approach has ability to handle a wide variety of Hamiltonian functions, including those that are non-smooth and dependent on time and space, through a simplified saddle point formulation that facilitates easy and parallelizable updates. Furthermore, our framework extends to viscous HJ PDEs and stochastic optimal control problems, showcasing its versatility. Through a series of numerical examples, we demonstrate the method's effectiveness in managing diverse Hamiltonians and achieving efficient parallel computation, highlighting its potential for wide-ranging applications in optimal control and beyond.