Global Convergence of a Line-Search Filter Differential Dynamic Programming Method

Resumen Técnico: Convergencia Global de un Método de Programación Dinámica Diferencial con Filtro de Búsqueda de Línea

Planteamiento del Problema
El artículo aborda el desafío de resolver problemas de control óptimo (OCP, por sus siglas en inglés) de tiempo discreto y horizonte finito sujetos a restricciones de igualdad no lineales en estados y controles, así como a la dinámica del sistema. Si bien el algoritmo de Programación Dinámica Diferencial (DDP), propuesto originalmente por Mayne y Jacobson, es un método bien establecido para OCPs no restringidos con conocida convergencia cuadrática local, su aplicación a problemas restringidos carece de una garantía de convergencia global formal en muchas extensiones existentes. Las variantes previas de DDP restringido, tales como las basadas en programación cuadrática secuencial o formulaciones primal-dual, a menudo proporcionan resultados de convergencia local pero omiten el análisis global. El vacío específico que este trabajo aborda es la falta de una prueba rigurosa de convergencia global para el algoritmo FilterDDP, un método de filtro de búsqueda de línea propuesto por Xu et al. que adapta el enfoque general de filtro de programación no lineal (NLP) de Wächter y Biegler al marco de DDP.

Metodología
Los autores proponen un análisis formal del algoritmo FilterDDP, el cual integra un procedimiento de filtro de búsqueda de línea con la estructura de DDP. La metodología central consiste en reemplazar el paso de Newton amortiguado utilizado típicamente en los métodos de filtro de NLP generales por un proceso de generación de puntos de prueba específico de DDP que consta de dos fases:

1. Recursión hacia atrás (Backward Recursion): Una actualización recursiva de las aproximaciones de la función de valor y de los multiplicadores de Lagrange. Esta fase computa aproximaciones de Hessian y resuelve un sistema lineal para determinar las direcciones de actualización ($\zeta, \beta, \psi, \omega$) para controles, multiplicadores y estados.
2. Simulación hacia adelante (Forward Simulation): Una fase de simulación que genera una nueva trayectoria basada en las actualizaciones computadas y un tamaño de paso $\alpha$. Crucialmente, esta fase asegura que las restricciones dinámicas ($x_{t+1} = f(x_t, u_t)$) se satisfagan en cada iteración, una propiedad inherente a DDP.

El algoritmo utiliza un mecanismo de filtro para aceptar puntos de prueba, equilibrando la reducción del Lagrangiano (como la medida de la función objetivo) y la medida de violación de las restricciones. Los criterios de aceptación de pasos incluyen condiciones de reducción suficiente para el Lagrangiano o la violación de restricciones, una condición de tipo Armijo para iteraciones "tipo L", y una fase de restauración de la factibilidad invocada cuando los tamaños de paso se vuelven demasiado pequeños o los Jacobianos de las restricciones carecen de rango completo.

Contribuciones Clave
La contribución principal de este trabajo es el establecimiento de la convergencia global del algoritmo FilterDDP. Los autores logran esto demostrando que el procedimiento específico de recursión hacia atrás-hacia adelante de DDP satisface las mismas propiedades analíticas requeridas para la convergencia global de los métodos de filtro de búsqueda de línea en NLP generales, según lo establecido por Wächter y Biegler.

Los pasos técnicos clave en esta contribución incluyen:

• Equivalencia de Pasos: Demostrar que la recursión hacia atrás y la simulación hacia adelante de DDP, cuando se ven a través del lente del análisis de convergencia global, se comportan de manera idéntica a un paso de Newton amortiguado aplicado a las condiciones de Karush-Kuhn-Tucker (KKT) del OCP.
• Derivación de Lemas: Establecer una serie de lemas (equivalentes a los Lemas 1–3 del trabajo de Wächter y Biegler) que acotan las reglas de actualización, establecen propiedades de descenso para puntos factibles no óptimos y muestran que la regla de actualización linealiza los criterios del filtro (Lagrangiano y violación de restricciones) localmente.
• Extensión de Punto Interior: Extender el análisis de convergencia global para manejar restricciones de desigualdad (específicamente $u_t \geq 0$) mediante un método de barrera de punto interior. Esto implica adaptar las aproximaciones de la Hessiana y demostrar que las iteraciones permanecen alejadas de los límites de la región factible, asegurando que la función objetivo de barrera y sus derivadas permanezcan bien definidas.

Resultos
Bajo un conjunto de supuestos estándar de regularidad y suavidad (denotados como Supuestos G para restricciones de igualdad y Supuestos B para la extensión de barrera), el artículo demuestra las siguientes propiedades de convergencia:

1. Factibilidad: Los puntos límite de la secuencia de iteraciones generadas por FilterDDP son factibles; específicamente, la medida de violación de restricciones $\theta(w_k)$ converge a cero cuando $k \to \infty$.
2. Optimalidad: Si la secuencia de iteraciones es acotada, existe al menos un punto límite que satisface las condiciones de optimalidad de primer orden (condiciones KKT) para el OCP restringido. Esto se demuestra mostrando que la medida de criticidad $\chi(w_k)$, definida por la norma de los componentes del gradiente proyectado, tiene un ínfimo de cero.
3. Convergencia de la Barrera: Para la extensión de punto interior, se demuestra que las iteraciones permanecen uniformemente alejadas de los límites de las restricciones de desigualdad, asegurando la validez de la formulación de barrera a lo largo de todo el proceso de optimización.

Significancia y Reivindicaciones
El artículo reivindica su significancia al cerrar formalmente la brecha entre el éxito práctico de FilterDDP y las garantías teóricas rigurosas. Los autores afirman que, si bien la convergencia cuadrática local de FilterDDP fue establecida previamente (ignorando los criterios de aceptación de pasos), el análisis de convergencia global estaba ausente. Al adaptar el análisis de Wächter y Biegler, el artículo demuestra que la estructura de DDP no impide las propiedades de convergencia global del método de filtro; más bien, la recursión hacia atrás-hacia adelante sirve efectivamente el mismo rol que el paso de Newton en el contexto de un NLP general.

Los autores señalan modestamente que este análisis depende del supuesto de que la fase de restauración de la factibilidad termina exitosamente y que el algoritmo no se detiene prematuramente en un punto que no sea KKT. Además, el artículo identifica que establecer una convergencia local rápida para FilterDDP (sin ignorar los criterios de aceptación de pasos) sigue siendo un problema abierto, sugiriendo que un paso de corrección de segundo orden, similar al utilizado en el NLP general, puede ser necesario para trabajos futuros. El artículo no propone nuevas aplicaciones o comparativas experimentales, centrándose estrictamente en las propiedades de convergencia teórica del algoritmo.