# Algorithms for Overcoming the Curse of Dimensionality for Certain Hamilton-Jacobi Equations Arising in Control Theory and Elsewhere

arXiv: https://arxiv.org/abs/1605.01799 · HTML: https://mlsanity.com/paper/1605.01799/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 May 2016.

## Built on by (most cited first, 24 of 24)

- [Tackling the Curse of Dimensionality with Physics-Informed Neural Networks](https://mlsanity.com/paper/2307.12306/) (2023)
- [Operator learning with PCA-Net: upper and lower complexity bounds](https://mlsanity.com/paper/2303.16317/) (2023)
- [Hutchinson Trace Estimation for High-Dimensional and High-Order Physics-Informed Neural Networks](https://mlsanity.com/paper/2312.14499/) (2023)
- [An Extreme Learning Machine-Based Method for Computational PDEs in Higher Dimensions](https://mlsanity.com/paper/2309.07049/) (2023)
- [Hamilton-Jacobi Reachability in Reinforcement Learning: A Survey](https://mlsanity.com/paper/2407.09645/) (2024)
- [A Physics-Informed Machine Learning Framework for Safe and Optimal Control of Autonomous Systems](https://mlsanity.com/paper/2502.11057/) (2025)
- [SympOCnet: Solving optimal control problems with applications to high-dimensional multi-agent path planning problems](https://mlsanity.com/paper/2201.05475/) (2022)
- [Binary structured physics-informed neural networks for solving equations with rapidly changing solutions](https://mlsanity.com/paper/2401.12806/) (2024)
- [Gradient-augmented Supervised Learning of Optimal Feedback Laws Using State-dependent Riccati Equations](https://mlsanity.com/paper/2103.04091/) (2021)
- [Neural network architectures using min-plus algebra for solving certain high dimensional optimal control problems and Hamilton-Jacobi PDEs](https://mlsanity.com/paper/2105.03336/) (2021)
- [Leveraging Multi-time Hamilton-Jacobi PDEs for Certain Scientific Machine Learning Problems](https://mlsanity.com/paper/2303.12928/) (2023)
- [Hamilton-Jacobi Based Policy-Iteration via Deep Operator Learning](https://mlsanity.com/paper/2406.10920/) (2024)
- [Neural Implicit Solution Formula for Efficiently Solving Hamilton-Jacobi Equations](https://mlsanity.com/paper/2501.19351/) (2025)
- [On Hamilton-Jacobi PDEs and image denoising models with certain non-additive noise](https://mlsanity.com/paper/2105.13997/) (2021)
- [An Optimal Control Method to Compute the Most Likely Transition Path for Stochastic Dynamical Systems with Jumps](https://mlsanity.com/paper/2203.16874/) (2022)
- [On Learning what to Learn: heterogeneous observations of dynamics and establishing (possibly causal) relations among them](https://mlsanity.com/paper/2406.06812/) (2024)
- [HJ-sampler: A Bayesian sampler for inverse problems of a stochastic process by leveraging Hamilton-Jacobi PDEs and score-based generative models](https://mlsanity.com/paper/2409.09614/) (2024)
- [A Structure-Adaptive Random Feature Method for High-Dimensional Elliptic PDEs](https://mlsanity.com/paper/2607.19786/) (2026)
- [A hierarchical resource-efficient deep policy gradient method for continuous-time optimal control problems](https://mlsanity.com/paper/2502.14141/) (2025)
- [Deep learning methods for inverse problems using connections between proximal operators and Hamilton-Jacobi equations](https://mlsanity.com/paper/2512.23829/) (2025)
- [Unifying Hamilton-Jacobi Reachability and Reinforcement Learning](https://mlsanity.com/paper/2601.08050/) (2026)
- [Monotone Neural Policy Iteration for High-Dimensional First-Order Hamilton--Jacobi--Bellman Equations](https://mlsanity.com/paper/2605.07116/) (2026)
- [Hessian-augmented Supervised Learning for Hamilton-Jacobi-Bellman PDEs](https://mlsanity.com/paper/2606.23827/) (2026)
- [Reachability-Preserving Bellman Operator for the Discounted Reach-Cost Value Function: Uniting Hamilton-Jacobi Reachability and Reinforcement Learning](https://mlsanity.com/paper/2607.07893/) (2026)

## Abstract (arXiv)

It is well known that time dependent Hamilton-Jacobi-Isaacs partial differential equations (HJ PDE), 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. This was first used for reachability problems. The cost of these algorithms, and, in fact, all PDE numerical approximations is exponential in the space dimension and time. 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. We have noticed that if the Hamiltonian is convex and positively homogeneous of degree one 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 ℓ1 optimization. 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 to 10-8 seconds 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. The term curse of dimensionality, was coined by Richard Bellman in 1957 when considering problems in dynamic optimization.