Algorithms for overcoming the curse of dimensionality for certain Hamilton–Jacobi equations arising in control theory and elsewhere

Jérôme Darbon, Stanley Osher

This paper, authored by Jérôme Darbon and Stanley Osher, presents a breakthrough in computational mathematics by providing a way to solve high-dimensional Hamilton-Jacobi (HJ) equations—a task traditionally thought to be impossible due to the "curse of dimensionality." By swapping traditional grid-based solvers for optimization techniques borrowed from the world of compressive sensing, the authors achieve solution speeds that are orders of magnitude faster than previous methods.

TL;DR

The authors develop a grid-free algorithm to solve a specific class of Hamilton-Jacobi PDEs by utilizing the Hopf formula and fast convex optimization (Split Bregman). This approach reduces the computational complexity from exponential to polynomial, allowing for near-instantaneous solutions in high-dimensional spaces on a standard laptop.

What Problem Does This Paper Address?

In control theory and physics, Hamilton-Jacobi equations are used to find optimal paths, determine reachability (where a system can go), and track moving interfaces (level set methods). However, these equations suffer from the "Curse of Dimensionality."

Standard numerical methods rely on a grid. If you have a 2D grid with 100 points per side, you have $100^2$ (10,000) points. In 10D, you’d have $100^{10}$ points, which is more than the number of stars in the observable universe. Consequently, solving these equations for systems with more than 3 or 4 variables was historically considered computationally infeasible.

Methods

The researchers bypass the grid entirely by using a mathematical "shortcut" called the Hopf formula. This formula represents the solution to the PDE not as a field to be evolved over time, but as the result of a specific optimization problem at a single point in space and time.

Key components of their method include:

  • Split Bregman Iteration: They adapt this fast iterative solver—originally designed for $\ell_1$ regularization in image processing and compressive sensing—to solve the optimization problem posed by the Hopf formula.
  • Proximal Operators: They use "proximal maps" (mathematical operators that find the closest point in a set) to handle different types of Hamiltonians (the functions describing the system's physics).
  • Moreau Identity: A classic result in convex analysis used to simplify the calculation of these proximal maps, particularly for different norms (like the Manhattan or Euclidean distance).
  • Pointwise Evaluation: Because the method is grid-free, you can calculate the solution at exactly one point $(x, t)$ without needing to know the solution anywhere else. This makes the algorithm "embarrassingly parallel."

Datasets

As a theoretical and algorithmic paper, it does not use traditional "big data" sets. Instead, it evaluates performance on high-dimensional geometric problems:

  • Computing distances to ellipsoids and convex sets in dimensions up to $n=16$.
  • Simulating the union and intersection of convex sets to model complex, non-convex boundaries.
  • Testing on various Hamiltonians, including $L_1, L_2,$ and $L_\infty$ norms, as well as quadratic forms.

Key Insights and Ideas

  • Optimization vs. Integration: The core "aha!" moment is realizing that for convex, 1-homogeneous Hamiltonians (common in geometric motion and control), the PDE problem is structurally identical to the "sparse recovery" problems solved in signal processing.
  • Gradient for Free: The optimization process naturally produces the spatial gradient of the solution. In control theory, this gradient is the "optimal control law"—the exact instruction the controller needs to give the system.
  • Handling Non-Convexity: While the method relies on convexity, the authors show that you can solve problems with non-convex initial data by taking the pointwise minimum of several convex solutions (a "min-plus" algebra approach).

Key Results

  • Extreme Speed: The algorithm evaluates solutions in $10^{-4}$ to $10^{-8}$ seconds per point on a standard laptop.
  • Polynomial Complexity: Unlike grid-based methods that scale exponentially ($O(e^n)$), this method scales polynomially (roughly $O(n \log n)$ or $O(n^2)$), making 16-dimensional (or higher) problems trivial.
  • Perfect Scaling: On a 16-core machine, the speedup was nearly linear because each point calculation is independent and requires very little memory (fitting entirely within the CPU's L1 cache).

Limitations and Future Work

  • Convexity Constraints: The current framework primarily requires the Hamiltonian to be convex and "positively homogeneous of degree one." While this covers many physical cases, it doesn't cover all possible control problems.
  • Initial Data: The most efficient versions of the algorithm require convex initial data, though the authors provide a workaround for certain non-convex cases.
  • Future Directions: The authors suggest extending this to time-dependent Hamiltonians and applying the technique to solve high-dimensional Linear Programming (LP) problems and differential games.

Summary updated

Abstract

It is well known that time-dependent Hamilton–Jacobi–Isaacs partial differential equations (HJ PDEs) play an important role in analyzing continuous dynamic games and control theory problems. An important tool for such problems when they involve geometric motion is the level set method (Osher and Sethian in J Comput Phys 79(1):12–49, 1988). This was first used for reachability problems in Mitchell et al. (IEEE Trans Autom Control 50(171):947–957, 2005) and Mitchell and Tomlin (J Sci Comput 19(1–3):323–346, 2003). The cost of these algorithms and, in fact, all PDE numerical approximations is exponential in the space dimension and time. In Darbon (SIAM J Imaging Sci 8(4):2268–2293, 2015), some connections between HJ PDE and convex optimization in many dimensions are presented. In this work, we propose and test methods for solving a large class of the HJ PDE relevant to optimal control problems without the use of grids or numerical approximations. Rather we use the classical Hopf formulas for solving initial value problems for HJ PDE (Hopf in J Math Mech 14:951–973, 1965). We have noticed that if the Hamiltonian is convex and positively homogeneous of degree one (which the latter is for all geometrically based level set motion and control and differential game problems) that very fast methods exist to solve the resulting optimization problem. This is very much related to fast methods for solving problems in compressive sensing, based on $$\ell _1$$ optimization (Goldstein and Osher in SIAM J Imaging Sci 2(2):323–343, 2009; Yin et al. in SIAM J Imaging Sci 1(1):143–168, 2008). We seem to obtain methods which are polynomial in the dimension. Our algorithm is very fast, requires very low memory and is totally parallelizable. We can evaluate the solution and its gradient in very high dimensions at $$10^{-4}$$ – $$10^{-8}$$ s per evaluation on a laptop. We carefully explain how to compute numerically the optimal control from the numerical solution of the associated initial valued HJ PDE for a class of optimal control problems. We show that our algorithms compute all the quantities we need to obtain easily the controller. In addition, as a step often needed in this procedure, we have developed a new and equally fast way to find, in very high dimensions, the closest point y lying in the union of a finite number of compact convex sets $$\Omega $$ to any point x exterior to the $$\Omega $$ . We can also compute the distance to these sets much faster than Dijkstra type “fast methods,” e.g., Dijkstra (Numer Math 1:269–271, 1959). The term “curse of dimensionality” was coined by Bellman (Adaptive control processes, a guided tour. Princeton University Press, Princeton, 1961; Dynamic programming. Princeton University Press, Princeton, 1957), when considering problems in dynamic optimization.
BibTeX
@inproceedings{darbon2016algorithms,
  author = {Jérôme Darbon and Stanley Osher},
  title = {{Algorithms for overcoming the curse of dimensionality for certain Hamilton–Jacobi equations arising in control theory and elsewhere}},
  booktitle = {Research},
  year = {2016},
  doi = {10.1186/s40687-016-0068-7},
}

Loading related content...

Figure