Tensor Decomposition Methods for High-dimensional Hamilton--Jacobi--Bellman Equations

Dolgov, Sergey; Kalise, Dante; Kunisch, Karl

Abstract

A tensor decomposition approach for the solution of high-dimensional, fully nonlin-ear Hamilton-Jacobi-Bellman equations arising in optimal feedback control of nonlinear dynamics is presented. The method combines a tensor train approximation for the value function together with a Newton-like iterative method for the solution of the resulting nonlinear system. The tensor approximation leads to a polynomial scaling with respect to the dimension, partially circumventing the curse of dimensionality. A convergence analysis for the linear-quadratic optimal control problem is presented. For nonlinear dynamics, the effectiveness of the high-dimensional control synthesis method is assessed in the optimal feedback stabilization of the Allen-Cahn and Fokker-Planck equations with a hundred of variables. 1. Introduction. Richard Bellman first coined the expression "curse of dimen-sionality" when referring to the overwhelming computational complexity associated to the solution of multi-stage decision processes through dynamic programming, what is nowadays known as Bellman's equation. More than 60 years down the road, the curse of dimensionality has become ubiquitous in different fields such as numerical analysis, compressed sensing and statistical machine learning. However, it is in the computation of optimal feedback policies for the control of dynamical systems where its meaning continues to be most evident. Here, the curse of dimensionality arises since the synthesis of optimal feedback laws by dynamic programming techniques demands the solution of a Hamilton-Jacobi-Bellman (HJB) fully nonlinear Partial Differential Equation (PDE) cast over the state space of the dynamics. This intrinsic relation between the dimensions of the state space of the control system and the domain of the HJB PDE generates computational challenges of formidable complexity even for relatively simple dynamical systems 1. Much of the research in control revolves around circumventing this barrier through different trade-offs between dimensional-ity, performance, and optimality of the control design. Prominent examples of the research landscape shaped by the curse of dimensionality include model order reduction , model predictive control, suboptimal feedback design, reinforcement learning and distributed control. However, the effective computational solution of dynamic programming equations of arbitrarily high dimensions through deterministic methods remains an open quest with fundamental implications in optimal control design.

Citation

Dolgov, S., Kalise, D., & Kunisch, K. (2021). Tensor Decomposition Methods for High-dimensional Hamilton--Jacobi--Bellman Equations. SIAM Journal on Scientific Computing, 43(3), A1625-A1650. https://doi.org/10.1137/19m1305136

• Journal Article Type: Article
• Acceptance Date: Feb 11, 2021
• Online Publication Date: May 10, 2021
• Publication Date: May 10, 2021
• Deposit Date: Feb 26, 2021
• Publicly Available Date: May 10, 2021
• Journal: SIAM Journal on Scientific Computing
• Print ISSN: 1064-8275
• Electronic ISSN: 1095-7197
• Publisher: Society for Industrial and Applied Mathematics
• Peer Reviewed: Peer Reviewed
• Volume: 43
• Issue: 3
• Pages: A1625-A1650
• DOI: https://doi.org/10.1137/19m1305136
• Keywords: Dynamic Programming; Optimal Feedback Control; Hamilton-Jacobi-Bellman Equations; Tensor Calculus; High-dimensional Approximations
• Public URL: https://nottingham-repository.worktribe.com/output/5352260
• Publisher URL: https://epubs.siam.org/doi/10.1137/19M1305136