Non-Negative Conjugate Gradients

Resumen Técnico: Gradientes Conjugados No Negativos

Planteamiento del Problema
El artículo aborda el programa cuadrático no negativo (NNQP) estrictamente convexo:
$$\min_{x \in \mathbb{R}^n} f(x) = \frac{1}{2}x^\top A x - b^\top x \quad \text{sujeto a} \quad x \ge 0,$$
donde $A$ es simétrica definida positiva (SPD). Los autores también consideran una variante aumentada por igualdades con restricciones lineales $Bx = c$. Aunque el método de Gradiente Conjugado (CG) es el resolvedor estándar para sistemas SPD sin restricciones $Ax=b$, este no respeta inherentemente la restricción de no negatividad $x \ge 0$. Los métodos de punto factible existentes (por ejemplo, gradiente proyectado, MPRGP) a menudo sufren de tasas de convergencia más lentas ($O(\kappa)$) o tienen dificultades con restricciones de igualdad generales sin introducir bucles externos de Lagrangiano aumentado. El objetivo es resolver este problema sin sacrificar la tasa de convergencia $O(\sqrt{\kappa})$ del CG ni sus capacidades libres de matriz (matrix-free).

Metodología
El método propuesto, Gradientes Conjugados No Negativos (NNCG), envuelve el resolvedor CG dentro de un bucle externo de conjunto activo primal-dual. La estrategia central consiste en:

1. Reducción del Conjunto Activo: El algoritmo mantiene un "conjunto libre" $F$ de índices donde $x_i > 0$. En este conjunto, las restricciones de cota son inactivas, reduciendo el problema a un sistema SPD sin restricciones $A_F x_F = b_F$ (o un sistema de punto de silla para el caso aumentado por igualdades).
2. Resolución Interna Libre de Matriz: El sistema interno se resuelve mediante CG. Crucialmente, el método es libre de matriz: si $A = M^\top M$, el operador $v \mapsto A_F v$ se computa como $M_F^\top (M_F v)$, requiriendo solo dos productos matriz-vector con $M$ y evitando el almacenamiento $O(n^2)$ de $A$.
3. Alternancia Primal-Dual:
   • Paso Primal: Cualquier variable libre $x_i$ que se vuelva negativa es eliminada de $F$ (se establece en 0).
   • Paso Dual: Cualquier variable de cota $x_i = 0$ con un gradiente reducido negativo $s_i = (Ax)_i - b_i$ es admitida en $F$.
   • Estos cambios de estado corresponden a pivotes principales del Problema de Complementariedad Lineal (LCP) $(A, -b)$.
4. Estrategia de Terminación: Para asegurar la terminación finita incluso bajo degeneración, el método emplea un camino de pivoteo de bloque principal (intercambios rápidos por lotes) resguardado por un retroceso de Bland de índice mínimo (intercambio de un solo índice). Esta construcción, basada en J´udice y Pires [21] y Murty [25], garantiza la convergencia al único minimizador global.
5. Manejo de la Inexactitud: Una contribución teórica clave es demostrar que si el residuo interno de CG es suficientemente pequeño en relación con el "margen de decisión" (el valor más pequeño distinto de cero de los valores primal o dual encontrados en la trayectoria exacta), el bucle inexacto toma decisiones de signo idénticas al bucle exacto. Esto transfiere la garantía de terminación finita al régimen inexacto y libre de matriz.
6. Regularización y Precondicionamiento: Se utiliza una división de tipo Ridge/Tikhonov $A_\alpha = (1-\alpha)A + \alpha R^\top R$ para comprimir el número de condición $\kappa$ y asegurar que $A_\alpha$ permanezca como una matriz P (submatrices principales estrictamente definidas positivas) incluso si la matriz original es deficiente en rango. El precondicionamiento (por ejemplo, Jacobi, Nyström) se aplica para acelerar aún más la resolución interna de CG.

Contribuciones Clave

