Thèse Année : 2023

Highway hierarchies for Hamilton-Jacobi-Bellman (HJB) PDEs

Hierarchies d'autoroutes pour les équations d'Hamilton-Jacobi-Bellman (HJB)

Résumé

In this thesis, we develop new numerical methods to solve deterministic optimal control problems and the associated first order Hamilton-Jacobi-Bellman (HJB) equations. Our primary aim is to mitigate the curse of dimensionality. One common idea in all our work is to focus on identifying one or several optimal trajectories with fixed initial and/or final conditions.In the first part, we address minimum time problems and solve eikonal equations. We introduce a multilevel fast marching method, relying on nested grid approximations to search for optimal trajectories within a tubular neighborhood obtained from coarse grid approximations.We establish the convergence and computational complexity of our algorithm. Furthermore, we analyze a Semi-Lagrangian scheme for eikonal equations. We demonstrate semiconcavity of the solution under certain conditions. This allows us to establish a convergence rate of order 1 for both the semi-discretized and fully discretized schemes, with the rate being in terms of the time step for the former and the mesh step for the latter.We apply these results to get convergence rate of the fast marching method and complexity of our multilevel fast marching method.In the second part, we explore tropical numerical methods for finite horizon problems. In a first work, we combine direct methods with the max-plus finite element method to achieve higher accuracy. Then, we combine the concepts of the first part with the tropical method to derive the best complexity bound under broader conditions. In a second work, we introduce a novel algorithm to numerically approximate the value at a fixed initial state, along with the optimal trajectory. This can be thought of as a combination of tropical numerical method and stochastic dual dynamic programming (SDDP) method. We show that our algorithm converges to the global optimum, in the case of semiconcave problems.
Dans cette thèse, nous développons de nouvelles méthodes numériques pour résoudre des problèmes de contrôle optimal déterministe et les équations d'Hamilton-Jacobi-Bellman (HJB) du premier ordre associées. L'objectif principal est d'atténuer la malédiction de la dimension. Une idée commune à tous nos travaux est de se concentrer sur le calcul d'une ou plusieurs trajectoires optimales avec des conditions initiales et/ou finales fixées.Dans la première partie, nous abordons les problèmes de temps minimum et la résolution des équations eikonales. Nous introduisons une méthode ``fast marching'' multi-niveaux, qui s'appuie sur des grilles imbriquées, permettant de rechercher les trajectoires optimales dans un voisinage tubulaire obtenu au moyen d'approximations dans des grilles grossières. Nous établissons la convergence et la complexité de notre algorithme. En outre, nous analysons un schéma Semi-Lagrangien pour les équations eikonales. Nous montrons la semiconcavité de la solution sous certaines conditions. Nous en déduisons un taux de convergence d'ordre 1 pour les schémas semi-discrétisés et entièrement discrétisés, le taux étant mesuré en terme de pas de temps pour le premier schéma et de pas en espace pour le second. Nous appliquons ces résultats pour obtenir le taux de convergence de la méthode ``fast marching'' et la complexité de notre méthode ``fast marching'' multi-niveaux.Dans la deuxième partie, nous explorons les méthodes num'eriques tropicales pour les problèmes en horizon fini.Dans un premier travail, nous combinons les méthodes directes avec la méthode des éléments finis max-plus, ce qui conduit à une plus grande précision. Ensuite, nous combinons les concepts de la première partie avec la méthode numérique tropicale afin d'obtenir la meilleure borne de complexité sous des conditions plus générales. Dans un deuxième travail, nous introduisons un nouvel algorithme pour approximer numériquement la valeur en un état initial fixé, ainsi que la trajectoire optimale correspondante. Cet algorithme peut être vu comme une combinaison de la méthode numérique tropicale et de la méthode de programmation dynamique stochastique duale. Nous montrons que notre algorithme converge vers l'optimum global, dans le cas de problèmes semi-concaves.
Fichier principal
Vignette du fichier
130690_LIU_2023_archivage-2.pdf (3) Télécharger le fichier
Origine Version validée par le jury (STAR)

Dates et versions

tel-04931347 , version 1 (05-02-2025)

Identifiants

  • HAL Id : tel-04931347 , version 1

Citer

Shanqing Liu. Hierarchies d'autoroutes pour les équations d'Hamilton-Jacobi-Bellman (HJB). Optimisation et contrôle [math.OC]. Institut Polytechnique de Paris, 2023. Français. ⟨NNT : 2023IPPAX107⟩. ⟨tel-04931347⟩
0 Consultations
0 Téléchargements

Partager

More