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.

 

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.

 

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 ∈ ℜⁿ

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.

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.