An inexact infeasible arc-search interior-point method for linear optimization problems

Resumen Técnico: Un Método de Punto Interior de Búsqueda de Arco Inexacto e Inviable para Problemas de Optimización Lineal

Planteamiento del Problema
El artículo aborda la resolución de Problemas de Optimización Lineal (LOP, por sus siglas en inglés) utilizando Métodos de Punto Interior (IPM). Específicamente, se centra en los IPM inefectivos invariantes (II-IPM), que son variantes diseñadas para resolver LOP partiendo de un punto inicial inviable y resolviendo los sistemas de Newton de forma inexacta (por ejemplo, mediante solvers iterativos como el Gradiente Conjugado). Si bien los solvers inexactos reducen el costo computacional por iteración para problemas de gran escala, los métodos existentes de búsqueda de línea de fase inviable inexacta sufren un inconveniente significativo: la acumulación de errores de linealización (derivados de la aproximación de la trayectoria central) y errores de inexactitud (del solver) a lo largo de una dirección de búsqueda recta. Esta acumulación obliga al algoritmo a tomar tamaños de paso muy pequeños, lo que resulta en un límite de complejidad de iteración en el peor de los casos relativamente laxo de $O(n^2 L)$, donde $n$ es el número de variables y $L$ es la longitud binaria de los datos de entrada.

Metodología
Los autores proponen un nuevo método denominado II-arc (Método de Punto Interior de Búsqueda de Arco Inefectivo Invariable). La innovación central radica en reemplazar la búsqueda estándar de línea recta por una estrategia de búsqueda de arco elíptico.

1. Marco de Búsqueda de Arco: En lugar de moverse a lo largo de una línea recta, el método aproxima la trayectoria central utilizando un arco elíptico definido por una expansión de Taylor de segundo orden. El siguiente iterado $(x_{k+1}, y_{k+1}, s_{k++1})$ se calcula como:
   $$x(\alpha) = x_k - \dot{x} \sin(\alpha) + \ddot{x}(1 - \cos(\alpha))$$
   (y de forma similar para $y$ y $s$), donde $\dot{x}, \ddot{x}$ son las primeras y segundas derivadas de la trayectoria central.
2. Resolución Inexacta: El método resuelve los sistemas de Newton para la primera derivada ($\dot{x}, \dot{y}, \dot{s}$) y la segunda derivada ($\ddot{x}, \ddot{y}, \ddot{s}$) de forma inexacta. Los autores utilizan la formulación del Sistema de Ecuaciones Normales Modificado (MNES) para el análisis teórico con el fin de relajar los requisitos de residuo, aunque los experimentos numéricos emplean el Sistema de Ecuaciones Normales (NES) estándar con un precondicionador de Jacobi debido a la inestabilidad numérica observada en las implementaciones de MNES para problemas de gran escala.
3. Selección del Tamaño de Paso: El tamaño de paso $\alpha$ se elige para satisfacer condiciones de vecindad específicas (asegurando que el iterado permanezca dentro de una región específica de la trayectoria central) y una condición de tipo Armijo para asegurar una reducción suficiente en la brecha de dualidad.
4. Análisis Teórico: Los autores demuestran que la trayectoria curva del arco de búsqueda suprime el error de linealización de manera más efectiva que una línea recta. Esto permite que el tamaño de paso se mantenga mayor incluso cuando los sistemas de Newton se resuelven con una inexactitud significativa.

Contribuciones Clave

• Primer IPM de Búsqueda de Arco Inexacto: Hasta donde los autores saben, este es el primer artículo que analiza un IPM inexacto dentro del marco de búsqueda de arco.
• Límite de Complejidad Mejorado: El artículo establece un límite de complejidad de iteración polinomial de $O(n^{1.5} L)$ para el método II-arc propuesto. Esto representa una mejora teórica sobre el mejor límite conocido para los métodos existentes de búsqueda de línea de fase inexacta ($O(n^2 L)$) por un factor de $n^{0.5}$.
• Mitigación de la Acumulación de Errores: Los autores demuestran que la estrategia de búsqueda de arco mitiga la acumulación de errores de linealización e inexactitud, que es el principal cuello de botella en los métodos de fase inviable inexactos existentes.

Resultados Numéricos
Los autores realizaron experimentos numéricos en problemas de gran escala del conjunto de pruebas NETLIB (incluyendo DFL001, QAP15, STOCFOR3 y problemas de Kennington) utilizando una implementación en Python con el Gradiente Conjugado Precondicionado (CG) como el solver lineal.

• Comparación: El método II-arc propuesto (específicamente la variante que utiliza el punto inicial heurístico de Yang, "II-arc-Yang") se comparó con un método existente de búsqueda de línea de fase inviable inexacta ("II-line-Yang").
• Desempeño:
  • Iteraciones: II-arc-Yang requirió consistentemente menos iteraciones que II-line-Yang. Para casi el 25% de los problemas de prueba, el método de búsqueda de línea requirió el doble o más de iteraciones que el método de búsqueda de arco.
  • Tiempo de Computación: II-arc-Yang redujo el tiempo de computación total para el 75% de los problemas. La reducción en las iteraciones compensó el costo adicional de resolver el sistema de la segunda derivada.
  • Robustez: El método resolvió con éxito 17 de los 18 problemas de prueba, demostrando estabilidad numérica.
• Puntos Iniciales: El estudio también comparó un punto inicial constante contra el punto inicial heurístico de Yang, encontrando que el enfoque heurístico (II-arc-Yang) generalmente produjo un mejor desempeño tanto en iteraciones como en tiempo.

Significancia y Reivindicaciones
El artículo afirma que el método II-arc propuesto ofrece un límite de iteración en el peor de los casos provablemente más ajustado que los métodos de búsqueda de línea de fase inexactos existentes. La significancia de este trabajo radica en cerrar la brecha entre los beneficios teóricos de la búsqueda de arco (mejor aproximación de la trayectoria central) y la necesidad práctica de solvers inexactos para problemas de gran escala.

Los autores señalan modestamente que, si bien la complejidad teórica se ha mejorado, el objetivo principal fue proponer el marco de trabajo y discutir su convergencia. Reconocen que el rendimiento numérico podría mejorarse aún más mediante:

• La implementación del método en lenguajes más rápidos (por ejemplo, C++, Julia).
• La investigación de solvers de sistemas lineales inexactos y precondicionadores más avanzados.
• La exploración de combinaciones con la estrategia de reinicio de Nesterov o IPMs de fase (feables).

El artículo concluye que la aproximación de arco elíptico permite tamaños de paso más grandes en presencia de inexactitud, lo que conduce tanto a una reducción teórica en la complejidad de iteración como a mejoras prácticas en la resolución de problemas de optimización lineal de gran escala.