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

DOI10.1186/S40687-016-0068-7zbMATH Open1348.49026arXiv1605.01799OpenAlexW2963395620WikidataQ59469038 ScholiaQ59469038MaRDI QIDQ313401FDOQ313401

Authors: Jérôme Darbon, Stanley Osher 

Publication date: 9 September 2016

Published in: Research in the Mathematical Sciences (Search for Journal in Brave)

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 $el{l}_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.

Full work available at URL: https://arxiv.org/abs/1605.01799

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

zbMATH Keywords

Hamilton-Jacobi equationsnumerical methodsoptimal control

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Dynamic programming in optimal control and differential games (49L20) Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games (49L25)

Cites Work

• Splitting Algorithms for the Sum of Two Nonlinear Operators
• A note on two problems in connexion with graphs
• On total variation minimization and surface evolution using parametric maximum flows
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations
• The Split Bregman Method for L1-Regularized Problems
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• Multiplier and gradient methods
• A first-order primal-dual algorithm for convex problems with applications to imaging
• Title not available (Why is that?)
• Some Properties of Viscosity Solutions of Hamilton-Jacobi Equations
• Title not available (Why is that?)
• Viscosity Solutions of Hamilton-Jacobi Equations
• Title not available (Why is that?)
• Monotone Operators and the Proximal Point Algorithm
• Title not available (Why is that?)
• High-Order WENO Schemes for Hamilton--Jacobi Equations on Triangular Meshes
• An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
• A Discontinuous Galerkin Finite Element Method for Hamilton--Jacobi Equations
• Title not available (Why is that?)
• A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games
• Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
• Proximité et dualité dans un espace hilbertien
• Title not available (Why is that?)
• Max-plus methods for nonlinear control and estimation.
• Title not available (Why is that?)
• Dynamics and control of trajectory tubes. Theory and computation
• Convergence of Proximal-Like Algorithms
• Fast Sweeping Algorithms for a Class of Hamilton--Jacobi Equations
• Efficient algorithms for globally optimal trajectories
• Title not available (Why is that?)
• Redistancing by flow of time dependent eikonal equation
• The Wulff shape as the asymptotic limit of a growing crystalline interface
• Overapproximating reachable sets by Hamilton-Jacobi projections
• Error forgetting of Bregman iteration
• On Convex Finite-Dimensional Variational Methods in Imaging Sciences and Hamilton--Jacobi Equations
• Proximal Thresholding Algorithm for Minimization over Orthonormal Bases
• Numerical methods for anisotropic mean curvature flow based on a discrete time variational formulation
• Hopf Formula and Multitime Hamilton-Jacobi Equations
• Title not available (Why is that?)
• High-Order Essentially Nonoscillatory Schemes for Hamilton–Jacobi Equations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (48)

• Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations
• Title not available (Why is that?)
• 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
• A review of level-set methods and some recent applications
• 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
• Value-Gradient Based Formulation of Optimal Control Problem and Machine Learning Algorithm
• An adaptive sparse grid local discontinuous Galerkin method for Hamilton-Jacobi equations in high dimensions
• 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
• Optimal polynomial feedback laws for finite horizon control problems
• Machine learning approximation algorithms for high-dimensional fully nonlinear partial differential equations and second-order backward stochastic differential equations
• Title not available (Why is that?)
• 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
• Binary structured physics-informed neural networks for solving equations with rapidly changing solutions
• Algorithm for Hamilton-Jacobi equations in density space via a generalized Hopf formula
• 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
• 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
• HJB-RBF based approach for the control of PDEs
• Recovery of a time-dependent bottom topography function from the shallow water equations via an adjoint approach
• Optimal feedback control, linear first-order PDE systems, and obstacle problems
• Algorithms of data generation for deep learning and feedback design: a survey
• 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
• An optimal control method to compute the most likely transition path for stochastic dynamical systems with jumps
• 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
• 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)