En la optimización numérica , el método de gradiente conjugado no lineal generaliza el método de gradiente conjugado a la optimización no lineal . Para una función cuadrática
el mínimo de se obtiene cuando el gradiente es 0:
- .
Mientras que el gradiente lineal conjugado busca una solución a la ecuación lineal , el método de gradiente conjugado no lineal se usa generalmente para encontrar el mínimo local de una función no lineal usando su gradiente solo. 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í.
Dada una función de variables a minimizar, su gradiente indica la dirección de aumento máximo. Uno simplemente comienza en la dirección opuesta ( descenso más empinado ):
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:
- ,
Después de esta primera iteración en la dirección más empinada , los siguientes pasos constituyen una iteración de moverse a lo largo de una dirección conjugada subsiguiente , dónde :
- Calcula la dirección más empinada: ,
- Calcular según una de las fórmulas siguientes,
- Actualice la dirección conjugada:
- Realizar una búsqueda de línea: optimizar ,
- Actualizar la posición: ,
Con una función cuadrática pura, el mínimo se alcanza dentro de 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 subsiguientes 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 se detiene el progreso. Sin embargo, restablecer cada iteración convierte el método en el descenso más pronunciado . El algoritmo se detiene cuando encuentra el mínimo, determinado cuando no se avanza 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 lineal conjugado pero se han obtenido con búsquedas de líneas. El método de gradiente conjugado puede seguir valles estrechos ( mal acondicionados ), donde el método de descenso más empinado se ralentiza y sigue un patrón entrecruzado.
Cuatro de las fórmulas más conocidas para llevan el nombre de sus desarrolladores:
- Fletcher – Reeves: [1]
- Polak – Ribière: [2]
- Hestenes-Stiefel: [3]
- Dai – Yuan: [4]
- .
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 reinicio de dirección automáticamente. [5]
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 de 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 caro, e incluso su almacenamiento puede ser problemático, requiriendomemoria (pero consulte el método de 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 de gradiente conjugado se convierte en un controlador de retroalimentación óptimo no lineal ,
para el sistema de doble integrador ,
Las cantidades y son ganancias de retroalimentación variables. [6]
Ver también
Referencias
- ^ Fletcher, R .; Reeves, CM (1964). "Minimización de funciones por gradientes conjugados". Computación. J . 7 : 149-154.
- ^ Polak, E .; Ribière, G. (1969). "Note sur la convergence de méthodes de directions conjuguées". Rev. Française Informat Recherche Opérationelle . 3 (1): 35–43.
- ^ Hestenes, MR; Stiefel, E. (1952). "Métodos de gradientes conjugados para resolver sistemas lineales". J. Investigación Nat. Rebaba. Estándares . 49 : 409–436.
- ^ Dai, Y.-H .; Yuan, Y. (1999). "Un método de gradiente conjugado no lineal con una fuerte propiedad de convergencia global". SIAM J. Optim . 10 (1): 177–182. doi : 10.1137 / S1052623497318992 .
- ^ Shewchuk, JR (agosto de 1994). "Una introducción al método de gradiente conjugado sin el dolor agonizante" (PDF) .
- ^ a b Ross, MI (2019). "Una teoría de control óptimo para la optimización acelerada". arXiv : 1902.09004 . Cite journal requiere
|journal=
( ayuda )