In the dynamic programming approach to optimal control problems a crucial role is played by the value function that is characterized as the unique viscosity solution of a Hamilton-Jacobi-Bellman (HJB) equation. It is well known that this approach suffers from the “curse of dimensionality” and this limitation has reduced its use in real world applications. Here, we analyze a dynamic programming algorithm based on a tree structure to mitigate the “curse of dimensionality”. The tree is built by the discrete time dynamics avoiding the use of a fixed space grid which is the bottleneck for highdimensional problems, this also drops the projection on the grid in the approximation of the value function. In this work, we present first order error estimates for the the approximation of the value function based on the tree-structure algorithm. The estimate turns out to have the same order of convergence of the numerical method used for the approximation of the dynamics. Furthermore, we analyze a pruning technique for the tree to reduce the complexity and minimize the computational effort. Finally, we present some numerical tests to show the theoretical results.
Keywords: Dynamic programming, Hamilton-Jacobi-Bellman equation, optimal control, tree structure, error estimates
@article{COCV_2022__28_1_A69_0,
author = {Saluzzi, Luca and Alla, Alessandro and Falcone, Maurizio},
title = {Error {Estimates} for a {Tree} {Structure} {Algorithm} {Solving} {Finite} {Horizon} {Control} {Problems}},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
year = {2022},
publisher = {EDP-Sciences},
volume = {28},
doi = {10.1051/cocv/2022067},
mrnumber = {4506570},
zbl = {1503.49025},
language = {en},
url = {https://www.numdam.org/articles/10.1051/cocv/2022067/}
}
TY - JOUR AU - Saluzzi, Luca AU - Alla, Alessandro AU - Falcone, Maurizio TI - Error Estimates for a Tree Structure Algorithm Solving Finite Horizon Control Problems JO - ESAIM: Control, Optimisation and Calculus of Variations PY - 2022 VL - 28 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/cocv/2022067/ DO - 10.1051/cocv/2022067 LA - en ID - COCV_2022__28_1_A69_0 ER -
%0 Journal Article %A Saluzzi, Luca %A Alla, Alessandro %A Falcone, Maurizio %T Error Estimates for a Tree Structure Algorithm Solving Finite Horizon Control Problems %J ESAIM: Control, Optimisation and Calculus of Variations %D 2022 %V 28 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/cocv/2022067/ %R 10.1051/cocv/2022067 %G en %F COCV_2022__28_1_A69_0
Saluzzi, Luca; Alla, Alessandro; Falcone, Maurizio. Error Estimates for a Tree Structure Algorithm Solving Finite Horizon Control Problems. ESAIM: Control, Optimisation and Calculus of Variations, Tome 28 (2022), article no. 69. doi: 10.1051/cocv/2022067
[1] , and , The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis. SIAM J. Control Optim. 47 (2008) 817–848. | MR | Zbl | DOI
[2] , and , An efficient policy iteration algorithm for dynamic programming equations. SIAM J. Sci. Comput. 37 (2015) 181–200. | MR | Zbl | DOI
[3] , and , An efficient DP algorithm on a tree-structure for finite horizon optimal control problems. SIAM J. Sci. Comput. 41 (2019) A2384–A2406. | MR | Zbl | DOI
[4] , and , High-order approximation of the finite horizon control problem via a tree structure algorithm. IFAC-PapersOnLine 52 (2019) 19–24. | MR | DOI
[5] , and , A tree structure algorithm for optimal control problems with state constraints. Rend. Matemat. Sue Applic. 41 (2020) 193–221. | MR | Zbl
[6] , and , Error analysis for POD approximations of infinite horizon problems via the dynamic programming approach. SIAM J. Control Optim. 55 (2017) 3091–3115. | MR | Zbl | DOI
[7] and , A HJB-POD approach for the control of nonlinear PDEs on a tree structure. Appl. Numer. Math. 155 (2020) 192–207. | MR | Zbl | DOI
[8] and , Feedback reconstruction techniques for optimal control problems on a tree structure, Preprint (2022). | arXiv | Zbl
[9] , and , , Value function and optimal trajectories for a maximum running cost control problem with state constraints. Application to an abort landing problem. ESAIM: Math. Model. Numer. Anal 52 (2018) 305–335. | MR | Zbl | Numdam | DOI
[10] , , and , Deep neural networks algorithms for stochastic control problems on finit hotizone: numerical applications. Methodol. Comput. Appl. Probab. 24 (2022) 143–178. | MR | Zbl | DOI
[11] and , Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Birkhäuser, Basel (1997). | Zbl | DOI
[12] , Dynamic Programming. Princeton University Press, Princeton, NJ (1957). | MR | Zbl
[13] , , and , A numerical comparison of different solvers for large-scale, continuous-time algebraic Riccati equations and LQR problems. SIAM J. Sci. Comput. 42 (2020) A957–A996. | MR | Zbl | DOI
[14] , and , Numerical Solution of Algebraic Riccati Equations, Fundam. Algorithms, SIAM, Philadelphia (2012). | MR | Zbl
[15] , , and , A patchy dynamic programming scheme for a class of Hamilton-Jacobi- Bellman equations. SIAM J. Sci. Comput. 34 (2012) A2625–A2649. | MR | Zbl | DOI
[16] and , Semiconcave functions, Hamilton-Jacobi equations and optimal control problems. Birkhäuser Boston (2004). | MR | Zbl | DOI
[17] , On a discrete approximation of the Hamilton-Jacobi equation of dynamic programming. Appl. Math. Optim. 10 (1983) 367–377. | MR | Zbl | DOI
[18] and , Approximate solutions of the Bellman equation of deterministic control theory. Appl. Math. Optim. 11 (1984) 161–181. | MR | Zbl | DOI
[19] and , Splitting enables overcoming the curse of dimensionality. Splitting methods in communication, imaging, science, and engineering, Sci. Comput., Springer, Cham (2016) 427–432. | MR | Zbl
[20] and , Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere. Res. Math. Sci. 3 (2016) 19–26. | MR | Zbl | DOI
[21] , and , Tensor decompositions for high-dimensional Hamilton-Jacobi-Bellman equations. SIAM J. Sci. Comput. 43 (2021) A1625–A1650. | MR | Zbl | DOI
[22] , and , Data-driven Tensor Train Gradient Cross Approximation for Hamilton-Jacobi-Bellman Equations. Preprint (2022). | arXiv | MR
[23] , A numerical approach to the infinite horizon problem of deterministic control theory, Appl. Math. Optim. 15 (1987) 1–13. | MR | Zbl | DOI
[24] and , Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations. Numer. Math. 67 (1994) 315–344. | MR | Zbl | DOI
[25] and , Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi equations. SIAM (2013). | MR | Zbl
[26] and , An approximation scheme for evolutive Hamilton-Jacobi equations, in , and (eds.), “Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming”. Birkhaäuser (1999) 289–303. | MR
[27] , and , A splitting algorithm for Hamilton-Jacobi-Bellman equations. Appl. Numer. Math. 15 (1994) 207–218. | MR | Zbl | DOI
[28] , Domain decomposition based parallel Howard’s algorithm. Math. Comput. Simul. 147 (2018) 121–139. | MR | Zbl | DOI
[29] and , Controlled Markov processes and viscosity solutions. Springer–Verlag, New York (1993). | MR | Zbl
[30] and , Suboptimal feedback control of PDEs by solving HJB equations on adaptive sparse grids. J. Sci. Comput. 70 (2017) 1–28. | MR | Zbl | DOI
[31] and , Nonlinear Model Predictive Control. Springer (2011). | MR | Zbl | DOI
[32] , Dynamic programming, optimal control and model predictive control. Handbook of Model Predictive Control. Control Eng., Birkhäuser/Springer, Cham (2019), pp. 29–52. | MR | DOI
[33] , and , Solving high-dimensional partial differential equations using deep learning. Proc. Natl. Acad. Sci. USA 115 (2018) 8505–8510. | MR | Zbl | DOI
[34] , , and , vol. 23 of Optimization with PDE Constraints. Mathematical Modelling: Theory and Applications. Springer–Verlag (2009). | MR | Zbl
[35] , , and , Deep neural networks algorithms for stochastic control problems on finite horizon: Convergence analysis. SINUM 59 (2021) 525–557. | MR | Zbl | DOI
[36] and , Polynomial approximation of high-dimensional Hamilton-Jacobi-Bellman equations and applications to feedback control of semilinear parabolic PDEs. SIAM J. Sci. Comput. 40 (2018) A629–A652. | MR | Zbl | DOI
[37] , and , HJB-POD based feedback design for the optimal control of evolution problems. SIAM J. Appl. Dyn. Syst. 4 (2004) 701–722. | MR | Zbl | DOI
[38] , Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems. SIAM Book (2007). | MR | Zbl | DOI
[39] , Convergence rate for a curse-of-dimensionality-free method for Hamilton-Jacobi-Bellman PDEs represented as maxima of quadratic forms. SIAM J. Control Optim. 48 (2009) 2651–2685. | MR | Zbl | DOI
[40] , A curse-of-dimensionality-free numerical method for solution of certain HJB PDEs. SIAM J. Control Optim. 46 (2007) 1239–1276. | MR | Zbl | DOI
[41] and , Patchy solutions of Hamilton-Jacobi-Bellman partial differential equations, in et al. (eds.), vol. 364 of Modeling, Estimation and Control, Lecture Notes in Control and Information Sciences (2007), pp. 251–270. | MR | Zbl
[42] and , Level Set Methods and Dynamic Implicit Surfaces. Springer (2003). | MR | Zbl | DOI
[43] , A Tree-Structure Algorithm for Optimal Control Problems via Dynamic Programming, PhD thesis, Gran Sasso Science Institute (2020) https://iris.gssi.it/handle/20.500.12571/10021.
[44] , Level set methods and fast marching methods. Cambridge University Press (1999). | MR | Zbl
[45] , Analysis of the rational Krylov subspace projection method for large-scale algebraic Riccati equations. SIAM J. Matrix Anal. Appl. 37 (2016) 1655–1674. | MR | Zbl | DOI
[46] , and , On two numerical methods for the solution of large-scale algebraic Riccati equations. IMA J. Numer. Anal. 34 (2014) 904–920. | MR | Zbl | DOI
[47] , Model Reduction using Proper Orthogonal Decomposition, Lecture Notes, University of Konstanz (2013).
[48] , and , A characteristics based curse-of-dimensionality-free approach for approximating control Lyapunov functions and feedback stabilization. Proceedings of the 23rd International Symposium on Mathematical Theory of Networks and Systems Hong Kong University of Science and Technology, Hong Kong, July 16–20 (2018) 342–349.
Cité par Sources :
Funding: This work was supported by the Italian Ministry of Instruction, University and Research (MIUR) PRIN Project 2107 (2017KKJP4X entitled ”Innovative numerical methods for evolutionary partial differential equations and applications
