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

DOI10.4310/CMS.2018.V16.N7.A9zbMATH Open1480.49039arXiv1803.01215WikidataQ128250692 ScholiaQ128250692MaRDI QIDQ667010FDOQ667010

Alex Tong Lin, Stanley Osher, Yat Tin Chow

Publication date: 12 March 2019

Published in: Communications in Mathematical Sciences (Search for Journal in Brave)

Abstract: Recent observations have been made that bridge splitting methods arising from optimization, to the Hopf and Lax formulas for Hamilton-Jacobi Equations with Hamiltonians $H(p)$. This has produced extremely fast algorithms in computing solutions of these PDEs. More recent observations were made in generalizing the Hopf and Lax formulas to state-and-time-dependent cases $H(x,p,t)$. In this article, we apply a new splitting method based on the Primal Dual Hybrid Gradient algorithm (a.k.a. Chambolle-Pock) to nonlinear optimal control and differential games problems, based on techniques from the derivation of the new Hopf and Lax formulas, which allow us to compute solutions at points $(x,t)$ directly, i.e. without the use of grids in space. This algorithm also allows us to create trajectories directly. Thus we are able to lift the curse of dimensionality a bit, and therefore compute solutions in much higher dimensions than before. And in our numerical experiments, we actually observe that our computations scale polynomially in time. Furthermore, this new algorithm is embarrassingly parallelizable.

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

Recommendations

• Splitting Enables Overcoming the Curse of Dimensionality
• 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 certain non-convex Hamilton-Jacobi equations, projections and differential games
• Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere
• Algorithm for overcoming the curse of dimensionality for state-dependent Hamilton-Jacobi equations

zbMATH Keywords

optimizationdifferential gamesHamilton-Jacobi equationsoptimal controlHopf-Lax formulaconvex-concave gamesnonconvex Hamiltoniannonsmooth Hamiltoniantrajectory generation

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Nonconvex programming, global optimization (90C26) Differential games and control (49N70) Minimax problems in mathematical programming (90C47) Hamilton-Jacobi equations (35F21) Optimality conditions for problems involving partial differential equations (49K20) Optimality conditions for minimax problems (49K35) Hamilton-Jacobi theories (49L99) Numerical aspects of the method of characteristics for initial value and initial-boundary value problems involving PDEs (65M25) Numerical methods in optimal control (49M99) Model predictive control (93B45)

Cited In (7)

• Value-Gradient Based Formulation of Optimal Control Problem and Machine Learning Algorithm
• A simple multiscale method for mean field games
• A neural network approach for stochastic optimal control
• A numerical construction of the universal feedback control in problems of nonlinear controls under disturbance
• A rotating-grid upwind fast sweeping scheme for a class of Hamilton-Jacobi equations
• Fourier approximation methods for first-order nonlocal mean-field games
• Algorithms of data generation for deep learning and feedback design: a survey

This page was built for publication: 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

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