Abstract
Time-dependent Hamilton-Jacobi-Isaacs (HJ) partial differential equations (PDEs) are fundamental to analyzing continuous dynamic games and control theory problems. Traditionally, numerical approximations for these PDEs—such as the level set method—have been limited by the "curse of dimensionality," where computational costs grow exponentially with the number of space dimensions. In this work, we present a grid-free approach for solving a large class of HJ PDEs relevant to optimal control. By utilizing classical Hopf formulas and fast convex optimization techniques borrowed from compressive sensing, we reduce the computational complexity from exponential to polynomial. Our algorithm is highly parallelizable, requires minimal memory, and can evaluate solutions and their gradients in high dimensions at speeds ranging from $10^{-4}$ to $10^{-8}$ seconds per evaluation on a standard laptop.
Introduction
The term "curse of dimensionality" was coined by Richard Bellman in 1957 to describe the difficulty of solving dynamic optimization problems as the number of variables increases. In the context of Hamilton-Jacobi equations, which are used to determine reachability and optimal paths in physical systems, standard numerical methods rely on spatial grids. As the dimension $n$ increases, the number of grid points grows at a rate of $O(N^n)$, making problems with more than three or four dimensions computationally intractable.
This paper introduces a breakthrough that bypasses grid-based limitations entirely. By reframing the PDE problem as an optimization problem via the Hopf formula, we enable the solution of high-dimensional HJ equations with unprecedented speed and efficiency.
The Grid-Free Methodology
The Hopf Formula
The core of our approach is the use of the Hopf formula, which provides a representation of the solution to the initial value problem for HJ PDEs. Unlike traditional methods that evolve a field over time across a grid, the Hopf formula allows for the evaluation of the solution at a specific point $(x, t)$ independently of all other points. This "pointwise" evaluation is the key to overcoming the exponential scaling of grids.
Optimization and Split Bregman Iteration
When the Hamiltonian is convex and positively homogeneous of degree one, the optimization problem posed by the Hopf formula becomes highly structured. We adapt the Split Bregman iteration—a fast solver originally developed for $\ell_1$ regularization in image processing—to solve these optimization problems.
Key mathematical tools employed include:
- Proximal Operators: These operators find the closest point in a set and are used to handle various Hamiltonians (e.g., $L_1, L_2,$ or $L_\infty$ norms).
- Moreau Identity: This identity simplifies the calculation of proximal maps, allowing the algorithm to handle different geometric norms efficiently.
Because each point calculation is independent, the algorithm is "embarrassingly parallel," scaling linearly with the number of available CPU cores.
Applications in Control Theory
In optimal control, knowing the value of the HJ PDE solution is only half the battle; one must also determine the optimal control law. Our algorithm naturally produces the spatial gradient of the solution during the optimization process. This gradient provides the exact instruction the controller needs to guide the system optimally. We demonstrate that all quantities required to obtain the controller are computed easily and accurately through our numerical framework.
Results and Performance
Computational Efficiency
The proposed method achieves polynomial complexity, roughly $O(n \log n)$ or $O(n^2)$, depending on the specific Hamiltonian. This is a massive improvement over the $O(e^n)$ complexity of grid-based solvers. On a standard laptop, we observed evaluation times between $10^{-4}$ and $10^{-8}$ seconds per point.
High-Dimensional Testing
We tested the algorithm on several high-dimensional geometric problems, including:
- Computing distances to ellipsoids and convex sets in up to 16 dimensions.
- Modeling complex, non-convex boundaries by taking the pointwise minimum of multiple convex solutions (a min-plus algebra approach).
- Simulating motion under various norms, demonstrating that the method remains robust across different physical constraints.
Conclusion and Future Work
By bridging the gap between PDE theory and fast convex optimization, we have developed a method that effectively overcomes the curse of dimensionality for a significant class of Hamilton-Jacobi equations. This has immediate implications for real-time optimal control and reachability analysis in high-dimensional systems.
Future research will focus on extending these methods to time-dependent Hamiltonians and exploring applications in high-dimensional Linear Programming (LP) and differential games. The ability to solve these equations near-instantaneously opens new doors for autonomous systems and complex trajectory planning.
Summary updated