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)- Machine learning approximation algorithms for high-dimensional fully nonlinear partial differential equations and second-order backward stochastic differential equations
- Constraint control of nonholonomic mechanical systems
- Error Estimates for a Tree Structure Algorithm Solving Finite Horizon Control Problems
- An overview on deep learning-based approximation methods for partial differential equations
- On some neural network architectures that can represent viscosity solutions of certain high dimensional Hamilton-Jacobi partial differential equations
- A review of level-set methods and some recent applications
- Value-Gradient Based Formulation of Optimal Control Problem and Machine Learning Algorithm
- Algorithm for overcoming the curse of dimensionality for certain non-convex Hamilton-Jacobi equations, projections and differential games
- Optimal feedback control, linear first-order PDE systems, and obstacle problems
- A rotating-grid upwind fast sweeping scheme for a class of Hamilton-Jacobi equations
- 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
- Algorithms for solving high dimensional PDEs: from nonlinear Monte Carlo to machine learning
- Algorithms of data generation for deep learning and feedback design: a survey
- 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
- Deep learning-based numerical methods for high-dimensional parabolic partial differential equations and backward stochastic differential equations
- SympOCnet: Solving Optimal Control Problems with Applications to High-Dimensional Multiagent Path Planning Problems
- Adaptive deep neural networks methods for high-dimensional partial differential equations
- Three ways to solve partial differential equations with neural networks — A review
- 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
- Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations
- Neural network architectures using min-plus algebra for solving certain high-dimensional optimal control problems and Hamilton-Jacobi PDEs
- Parallel redistancing using the Hopf-Lax formula
- HJB-RBF based approach for the control of PDEs
- Lax-Oleinik-type formulas and efficient algorithms for certain high-dimensional optimal control problems
- Jarzynski's equality, fluctuation theorems, and variance reduction: mathematical analysis and numerical algorithms
- A multilevel fast marching method for the minimum time problem
- Adaptive deep learning for high-dimensional Hamilton-Jacobi-Bellman equations
- Operator-splitting based fast sweeping methods for isotropic wave propagation in a moving fluid
- An efficient algorithm for Hamilton-Jacobi equations in high dimension
- An adaptive sparse grid local discontinuous Galerkin method for Hamilton-Jacobi equations in high dimensions
- An optimal control method to compute the most likely transition path for stochastic dynamical systems with jumps
- Payoff suboptimality and errors in value induced by approximation of the Hamiltonian
- scientific article; zbMATH DE number 7370565 (Why is no real title available?)
- Algorithm for Hamilton-Jacobi equations in density space via a generalized Hopf formula
- Algorithm for overcoming the curse of dimensionality for state-dependent Hamilton-Jacobi equations
- A deep learning Galerkin method for the second-order linear elliptic equations
- Consistent smooth approximation of feedback laws for infinite horizon control problems with non-smooth value functions
- Recovery of a time-dependent bottom topography function from the shallow water equations via an adjoint approach
- Optimal polynomial feedback laws for finite horizon control problems
- 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
- Solving 1D conservation laws using Pontryagin's minimum principle
- scientific article; zbMATH DE number 1168338 (Why is no real title available?)
- Mitigating the curse of dimensionality: sparse grid characteristics method for optimal feedback control and HJB equations
- A kernel based high order ``explicit unconditionally stable scheme for time dependent Hamilton-Jacobi 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)
