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

Technische Zusammenfassung: Optimale Schranken für numerische Approximationen von Problemen mit unendlichem Horizont basierend auf dem dynamischen Programmierungsansatz

Problemstellung
Die vorliegende Arbeit befasst sich mit der numerischen Approximation von optimalen Kontrollproblemen mit unendlichem Horizont, die durch dynamische Systeme in $\mathbb{R}^n$ getrieben werden. Die Wertfunktion für solche Probleme lässt sich als viskose Lösung einer erstklassigen, nichtlinearen Hamilton-Jacobi-Bellman (HJB) partiellen Differentialgleichung charakterisieren. Während verschiedene Approximationsverfahren existieren (Finite Differenzen, Semi-Lagrange-Verfahren, Finite Volumina), bleibt eine wesentliche Herausforderung in der Etablierung strenger Fehlerschranken für voll diskrete Methoden, die sowohl die Zeit- als auch die räumliche Diskretisierung beinhalten.

Die bestehende Literatur, insbesondere unter Bezugnahme auf Arbeiten von Falcone und Ferretti [12] sowie anderen [9, 11], legt eine Fehlerschranke der Größenordnung $O(k/h)$ für voll diskrete Semi-Lagrange-Verfahren fest, wobei $h$ der Zeitschritt und $k$ die räumliche Gitterweite ist. Diese Schranke legt nahe, dass der Fehler mit abnehmendem Zeitschritt $h$ aufgrund des Faktors $1/h$ divergiert. Die Autoren stellen jedoch fest, dass numerische Experimente in der Literatur (z. B. [4]) dieses $1/h$-Verhalten nicht beobachten, was darauf hindeutet, dass die theoretische Schranke suboptimal ist. Das Ziel der Arbeit ist es, diese Diskrepanz zu lösen, indem die Fehleranalyse revidiert wird, um eine engere Schranke zu beweisen.

Methodik
Die Autoren schlagen eine neue Charakterisierung der voll diskreten Approximation vor, um verbesserte Fehlerschranken abzuleiten. Die Methodik verläuft wie folgt:

1. Reformulierung über Kostenfunktionale: Anstatt sich ausschließlich auf das Standard-Dynamische-Programmierung-Prinzip zu verlassen, definieren die Autoren ein voll diskretes Kostenfunktional $\hat{J}_{h,k}$. Dieses Funktional verwendet einen linearen Interpolationsoperator $I_k$, der auf die Systemdynamik und die laufenden Kosten zu jedem Zeitschritt angewendet wird.
2. Charakterisierung der Lösung: Theorem 3 beweist, dass die voll diskrete Wertfunktion $v_{h,k}$ (definiert durch die diskrete dynamische Programmiergleichung) exakt das Infimum dieses neuen voll diskreten Kostenfunktionalen über den Raum der zulässigen Kontrollsequenzen ist. Dies spiegelt die Charakterisierung wider, die für den semi-diskreten Fall in [5] verwendet wurde.
3. Fehlerzerlegung: Die Fehleranalyse vergleicht das kontinuierliche Kostenfunktional $\hat{J}$ mit dem voll diskreten Funktional $\hat{J}_{h,k}$. Die Differenz wird durch die Analyse der Trajektorienfehler zwischen der kontinuierlichen Systemlösung $y(t)$ und der diskreten interpolierten Lösung $\tilde{y}(t)$ sowie der Interpolationsfehler der Kosten- und Dynamikfunktionen begrenzt.
4. Regularitätsannahmen: Die Analyse berücksichtigt verschiedene Regularitätsannahmen auf die Kontrollinputs $u(t)$:
   • Gleichmäßig stetige Kontrollen (mit einer endlichen Anzahl von Sprungdiskontinuitäten).
   • Lipschitz-stetige Kontrollen.
   • Stückweise konstante Kontrollen (unter einer Konvexitätsannahme auf der Menge der Dynamiken/Kosten).

Wesentliche Beiträge und Ergebnisse

