Métodos de gradiente

Los métodos de gradiente son métodos numéricos para resolver problemas usando un gradiente , que se reducen a encontrar los extremos de una función.

Enunciado del problema de resolución de un sistema de ecuaciones en términos de métodos de optimización

La tarea de resolver un sistema de ecuaciones :

$\left\{{\begin{matriz}{lcr}f_{1}(x_{1},x_{2},\ldots,x_{n})&=&0\\\ldots &&\\f_{n} (x_{1},x_{2},\ldots,x_{n})&=&0\end{matriz}}\right.$ (una)

c es equivalente al problema de minimizar la función $norte$ $x_{1},x_{2},\ldots,x_{n}$

$F(x_{1},x_{2},\ldots,x_{n})\equiv \sum_{i=1}^{n}|f_{i}(x_{1},x_{2}, ...,x_{n})|^{2}$ (2)

o alguna otra función creciente de los valores absolutos de los residuos (errores) , . El problema de encontrar el mínimo (o máximo) de una función de variables es en sí mismo de gran importancia práctica. $|f_{yo}|$ $f_{i}=f_{i}(x_{1},x_{2},\ldots,x_{n})$ $i=1,2,\ldots,n$ $norte$

Para resolver este problema usando métodos iterativos , uno comienza con valores arbitrarios y construye aproximaciones sucesivas: $x_{i}^{[0]}(i=1,2,...,n)$

${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}+\lambda ^{[j]}{\vec {v}}^{[j] }$

o coordinadamente:

$x_{i}^{[j+1]}=x_{i}^{[j]}+\lambda ^{[j]}v_{i}^{[j]},\quad i=1,2 ,\ldots,n,\quad j=0,1,2,\ldots$ (3)

que convergen a alguna solución para . ${\ vec {x}}^{[k]}$ ${j\a\infty}$

Los diferentes métodos difieren en la elección de la "dirección" para el siguiente paso, es decir, la elección de las relaciones

$v_{1}^{[j]}:v_{2}^{[j]}:\ldots :v_{n}^{[j]}$ .

El valor del paso (la distancia para moverse en una dirección dada en busca de un extremo) está determinado por el valor del parámetro que minimiza el valor en función de . Esta función generalmente se aproxima por su expansión de Taylor o por un polinomio de interpolación sobre tres a cinco valores elegidos . El último método es aplicable para encontrar el máximo y el mínimo de una función de tabla . $\lambda^{[j]}$ $F(x_{1}^{[j+1]},x_{2}^{[j+1]},\ldots,x_{n}^{[j+1]})$ $\lambda^{[j]}$ $\lambda^{[j]}$ $F(x_{1},x_{2},...,x_{n})$

Métodos de gradiente

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

${\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^ {[j]})$

donde se selecciona: $\lambda^{[j]}$

constante, en cuyo caso el método puede divergir;
paso fraccionario, es decir, la longitud del paso en el proceso de descenso se divide por un cierto número;
descenso más rápido: $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F({ \vec{x}}^{[j]}))$

Método de descenso más pronunciado ( método de gradiente )

Elija dónde se calculan todas las derivadas y reduzca la longitud del paso a medida que se acerque al mínimo de la función . $v_{i}^{[j]}=-{\frac {\parcial F}{\parcial x_{i))}$ $x_{i}=x_{i}^{[j]}$ $\lambda^{[j]}$ $F$

Para funciones analíticas y valores pequeños, la expansión de Taylor permite elegir el tamaño de paso óptimo $F$ $f_{i}$ $F(\lambda ^{[j]})$

$\lambda ^{[j]}={\frac {\sum _{k=1}^{n}({\frac {\parcial F}{\parcial x_{k))})^{2)){ \sum _{k=1}^{n}\sum _{h=1}^{n}{\frac {\parcial ^{2}F}{\parcial x_{k}dx_{h))}{ \frac {\parcial F}{\parcial x_{k))}{\frac {\parcial F}{\parcial x_{h))))}$ (5)

donde todas las derivadas se calculan en . La interpolación de funciones parabólicas puede ser más conveniente. $x_{i}=x_{i}^{[j]}$ $F(\lambda ^{[j]})$

Algoritmo

Se establecen la aproximación inicial y la precisión del cálculo. ${\vec{x}}^{0}\!,\,\epsilon$
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 ^{[j]} \nabla F\izquierda({\vec {x}}^{[j]}\derecha)\derecha)$
Compruebe la condición de parada:
- Si , vaya al paso 2. $\left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\epsilon$ $j=j+1$
- De lo contrario , deténgase. ${\vec {x}}={\vec {x}}^{[j+1]}$

