Abstract
Recent observations have bridged optimization-based splitting methods to the Hopf and Lax formulas for Hamilton-Jacobi (HJ) equations with Hamiltonians $H(p)$, resulting in extremely fast algorithms. This research generalizes these formulas to state-and-time-dependent cases $H(x,p,t)$ by applying a new splitting method based on the Primal-Dual Hybrid Gradient (PDHG) algorithm (Chambolle-Pock). By leveraging techniques from the derivation of new Hopf and Lax formulas, this approach computes solutions at specific points $(x,t)$ directly without the use of spatial grids. This grid-free nature allows the algorithm to lift the curse of dimensionality, enabling solutions in much higher dimensions than previously possible. Numerical experiments demonstrate that the computation scales polynomially in time and is embarrassingly parallelizable, facilitating real-time trajectory generation for complex nonlinear systems.
Introduction
Hamilton-Jacobi (HJ) equations serve as the mathematical foundation for optimal control, differential games, and classical mechanics. Solving these equations allows researchers to determine the "value function"—the optimal cost-to-go from any given state—and subsequently derive optimal trajectories. However, traditional numerical methods have long been stymied by the "curse of dimensionality." Because standard solvers rely on spatial discretization (grids), the computational requirements grow exponentially with the number of dimensions. Solving a problem in 10 or 100 dimensions has historically been viewed as computationally intractable.
This paper introduces a significant leap in computational control theory by presenting a grid-free splitting method. By avoiding the need to discretize the entire state space, the proposed algorithm can solve nonlinear optimal control problems in hundreds, or even thousands, of dimensions.
Overcoming the Curse of Dimensionality
The Grid-Free Advantage
Traditional methods require a global mesh, calculating the solution at every point in a bounded domain. In contrast, the proposed method calculates the solution only at the specific point $(x, t)$ of interest. This localized approach means the memory and processing overhead associated with a global spatial mesh is entirely bypassed. Furthermore, because each point is calculated independently, the algorithm is "embarrassingly parallelizable," allowing for massive speedups on modern multi-core hardware.
The PDHG Splitting Method
The core innovation lies in applying the Primal-Dual Hybrid Gradient (PDHG) algorithm—originally popular in image processing—to the generalized Lax and Hopf formulas. The technical process involves several key steps:
- Time Discretization: The authors discretize only the time domain, leaving the spatial variables continuous.
- Optimization Splitting: The HJ equation is reformulated as a minimization problem. PDHG "splits" this complex problem into simpler sub-problems, alternating updates between the state (position) and the dual variable (momentum or costate).
- Hamiltonian Encoding: By using the Hamiltonian to encode both system dynamics and running costs, the researchers transform a constrained optimization problem into an unconstrained one. This significantly simplifies the numerical search for an optimal solution.
Experimental Validation
The authors evaluated the method across several complex mathematical benchmarks and real-world engineering models:
- High-Dimensional Scaling: In a synthetic Eikonal problem, the algorithm successfully computed solutions in up to 2,000 dimensions. This is a feat fundamentally impossible for any grid-based method.
- Quadcopter Trajectory Generation: The method was applied to a 12-dimensional nonlinear model of a drone. It generated optimal trajectories in approximately 24 seconds on a standard laptop, outperforming Sequential Quadratic Programming (SQP) solvers by 5-10x in speed while maintaining identical accuracy.
- Differential Games: The solver was tested against the Isaacs Equation, a notoriously difficult, highly nonconvex differential game involving two players. Even in these harsh mathematical landscapes, the method proved robust.
Key Insights
Polynomial Scaling
Perhaps the most striking finding is that the computation time scales polynomially (often nearly linearly) with the number of dimensions. This shift from exponential to polynomial scaling is what makes 100D+ problems feasible for the first time on commodity hardware.
Trajectory Synthesis
Unlike many solvers that only provide the value function, this splitting method naturally produces the optimal trajectory as a byproduct of the optimization. This makes it an ideal candidate for real-time motion planning in robotics and autonomous systems.
Limitations and Future Directions
While the algorithm demonstrates exceptional empirical performance, the authors note that a formal proof of convergence for the fully nonlinear, non-convex case remains a work-in-progress. Additionally, the algorithm's performance is sensitive to the choice of step-sizes ($\sigma$ and $\tau$), which function similarly to the CFL condition in fluid dynamics. Future work will explore higher-order time discretization (such as trapezoidal rules) to further improve accuracy and investigate automated ways to tune algorithm hyperparameters.
Conclusion
By bridging optimization splitting techniques with Hamilton-Jacobi theory, this work provides a powerful new tool for high-dimensional control. The ability to solve 2,000-dimensional problems with polynomial scaling represents a major step toward practical, real-time optimal control for complex, many-degree-of-freedom systems.
Summary updated