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

Resumo Técnico: Limites Ótimos para Aproximações Numéricas de Problemas de Horizonte Infinito Baseados na Abordagem de Programação Dinâmica

Enunciado do Problema
O artigo aborda a aproximação numérica de problemas de controle ótimo de horizonte infinito regidos por sistemas dinâmicos em $\mathbb{R}^n$. A função valor para tais problemas é caracterizada como a solução viscosa de uma equação diferencial parcial Hamilton-Jacobi-Bellman (HJB) não linear de primeira ordem. Embora existam vários esquemas de aproximação (diferenças finitas, semi-Lagrangiana, volumes finitos), um desafio significativo permanece no estabelecimento de limites de erro rigorosos para métodos totalmente discretos que incluem tanto a discretização temporal quanto a espacial.

A literatura existente, referenciando especificamente trabalhos de Falcone e Ferretti [12] e outros [9, 11], estabelece um limite de erro de ordem $O(k/h)$ para métodos semi-Lagrangianos totalmente discretos, onde $h$ é o passo de tempo e $k$ é a malha espacial. Este limite sugere que, à medida que o passo de tempo $h$ diminui, o erro deteriora-se devido ao fator $1/h$. No entanto, os autores observam que experimentos numéricos na literatura (por exemplo, [4]) não observam este comportamento $1/h$, sugerindo que o limite teórico é subótimo. O artigo visa resolver esta discrepância revisando a análise de erro para provar um limite mais justo.

Metodologia
Os autores propõem uma nova caracterização da aproximação totalmente discreta para derivar limites de erro melhorados. A metodologia procede da seguinte forma:

1. Reformulação via Funcionais de Custo: Em vez de depender apenas do princípio padrão de programação dinâmica, os autores definem um funcional de custo totalmente discreto $\hat{J}_{h,k}$. Este funcional utiliza um operador de interpolante linear $I_k$ aplicado à dinâmica do sistema e ao custo corrente em cada passo de tempo.
2. Caracterização da Solução: O Teorema 3 prova que a função valor totalmente discreta $v_{h,k}$ (definida pela equação de programação dinâmica discreta) é exatamente o ínfimo deste novo funcional de custo totalmente discreto sobre o espaço de sequências de controle admissíveis. Isso espelha a caracterização utilizada para o caso semi-discreto em [5].
3. Decomposição do Erro: A análise de erro compara o funcional de custo contínuo $\hat{J}$ com o funcional totalmente discreto $\hat{J}_{h,k}$. A diferença é limitada analisando o erro de trajetória entre a solução do sistema contínuo $y(t)$ e a solução interpolada discreta $\tilde{y}(t)$, bem como os erros de interpolação das funções de custo e dinâmica.
4. Pressupostos de Regularidade: A análise considera diferentes pressupostos de regularidade para as entradas de controle $u(t)$:
   • Controles uniformemente contínuos (com um número finito de descontinuidades de salto).
   • Controles Lipschitz contínuos.
   • Controles constantes por partes (sob uma suposição de convexidade sobre o conjunto de dinâmicas/custos).

Principais Contribuições e Resultados

• Limite de Erro Melhorado: A principal contribuição é a prova de que o erro entre a função valor contínua $v$ e a aproximação totalmente discreta $v_{h,k}$ é de ordem $O(h + k)$, em vez do anteriormente citado $O(k/h)$. Isto estabelece convergência de primeira ordem tanto em tempo quanto em espaço, consistente com o uso de uma discretização temporal de Euler de primeira ordem e aproximação espacial linear por partes.
• Teorema 4 (Limite Geral): Sob pressupostos Lipschitz padrão nas dinâmicas do sistema $f$ e no custo $g$, e assumindo $\lambda > L$ (onde $L$ é uma constante derivada das constantes Lipschitz), o erro é limitado por:
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 M_u$$
  onde $M_u$ mede a oscilação do controle dentro dos intervalos de tempo.
• Teorema 6 (Controles Lipschitz): Se os controles forem Lipschitz contínuos, $M_u$ escala com $h$, resultando no limite de erro ótimo:
  $$|v(y) - v_{h,k}(y)| \leq C(h + k)$$
• Teorema 5 (Controles Uniformemente Contínuos): Se os controles forem meramente uniformemente contínuos (permitindo um número finito de saltos), o erro converge para zero quando $h, k \to 0$, embora a taxa específica dependa do módulo de continuidade.
• Controles Constantes por Partes (Teorema 7): Adaptando argumentos de [6] (originalmente para problemas de horizonte finito) para o caso de horizonte infinito, os autores provam a convergência sob uma suposição de convexidade (CA) sobre o conjunto $\{f(y,u), g(y,u)\}$. No entanto, esta adaptação resulta em uma taxa de convergência temporal mais fraca para o caso de horizonte infinito:
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 (\log h)^2 h^{\frac{1}{1+\beta}}$$
  onde $\beta = \frac{\sqrt{n}L_f}{\lambda}$. Os autores observam que isto representa uma perda de no máximo meio de uma ordem na convergência temporal comparado ao caso de horizonte finito, atribuída ao horizonte de tempo infinito.

Significância e Alegações
O artigo afirma que a nova caracterização baseada em argumentos de otimalidade explica com sucesso o comportamento numérico observado na prática, onde a deterioração $1/h$ prevista pelos limites antigos não é observada. Ao provar o limite $O(h+k)$, os autores confirmam que o método semi-Lagrangiano totalmente discreto alcança convergência de primeira ordem tanto em tempo quanto em espaço sob pressupostos de regularidade padrão.

Os autores sugerem modestamente que esta nova caracterização, enraizada em argumentos de otimalidade, tem potencial para aplicação em outros tipos de equações Hamilton-Jacobi-Bellman onde as taxas de convergência atuais são subótimas. Eles declaram explicitamente que, embora recuperem a convergência de primeira ordem para controles Lipschitz, uma regularidade mais fraca (como a continuidade Hölder com expoente $\alpha$) produz taxas de convergência de $O(h^\alpha)$, e a abordagem de controle constante por partes para horizontes infinitos incorre em uma penalidade logarítmica em comparação com os resultados de horizonte finito. O trabalho não propõe novos setups experimentais, mas sim fornece uma correção teórica à análise de erro existente na área.