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

Resumen Técnico: Límites Óptimos para Aproximaciones Numéricas de Problemas de Horizonte Infinito Basados en el Enfoque de Programación Dinámica

Planteamiento del Problema
El artículo aborda la aproximación numérica de problemas de control óptimo de horizonte infinito impulsados por sistemas dinámicos en $\mathbb{R}^n$. La función de valor para tales problemas se caracteriza como la solución viscosa de una ecuación diferencial parcial de Hamilton-Jacobi-Bellman (HJB) no lineal de primer orden. Si bien existen diversos esquemas de aproximación (diferencias finitas, semi-Lagrangiano, volúmenes finitos), un desafío significativo sigue siendo establecer límites de error rigurosos para métodos totalmente discretos que incluyen tanto la discretización temporal como la espacial.

La literatura existente, haciendo referencia específicamente a los trabajos de Falcone y Ferretti [12] y otros [9, 11], establece un límite de error de tamaño $O(k/h)$ para métodos semi-Lagrangianos totalmente discretos, donde $h$ es el paso de tiempo y $k$ es el tamaño de la malla espacial. Este límite sugiere que, a medida que el paso de tiempo $h$ disminuye, el error se deteriora debido al factor $1/h$. Sin embargo, los autores señalan que los experimentos numéricos en la literatura (por ejemplo, [4]) no observan este comportamiento $1/h$, lo que sugiere que el límite teórico es subóptimo. El artículo tiene como objetivo resolver esta discrepancia revisando el análisis de error para demostrar un límite más ajustado.

Metodología
Los autores proponen una nueva caracterización de la aproximación totalmente discreta para derivar límites de error mejorados. La metodología procede de la siguiente manera:

1. Reformulación mediante Funcionales de Costo: En lugar de depender únicamente del principio de programación dinámica estándar, los autores definen un funcional de costo totalmente discreto $\hat{J}_{h,k}$. Este funcional utiliza un operador de interpolación lineal $I_k$ aplicado a la dinámica del sistema y al costo corriente en cada paso de tiempo.
2. Caracterización de la Solución: El Teorema 3 demuestra que la función de valor totalmente discreta $v_{h,k}$ (definida por la ecuación de programación dinámica discreta) es exactamente el ínfimo de este nuevo funcional de costo totalmente discreto sobre el espacio de secuencias de control admisibles. Esto refleja la caracterización utilizada para el caso semi-discreto en [5].
3. Descomposición del Error: El análisis de error compara el funcional de costo continuo $\hat{J}$ con el funcional totalmente discreto $\hat{J}_{h,k}$. La diferencia se acota analizando los errores de trayectoria entre la solución del sistema continuo $y(t)$ y la solución interpolada discreta $\tilde{y}(t)$, así como los errores de interpolación de las funciones de costo y dinámica.
4. Supuestos de Regularidad: El análisis considera diferentes supuestos de regularidad sobre las entradas de control $u(t)$:
   • Controles uniformemente continuos (con un número finito de discontinuidades de salto).
   • Controles Lipschitz continuos.
   • Controles constantes a trozos (bajo un supuesto de convexidad sobre el conjunto de dinámicas/costos).

Contribuciones Clave y Resultados

• Límite de Error Mejorado: La contribución principal es la demostración de que el error entre la función de valor continua $v$ y la aproximación totalmente discreta $v_{h,k}$ es del orden de $O(h + k)$, en lugar del $O(k/h)$ previamente citado. Esto establece una convergencia de primer orden tanto en tiempo como en espacio, consistente con el uso de una discretización temporal de Euler de primer orden y una aproximación espacial lineal por trozos.
• Teorema 4 (Límite General): Bajo supuestos Lipschitz estándar en la dinámica del sistema $f$ y el costo $g$, y asumiendo que $\lambda > L$ (donde $L$ es una constante derivada de las constantes Lipschitz), el error está acotado por:
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 M_u$$
  donde $M_u$ mide la oscilación del control dentro de los intervalos de tiempo.
• Teorema 6 (Controles Lipschitz): Si los controles son Lipschitz continuos, $M_u$ escala con $h$, resultando en el límite de error óptimo:
  $$|v(y) - v_{h,k}(y)| \leq C(h + k)$$
• Teorema 5 (Controles Uniformemente Continuos): Si los controles son meramente uniformemente continuos (permitiendo un número finito de saltos), el error converge a cero cuando $h, k \to 0$, aunque la tasa específica depende del módulo de continuidad.
• Controles Constantes a Trozos (Teorema 7): Adaptando los argumentos de [6] (originalmente para problemas de horizonte finito) al caso de horizonte infinito, los autores demuestran la convergencia bajo un supuesto de convexidad (CA) sobre el conjunto $\{f(y,u), g(y,u)\}$. Sin embargo, esta adaptación resulta en una tasa de convergencia temporal más débil para el 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}}$$
  donde $\beta = \frac{\sqrt{n}L_f}{\lambda}$. Los autores señalan que esto representa una pérdida de a lo sumo medio orden en la tasa de convergencia temporal en comparación con el caso de horizonte finito, atribuido al horizonte de tiempo infinito.

Significancia y Reivindicaciones
El artículo afirma que la nueva caracterización basada en argumentos de optimalidad explica con éxito el comportamiento numérico observado en la práctica, donde no se observa el deterioro $1/h$ predicho por los límites anteriores. Al demostrar el límite $O(h+k)$, los autores confirman que el método semi-Lagrangiano totalmente discreto logra una convergencia de primer orden tanto en tiempo como en espacio bajo supuestos de regularidad estándar.

Los autores sugieren modestamente que esta nueva caracterización, arraigada en argumentos de optimalidad, tiene el potencial de aplicarse a otros tipos de ecuaciones de Hamilton-Jacobi-Bellman donde las tasas de convergencia actuales son subóptimas. Expresan explícitamente que, si bien recuperan la convergencia de primer orden para controles Lipschitz, una regularidad más débil (como la continuidad Hölder con exponente $\alpha$) produce tasas de convergencia de $O(h^\alpha)$, y el enfoque de control constante a trozos para horizontes infinitos incurre en una penalización logarítmica en comparación con los resultados de horizonte finito. El trabajo no propone nuevos montajes experimentales, sino que proporciona una corrección teórica al análisis de error existente en el campo.