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

Technische Samenvatting: Optimale Grenzen voor Numerieke Benaderingen van Oneindige Horizon Problemen Gebaseerd op een Dynamische Programmeringsbenadering

Probleemstelling
Het artikel behandelt de numerieke benadering van optimale controleproblemen met een oneindige horizon die worden gedreven door dynamische systemen in $\mathbb{R}^n$. De waardefunctie voor dergelijke problemen wordt gekarakteriseerd als de viscositeitsoplossing van een eerste-orde nietlineaire Hamilton-Jacobi-Bellman (HJB) partiële differentiaalvergelijking. Hoewel er diverse benaderingsschema's bestaan (eindige differenties, semi-Lagrangiaans, eindige volumes), blijft een aanzienlijke uitdaging het vaststellen van strikte foutgrenzen voor volledig discrete methoden die zowel tijd- als ruimtelijke discretisatie bevatten.

Bestaande literatuur, specifiek verwijzendend naar werken van Falcone en Ferretti [12] en anderen [9, 11], stelt een foutgrens vast van de grootte $O(k/h)$ voor volledig discrete semi-Lagrangiaanse methoden, waarbij $h$ de tijdstap is en $k$ de ruimtelijke roostergrootte. Deze grens suggereert dat naarmate de tijdstap $h$ kleiner wordt, de fout verslechtert door de $1/h$ factor. De auteurs merken echter op dat numerieke experimenten in de literatuur (bijv. [4]) dit $1/h$-gedrag niet observeren, wat suggereert dat de theoretische grens suboptimaal is. Het doel van het artikel is om deze discrepantie op te lossen door de foutanalyse te herzien om een nauwere grens te bewijzen.

Methodologie
De auteurs stellen een nieuwe karakterisering van de volledig discrete benadering voor om verbeterde foutgrenzen af te leiden. De methodologie verloopt als volgt:

1. Herformulering via Kostenfunctionalen: In plaats van uitsluitend te vertrouwen op het standaard principe van dynamische programmering, definiëren de auteurs een volledig discreet kostenfunctional $\hat{J}_{h,k}$. Dit functional maakt gebruik van een lineaire interpolatie-operator $I_k$ toegepast op de systeemdynamica en de lopende kosten bij elke tijdstap.
2. Karakterisering van de Oplossing: Stelling 3 bewijst dat de volledig discrete waardefunctie $v_{h,k}$ (gedefinieerd door de discrete dynamische programmeervergelijking) exact het infimum is van dit nieuwe volledig discrete kostenfunctional over de ruimte van toelaatbare controle-sequenties. Dit weerspiegelt de karakterisering die gebruikt werd voor het semi-discrete geval in [5].
3. Foutdecompositie: De foutanalyse vergelijkt het continue kostenfunctional $\hat{J}$ met het volledig discrete functional $\hat{J}_{h,k}$. Het verschil wordt begrensd door de trajectfouten tussen de continue systeemoplossing $y(t)$ en de discrete geïnterpoleerde oplossing $\tilde{y}(t)$ te analyseren, evenals de interpolatiefouten van de kosten- en dynamische functies.
4. Regulariteitsveronderstellingen: De analyse beschouwt verschillende regulariteitsveronderstellingen op de controle-inputs $u(t)$:
   • Uniform continuüm de controles (met een eindig aantal sprongdiscontinuïteiten).
   • Lipschitz-continue controles.
   • Stukgewijs constante controles (onder een convexiteitsveronderstelling op de verzameling dynamica/kosten).

Belangrijkste Bijdragen en Resultaten

• Verbeterde Foutgrens: De primaire bijdrage is het bewijs dat de fout tussen de continue waardefunctie $v$ en de volledig discrete benadering $v_{h,k}$ van de orde $O(h + k)$ is, in plaats van de eerder geciteerde $O(k/h)$. Dit vestigt eerste-orde convergentie in zowel tijd als ruimte, consistent met het gebruik van een eerste-orde Euler tijd-discretisatie en een stukgewijs lineaire ruimtelijke benadering.
• Theorem 4 (Algemene grens): Onder standaard Lipschitz-aannames op de systeemdynamica $f$ en kosten $g$, en uitgaande van $\lambda > L$ (waarbij $L$ een constante is afgeleid van de Lipschitz-constanten), is de fout begrensd door:
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 M_u$$
  waarbij $M_u$ de oscillatie van de controle binnen tijdsintervallen meet.
• Theorem 6 (Lipschitz-controles): Indien de controles Lipschitz-continu zijn, schaalt $M_u$ met $h$, wat resulteert in de optimale foutgrens:
  $$|v(y) - v_{h,k}(y)| \leq C(h + k)$$
• Theorem 5 (Uniform continuüm de controles): Indien controles louter uniform continu zijn (waarbij een eindig aantal sprongen is toegestaan), convergeert de fout naar nul wanneer $h, k \to 0$, hoewel de specifieke snelheid afhangt van de modulus van continuïteit.
• Stukgewijs constante controles (Theorem 7): Door argumenten uit [6] (oorspronkelijk voor eindige horizon problemen) aan te passen aan de oneindige horizon zaak, bewijzen de auteurs convergentie onder een convexiteitsveronderstelling (CA) op de verzameling $\{f(y,u), g(y,u)\}$. Echter, deze aanpassing resulteert in een zwakkere tijd-convergentiesnelheid voor de oneindige horizon zaak:
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 (\log h)^2 h^{\frac{1}{1+\beta}}$$
  waarbij $\beta = \frac{\sqrt{n}L_f}{\lambda}$. De auteurs merken op dat dit een verlies van maximaal een halve orde in tijdconvergentie vertegenwoordigt vergeleken met het eindige horizon geval, toegeschreven aan de oneindige tijdhorizon.

Betekenis en Claims
Het artikel claimt dat de nieuwe karakterisering gebaseerd op optimaliteitsargumenten succesvol het numerieke gedrag verklaart dat in de praktijk wordt waargenomen, waarbij de $1/h$ verslechtering die door oudere grenzen wordt voorspeld, niet optreedt. Door de $O(h+k)$ grens te bewijzen, bevestigen de auteurs dat de volledig discrete semi-Lagrangiaanse methode eerste-orde convergentie bereikt in zowel tijd als ruimte onder standaard regulariteitsveronderstellingen.

De auteurs suggereren bescheiden dat deze nieuwe karakterisering, geworteld in optimaliteitsargumenten, potentieel heeft voor toepassing op andere typen Hamilton-Jacobi-Bellman vergelijkingen waar de huidige convergentiesnelheden suboptimaal zijn. Ze stellen expliciet dat terwijl ze eerste-orde convergentie herstellen voor Lipschitz-controles, zwakkere regulariteit (zoals Hölder-continuïteit met exponent $\alpha$) convergentiesnelheden van $O(h^\alpha)$ oplevert, en de stukgewijs constante controle-benadering voor oneindige horizonten een logaritmische straf met zich meebrengt vergeleken met eindige horizon resultaten. Het werk stelt geen nieuwe experimentele opstellingen voor, maar biedt eerder een theoretische correctie op de bestaande foutanalyse in het vakgebied.