• Terminación Finita para Resoluciones Inexactas: El artículo extiende la garantía de terminación finita del pivoteo de bloque principal (previamente válida solo para resoluciones exactas) al régimen de CG inexacto y libre de matriz. El Lema 4.1 demuestra que una vez que el residuo interno está vinculado al margen de decisión, la trayectoria aproximada recorre la trayectoria del conjunto libre exacto.
• Manejo Directo de Restricciones de Igualdad: A diferencia de los métodos de punto factible que requieren bucles externos de Lagrangiano aumentado para igualdades generales $Bx=c$, este método elimina los multiplicadores analíticamente mediante un complemento de Schur, resolviendo el problema aumentado por igualdades directamente dentro del marco de conjunto activo.
• Eficiencia Libre de Matriz: El resolvedor opera sin ensamblar $A$, requiriendo solo $O(n)$ de memoria de trabajo y $O(\sqrt{\kappa})$ iteraciones internas de CG por cada paso externo.
• Inicio con Calor (Warm-Starting): El método admite el inicio con calor a través de familias paramétricas (por ejemplo, fronteras eficientes), donde el conjunto libre y la solución de un paso previo sirven como la estimación inicial, reduciendo drásticamente las iteraciones externas cuando el soporte es estable.

Resultados

• Rendimiento Sintético: En problemas SPD sintéticos con óptimos plantados, el algoritmo alcanza el óptimo en un máximo de 6 pasos externos. El conteo total de iteraciones internas de CG crece sublinealmente con el número de condición $\kappa$ (pendiente $\approx 0.35$ en escala log-log), confirmando el comportamiento $O(\sqrt{\kappa})$.
• Degeneración y Ciclado: En una familia adversaria de diseños anticorrelacionados diseñada para causar ciclos en pivotes por lotes sin resguardo, el mecanismo de retroceso propuesto logra terminar el bucle, mientras que el camino sin resguardo entra en un ciclo.
• Deficiencia de Rango: En regímenes de deficiencia de rango ($m < n$), el resolvedor no regularizado falla en converger o certificar la optimalidad. La introducción de un pequeño parámetro de regularización $\alpha > 0$ restaura la propiedad de matriz P, asegurando la convergencia y la certificación KKT.
• Comparación con Referencias:
  • vs. Gradiente Proyectado: NNCG supera al gradiente proyectado por un factor de $\sqrt{\kappa}$ en problemas mal condicionados.
  • vs. Lawson-Hanson e Interior Point: En problemas densos ensamblados, NNCG (con una resolución interna directa) es significativamente más rápido (por ejemplo, 48 veces más rápido que Lawson-Hanson para $n=2000$) debido a que el pivoteo por bloques alcanza el soporte óptimo en dígitos simples de pasos externos.
  • vs. Resolvedores Densos a Escala: En aplicaciones de desenfoque (deblurring) libres de matriz ($n=65,536$), los resolvedores densos (Lawson-Hanson, Clarabel) fallan debido a restricciones de memoria ($O(n^2)$ de almacenamiento). NNCG resuelve estos casos con $O(n)$ de memoria y en segundos, mientras que los resolvedores densos ni siquiera pueden instanciar el operador.
• Aplicación en el Mundo Real: En un problema de desmezclado hiperespectral (escena Cuprite, $n=498$ firmas), el método logra una aceleración de 672x respecto a ejecuciones con inicio en frío mediante el uso de warm-starting, y proporciona certificados KKT exactos (identificando soportes de un solo mineral), mientras que los métodos de punto factible devuelven soluciones aproximadas que requieren umbralización.

Significación y Reivindicaciones
El artículo afirma que NNCG proporciona una garantía de terminación finita incondicional para la programación cuadrática no negativa, incluso ante la presencia de degeneración y resoluciones internas inexactas. El método cierra la brecha entre la eficiencia de los métodos de subespacio de Krylov (CG) y las garantías de optimalidad combinatoria de los métodos de conjunto activo.

Los autores enfatizan que el método es agnóstico a la aplicación, manejando tanto restricciones de cota como igualdades lineales generales sin necesidad de bucles externos. Aunque el método trata únicamente el ortante no negativo (no restricciones de caja generales), ofrece una ventaja distintiva sobre los métodos de punto factible (como MPRGP) al proporcionar un certificado KKT exacto y manejar las restricciones de igualdad de forma nativa. El trabajo establece que la transferencia de "decisión por decisión" de resoluciones exactas a inexactas es posible, permitiendo combinar la robustez del pivoteo principal con la escalabilidad de los resolvedores de Krylov libres de matriz.