Gradiente Conjugado (GC)

En 1.952  Magnus R. Hestenes y Eduard Stiefel publican «Methods of Congugate Gradients for Solving Linear Systems» siendo los primeros que hablan del gradiente conjugado (CG). Con posterioridad y en 1.971, J. K. Reid publica «On the Method of Conjugate Gradients for the Solution of Large Sparce Systems of Linear Equations», donde plantea el gradiente conjugado como un método iterativo, es la forma en la cual lo utilizmos ahora.

Magnus-Hestenes
Hestenes
Eduard Stiefel
Stiefel

 

Su objetivo era llegar al mínimo de las funciones cuadráticas, ampliándose después para las funciones generales simples (no necesariamente convexas).

 

 

Fundamentalmente es una modificación del gradiente descendente, donde el gradiente ha sido reemplazado por direcciones conjugadas «ortogonales» (subespacio de Krylov) que pueden ser construidas usando gradientes como vectores de base. Su desarrollo está motivado por la necesidad de acelerar la convergencia, más lenta en el gradiente descendente y superar la limitación computacional del método de segundo orden.

 

Las ventajas del gradiente conjugado son varias: no requiere álgebra lineal numérica, utiliza poca memoria para problemas a gran escala, no requiere la matriz de Hesse, por tanto es más efectivo que otros métodos para el entrenamiento de redes neuronales grandes. Tiene el inconveniente de converger más lentamente que los métodos cuasi-Newton y los pasos suelen tener una reducida escala de longitud, por lo que puede requerir más iteraciones para encontrar un paso aceptable.

 

En el gráfico vemos el problema del método del gradiente descendente representado por la  línea negra. Este necesita más iteraciones para funciones que tienen estructuras de valle largas y estrechas. En frente está el gradiente conjugado, aquí representado por la línea verde.

 

Gradiente conjugado

Matemáticamente es un método iterativo no estacionario que permite resolver sistemas lineales bajo la restricción de que la matriz de coeficientes A, sea simétrica y definida positiva:

 

donde:

x  es un vector desconocido,

b es un vector conocido, b ∈ ℜn

A es una matriz cuadrada simétrica y definida positiva, A ∈ ℜn×n  y  A > 0

Antes de ver otros métodos debemos introducir el concepto de reinicio (búsqueda local repetida). El reinicio se aplica cuando se encuentra o podemos encontrar un comportamiento irregular de convergencia. El reinicio es la acción de limpiar la memoria y volver a comenzar desde el punto actual, esto lleva implícita la pregunta, ¿cuándo lo hacemos?. En función del algoritmo podemos ajecutarlo cuando dos gradientes consecutivos estén muy lejanos de la ortogonalidad o cada n iteracciones

 

Otros métodos.

Existen también variantes para abordar matrices no simétricas:

  • Sistemas Transformadores. Toman el sistema no simétrico convirtiéndolo en simétrico y trabajan con él. El coste de almacenamiento se duplica por lo que su uso no es adecuado para grandes sistemas.
  • Sistemas Directos.

PCG. Para resolver las deficiencias del Gradiente Conjugado en la convergencia, surgen los métodos pre-condicionados (PCG), la proposición es de Paul Concus, Gene H. Golub y Dianne P. O’Leary en 1.976. Pero estos tienen otro problema, es difícil encontrar un pre-condicionador que funcione bien en todas las situaciones, acción que no ayudará a mejorar la velocidad. Algunos de ellos:

  • Jacobi, Gauss-Seidel, SOR, SSOR, Chebyshev.
  • Factorizaciones Incompletas (ILU o ILUT)
  • Aproximada Inversa de estructura diagonal.

La aplicación de un pre-condicionador o matriz de pre-condicionado consiste en reemplazar el sistema de ecuaciones original por uno de idéntica solución, pero cuyas propiedades numéricas puedan tener menores errores de redondeo. Su trabajo se basa en calcular una factorización de la matriz A con cierto grado de llenado, mientras se espera que el producto de dichos factores se asemeje a la matriz A y, más importante, que el producto de sus inversas se asemeje a A−1.
.

 

FOM (Full Orthogonalization Method). Aplica en cada paso el algoritmo de Arnoldi, modificado Gram-Schmidt. El coste computacional es ± k2n y el coste de almacenamiento es de kn, un problema para grandes valores de n.

 

GMRES y FGMRES. Generalized Minimal Residual y Algoritmo Flexible GMRES. Desarrollado por Y. Saad y M. H. Schultz en 1.986. Admite varios pre-condicionadores. Crea una base ortogonal del subespacio de Krylov utilizando la ortogonalización de Grahm-Schmidt. Es un devorador de memoria, ya que le es necesario almacenar la base que se incrementa con cada iteración. Se mejoró al incluir un reinicio cada cierto número de pasos (Restarted GMRES).

 

VFGMRES. Algoritmo Variable FGMRES. Utiliza la solución directa del problema de mínimos cuadrados. Su idea básica es usar el GMRES al principio del algoritmo hasta que satisface una cierta tolerancia, al finalizar hace un rearranque y comenza nuevamente con GMRES hasta finalizar.

 

BiCG.  Gradiente Bi-conjugado. Desarrollado por D. A. H. Jacobs en 1.981. No exige que la matriz sea simétrica. Utiliza el algoritmo de biortogonalización de Lanczos. Se basa en reemplazar las secuencias ortogonales de residuos por dos secuencias mutuamente ortogonales. Para matrices simétricas y definidas positivas obtiene los mismos resultados que el método del GC.

 

CGS. Gradiente Conjugado Cuadrático. Fue desarrollado po P. Sonneveld en 1.989. Es una variante del Bi-Conjugado. La Cantidad de operaciones es muy similar al BiCG pero la convergencia puede ser más irregular que para el BiCG.

 

Bi-CGSTAB. Gradiente Bi-conjugado Estabilizado. Fue desarrollado por Hendrik A. Van der Vorst en 1.992 como una variante del CGS. Es aplicable a sistemas lineales no simétricos y reduce la irregularidad del CGS modificando el polinomio que se usa para el cálculo del residuo.

 

QMRCGSTAB. Este método aplica el principio de cuasi-minimización al BI-CGSTAG. La minimización por mínimos cuadrados incluida en el proceso es resuelta usando la descomposición QR de la matriz de Hessemberg.

12 thoughts on “Gradiente Conjugado (GC)

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

5 × 5 =