• Verbesserte Fehlerschranke: Der primäre Beitrag ist der Beweis, dass der Fehler zwischen der kontinuierlichen Wertfunktion $v$ und der voll diskreten Approximation $v_{h,k}$ der Ordnung $O(h + k)$ entspricht, statt der zuvor zitierten $O(k/h)$. Dies etabliert eine Konvergenz erster Ordnung sowohl in der Zeit als auch im Raum, was konsistent mit der Verwendung einer Euler-Zeitschritt-Diskretisation erster Ordnung und einer stückweise linearen räumlichen Approximation ist.
• Theorem 4 (Allgemeine Schranke): Unter Standard-Lipschitz-Annahmen auf die Systemdynamik $f$ und die Kosten $g$ sowie unter der Annahme $\lambda > L$ (wobei $L$ eine Konstante ist, die aus den Lipschitz-Konstanten abgeleitet wurde), ist der Fehler begrenzt durch:
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 M_u$$
  wobei $M_u$ die Oszillation der Kontrolle innerhalb der Zeitintervalle misst.
• Theorem 6 (Lipschitz-stetige Kontrollen): Wenn die Kontrollen Lipschitz-stetig sind, skaliert $M_u$ mit $h$, was zu der optimalen Fehlerschranke führt:
  $$|v(y) - v_{h,k}(y)| \leq C(h + k)$$
• Theorem 5 (Gleichmäßig stetige Kontrollen): Wenn die Kontrollen lediglich gleichmäßig stetig sind (Sprünge zulassen), konvergiert der Fehler gegen Null, wenn $h, k \to 0$, wobei die spezifische Rate vom Modul der Stetigkeit abhängt.
• Stückweise konstante Kontrollen (Theorem 7): Durch die Anpassung von Argumenten aus [6] (ursprünglich für Probleme mit endlichem Horizont) an den Fall mit unendlichem Horizont beweisen die Autoren die Konvergenz unter einer Konvexitätsannahme (CA) auf der Menge $\{f(y,u), g(y,u)\}$. Diese Anpassung führt jedoch zu einer schwächeren Zeitkonvergenzrate für den Fall mit unendlichem Horizont:
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 (\log h)^2 h^{\frac{1}{1+\beta}}$$
  wobei $\beta = \frac{\sqrt{n}L_f}{\lambda}$. Die Autoren merken an, dass dies eine Verlust von höchstens einer halben Ordnung in der Zeitkonvergenz gegenüber dem Fall mit endlichem Horizont darstellt, was auf den unendlichen Zeithorizont zurückzuführen ist.

Bedeutung und Ansprüche
Das Paper behauptet, dass die neue Charakterisierung basierend auf Optimierungsargumenten erfolgreich das in der Praxis beobachtete numerische Verhalten erklärt, bei dem die in älteren Schranken vorhergesagte $1/h$-Deterioration nicht auftritt. Durch den Beweis der $O(h+k)$-Schranke bestätigt die Arbeit, dass das voll diskrete Semi-Lagrange-Verfahren unter Standard-Regularitätsannahmen eine Konvergenz erster Ordnung sowohl in der Zeit als auch im Raum erreicht.

Die Autoren schlagen bescheiden vor, dass diese neue Charakterisierung, die in Optimierungsargumenten wurzelt, Potenzial für die Anwendung auf andere Arten von Hamilton-Jacobi-Bellman-Gleichungen besitzt, bei denen aktuelle Konvergenzraten suboptimal sind. Sie stellen explizit klar, dass sie zwar die Konvergenz erster Ordnung für Lipschitz-stetige Kontrollen wiederherstellen, eine schwächere Regularität (wie etwa Hölder-Stetigkeit mit Exponent $\alpha$) jedoch Konvergenzraten von $O(h^\alpha)$ liefert, und der Ansatz für stückweise konstante Kontrollen für unendliche Horizonte eine logarithmische Strafe gegenüber Ergebnissen für endliche Horizonte nach sich zieht. Die Arbeit schlägt keine neuen experimentellen Setups vor, sondern liefert vielmehr eine theoretische Korrektur der bestehenden Fehleranalyse auf diesem Gebiet.