Método de descenso de coordenadas de Gauss-Seidel

Este método se denomina por analogía con el método de Gauss-Seidel para resolver un sistema de ecuaciones lineales. Mejora el método anterior debido a que en la siguiente iteración el descenso se realiza gradualmente a lo largo de cada una de las coordenadas, pero ahora es necesario calcular nuevas una vez en un solo paso. ${\ estilo de visualización \ lambda \ quad n}$

Algoritmo

Se establecen la aproximación inicial y la precisión del cálculo. ${\vec {x}}_{0}^{0},\quad\varepsilon$
cuenta donde $\left\{{\begin{matriz}{lcr}{\vec {x}}_{1}^{[j]}&=&{\vec {x}}_{0}^{[j]} -\lambda _{1}^{[j]}{\frac {\parcial F({\vec {x}}_{0}^{[j]})}{\parcial x_{1}}}{ \vec {e}}_{1}\\\ldots &&\\{\vec {x}}_{n}^{[j]}&=&{\vec {x}}_{n-1} ^{[j]}-\lambda _{n}^{[j]}{\frac {\parcial F({\vec {x))_{n-1}^{[j]})}{\ parcial x_{n}}}{\vec {e}}_{n}\end{array}}\right.$ $\lambda _{i}^{[j]}=\mathrm {argmin}_{\lambda}\,F\left({\vec {x))_{i-1}^{[j]}-\ lambda ^{[j]}{\frac {\parcial F({\vec {x}}_{i-1}^{[j]})}{\parcial x_{i}}}{\vec {e }}_{i}\derecho)$
Compruebe la condición de parada:
- Si , vaya al paso 2. $|{\vec {x}}_{n}^{[j]}-{\vec {x}}_{0}^{[j]}|>\varepsilon$ ${\vec {x}}_{0}^{[j+1]}={\vec {x}}_{n}^{[j]},\quad j=j+1$
- De lo contrario , deténgase. ${\vec {x}}={\vec {x}}_{n}^{[j]}$

Método de gradiente conjugado

El método del gradiente conjugado se basa en los conceptos del método directo de optimización multidimensional : el método de las direcciones conjugadas .

Aplicando el método a funciones cuadráticas en determina el mínimo en pasos. $\mathbb{R} ^{n}$ $norte$

Algoritmo

Están dados por la aproximación inicial y el error: ${\vec {x}}_{0},\quad \varepsilon,\quad k=0$
Calcular la dirección inicial: $j=0,\quad {\vec {S}}_{k}^{j}=-\nabla f({\vec {x}}_{k}),\quad {\vec {x}}_ {k}^{j}={\vec{x}}_{k}$
${\vec {x}}_{k}^{j+1}={\vec {x}}_{k}^{j}+\lambda {\vec {S}}_{k}^{j },\quad \lambda =\arg \min_{\lambda }f({\vec {x}}_{k}^{j}+\lambda {\vec {S}}_{k}^{j }),\quad {\vec {S}}_{k}^{j+1}=-\nabla f({\vec {x}}_{k}^{j+1})+\omega { \vec {S}}_{k}^{j},\quad \omega ={\frac {||\nabla f({\vec {x}}_{k}^{j+1})|| ^{2}}{||\nabla f({\vec {x}}_{k}^{j})||^{2}}}$
- Si o , entonces deténgase. $||{\vec {S}}_{k}^{j+1}||<\varepsilon$ $||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon$ ${\vec {x}}={\vec {x}}_{k}^{j+1}$
- De lo contrario
  - si , entonces vaya a 3; ${\ estilo de visualización (j + 1) <n}$ $j=j+1$
  - de lo contrario , vaya a 2. ${\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1$

Véase también

Literatura

Akulich I.L. Programación matemática en ejemplos y tareas: Proc. Subsidio para la economía de los estudiantes. especialista. universidades - M. : Superior. escuela, 1986.
Gill F., Murray W., Wright M. Optimización práctica. Por. De inglés. — M .: Mir, 1985.
Korshunov Yu.M., Korshunov Yu.M. Fundamentos matemáticos de la cibernética. — M .: Energoatomizdat, 1972.
Maksimov Yu.A.,Filipovskaya E.A. Algoritmos para la resolución de problemas de programación no lineal. — M. : MEPHI, 1982.
Maksimov Yu.A. Algoritmos para 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.

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 metodo 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