Método de gradiente conjugado no lineal

En optimización numérica , el método del gradiente conjugado no lineal generaliza el método del gradiente conjugado a la optimización no lineal . Para una función cuadrática ${\displaystyle \displaystyle f(x)}$

${\displaystyle \displaystyle f(x)=\|Ax-b\|^{2},}$

El mínimo de se obtiene cuando el gradiente es 0: ${\displaystyle f}$

${\displaystyle \nabla _{x}f=2A^{T}(Ax-b)=0}$.

Mientras que el gradiente conjugado lineal busca una solución para la ecuación lineal , el método del gradiente conjugado no lineal se utiliza generalmente para encontrar el mínimo local de una función no lineal utilizando solo su gradiente . Funciona cuando la función es aproximadamente cuadrática cerca del mínimo, que es el caso cuando la función es dos veces diferenciable en el mínimo y la segunda derivada no es singular allí. ${\displaystyle \displaystyle A^{T}Ax=A^{T}b}$ ${\displaystyle \nabla _{x}f}$

Dada una función de variables a minimizar, su gradiente indica la dirección del aumento máximo. Simplemente se comienza en la dirección opuesta ( la de descenso más pronunciado ): ${\displaystyle \displaystyle f(x)}$ ${\displaystyle N}$ ${\displaystyle \nabla _{x}f}$

${\displaystyle \Delta x_{0}=-\nabla _{x}f(x_{0})}$

con una longitud de paso ajustable y realiza una búsqueda de línea en esta dirección hasta que alcanza el mínimo de : ${\displaystyle \displaystyle \alpha }$ ${\displaystyle \displaystyle f}$

${\displaystyle \displaystyle \alpha _{0}:=\arg \min _{\alpha }f(x_{0}+\alpha \Delta x_{0})}$,

${\displaystyle \displaystyle x_{1}=x_{0}+\alpha _{0}\Delta x_{0}}$

Después de esta primera iteración en la dirección más empinada , los siguientes pasos constituyen una iteración de movimiento a lo largo de una dirección conjugada posterior , donde : ${\displaystyle \displaystyle \Delta x_{0}}$ ${\displaystyle \displaystyle s_{n}}$ ${\displaystyle \displaystyle s_{0}=\Delta x_{0}}$

1. Calcular la dirección más empinada: , ${\displaystyle \Delta x_{n}=-\nabla _{x}f(x_{n})}$
2. Calcular según una de las fórmulas siguientes, ${\displaystyle \displaystyle \beta _{n}}$
3. Actualizar la dirección conjugada: ${\displaystyle \displaystyle s_{n}=\Delta x_{n}+\beta _{n}s_{n-1}}$
4. Realizar una búsqueda de línea: optimizar , ${\displaystyle \displaystyle \alpha _{n}=\arg \min _{\alpha }f(x_{n}+\alpha s_{n})}$
5. Actualizar la posición: , ${\displaystyle \displaystyle x_{n+1}=x_{n}+\alpha _{n}s_{n}}$

Con una función cuadrática pura, el mínimo se alcanza en N iteraciones (excepto el error de redondeo), pero una función no cuadrática hará un progreso más lento. Las direcciones de búsqueda posteriores pierden conjugación, lo que requiere que la dirección de búsqueda se restablezca a la dirección de descenso más pronunciado al menos cada N iteraciones, o antes si el progreso se detiene. Sin embargo, restablecer cada iteración convierte el método en descenso más pronunciado . El algoritmo se detiene cuando encuentra el mínimo, determinado cuando no se realiza ningún progreso después de un restablecimiento de dirección (es decir, en la dirección de descenso más pronunciado), o cuando se alcanza algún criterio de tolerancia.

En una aproximación lineal, los parámetros y son los mismos que en el método de gradiente conjugado lineal, pero se han obtenido con búsquedas lineales. El método de gradiente conjugado puede seguir valles estrechos ( mal acondicionados ), donde el método de descenso más pronunciado se ralentiza y sigue un patrón entrecruzado. ${\displaystyle \displaystyle \alpha }$ ${\displaystyle \displaystyle \beta }$

Cuatro de las fórmulas más conocidas llevan el nombre de sus desarrolladores: ${\displaystyle \displaystyle \beta _{n}}$

• Fletcher–Reeves: ^[1]

${\displaystyle \beta _{n}^{FR}={\frac {\Delta x_{n}^{T}\Delta x_{n}}{\Delta x_{n-1}^{T}\Delta x_{n-1}}}.}$

• Polak–Ribière: ^[2]

${\displaystyle \beta _{n}^{PR}={\frac {\Delta x_{n}^{T}(\Delta x_{n}-\Delta x_{n-1})}{\Delta x_{n-1}^{T}\Delta x_{n-1}}}.}$

• Hestenes–Stiefel: ^[3]

${\displaystyle \beta _{n}^{HS}={\frac {\Delta x_{n}^{T}(\Delta x_{n}-\Delta x_{n-1})}{-s_{n-1}^{T}(\Delta x_{n}-\Delta x_{n-1})}}.}$

• Dai-Yuan: ^[4]

${\displaystyle \beta _{n}^{DY}={\frac {\Delta x_{n}^{T}\Delta x_{n}}{-s_{n-1}^{T}(\Delta x_{n}-\Delta x_{n-1})}}.}$.

Estas fórmulas son equivalentes para una función cuadrática, pero para la optimización no lineal la fórmula preferida es una cuestión de heurística o gusto. Una opción popular es , que proporciona un restablecimiento automático de la dirección. ^[5] ${\displaystyle \displaystyle \beta =\max\{0,\beta ^{PR}\}}$

Los algoritmos basados ​​en el método de Newton convergen potencialmente mucho más rápido. Allí, tanto la dirección como la longitud del paso se calculan a partir del gradiente como la solución de un sistema lineal de ecuaciones, siendo la matriz de coeficientes la matriz hessiana exacta (para el método de Newton propiamente dicho) o una estimación de la misma (en los métodos cuasi-Newton , donde el cambio observado en el gradiente durante las iteraciones se utiliza para actualizar la estimación hessiana). Para problemas de alta dimensión, el cálculo exacto de la hessiana suele ser prohibitivamente costoso, e incluso su almacenamiento puede ser problemático, requiriendo memoria (pero véase el método cuasi-Newton L-BFGS de memoria limitada ). ${\displaystyle O(N^{2})}$

El método del gradiente conjugado también se puede derivar utilizando la teoría de control óptimo . ^[6] En esta teoría de optimización acelerada, el método del gradiente conjugado resulta ser un controlador de retroalimentación óptimo no lineal .

${\displaystyle u=k(x,{\dot {x}}):=-\gamma _{a}\nabla _{x}f(x)-\gamma _{b}{\dot {x}}}$para el sistema integrador doble ,

${\displaystyle {\ddot {x}}=u}$

Las cantidades y son ganancias de retroalimentación variables. ^[6] ${\displaystyle \gamma _{a}>0}$ ${\displaystyle \gamma _{b}>0}$

Véase también

• Descenso de gradiente
• Algoritmo de Broyden-Fletcher-Goldfarb-Shanno
• Método del gradiente conjugado
• L-BFGS (BFGS de memoria limitada)
• Método Nelder-Mead
• Condiciones de Wolfe

Referencias

1. Fletcher, R.; Reeves, CM (1964). "Minimización de funciones mediante gradientes conjugados". The Computer Journal . 7 (2): 149–154. doi : 10.1093/comjnl/7.2.149 .
2. Polak, E.; Ribière, G. (1969). "Nota sobre la convergencia de métodos de direcciones conjugadas". Revue Française d'Automatique, Informatique, Recherche Opérationnelle . 3 (1): 35–43.
3. Hestenes, MR; Stiefel, E. (1952). "Métodos de gradientes conjugados para resolver sistemas lineales". Revista de investigación de la Oficina Nacional de Normas . 49 (6): 409–436. doi : 10.6028/jres.049.044 .
4. Dai, Y.-H.; Yuan, Y. (1999). "Un método de gradiente conjugado no lineal con una fuerte propiedad de convergencia global". Revista SIAM sobre optimización . 10 (1): 177–182. doi :10.1137/S1052623497318992.
5. Shewchuk, JR (agosto de 1994). "Una introducción al método del gradiente conjugado sin el dolor agonizante" (PDF) .
6. Ross, IM (2019). "Una teoría de control óptimo para la optimización acelerada". arXiv : 1902.09004 [math.OC].