The classical Dynamic Programming (DP) approach to optimal control problems is based on the characterization of the value function as the unique viscosity solution of a Hamilton-Jacobi-Bellman (HJB) equation. The DP scheme for the numerical approximation of viscosity solutions of Bellman equations is typically based on a time discretization which is projected on a fixed state-space grid. The time discretization can be done by a one-step scheme for the dynamics and the projection on the grid typically uses a local interpolation. Clearly the use of a grid is a limitation with respect to possible applications in high-dimensional problems due to the curse of dimensionality. Here, we present a new approach for finite horizon optimal control problems where the value function is computed using a DP algorithm with a tree structure algorithm (TSA) constructed by the time discrete dynamics. In this way there is no need to build a fixed space triangulation and to project on it. The tree will guarantee a perfect matching with the discrete dynamics and drop off the cost of the space interpolation allowing for the solution of very high-dimensional problems. Then, we analyse first order error estimates which ensure the convergence of the scheme. Finally, we introduce the extension to high-order schemes and the coupling with Proper Orthogonal Decomposition technique. Numerical tests will show the effectiveness of the proposed method.

A Tree-Structure Algorithm for Optimal Control Problems via Dynamic Programming / Saluzzi, Luca. - (2020 Feb 10).

A Tree-Structure Algorithm for Optimal Control Problems via Dynamic Programming

SALUZZI, LUCA
2020-02-10

Abstract

The classical Dynamic Programming (DP) approach to optimal control problems is based on the characterization of the value function as the unique viscosity solution of a Hamilton-Jacobi-Bellman (HJB) equation. The DP scheme for the numerical approximation of viscosity solutions of Bellman equations is typically based on a time discretization which is projected on a fixed state-space grid. The time discretization can be done by a one-step scheme for the dynamics and the projection on the grid typically uses a local interpolation. Clearly the use of a grid is a limitation with respect to possible applications in high-dimensional problems due to the curse of dimensionality. Here, we present a new approach for finite horizon optimal control problems where the value function is computed using a DP algorithm with a tree structure algorithm (TSA) constructed by the time discrete dynamics. In this way there is no need to build a fixed space triangulation and to project on it. The tree will guarantee a perfect matching with the discrete dynamics and drop off the cost of the space interpolation allowing for the solution of very high-dimensional problems. Then, we analyse first order error estimates which ensure the convergence of the scheme. Finally, we introduce the extension to high-order schemes and the coupling with Proper Orthogonal Decomposition technique. Numerical tests will show the effectiveness of the proposed method.
10-feb-2020
A Tree-Structure Algorithm for Optimal Control Problems via Dynamic Programming / Saluzzi, Luca. - (2020 Feb 10).
File in questo prodotto:
File Dimensione Formato  
2020_Saluzzi.pdf

accesso aperto

Tipologia: Tesi di dottorato
Licenza: Accesso gratuito
Dimensione 10.6 MB
Formato Adobe PDF
10.6 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12571/10021
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact