Descenso de gradiente

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 17 de julio de 2021; la verificación requiere 1 edición .

Descenso de gradiente, el método de descenso de gradiente es un método numérico para encontrar un mínimo o máximo local de una función moviéndose a lo largo de un gradiente , uno de los principales métodos numéricos de optimización moderna.

Se usa activamente en matemáticas computacionales no solo para la solución directa de problemas de optimización (minimización), sino también para problemas que pueden reescribirse en el lenguaje de optimización (solución de ecuaciones no lineales, búsqueda de equilibrios, problemas inversos, etc.). El método de descenso de gradiente se puede utilizar para problemas de optimización en espacios de dimensión infinita, por ejemplo, para la solución numérica de problemas de control óptimo.

El interés particularmente grande en los métodos de gradiente en los últimos años se debe al hecho de que los descensos de gradiente y sus variantes estocásticas/aleatorias son la base de casi todos los algoritmos de aprendizaje modernos desarrollados en el análisis de datos.

Descripción

Deje que la función objetivo se vea como:

F({\vec {x}}):\;\mathbb {X} \to \mathbb {R}

Y el problema de optimización queda dado de la siguiente manera:

F({\vec {x}})\to \min _({\vec {x}}\in \mathbb {X}} }

En el caso de que se requiera encontrar el máximo, en lugar de usar $F({\vec {x)))$ $-F({\vec{x)))$

La idea principal del método es ir en la dirección de la bajada más empinada, y esta dirección viene dada por el anti - gradiente : $-\ nabla F$

{\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\derecho)

donde especifica la velocidad de descenso del gradiente y se puede elegir $\lambda^{[j]}$

constante (en este caso, el método puede divergir);
disminuyendo durante el descenso de gradiente;
garantizando el descenso más rápido:
1. Para encontrar el mínimo, obtenemos ${\ estilo de visualización F \ izquierda ({\ vec {x}} \ derecha)}$ $\lambda ^{[j]}=\mathrm {argmin}_{\lambda}F\left({\vec {x}}^{[j+1]}\right)=\mathrm {argmin} _{\lambda}\,F\left({\vec {x}}^{[j]}-\lambda \nabla F\left({\vec {x}}^{[j]}\right)\ Correcto)$
2. Para encontrar el máximo, obtenemos ${\ estilo de visualización F \ izquierda ({\ vec {x}} \ derecha)}$ $\lambda ^{[j]}=\mathrm {argmax}_{\lambda}F\left({\vec {x}}^{[j+1]}\right)=\mathrm {argmax} _{\lambda}\,F\left({\vec {x}}^{[j]}+\lambda \nabla F\left({\vec {x}}^{[j]}\right)\ Correcto)$

Algoritmo

Establecer la aproximación inicial y la precisión del cálculo ${\vec{x}}^{0},\varepsilon$
cuenta donde ${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\derecho)$ $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda \nabla F\left( {\ vec {x}}^{[j]}\derecho)\derecho)$
Compruebe la condición de parada:
- Si , o (elija una de las condiciones), vaya al paso 2. $\left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\varepsilon$ $\left|F\left({\vec {x}}^{[j+1]}\right)-F\left({\vec {x}}^{[j]}\right)\ derecha|>\varepsilon$ $\left\|\nabla F\left({\vec {x}}^{[j+1]}\right)\right\|>\varepsilon$ $j=j+1$
- De lo contrario , deténgase. ${\vec {x}}={\vec {x}}^{[j+1]}$

La relación de Kantorovich

Para una función cuadrática de la forma , el método de búsqueda del gradiente más pronunciado converge desde cualquier punto de partida a la velocidad de una progresión geométrica (linealmente) con un denominador que no excede . En este caso, las siguientes estimaciones son válidas: ${\frac{x^{T}\Gamma x}{2}}+c^{T}x,\Gamma ^{T}=\Gamma$ $x_{0}$ $q$

\existe a=a(x_{0}),T>0:0\leq a\leq q={\frac {\left(\lambda _{min}/\lambda _{max}-1\right)^ {2}}{\izquierda(\lambda_{min}/\lambda_{max}+1\derecha)^{2}}}

f(x_{k})-f(x^{*})\leq a^{k}(f(x_{0})-f(x^{*}))

\|x_{k}-x^{*}\|\leq Ta^{k/2}\|x_{0}-x^{*}\|

donde y son los valores propios mínimo y máximo de la matriz de segundas derivadas . $\lambda _{min}$ $\lambda _{max}$ $\nabla ^{2}f(x)=\Gamma$

Así, dado que la función está un poco cerca de su aproximación cuadrática, la tasa de convergencia, en la vecindad del punto mínimo, depende de la relación de los valores propios. Cuanto mayor sea esta relación, peor será la convergencia del método.

Ejemplo

