Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations

DOI10.1007/S00245-018-9509-6zbMATH Open1461.49028arXiv1711.03314OpenAlexW2767915842MaRDI QIDQ2019982FDOQ2019982

Ivan Yegorov, Peter M. Dower

Publication date: 22 April 2021

Published in: Applied Mathematics and Optimization (Search for Journal in Brave)

Abstract: This paper extends the considerations of the works [1, 2] regarding curse-of-dimensionality-free numerical approaches to solve certain types of Hamilton-Jacobi equations arising in optimal control problems, differential games and elsewhere. A rigorous formulation and justification for the extended Hopf-Lax formula of [2] is provided together with novel theoretical and practical discussions including useful recommendations. By using the method of characteristics, the solutions of some problem classes under convexity/concavity conditions on Hamiltonians (in particular, the solutions of Hamilton-Jacobi-Bellman equations in optimal control problems) are evaluated separately at different initial positions. This allows for the avoidance of the curse of dimensionality, as well as for choosing arbitrary computational regions. The corresponding feedback control strategies are obtained at selected positions without approximating the partial derivatives of the solutions. The results of numerical simulations demonstrate the high potential of the proposed techniques. It is also pointed out that, despite the indicated advantages, the related approaches still have a limited range of applicability, and their extensions to Hamilton-Jacobi-Isaacs equations in zero-sum two-player differential games are currently developed only for sufficiently narrow classes of control systems. That is why further extensions are worth investigating.

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

Recommendations

• Algorithm for overcoming the curse of dimensionality for state-dependent Hamilton-Jacobi equations
• Algorithm for overcoming the curse of dimensionality for certain non-convex Hamilton-Jacobi equations, projections and differential games
• Algorithm for overcoming the curse of dimensionality for time-dependent non-convex Hamilton-Jacobi equations arising from optimal control and differential games problems
• Stable numerical schemes for solving Hamilton-Jacobi-Bellman-Isaacs equations
• Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere

zbMATH Keywords

curse of dimensionalitydifferential gamesHamilton-Jacobi equationsoptimal controlmethod of characteristicsfeedback strategies

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Differential games and control (49N70) Hamilton-Jacobi equations (35F21) Optimality conditions for problems involving ordinary differential equations (49K15) Dynamic programming in optimal control and differential games (49L20) Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games (49L25) Finite difference methods for initial value and initial-boundary value problems involving PDEs (65M06) Numerical aspects of the method of characteristics for initial value and initial-boundary value problems involving PDEs (65M25) Numerical methods based on necessary conditions (49M05) Optimal feedback synthesis (49N35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations
• Convex Analysis
• Numerical recipes. The art of scientific computing.
• Differential inclusions and optimal control
• Level set methods and dynamic implicit surfaces
• Controlled Markov processes and viscosity solutions
• Reachability and Minimal Times for State Constrained Nonlinear Problems without Any Controllability Assumption
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• High-Order WENO Schemes for Hamilton--Jacobi Equations on Triangular Meshes
• A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games
• NUMERICAL METHODS FOR DIFFERENTIAL GAMES BASED ON PARTIAL DIFFERENTIAL EQUATIONS
• Title not available (Why is that?)
• An efficient data structure and accurate scheme to solve front propagation problems
• Max-plus methods for nonlinear control and estimation.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The method of characteristics for Hamilton-Jacobi equations and applications to dynamical optimization
• Convergence Rate for a Curse-of-Dimensionality-Free Method for a Class of HJB PDEs
• A Curse-of-Dimensionality-Free Numerical Method for Solution of Certain HJB PDEs
• Convergence Analysis for a Class of High-Order Semi-Lagrangian Advection Schemes
• Title not available (Why is that?)
• Model predictive control system design and implementation using \texttt{MATLAB}
• A Level Set Formulation for the Solution of the Dirichlet Problem for Hamilton–Jacobi Equations
• Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations
• Numerical solution of stochastic differential problems in the biosciences
• Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere
• High-Order Essentially Nonoscillatory Schemes for Hamilton–Jacobi Equations
• Two Approximations of Solutions of Hamilton-Jacobi Equations
• Weighted ENO Schemes for Hamilton--Jacobi Equations
• On the structure of locally Lipschitz minimax solutions of the Hamilton-Jacobi-Bellman equation in terms of classical characteristics
• The Max-Plus Finite Element Method for Solving Deterministic Optimal Control Problems: Basic Properties and Convergence Analysis
• Title not available (Why is that?)
• On the efficiency of optimal grid synthesis in optimal control problems with fixed terminal time
• Fast Semi-Lagrangian Schemes for the Eikonal Equation and Applications
• The Existence of Value and Saddle Point in Games of Fixed Duration
• Envelopes and nonconvex Hamilton-Jacobi equations
• Title not available (Why is that?)
• Mitigating the curse of dimensionality: sparse grid characteristics method for optimal feedback control and HJB equations
• Geometry of optimal paths around focal singular surfaces in differential games
• Title not available (Why is that?)
• Estimating error of the optimal grid design in the problems of nonlinear optimal control of prescribed duration
• Differential Games
• Algorithm for overcoming the curse of dimensionality for time-dependent non-convex Hamilton-Jacobi equations arising from optimal control and differential games problems
• Generalized Hopf formulas for the nonautonomous Hamilton-Jacobi equation
• Probabilistic max-plus schemes for solving Hamilton-Jacobi-Bellman equations

Cited In (15)

• Lax-Oleinik-type formulas and efficient algorithms for certain high-dimensional optimal control problems
• On some neural network architectures that can represent viscosity solutions of certain high dimensional Hamilton-Jacobi partial differential equations
• Robust Feedback Control of Nonlinear PDEs by Numerical Approximation of High-Dimensional Hamilton--Jacobi--Isaacs Equations
• Title not available (Why is that?)
• Neural network architectures using min-plus algebra for solving certain high-dimensional optimal control problems and Hamilton-Jacobi PDEs
• A tree structure approach to reachability analysis
• 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
• Exploiting characteristics in stationary action problems
• Tensor Decomposition Methods for High-dimensional Hamilton--Jacobi--Bellman Equations
• Overcoming the curse of dimensionality for some Hamilton-Jacobi partial differential equations via neural network architectures
• Reliable optimal controls for SEIR models in epidemiology
• SympOCnet: Solving Optimal Control Problems with Applications to High-Dimensional Multiagent Path Planning Problems
• Adaptive Deep Learning for High-Dimensional Hamilton--Jacobi--Bellman Equations
• Algorithms of data generation for deep learning and feedback design: a survey

Uses Software

• ToolboxLS
• ROC-HJ

This page was built for publication: Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2019982)