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${\displaystyle f}$se obtiene cuando el gradiente es 0:

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

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

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

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

con longitud de paso ajustable${\displaystyle \displaystyle \alpha}$y realiza una búsqueda lineal en esta dirección hasta que alcanza el mínimo de${\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 pronunciada${\displaystyle \displaystyle \Delta x_ {0}}$Los siguientes pasos constituyen una iteración de movimiento a lo largo de una dirección conjugada subsiguiente.${\displaystyle \displaystyle s_ {n}}$, dónde${\displaystyle \displaystyle s_{0}=\Delta x_{0}}$:

1. Calcula la dirección de mayor pendiente:${\displaystyle \Delta x_{n}=-\nabla _{x}f(x_{n})}$,
2. Calcular${\displaystyle \displaystyle \beta _ {n}}$Según una de las fórmulas que aparecen a continuación,
3. Actualizar la dirección conjugada:${\displaystyle \displaystyle s_{n}=\Delta x_{n}+\beta _{n}s_{n-1}}$
4. Realizar una búsqueda lineal: optimizar${\displaystyle \displaystyle \alpha _{n}=\arg \min _{\alpha }f(x_{n}+\alpha s_{n})}$,
5. Actualizar el puesto:${\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 por errores de redondeo), pero una función no cuadrática avanza más lentamente. Las direcciones de búsqueda subsiguientes 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 la dirección en cada iteración convierte el método en un descenso más pronunciado . El algoritmo se detiene cuando encuentra el mínimo, determinado cuando no se produce ningún progreso después de restablecer la dirección (es decir, en la dirección de descenso más pronunciado), o cuando se alcanza algún criterio de tolerancia.

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

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

• 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 preferencia. Una opción popular es${\displaystyle \displaystyle \beta =\max\{0,\beta ^{PR}\}}$, que proporciona un restablecimiento de dirección automático. ^{[ 5 ]}

Los algoritmos basados ​​en el método de Newton convergen potencialmente mucho más rápido. En ellos, tanto la dirección como la longitud del paso se calculan a partir del gradiente como 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 de la 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${\displaystyle O(N^{2})}$memoria (pero véase el método cuasi-Newton L-BFGS de memoria limitada ).

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 surge como 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 de doble integrador ,

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

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

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