Spectral conjugate gradient projection methods for large-scale monotone equations without Lipschitz continuity

Resumen Técnico: Métodos de Proyección de Gradiente Conjugado Espectral para Ecuaciones Monótonas a Gran Escala

Planteamiento del Problema
El artículo aborda el problema de encontrar un vector $x \in \Gamma$ tal que $G(x) = 0$, donde $G: \mathbb{R}^n \to \mathbb{R}^n$ es una aplicación monótona continua y $\Gamma \subset \mathbb{R}^n$ es un conjunto no vacío, cerrado y convexo. Esta formulación engloba problemas de desigualdades variacionales, problemas de complementariedad, cálculos de equilibrio químico, detección comprimida (compressed sensing) y regresión logística regularizada. Si bien los métodos de tipo Newton ofrecen una convergencia local rápida para $G$ diferenciable, son poco prácticos para problemas a gran escala debido a los requisitos de almacenamiento de $O(n^2)$ y la necesidad de calcular jacobianos. Los métodos de gradiente conjugado (CG) son preferidos en entornos a gran escala, ya que requieren únicamente evaluaciones de funciones y almacenamiento de $O(n)$. Sin embargo, extender los métodos CG a entornos con restricciones generalmente depende de técnicas de proyección, y los métodos existentes a menudo requieren continuidad Lipschitz de $G$ o sufren tasas de convergencia subóptimas.

Metodología
Los autores proponen dos métodos de proyección libres de derivadas que integran un parámetro espectral adaptativo $\lambda_k$ en marcos de gradiente conjugado establecidos. Ambos métodos utilizan la técnica de proyección de Solodov–Svaiter, que implica calcular una dirección de descenso, realizar una búsqueda lineal para generar un punto de prueba, construir un hiperplano separador basado en la monotonía de $G$ y proyectar la iteración actual sobre este hiperplano.

1. GMOPCGM (Método de Gradiente Conjugado de Perry Óptimo Modificado Generalizado):
   Este método generaliza el Método de Gradiente Conjugado de Perry Óptimo Modificado (MOPCGM) de Sabi'u et al. La dirección de búsqueda se deriva de una matriz de Perry óptima modificada donde el parámetro de escala se reemplaza por un parámetro espectral adaptativo $\lambda_k$. El parámetro $\lambda_k$ está acotado dentro de $[\alpha_{\min}, \alpha_{\max}]$ y se actualiza utilizando razones espectrales del tipo Barzilai–Borwein basadas en la curvatura local ($s_{k-1}$ y $v_{k-1}$). La dirección de búsqueda resultante satisface una condición de descenso suficiente independiente de la búsqueda lineal.

2. GCGPM (Método de Proyección de Gradiente Conjugado Generalizado):
   Este método generaliza el CGPM de Zheng et al., que se basa en el parámetro Hager–Zhang. Los autores introducen un parámetro espectral Dai–Liao $\lambda_k$ en la fórmula de actualización. Similar al GMOPCGM, el parámetro espectral se adapta a la geometría local del problema. La dirección de búsqueda se construye para garantizar un descenso suficiente.

Contribuciones Clave

• Derivación de Nuevas Direcciones de Búsqueda: El artículo deriva dos nuevas direcciones de búsqueda que generalizan los marcos existentes de MOPCGM y CGPM mediante un parámetro espectral $\lambda_k$.
• Independencia del Descenso Suficiente: Se demuestra que ambos métodos propuestos satisfacen una condición de descenso suficiente ($G_k^T p_k \leq -c \|G_k\|^2$) que se cumple independientemente de la estrategia de búsqueda lineal.
• Convergencia Global bajo Supuestos Más Débiles:
  • Para GMOPCGM, la convergencia global se establece únicamente bajo las Suposiciones A1 (conjunto de soluciones no vacío) y A2 (monotonía). Crucialmente, este resultado no requiere la continuidad Lipschitz de $G$.
  • Para GCGPM, la convergencia global se demuestra bajo las suposiciones estándar A1–A3, que incluyen la continuidad Lipschitz.
• Efectividad Práctica: Los métodos se probaron en 18 problemas de referencia con dimensiones de hasta 120,000, así como en aplicaciones de detección comprimida y regresión logística regularizada.

Resultados Numéricos
Los autores realizaron experimentos numéricos extensos comparando GMOPCGM y GCGPM contra tres métodos existentes: MOPCGM, CGPM y STTDFPM.

• Problemas de Referencia: En 5,400 ejecuciones (18 problemas, 6 dimensiones, 10 puntos iniciales), GCGPM logró la tasa de convergencia más alta (96.9%) y la menor mediana de conteo de iteraciones (10) y evaluaciones de funciones (52). GMOPCGM convergió en el 93.0% de las instancias con una mediana de 28 iteraciones, una mejora significativa sobre su predecesor MOPCGM (160 iteraciones).
• Detección Comprimida: En tareas de recuperación de señales regularizadas con $\ell_1$, ambos métodos propuestos convergieron en las 240 instancias de prueba. GCGPM y GMOPCGM requirieron significativamente menos iteraciones y tiempo de CPU en comparación con MOPCGM, que falló en 20 instancias. Todos los métodos lograron un error cuadrático medio (MSE) comparable en la recuperación de señales.
• Regresión Logística Regularizada: En conjuntos de datos de clasificación binaria del mundo real, ambos métodos propuestos convergieron en las 60 instancias. GMOPCGM redujo la mediana de iteraciones de 2,447 (MOPCGM) a 313, demostrando el beneficio de la generalización espectral para ecuaciones monótonas no lineales. GCGPM fue el más eficiente, requiriendo 184 iteraciones medianas.

Significado y Afirmaciones
El artículo afirma que la integración de parámetros espectrales adaptativos en marcos de proyección de gradiente conjugado ofrece un enfoque robusto para resolver ecuaciones monótonas a gran escala. El significado teórico principal reside en la prueba de convergencia para GMOPCGM, que elimina el requisito de continuidad Lipschitz, un cuello de botella común en el análisis de métodos libres de derivadas para ecuaciones monótonas. En la práctica, los resultados demuestran que la generalización espectral mejora consistentemente el rendimiento sobre los métodos base en términos de velocidad de convergencia y costo computacional, haciendo que los algoritmos propuestos sean adecuados para aplicaciones de alta dimensión en procesamiento de señales y aprendizaje automático. Los autores señalan que el trabajo futuro podría extender el análisis de convergencia de GCGPM al entorno pseudomonótono y explorar técnicas de aceleración inercial.