Método de gradiente conjugado no lineal

En la 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 a la ecuación lineal , el método del gradiente conjugado no lineal se usa generalmente para encontrar el mínimo local de una función no lineal usando 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 de máximo aumento. Simplemente se comienza en la dirección opuesta ( el 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 alcanzar 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 pronunciada , 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. Calcule la dirección más pronunciada: , ${\displaystyle \Delta x_{n}=-\nabla _{x}f(x_{n})}$
2. Calcule de acuerdo con una de las fórmulas siguientes, ${\displaystyle \displaystyle \beta _{n}}$
3. Actualiza 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 progresará más lentamente. 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 pronunciada al menos cada N iteraciones, o antes si el progreso se detiene. Sin embargo, restablecer 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 logra ningún progreso después de un reinicio de dirección (es decir, en la dirección de descenso más pronunciada), o cuando se alcanza algún criterio de tolerancia.

Dentro de 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 del gradiente conjugado puede seguir valles estrechos ( mal condicionados ), 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 de gusto. Una opción popular es , que proporciona un restablecimiento de dirección automáticamente. ^[5] ${\displaystyle \displaystyle \beta =\max\{0,\beta ^{PR}\}}$

Los algoritmos basados ​​en el método de Newton potencialmente convergen 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 de Hesse 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 Hesse). Para problemas de alta dimensión, el cálculo exacto del hessiano suele ser prohibitivamente costoso, e incluso su almacenamiento puede ser problemático, ya que requiere memoria (pero consulte 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 doble integrador ,

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

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

Ver también

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

Referencias

1. Fletcher, R.; Reeves, CM (1964). "Minimización de funciones mediante gradientes conjugados". La revista informática . 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, señor; 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 [matemáticas.OC].