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

Sintesi Tecnica: Limiti Ottimali per le Approssimazioni Numeriche di Problemi a Orizzonte Infinito Basati sull'Approccio di Programmazione Dinamica

Enunciato del Problema
Il documento affronta l'approssimazione numerica di problemi di controllo ottimale a orizzonte infinito guidati da sistemi dinamici in $\mathbb{R}^n$. La funzione valore per tali problemi è caratterizzata come la soluzione viscosa di un'equazione differenziale alle derivate parziali Hamilton-Jacobi-Bellman (HJB) non lineare del primo ordine. Sebbene esistano vari schemi di approssimazione (differenze finite, semi-Lagrangiane, volumi finiti), una sfida significativa rimane l'instaurare limiti di errore rigorosi per metodi completamente discreti che includono sia la discretizzazione temporale che quella spaziale.

La letteratura esistente, facendo riferimento specificamente ai lavori di Falcone e Ferretti [12] e altri [9, 11], stabilisce un limite di errore di grandezza $O(k/h)$ per i metodi semi-Lagrangiani completamente discreti, dove $h$ è il passo temporale e $k$ è la griglia spaziale. Questo limite suggerisce che, al diminuire del passo temporale $h$, l'errore peggiori a causa del fattore $1/h$. Tuttavia, gli autori osservano che gli esperimenti numerici nella letteratura (ad esempio, [4]) non riscontrano questo comportamento $1/h$, suggerendo che il limite teorico sia subottimale. Il presente articolo mira a risolvere questa discrepanza rivedendo l'analisi dell'errore per dimostrare un limite più stretto.

Metodologia
Gli autori propongono una nuova caratterizzazione dell'approssimazione completamente discreta per derivare limiti di errore migliorati. La metodologia procede come segue:

1. Riformulazione tramite Funzionali del Costo: Invece di fare affidamento esclusivamente sul classico principio di programmazione dinamica, gli autori definiscono un funzionale del costo completamente discreto $\hat{J}_{h,k}$. Questo funzionale utilizza un operatore di interpolante lineare $I_k$ applicato alla dinamica del sistema e al costo corrente ad ogni passo temporale.
2. Caratterizzazione della Soluzione: Il Teorema 3 dimostra che la funzione valore completamente discreta $v_{h,k}$ (definita dall'equazione di programmazione dinamica discreta) è esattamente l'infimo di questo nuovo funzionale del costo completamente discreto sullo spazio delle sequenze di controllo ammissibili. Ciò rispecchia la caratterizzazione utilizzata per il caso semi-discreto in [5].
3. Decomposizione dell'Errore: L'analisi dell'errore confronta il funzionale del costo continuo $\hat{J}$ con il funzionale completamente discreto $\hat{J}_{h,k}$. La differenza è limitata analizzando gli errori di traiettoria tra la soluzione del sistema continuo $y(t)$ e la soluzione interpolata discreta $\tilde{y}(t)$, nonché gli errori di interpolazione delle funzioni di costo e di dinamica.
4. Assunzioni di Regolarità: L'analisi considera diverse assunzioni di regolarità sugli input di controllo $u(t)$:
   • Controlli uniformemente continui (con un numero finito di discontinuità di salto).
   • Controlli Lipschitz continui.
   • Controlli a costanti a tratti (sotto un'assunzione di convessità sull'insieme di dinamiche/costi).

Contributi Chiave e Risultati

• Limite di Errore Migliorato: Il contributo primario è la dimostrazione che l'errore tra la funzione valore continua $v$ e l'approssimazione completamente discreta $v_{h,k}$ è dell'ordine di $O(h + k)$, piuttosto che del precedentemente citato $O(k/h)$. Ciò stabilisce una convergenza del primo ordine sia nel tempo che nello spazio, coerentemente con l'uso di una discretizzazione temporale di Eulero del primo ordine e di un'approssimazione spaziale lineare a tratti.
• Teorema 4 (Limite Generale): Sotto le standard assunzioni Lipschitz sulla dinamica del sistema $f$ e sul costo $g$, e assumendo $\lambda > L$ (dove $L$ è una costante derivata dalle costanti Lipschitz), l'errore è limitato da:
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 M_u$$
  dove $M_u$ misura l'oscillazione del controllo all'interno degli intervalli temporali.
• Teorema 6 (Controlli Lipschitz): Se i controlli sono Lipschitz continui, $M_u$ scala con $h$, risultando nel limite di errore ottimale:
  $$|v(y) - v_{h,k}(y)| \leq C(h + k)$$
• Teorema 5 (Controlli Uniformemente Continui): Se i controlli sono meramente uniformemente continui (permettendo un numero finito di salti), l'errore converge a zero quando $h, k \to 0$, sebbene il tasso specifico dipenda dal modulo di continuità.
• Controlli a Costanti a Tratti (Teorema 7): Adattando gli argomenti di [6] (originariamente per problemi a orizzonte finito) al caso a orizzonte infinito, gli autori dimostrano la convergenza sotto un'assunzione di convessità (CA) sull'insieme $\{f(y,u), g(y,u)\}$. Tuttavia, questo adattamento risulta in un tasso di convergenza temporale più debole per il caso a orizzonte infinito:
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 (\log h)^2 h^{\frac{1}{1+\beta}}$$
  dove $\beta = \frac{\sqrt{n}L_f}{\lambda}$. Gli autori notano che questo rappresenta una perdita di al massimo mezzo ordine nella convergenza temporale rispetto al caso a orizzonte finito, attribuita all'orizzonte temporale infinito.

Significatività e Rivendicazioni
L'articolo sostiene che la nuova caratterizzazione basata su argomenti di ottimalità spiega con successo il comportamento numerico osservato nella pratica, dove il deterioramento $1/h$ previsto dai vecchi limiti non si verifica. Dimostrando il limite $O(h+k)$, gli autori confermano che il metodo semi-Lagrangiano completamente discreto raggiunge una convergenza del primo ordine sia nel tempo che nello spazio sotto standard assunzioni di regolarità.

Gli autori suggeriscono con modestia che questa nuova caratterizzazione, radicata in argomenti di ottimalità, ha il potolo di essere applicata ad altri tipi di equazioni Hamilton-Jacobi-Bellman dove i tassi di convergenza attuali sono subottimali. Essi dichiarano esplicitamente che, mentre recuperano la convergenza del primo ordine per i controlli Lipschitz, una regolarità più debole (come la continuità Hölder con esponente $\alpha$) produce tassi di convergenza di $O(h^\alpha)$, e l'approccio del controllo a costanti a tratti per orizzonti infiniti incorre in una penalità logaritmica rispetto ai risultati a orizzonte finito. Il lavoro non propone nuovi setup sperimentali, ma fornisce una correzione teorica alla precedente analisi dell'errore nel campo.