Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere
From MaRDI portal
(Redirected from Publication:313401)
Abstract: 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 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 to 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.
Recommendations
- Algorithm for overcoming the curse of dimensionality for time-dependent non-convex Hamilton-Jacobi equations arising from optimal control and differential games problems
- Algorithm for overcoming the curse of dimensionality for state-dependent Hamilton-Jacobi equations
- Splitting Enables Overcoming the Curse of Dimensionality
- Algorithm for overcoming the curse of dimensionality for certain non-convex Hamilton-Jacobi equations, projections and differential games
- An efficient algorithm for Hamilton-Jacobi equations in high dimension
Cites work
- scientific article; zbMATH DE number 439380 (Why is no real title available?)
- scientific article; zbMATH DE number 3126094 (Why is no real title available?)
- scientific article; zbMATH DE number 3168214 (Why is no real title available?)
- scientific article; zbMATH DE number 3855514 (Why is no real title available?)
- scientific article; zbMATH DE number 5604590 (Why is no real title available?)
- scientific article; zbMATH DE number 3961334 (Why is no real title available?)
- scientific article; zbMATH DE number 3504682 (Why is no real title available?)
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 1138782 (Why is no real title available?)
- scientific article; zbMATH DE number 2019805 (Why is no real title available?)
- scientific article; zbMATH DE number 1766614 (Why is no real title available?)
- scientific article; zbMATH DE number 3451403 (Why is no real title available?)
- scientific article; zbMATH DE number 5681750 (Why is no real title available?)
- scientific article; zbMATH DE number 3270165 (Why is no real title available?)
- scientific article; zbMATH DE number 3398324 (Why is no real title available?)
- A Discontinuous Galerkin Finite Element Method for Hamilton--Jacobi Equations
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A note on two problems in connexion with graphs
- A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
- Compressed sensing
- Convergence of Proximal-Like Algorithms
- Dynamics and control of trajectory tubes. Theory and computation
- Efficient algorithms for globally optimal trajectories
- Error forgetting of Bregman iteration
- Fast Sweeping Algorithms for a Class of Hamilton--Jacobi Equations
- Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations
- High-Order Essentially Nonoscillatory Schemes for Hamilton–Jacobi Equations
- High-Order WENO Schemes for Hamilton--Jacobi Equations on Triangular Meshes
- Hopf Formula and Multitime Hamilton-Jacobi Equations
- Max-plus methods for nonlinear control and estimation.
- Monotone Operators and the Proximal Point Algorithm
- Multiplier and gradient methods
- Numerical methods for anisotropic mean curvature flow based on a discrete time variational formulation
- On Convex Finite-Dimensional Variational Methods in Imaging Sciences and Hamilton--Jacobi Equations
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On total variation minimization and surface evolution using parametric maximum flows
- Overapproximating reachable sets by Hamilton-Jacobi projections
- Proximal Thresholding Algorithm for Minimization over Orthonormal Bases
- Proximité et dualité dans un espace hilbertien
- Redistancing by flow of time dependent eikonal equation
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Some Properties of Viscosity Solutions of Hamilton-Jacobi Equations
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- The Split Bregman Method for L1-Regularized Problems
- The Wulff shape as the asymptotic limit of a growing crystalline interface
- Viscosity Solutions of Hamilton-Jacobi Equations
Cited in
(49)- Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations
- scientific article; zbMATH DE number 1168338 (Why is no real title available?)
- A review of level-set methods and some recent applications
- Three ways to solve partial differential equations with neural networks — A review
- Lax-Oleinik-type formulas and efficient algorithms for certain high-dimensional optimal control problems
- Constraint control of nonholonomic mechanical systems
- Operator-splitting based fast sweeping methods for isotropic wave propagation in a moving fluid
- Adaptive deep learning for high-dimensional Hamilton-Jacobi-Bellman equations
- An overview on deep learning-based approximation methods for partial differential equations
- An adaptive sparse grid local discontinuous Galerkin method for Hamilton-Jacobi equations in high dimensions
- Value-Gradient Based Formulation of Optimal Control Problem and Machine Learning Algorithm
- On some neural network architectures that can represent viscosity solutions of certain high dimensional Hamilton-Jacobi partial differential equations
- An efficient algorithm for Hamilton-Jacobi equations in high dimension
- Machine learning approximation algorithms for high-dimensional fully nonlinear partial differential equations and second-order backward stochastic differential equations
- Optimal polynomial feedback laws for finite horizon control problems
- scientific article; zbMATH DE number 7370565 (Why is no real title available?)
- Adaptive deep neural networks methods for high-dimensional partial differential equations
- Neural network architectures using min-plus algebra for solving certain high-dimensional optimal control problems and Hamilton-Jacobi PDEs
- A rotating-grid upwind fast sweeping scheme for a class of Hamilton-Jacobi equations
- Algorithm for Hamilton-Jacobi equations in density space via a generalized Hopf formula
- Binary structured physics-informed neural networks for solving equations with rapidly changing solutions
- On Hamilton-Jacobi PDEs and image denoising models with certain nonadditive noise
- Algorithm for overcoming the curse of dimensionality for state-dependent Hamilton-Jacobi equations
- Consistent smooth approximation of feedback laws for infinite horizon control problems with non-smooth value functions
- A kernel based high order ``explicit unconditionally stable scheme for time dependent Hamilton-Jacobi equations
- A multilevel fast marching method for the minimum time problem
- Algorithms for solving high dimensional PDEs: from nonlinear Monte Carlo to machine learning
- Monotone discretizations of levelset convex geometric PDEs
- Overcoming the curse of dimensionality for some Hamilton-Jacobi partial differential equations via neural network architectures
- Algorithm for overcoming the curse of dimensionality for time-dependent non-convex Hamilton-Jacobi equations arising from optimal control and differential games problems
- Revisiting the redistancing problem using the Hopf-Lax formula
- Algorithm for overcoming the curse of dimensionality for certain non-convex Hamilton-Jacobi equations, projections and differential games
- SympOCnet: Solving Optimal Control Problems with Applications to High-Dimensional Multiagent Path Planning Problems
- Error Estimates for a Tree Structure Algorithm Solving Finite Horizon Control Problems
- Optimal feedback control, linear first-order PDE systems, and obstacle problems
- HJB-RBF based approach for the control of PDEs
- Algorithms of data generation for deep learning and feedback design: a survey
- Recovery of a time-dependent bottom topography function from the shallow water equations via an adjoint approach
- Solving 1D conservation laws using Pontryagin's minimum principle
- Mitigating the curse of dimensionality: sparse grid characteristics method for optimal feedback control and HJB equations
- Parallel redistancing using the Hopf-Lax formula
- A splitting method for overcoming the curse of dimensionality in Hamilton-Jacobi equations arising from nonlinear optimal control and differential games with applications to trajectory generation
- An optimal control method to compute the most likely transition path for stochastic dynamical systems with jumps
- A deep learning Galerkin method for the second-order linear elliptic equations
- Sliding-mode surface-based approximate optimal control for nonlinear multiplayer Stackelberg-Nash games via adaptive dynamic programming
- An extreme learning machine-based method for computational PDEs in higher dimensions
- Jarzynski's equality, fluctuation theorems, and variance reduction: mathematical analysis and numerical algorithms
- Payoff suboptimality and errors in value induced by approximation of the Hamiltonian
- Deep learning-based numerical methods for high-dimensional parabolic partial differential equations and backward stochastic differential equations
This page was built for publication: Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313401)
