Optimal bounds for numerical approximations of infinite horizon problems based on dynamic programming approach

Résumé Technique : Bornes Optimales pour les Approximations Numériques de Problèmes à Horizon Infini Basées sur une Approche de Programmation Dynamique

Énoncé du Problème
L'article traite de l'approximation numérique de problèmes de contrôle optimal à horizon infini pilotés par des systèmes dynamiques dans $\mathbb{R}^n$. La fonction de valeur pour de tels problèmes est caractérisée comme la solution viscosité d'une équation aux dérivées partielles de Hamilton-Jacobi-Bellman (HJB) non linéaire de premier ordre. Bien que divers schémas d'approximation existent (différences finies, semi-lagrangiens, volumes finis), un défi important demeure dans l'établissement de bornes d'erreur rigoureuses pour les méthodes entièrement discrètes incluant à la fois la discrétisation temporelle et spatiale.

La littérature existante, faisant spécifiquement référence aux travaux de Falcone et Ferretti [12] et d'autres [9, 11], établit une borne d'erreur de taille $O(k/h)$ pour les méthodes semi-lagrangiennes entièrement discrètes, où $h$ est le pas de temps et $k$ est le maillage spatial. Cette borne suggère qu'à mesure que le pas de temps $h$ diminue, l'erreur se détériore en raison du facteur $1/h$. Cependant, les auteurs notent que les expériences numériques dans la littérature (par exemple, [4]) n'observent pas ce comportement en $1/h$, suggérant que la borne théorique est sous-optimale. L'article vise à résoudre cette divergence en révisant l'analyse de l'erreur pour prouver une borne plus étroite.

Méthodologie
Les auteurs proposent une nouvelle caractérisation de l'approximation entièrement discrète pour dériver des bornes d'erreur améliorées. La méthodologie procède comme suit :

1. Reformulation via des Fonctionnelles de Coût : Au lieu de s'appuyer uniquement sur le principe de programmation dynamique standard, les auteurs définissent une fonctionnelle de coût entièrement discrète $\hat{J}_{h,k}$. Cette fonctionnelle utilise un opérateur d'interpolation linéaire $I_k$ appliqué à la dynamique du système et au coût courant à chaque pas de temps.
2. Caractérisation de la Solution : Le Théorème 3 prouve que la fonction de valeur entièrement discrète $v_{h,k}$ (définie par l'équation de programmation dynamique discrète) est exactement l'infimum de cette nouvelle fonctionnelle de coût entièrement discrète sur l'espace des séquences de commandes admissibles. Cela reflète la caractérisation utilisée pour le cas semi-discret dans [5].
3. Décomposition de l'Erreur : L'analyse de l'erreur compare la fonctionnelle de coût continue $\hat{J}$ avec la fonctionnelle entièrement discrète $\hat{J}_{h,k}$. La différence est bornée en analysant les erreurs de trajectoire entre la solution du système continu $y(t)$ et la solution interpolée discrète $\tilde{y}(t)$, ainsi que les erreurs d'interpolation des fonctions de coût et de dynamique.
4. Hypothèses de Régularité : L'analyse considère différentes hypothèses de régularité sur les entrées de commande $u(t)$ :
   • Commandes uniformément continues (avec un nombre fini de discontinuités de saut).
   • Commandes lipschitziennes.
   • Commandes constantes par morceaux (sous une hypothèse de convexité sur l'ensemble des dynamiques/coûts).

Contributions Clés et Résultats

• Borne d'Erreur Améliorée : La principale contribution est la preuve que l'erreur entre la fonction de valeur continue $v$ et l'approximation entièrement discrète $v_{h,k}$ est de l'ordre de $O(h + k)$, plutôt que de l'ordre précédemment cité de $O(k/h)$. Cela établit une convergence de premier ordre en temps et en espace, cohérente avec l'utilisation d'une discrétisation temporelle d'Euler de premier ordre et d'une approximation spatiale linéaire par morceaux.
• Théorème 4 (Borne Générale) : Sous les hypothèses de Lipschitz standard sur la dynamique du système $f$ et le coût $g$, et en supposant $\lambda > L$ (où $L$ est une constante dérivée des constantes de Lipschitz), l'erreur est bornée par :
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 M_u$$
  où $M_u$ mesure l'oscillation de la commande au sein des intervalles de temps.
• Théorème 6 (Commandes Lipschitziennes) : Si les commandes sont Lipschitz continues, $M_u$ est proportionnel à $h$, résultant en la borne d'erreur optimale :
  $$|v(y) - v_{h,k}(y)| \leq C(h + k)$$
• Théorème 5 (Commandes Uniformément Continues) : Si les commandes sont simplement uniformément continues (autorisant un nombre fini de sauts), l'erreur converge vers zéro lorsque $h, k \to 0$, bien que le taux spécifique dépende du module de continuité.
• Commandes Constantes par Morceaux (Théorème 7) : Adaptant les arguments de [6] (originellement pour les problèmes à horizon fini) au cas de l'horizon infini, les auteurs prouvent la convergence sous une hypothèse de convexité (CA) sur l'ensemble $\{f(y,u), g(y,u)\}$. Cependant, cette adaptation entraîne un taux de convergence temporelle plus faible pour le cas de l'horizon infini :
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 (\log h)^2 h^{\frac{1}{1+\beta}}$$
  où $\beta = \frac{\sqrt{n}L_f}{\lambda}$. Les auteurs notent que cela représente une perte d'au plus un demi-ordre de convergence en temps par rapport au cas à horizon fini, attribuée à l'horizon temporel infini.

Signification et Revendications
L'article affirme que la nouvelle caractérisation basée sur des arguments d'optimalité explique avec succès le comportement numérique observé en pratique, où la détérioration en $1/h$ prédite par les anciennes bornes n'est pas observée. En prouvant la borne $O(h+k)$, les auteurs confirment que la méthode semi-lagrangienne entièrement discrète atteint une convergence de premier ordre en temps et en espace sous des hypothèses de régularité standard.

Les auteurs suggèrent modestement que cette nouvelle caractérisation, ancrée dans des arguments d'optimalité, présente un potentiel d'application à d'autres types d'équations de Hamilton-Jacobi-Bellman où les taux de convergence actuels sont sous-optimaux. Ils précisent explicitement que si l'on récupère une convergence de premier ordre pour les commandes Lipschitziennes, une régularité plus faible (telle que la continuité de Hölder avec exposant $\alpha$) produit des taux de convergence de $O(h^\alpha)$, et que l'approche des commandes constantes par morceaux pour les horizons infinis subit une pénalité logarithmique par rapport aux résultats à horizon fini. Le travail ne propose pas de nouveaux dispositifs expérimentaux mais apporte plutôt une correction théorique à l'analyse d'erreur existante dans le domaine.