Immunity to Increasing Condition Numbers of Linear Superiorization versus Linear Programming

Resumen Técnico: Inmunidad al aumento de los números de condición de la Superiorización Lineal frente a la Programación Lineal

Planteamiento del Problema
El artículo aborda el rendimiento comparativo de los algoritmos de Programación Lineal (LP) y la metodología de Superiorización Lineal (LinSup) cuando se aplican a problemas de programación lineal caracterizados por números de condición crecientes. Mientras que la LP clásica busca encontrar un punto óptimo (minimizando la función objetivo sujeta a restricciones), LinSup busca encontrar un punto factible con un valor de función objetivo "superior" (reducido, aunque no necesariamente mínimo). El problema central investigado es la sensibilidad de ambos enfoques a la maldad de la formulación (ill-posedness), específicamente cómo el aumento de los números de condición de la matriz de restricciones afecta el tiempo de ejecución, la consecución de la factibilidad y la reducción de la función objetivo de estos algoritmos.

Metodología
Los autores realizaron un estudio experimental controlado comparando LinSup contra solvers de LP establecidos.

• Generación de Problemas: Los investigadores construyeron problemas de programación lineal de la forma $\min \langle c, x \rangle$ sujeto a $Ax \le b$ y $\ell \le x \le u$. Para asegurar la similitud estructural a través de diferentes números de condición, utilizaron la Descomposición en Valores Singulares (SVD). Generaron matrices semi-ortogonales aleatorias $U$ y $V$ y construyeron matrices diagonales $\Sigma_\kappa$ con valores singulares distribuidos para lograr números de condición $\kappa$ específicos (que van desde bien condicionados hasta altamente mal condicionados). Los tamaños de las matrices oscilaron entre $80 \times 100$ y $4000 \times 5000$.
• Algoritmos Probados:
  • LinSup: Implementado utilizando el método de proyección de Agmon-Motzkin-Schönberg (AMS) como el algoritmo base de búsqueda de factibilidad. Se introdujeron perturbaciones utilizando el gradiente negativo normalizado de la función objetivo. El algoritmo empleó perturbaciones acotadas y proyecciones cíclicas con esquemas de tamaño de paso específicos y mecanismos de reinicio.
  • Solvers de LP: El estudio comparó LinSup contra scipy.simplex, scipy.revised simplex, scipy.interior-point y gurobi.primal simplex.
• Protocolo Experimental: Para asegurar una comparación justa, los autores impusieron un criterio de parada unificado basado en un umbral de infactibilidad fijo ($\varepsilon = 10^{-8}$).
  • LinSup se ejecutó hasta alcanzar este umbral.
  • Los solvers de LP se ejecutaron bajo el mismo umbral. Si un solver de LP no lograba alcanzar el umbral dentro del tiempo $T_{sup}$ (el tiempo que LinSup tardó en terminar), se detenía en $T_{sup}$, y se registraba su iterado actual.
  • Las métricas registradas incluyeron tiempo de ejecución, valores de la función objetivo y violaciones máximas de las restricciones (infactibilidad) al término y a lo largo de las iteraciones.

Contribuciones Clave y Resultados
El estudio proporciona evidencia empírica sobre la robustez de LinSup en comparación con los solvers de LP clásicos bajo variaciones en la dificultad del problema:

1. Rendimiento ante el aumento de dimensiones ( $\kappa$ fijo):

   • Para dimensiones pequeñas, los solvers basados en el método simplex fueron más rápidos.
   • A medida que las dimensiones del problema aumentaban (hasta $4000 \times 5000$), el tiempo de ejecución de las implementaciones de simplex (incluyendo Gurobi) aumentó significamente. En dimensiones altas, LinSup terminó más rápido que los solvers de simplex.
   • Notablemente, en las dimensiones más grandes probadas, LinSup alcanzó el umbral de factibilidad antes de que los algoritmos de simplex siquiera alcanzaran la factibilidad.

2. Inmunidad al aumento de los números de condición (Dimensiones Fijas):

   • Métodos Simplex: A medida que el número de condición aumentaba, las implementaciones de simplex de scipy exhibieron una degradación severa. A menudo terminaban prematuramente con valores de la función objetivo subóptimos, "rindiéndose" efectivamente debido a la dificultad del problema.
   • Método de Punto Interior: Aunque este método parecía encontrar valores de la función objetivo bajos rápidamente, tuvo dificultades para alcanzar el nivel requerido de factibilidad para números de condición altos, resultando en valores de infactibilidad elevados (hasta $10^1$).
   • LinSup: El método de superiorización demostró una estabilidad notable. Su tiempo de ejecución se mantuvo relativamente constante independientemente del número de condición, y consistentemente logró el nivel de factibilidad objetivo ($\varepsilon = 10^{-8}$) a través de todos los números de condición probados.
   • Función Objetivo: LinSup produjo consistentemente mejores (menores) valores de la función objetivo en el punto de terminación comparado con los métodos simplex en escenarios mal condicionados.

3. Análisis de Proximidad-Objetivo:

   • Los gráficos de infactibilidad frente al valor de la función objetivo (curvas de proximidad-objetivo) confirmaron que LinSup mantenía un camino constante hacia la factibilidad mientras reducía la función objetivo. En contraste, el método de punto interior mostró una desconexión entre encontrar un valor de la función objetivo bajo y satisfacer las restricciones en entornos mal condicionados.

Significancia y Reivindicaciones
El artículo afirma que la Superiorización Lineal ofrece una ventaja distintiva sobre los solvers de LP clásicos cuando se trata de sistemas lineales mal condicionados, particularmente en escenarios de gran escala.

• Robustez: Los autores concluyen que LinSup es menos afectado por altos números de condición que los solvers de LP probados. Atribuyen esto a la naturaleza del algoritmo: LinSup realiza proyecciones individuales sobre hiperplanos en lugar de resolver el sistema completo simultáneamente, y la "resiliencia a la perturbación acotada" del algoritmo base puede ayudar a absorber errores computacionales que de otro modo serían amplificados por el mal condicionamiento.
• Utilidad Práctica: El estudio sugiere que para aplicaciones donde encontrar un punto factible con un valor de la función objetivo reducido es suficiente (un enfoque de "satisfacción" en lugar de optimidad estricta), LinSup es una herramienta más fiable y eficiente para problemas mal planteados.
• Alcance Modesto: Los autores declaran explícicamente que sus resultados se basan en configuraciones experimentales y tamaños de problemas específicos. Expresan confianza en que las tendencias observadas se mantendrán para instancias más grandes, pero no afirman que LinSup reemplace a los solvers de LP para todas las tareas de optimización. Señalan que LinSup no es un solver de LP y no busca la optimidad restringida, sino un punto factible "superior".
• Trabajo Futuro: El artículo sugiere que la robustez observada de LinSup en entornos lineales justifica la investigación en entornos no lineales, particularmente donde los métodos de punto interior suelen tener dificultades con el mal condicionamiento (por ejemplo, en la radioterapia modulada por intensidad).