Apliquemos el método del gradiente a la función . Entonces las aproximaciones sucesivas se verán así: $F(x,y)=\sin \left({\frac {1}{2}}x^{2}-{\frac {1}{4}}y^{2}+3\right)\cos (2x+1-e^{y})$

Este es un ejemplo típico de una función de barranco. El método del gradiente "salta" de una vertiente del barranco a otra y viceversa, a veces casi sin moverse en la dirección correcta, lo que ralentiza significativamente la convergencia. Otro ejemplo de una función de barranco de prueba es la función de Rosenbrock .

Mejoras, modificaciones

Para minimizar la función en la dirección del gradiente se utilizan métodos de optimización unidimensional , como el método de la sección áurea . También puede buscar no el mejor punto en la dirección del gradiente, sino algo mejor que el actual.

El método de descenso de gradiente es el más fácil de implementar de todos los métodos de optimización local. Tiene condiciones de convergencia bastante débiles, pero la tasa de convergencia es bastante pequeña (lineal). El paso del método de gradiente se usa a menudo como parte de otros métodos de optimización, como el método de Fletcher-Reeves .

El método de descenso de gradiente resulta muy lento al moverse a lo largo de un barranco, ya medida que aumenta el número de variables de la función objetivo, este comportamiento del método se vuelve típico. Para combatir este fenómeno, se utiliza el método del barranco , cuya esencia es muy simple. Habiendo dado dos pasos de descenso de pendiente y habiendo recibido tres puntos, el tercer paso se debe dar en la dirección del vector que conecta el primer y el tercer punto, a lo largo del fondo del barranco.

Para funciones cercanas a las cuadráticas, el método del gradiente conjugado es efectivo .

Aplicaciones en redes neuronales artificiales

El método de descenso de gradiente con algunas modificaciones se usa ampliamente para entrenar al perceptrón y se conoce en la teoría de las redes neuronales artificiales como el método de retropropagación . Cuando se entrena una red neuronal del tipo perceptrón, se requiere cambiar los coeficientes de peso de la red de tal manera que se minimice el error promedio en la salida de la red neuronal cuando se alimenta a la entrada una secuencia de datos de entrada de entrenamiento. . Formalmente, para dar solo un paso de acuerdo con el método de descenso de gradiente (hacer solo un cambio en los parámetros de la red), es necesario alimentar secuencialmente todo el conjunto de datos de entrenamiento a la entrada de la red, calcular el error para cada dato de entrenamiento objeto y calcule la corrección necesaria de los coeficientes de red (pero no haga esta corrección), y después de enviar todos los datos, calcule la suma en la corrección de cada coeficiente de red (suma de gradientes) y corrija los coeficientes "en un paso" . Obviamente, con un gran conjunto de datos de entrenamiento, el algoritmo funcionará extremadamente lento, por lo tanto, en la práctica, los coeficientes de red a menudo se ajustan después de cada elemento de entrenamiento, donde el valor del gradiente se aproxima por el gradiente de la función de costo calculada en solo uno. elemento de entrenamiento. Este método se denomina descenso de gradiente estocástico o descenso de gradiente operativo . El descenso de gradiente estocástico es una forma de aproximación estocástica. La teoría de las aproximaciones estocásticas proporciona condiciones para la convergencia del método de descenso del gradiente estocástico.

Enlaces

J. Mathews. Módulo para Método de Descenso Más Profundo o Gradiente.
Demostración interactiva metafórica del método Fastest Pyu

Literatura

Polyak B. T. Introducción a la optimización. - M. : Ciencia. Edición principal de literatura física y matemática, 1983. - 384 p.
Nesterov Yu. E. Métodos de optimización convexa . - M. : Editorial MTSNMO, 2010. - 281 p.
Gasnikov AV Métodos numéricos modernos de optimización. El método de descenso de gradiente universal: una guía de estudio . - M. : MIPT, 2018. - 291 p. - ISBN 978-5-7417-0667-1 .
Akulich IL Programación matemática en ejemplos y problemas. - M. : Escuela Superior, 1986. - S. 298-310.
Gill F., Murray W., Wright M. Optimización práctica = Optimización práctica. — M .: Mir, 1985.
Korshunov Yu. M., Korshunov Yu. M. Fundamentos matemáticos de la cibernética. — M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmos para resolver problemas de programación no lineal. — M. : MEPHI, 1982.
Maksimov Yu. A. Algoritmos de programación lineal y discreta. — M. : MEPhI, 1980.
Korn G., Korn T. Manual de matemáticas para científicos e ingenieros. - M. : Nauka, 1970. - S. 575-576.
Gorodetsky S. Yu., Grishagin VA Programación no lineal y optimización multiextremal. - Nizhny Novgorod: Editorial de la Universidad de Nizhny Novgorod, 2007. - S. 357-363.

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock Método Powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial