El método de descenso más pronunciado (en la literatura inglesa “método de descenso más pronunciado”) es un método numérico iterativo (primer orden) para resolver problemas de optimización, que permite determinar el extremo (mínimo o máximo) de la función objetivo:

son los valores del argumento de la función (parámetros controlados) en el dominio real.

De acuerdo con el método considerado, el extremo (máximo o mínimo) de la función objetivo se determina en la dirección del aumento (disminución) más rápido de la función, es decir en la dirección del gradiente (antigradiente) de la función. Función de gradiente en un punto es un vector cuyas proyecciones sobre los ejes de coordenadas son las derivadas parciales de la función con respecto a las coordenadas:

donde i, j,…, n son vectores unitarios paralelos a los ejes de coordenadas.

gradiente en el punto base es estrictamente ortogonal a la superficie, y su dirección muestra la dirección del aumento más rápido de la función, y la dirección opuesta (antigradiente), respectivamente, muestra la dirección del descenso más rápido de la función.

El método de descenso más pronunciado es un desarrollo posterior del método de descenso en gradiente. En general, el proceso de encontrar el extremo de una función es un procedimiento iterativo, que se escribe de la siguiente manera:

donde el signo "+" se usa para encontrar el máximo de una función y el signo "-" se usa para encontrar el mínimo de una función;

Vector de dirección unitario, que está determinado por la fórmula:

- el módulo de gradiente determina la tasa de aumento o disminución de la función en la dirección del gradiente o antigradiente:

Una constante que determina el tamaño del paso y es la misma para todas las i-ésimas direcciones.

El tamaño del paso se selecciona a partir de la condición del mínimo de la función objetivo f(x) en la dirección del movimiento, es decir, como resultado de resolver el problema de optimización unidimensional en la dirección del gradiente o antigradiente:

En otras palabras, el tamaño del paso se determina resolviendo esta ecuación:

Así, el paso de cálculo se elige de forma que el movimiento se realice hasta que la función mejore, llegando así en algún momento a un extremo. En este punto se vuelve a determinar la dirección de búsqueda (utilizando el gradiente) y se busca un nuevo punto óptimo de la función objetivo, etc. Por tanto, en este método, la búsqueda se produce en pasos más grandes y el gradiente de la función se calcula en un número menor de puntos.

En el caso de una función de dos variables, este método tiene la siguiente interpretación geométrica: la dirección del movimiento desde un punto toca la línea de nivel en el punto . La trayectoria de descenso es en zigzag, con enlaces en zigzag adyacentes ortogonales entre sí. La condición para la ortogonalidad de los vectores de direcciones de descenso en puntos vecinos se escribe mediante la siguiente expresión:

La trayectoria de movimiento hasta el punto extremo utilizando el método de descenso más pronunciado, que se muestra en la gráfica de la línea de igual nivel de la función f(x)

La búsqueda de una solución óptima finaliza en el paso de cálculo iterativo (varios criterios):

La trayectoria de búsqueda permanece en una pequeña vecindad del punto de búsqueda actual:

El incremento de la función objetivo no cambia:

El gradiente de la función objetivo en el punto mínimo local se vuelve cero:

Cabe señalar que el método de descenso de gradiente resulta muy lento cuando se avanza por un barranco, y a medida que aumenta el número de variables en la función objetivo, este comportamiento del método se vuelve típico. El barranco es una depresión cuyas líneas de nivel tienen aproximadamente la forma de elipses con semiejes que difieren muchas veces. En presencia de un barranco, la trayectoria de descenso toma la forma de una línea en zigzag con un pequeño paso, por lo que la velocidad de descenso resultante al mínimo se ralentiza considerablemente. Esto se explica por el hecho de que la dirección del antigradiente de estas funciones se desvía significativamente de la dirección al punto mínimo, lo que provoca un retraso adicional en el cálculo. Como resultado, el algoritmo pierde eficiencia computacional.

Función de barranco

El método del gradiente, junto con sus numerosas modificaciones, es un método común y eficaz para buscar el óptimo de los objetos en estudio. La desventaja de la búsqueda de gradiente (así como los métodos discutidos anteriormente) es que cuando se usa, solo se puede detectar el extremo local de la función. Para encontrar otros extremos locales, es necesario buscar desde otros puntos de partida. Además, la tasa de convergencia de los métodos de gradiente también depende significativamente de la precisión de los cálculos de gradiente. La pérdida de precisión, que suele ocurrir en las proximidades de puntos mínimos o en una situación de barrancos, generalmente puede alterar la convergencia del proceso de descenso del gradiente.

Método de cálculo

Paso 1: Definición de expresiones analíticas (en forma simbólica) para calcular el gradiente de una función.

Paso 2: establece la aproximación inicial

Paso 3: Se determina la necesidad de reiniciar el procedimiento algorítmico para restablecer la última dirección de búsqueda. Como resultado del reinicio, se vuelve a buscar en la dirección del descenso más rápido.

Fig. 3. Interpretación geométrica del método de descenso más pronunciado. En cada paso, se elige de modo que la siguiente iteración sea el punto mínimo de la función en el rayo L.

Esta versión del método de gradiente se basa en la elección del paso entre las siguientes consideraciones. Desde el punto nos moveremos en la dirección del antigradiente hasta alcanzar el mínimo de la función f en esta dirección, es decir, en el rayo:

En otras palabras, se elige de modo que la siguiente iteración sea el punto mínimo de la función f en el rayo L (ver Fig. 3). Esta versión del método del gradiente se denomina método de descenso más pronunciado. Por cierto, tenga en cuenta que en este método las direcciones de los pasos adyacentes son ortogonales.

El método de descenso más pronunciado requiere resolver un problema de optimización unidimensional en cada paso. La práctica demuestra que este método a menudo requiere menos operaciones que el método de gradiente con un paso constante.

Sin embargo, en la situación general, la tasa de convergencia teórica del método de descenso más pronunciado no es mayor que la tasa de convergencia del método de gradiente con un paso constante (óptimo).

Ejemplos numéricos

Método de descenso de gradiente con paso constante.

Para estudiar la convergencia del método de descenso de gradiente con paso constante se eligió la función:

De los resultados obtenidos podemos concluir que si la brecha es demasiado grande, el método diverge; si la brecha es demasiado pequeña, converge lentamente y la precisión es peor. Es necesario elegir el paso más grande entre aquellos en los que converge el método.

Método de gradiente con división de pasos.

Para estudiar la convergencia del método de descenso de gradiente con división de pasos (2), se eligió la función:

La aproximación inicial es el punto (10,10).

Criterio de parada utilizado:

Los resultados del experimento se muestran en la tabla:

De los resultados obtenidos podemos concluir sobre la elección óptima de parámetros: , aunque el método no es muy sensible a la elección de parámetros.

Método de descenso más pronunciado.

Para estudiar la convergencia del método de descenso más pronunciado se eligió la siguiente función:

La aproximación inicial es el punto (10,10). Criterio de parada utilizado:

Para resolver problemas de optimización unidimensionales se utilizó el método de la sección áurea.

El método logró una precisión de 6e-8 en 9 iteraciones.

De esto podemos concluir que el método de descenso más pronunciado converge más rápido que el método de gradiente dividido en pasos y el método de descenso de gradiente en pasos constantes.

La desventaja del método de descenso más pronunciado es que requiere resolver un problema de optimización unidimensional.

Al programar métodos de descenso de gradiente, se debe tener cuidado al elegir los parámetros, es decir

• · Método de descenso de gradiente con un paso constante: el paso debe elegirse inferior a 0,01; de lo contrario, el método diverge (el método puede divergir incluso con dicho paso, dependiendo de la función que se esté estudiando).
• · El método de gradiente con división de pasos no es muy sensible a la elección de parámetros. Una de las opciones para seleccionar parámetros:
• · Método de descenso más pronunciado: el método de proporción áurea (cuando corresponda) se puede utilizar como método de optimización unidimensional.

El método del gradiente conjugado es un método iterativo para la optimización sin restricciones en un espacio multidimensional. La principal ventaja del método es que resuelve un problema de optimización cuadrática en un número finito de pasos. Por lo tanto, primero se describe el método del gradiente conjugado para optimizar el funcional cuadrático, se derivan fórmulas iterativas y se dan estimaciones de la tasa de convergencia. Después de esto, se muestra cómo se generaliza el método adjunto para optimizar un funcional arbitrario, se consideran varias variantes del método y se discute la convergencia.

Declaración del problema de optimización.

Sea dado un conjunto y definida una función objetivo en este conjunto. El problema de optimización consiste en encontrar el límite superior o inferior exacto de la función objetivo en el conjunto. Se designa el conjunto de puntos en los que se alcanza el límite inferior de la función objetivo.

Si, entonces el problema de optimización se llama sin restricciones. Si, entonces el problema de optimización se llama restringido.

Método de gradiente conjugado para funcional cuadrática.

Declaración del método

Considere el siguiente problema de optimización:

Aquí hay una matriz simétrica de tamaño definido positivo. Este problema de optimización se llama cuadrático. Darse cuenta de. La condición para un extremo de una función es equivalente al sistema. La función alcanza su límite inferior en un único punto definido por la ecuación. Así, este problema de optimización se reduce a resolver un sistema de ecuaciones lineales. La idea del método del gradiente conjugado es la siguiente: Sea la base en. Luego, para cualquier punto, el vector se expande hasta formar la base. Por lo tanto, se puede representar en la forma.

Cada aproximación posterior se calcula mediante la fórmula:

Definición. Se dice que dos vectores y son conjugados con respecto a la matriz simétrica B si

Describamos el método de construcción de una base en el método del gradiente conjugado. Seleccionamos un vector arbitrario como aproximación inicial. En cada iteración se seleccionan las siguientes reglas:

Los vectores base se calculan mediante las fórmulas:

Los coeficientes se eligen de modo que los vectores y sean conjugados con respecto a A.

Si lo denotamos por , luego de varias simplificaciones obtenemos las fórmulas finales utilizadas al aplicar el método del gradiente conjugado en la práctica:

Para el método del gradiente conjugado, se cumple el siguiente teorema: Teorema Sea, donde es una matriz de tamaño definida positiva simétrica. Entonces el método del gradiente conjugado converge en no más de pasos y se mantienen las siguientes relaciones:

Convergencia del método

Si todos los cálculos son precisos y los datos iniciales son precisos, entonces el método converge para resolver el sistema en no más de iteraciones, donde está la dimensión del sistema. Un análisis más refinado muestra que el número de iteraciones no excede, donde está el número de valores propios diferentes de la matriz A. Para estimar la tasa de convergencia, la siguiente estimación (bastante aproximada) es correcta:

Le permite estimar la tasa de convergencia si se conocen las estimaciones de los valores propios máximo y mínimo de la matriz. En la práctica, se utiliza con mayor frecuencia el siguiente criterio de parada:

Complejidad computacional

En cada iteración del método, se realizan operaciones. Esta cantidad de operaciones es necesaria para calcular el producto; este es el procedimiento que requiere más tiempo en cada iteración. Otros cálculos requieren operaciones O(n). La complejidad computacional total del método no excede, ya que el número de iteraciones no supera n.

Ejemplo numérico

Apliquemos el método del gradiente conjugado para resolver un sistema donde, utilizando el método del gradiente conjugado, la solución de este sistema se obtiene en dos iteraciones. Los valores propios de la matriz son 5, 5, -5; entre ellos hay dos diferentes, por lo tanto, según la estimación teórica, el número de iteraciones no podría exceder dos

El método del gradiente conjugado es uno de los métodos más eficaces para resolver SLAE con una matriz definida positiva. El método garantiza la convergencia en un número finito de pasos y la precisión requerida se puede lograr mucho antes. El principal problema es que debido a la acumulación de errores se puede violar la ortogonalidad de los vectores base, lo que perjudica la convergencia.

El método del gradiente conjugado en general.

Consideremos ahora una modificación del método del gradiente conjugado para el caso en que el funcional minimizado no sea cuadrático: Resolveremos el problema:

Función continuamente diferenciable. Para modificar el método del gradiente conjugado para resolver este problema, es necesario obtener para fórmulas que no incluyen la matriz A:

se puede calcular usando una de tres fórmulas:

1.- Método Fletcher-Reeves

• 2.- Método Polak-Ribi`ere

Si la función es cuadrática y estrictamente convexa, entonces las tres fórmulas dan el mismo resultado. Si es una función arbitraria, entonces cada una de las fórmulas corresponde a su propia modificación del método del gradiente conjugado. La tercera fórmula rara vez se utiliza porque requiere la función y el cálculo del hessiano de la función en cada paso del método.

Si la función no es cuadrática, es posible que el método del gradiente conjugado no converja en un número finito de pasos. Además, un cálculo preciso en cada paso sólo es posible en casos excepcionales. Por tanto, la acumulación de errores lleva a que los vectores ya no indiquen la dirección de disminución de la función. Luego, en algún momento, creen. El conjunto de todos los números en los que se acepta se indicará con. Los números se denominan momentos de actualización del método. En la práctica, a menudo se elige dónde está la dimensión del espacio.

Convergencia del método

Para el método de Fletcher-Reeves, existe un teorema de convergencia que impone condiciones no demasiado estrictas a la función que se minimiza: Teorema. Que se cumplan las siguientes condiciones:

La variedad es limitada

La derivada satisface la condición de Lipschitz con una constante en alguna vecindad

establece M: .

Para el método Polak-Reiber, la convergencia se prueba bajo el supuesto de que es una función estrictamente convexa. En el caso general, es imposible demostrar la convergencia del método Polak-Reiber. Por el contrario, es verdadero el siguiente teorema: Teorema. Supongamos que en el método Polak-Reiber los valores en cada paso se calculan exactamente. Luego hay una función y una suposición inicial tal que.

Sin embargo, en la práctica el método Polak-Reiber funciona mejor. Los criterios de parada más comunes en la práctica: La norma de gradiente se vuelve inferior a un cierto umbral. El valor de la función se ha mantenido casi sin cambios durante m iteraciones consecutivas.

Complejidad computacional

En cada iteración de los métodos de Polak-Reiber o Fletcher-Reeves, la función y su gradiente se calculan una vez y se resuelve el problema de optimización unidimensional. Por tanto, la complejidad de un paso del método del gradiente conjugado es del mismo orden de magnitud que la complejidad de un paso del método de descenso más pronunciado. En la práctica, el método del gradiente conjugado muestra la mejor velocidad de convergencia.

Buscaremos el mínimo de la función utilizando el método del gradiente conjugado.

El mínimo de esta función es 1 y se alcanza en el punto (5, 4). Usando esta función como ejemplo, comparemos los métodos de Polak-Reiber y Fletcher-Reeves. Las iteraciones en ambos métodos se detienen cuando la norma al cuadrado del gradiente se vuelve más pequeña en el paso actual. Para la selección se utiliza el método de la proporción áurea.

Se han implementado dos versiones del método del gradiente conjugado: para minimizar una función cuadrática y para minimizar una función arbitraria. En el primer caso, el método se implementa mediante la función vectorial. EncontrarSolución(matriz Un vector b) Aquí A y b son la matriz y el vector involucrados en la definición del problema de optimización cuadrática. Para minimizar la funcionalidad arbitraria, puede utilizar una de dos funciones: vector FletcherRievesMétodo(int spaceSize, Función F, vector (*GradF) (vector )) vector PolakRibiereMethod(int spaceSize, Función F, vector (*GradF) (vector )) Los parámetros para ambas funciones son los mismos y tienen el siguiente significado: spaceSize - la dimensión del espacio (el número de variables de las que depende la función minimizada) F - un puntero a la función a minimizar. La función debe ser de la forma doble.<имя функции>(vector ) GradF: puntero a una función que calcula el gradiente del funcional minimizado. Ambos métodos utilizan una función auxiliar para resolver un problema de optimización unidimensional. El programa implementa una optimización unidimensional utilizando el método de la sección áurea.

Los métodos de descenso de gradiente son herramientas bastante poderosas para resolver problemas de optimización. La principal desventaja de los métodos es el rango limitado de aplicabilidad. El método de gradiente conjugado utiliza información solo sobre la parte lineal del incremento en un punto, como en los métodos de descenso de gradiente. Además, el método del gradiente conjugado permite resolver problemas cuadráticos en un número finito de pasos. En muchos otros problemas, el método del gradiente conjugado también supera al método de descenso del gradiente. La convergencia del método del gradiente depende significativamente de la precisión con la que se resuelva el problema de optimización unidimensional. Los posibles bucles de métodos se resuelven mediante actualizaciones. Sin embargo, si un método llega al mínimo local de una función, lo más probable es que no pueda escapar de él.

El método de descenso más pronunciado es un método de gradiente con un paso variable. En cada iteración, el tamaño del paso k se selecciona a partir de la condición del mínimo de la función f(x) en la dirección de descenso, es decir

Esta condición significa que el movimiento a lo largo del antigradiente ocurre siempre que el valor de la función f (x) disminuya. Desde un punto de vista matemático, en cada iteración es necesario resolver el problema de minimización unidimensional por función.

()=f (x (k) -f (x (k)))

Usemos el método de la proporción áurea para esto.

El algoritmo del método de descenso más pronunciado es el siguiente.

Se especifican las coordenadas del punto inicial x (0).

En el punto x (k), k = 0, 1, 2, ..., se calcula el valor del gradiente f (x (k)).

El tamaño del paso k se determina mediante minimización unidimensional utilizando la función

()=f(x(k)-f(x(k))).

Las coordenadas del punto x (k) se determinan:

x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.

Se verifica la condición para detener el proceso iterativo:

||f(x(k+1))|| .

Si se cumple, entonces los cálculos se detienen. De lo contrario, procedemos al paso 1. La interpretación geométrica del método de descenso más pronunciado se presenta en la Fig. 1.

Arroz. 2.1. Diagrama de bloques del método de descenso más pronunciado.

Implementación del método en el programa:

Método de descenso más pronunciado.

Arroz. 2.2. Implementación del método de descenso más pronunciado.

Conclusión: En nuestro caso, el método convergió en 7 iteraciones. El punto A7 (0,6641; -1,3313) es un punto extremo. Método de direcciones conjugadas. Para funciones cuadráticas, puede crear un método de gradiente en el que el tiempo de convergencia será finito e igual al número de variables n.

Llamemos H a una determinada dirección y conjuguemos con respecto a alguna matriz de Hess definida positiva si:

Entonces, es decir, para la unidad H, la dirección conjugada significa su perpendicular. En el caso general, H no es trivial. En el caso general, la conjugación es la aplicación de la matriz de Hess a un vector; significa rotar este vector en algún ángulo, estirarlo o comprimirlo.

Y ahora el vector es ortogonal, es decir, la conjugación no es la ortogonalidad del vector, sino la ortogonalidad del vector rotado.e.i.

Arroz. 2.3. Diagrama de bloques del método de direcciones conjugadas.

Implementación del método en el programa: Método de direcciones conjugadas.

Arroz. 2.4. Implementación del método de direcciones conjugadas.

Arroz. 2.5. Gráfica del método de direcciones conjugadas.

Conclusión: El punto A3 (0,6666; -1,3333) se encontró en 3 iteraciones y es un punto extremo.

3. Análisis de métodos para determinar el valor mínimo y máximo de una función en presencia de restricciones.

Recuerde que un problema general de optimización restringida se ve así:

f(x) ® min, x О W,

donde W es un subconjunto propio de R m. Una subclase de problemas con restricciones de tipo igualdad se distingue por el hecho de que el conjunto  está definido por restricciones de la forma

f i (x) = 0, donde f i: R m ®R (i = 1, …, k).

Así,W = (x О R m: f i (x) = 0, i = 1, …, k).

Nos resultará conveniente escribir el índice "0" para la función f. Por lo tanto, el problema de optimización con restricciones de tipo igualdad se escribe como

f 0 (x) ® mín, (3.1)

f yo (x) = 0, yo = 1,…, k. (3.2)

Si ahora denotamos por f una función en R m con valores en R k, cuya notación de coordenadas tiene la forma f(x) = (f 1 (x), ..., f k (x)), entonces ( 3.1)–(3.2) también podemos escribirlo en la forma

f 0 (x) ® mín, f(x) = Q.

Geométricamente, un problema con restricciones de tipo igualdad es un problema de encontrar el punto más bajo de la gráfica de una función f 0 sobre la variedad  (ver Fig. 3.1).

Los puntos que satisfacen todas las restricciones (es decir, los puntos del conjunto ) suelen denominarse admisibles. Un punto admisible x* se llama mínimo condicional de la función f 0 bajo las restricciones f i (x) = 0, i = 1, ..., k (o una solución al problema (3.1)–(3.2)), si para todos los puntos admisibles x f 0 (x *)  f 0 (x). (3.3)

Si (3.3) se satisface sólo para x admisible que se encuentra en alguna vecindad V x * del punto x*, entonces hablamos de un mínimo condicional local. Los conceptos de mínimos condicionales estrictos locales y globales se definen de forma natural.

Anotación: Esta conferencia cubre ampliamente métodos de optimización multiparamétrica como el método de descenso más pronunciado y el método Davidon-Fletcher-Powell. Además, se realiza un análisis comparativo de los métodos anteriores con el fin de determinar cuál es el más efectivo, se identifican sus ventajas y desventajas; y también considera problemas de optimización multidimensionales, como el método del barranco y el método multiextremal.

1. Método de descenso más pronunciado.

La esencia de este método es que utilizando lo mencionado anteriormente método de descenso coordinado se realiza una búsqueda desde un punto determinado en una dirección paralela a uno de los ejes hasta el punto mínimo en esta dirección. Luego la búsqueda se realiza en dirección paralela al otro eje, y así sucesivamente. Las direcciones, por supuesto, son fijas. Parece razonable intentar modificar este método para que en cada etapa la búsqueda del punto mínimo se realice en la "mejor" dirección. No está claro qué dirección es la "mejor", pero se sabe que dirección del gradiente es la dirección del aumento más rápido de la función. Por lo tanto, la dirección opuesta es la dirección de disminución más rápida de la función. Esta propiedad se puede justificar de la siguiente manera.

Supongamos que nos estamos moviendo del punto x al siguiente punto x + hd, donde d es una dirección determinada y h es un paso de cierta longitud. En consecuencia, el movimiento se realiza desde el punto (x 1, x 2, ..., x n) hasta el punto (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Dónde

El cambio en los valores de las funciones está determinado por las relaciones.

Hasta zxi de primer orden, calculándose las derivadas parciales en el punto x. ¿Cómo se deben elegir las direcciones d i que satisfagan la ecuación (1.2) para obtener el mayor valor del cambio en la función df? Aquí es donde surge un problema de maximización con una restricción. Apliquemos el método de los multiplicadores de Lagrange, con la ayuda del cual determinamos la función.

El valor df que satisface la restricción (1.2) alcanza su máximo cuando la función

Alcanza el máximo. su derivado

Por eso,

(1.6)

Entonces di ~ df/dx i y la dirección d es paralela a la dirección V/(x) en el punto x.

De este modo, mayor aumento local La función para un pequeño paso h dado ocurre cuando d es la dirección de Vf(x) o g(x). Por lo tanto, la dirección del descenso más pronunciado es la dirección

De forma más sencilla, la ecuación (1.3) se puede escribir de la siguiente manera:

¿Dónde está el ángulo entre los vectores Vf(x) y dx? Para un valor dado de dx, minimizamos df eligiendo que la dirección de dx coincida con la dirección de -Vf(x).

Comentario. Dirección del gradiente perpendicular a cualquier punto sobre una línea de nivel constante, ya que a lo largo de esta línea la función es constante. Por lo tanto, si (d 1, d 2, ..., d n) es un pequeño paso a lo largo de la línea de nivel, entonces

Y por lo tanto

(1.8)

Cuando se utiliza el método de descenso más pronunciado en cada iteración, el tamaño del paso A k se selecciona de la condición mínima de la función f(x) en la dirección de descenso, es decir

f(x)[k] -a k f"(x[k])) = f(x)[k] -af"(x[k])) .

Esta condición significa que el movimiento a lo largo del antigradiente ocurre siempre que el valor de la función f(x) disminuye. Desde un punto de vista matemático, en cada iteración es necesario resolver el problema de minimización unidimensional según A funciones

j (a) = f(x)[k]-af"(x[k])) .

El algoritmo del método de descenso más pronunciado es el siguiente.

• 1. Establecer las coordenadas del punto de partida. X.
• 2. En el punto X[k], k = 0, 1, 2, ... calcula el valor del gradiente f"(x[k]) .
• 3. Se determina el tamaño del paso. a k, por minimización unidimensional sobre A funciones j (a) = f(x)[k]-af"(x[k])).
• 4. Se determinan las coordenadas del punto. X[k+ 1]:

X i [k+ 1]=x i [k] -A k F" i (X[k]), i = 1,..., pág.

5. Se verifican las condiciones para detener el proceso de esteración. Si se cumplen, los cálculos se detienen. De lo contrario, vaya al paso 1.

En el método considerado, la dirección del movimiento desde el punto X[k] toca la línea de nivel en el punto X[k+ 1] (Figura 2.9). La trayectoria de descenso es en zigzag, con enlaces en zigzag adyacentes ortogonales entre sí. De hecho, un paso a k se elige minimizando por A funciones? (a) = f(x)[k] -af"(x[k])) . Condición necesaria para el mínimo de una función. d j (a)/da = 0. Habiendo calculado la derivada de una función compleja, obtenemos la condición para la ortogonalidad de los vectores de direcciones de descenso en puntos vecinos:

d j (a)/da = -f"(x[k+ 1]f"(x[k]) = 0.

Arroz. 2.9.

Los métodos de gradiente convergen a un mínimo a una tasa alta (tasa de progresión geométrica) para funciones convexas suaves. Tales funciones tienen la mayor METRO y menos metro valores propios de la matriz de segundas derivadas (matriz de Hesse)

difieren poco entre sí, es decir, la matriz norte(x) bien acondicionado. Recuerde que los valores propios l i, i =1, …, norte, las matrices son las raíces de la ecuación característica

Sin embargo, en la práctica, por regla general, las funciones que se minimizan tienen matrices de segundas derivadas mal condicionadas. (t/m<< 1). Los valores de tales funciones en algunas direcciones cambian mucho más rápido (a veces en varios órdenes de magnitud) que en otras direcciones. Sus superficies niveladas en el caso más simple están muy alargadas (Fig. 2.10), y en casos más complejos se doblan y parecen barrancos. Las funciones con tales propiedades se llaman quebrada. La dirección del antigradiente de estas funciones (ver Fig. 2.10) se desvía significativamente de la dirección al punto mínimo, lo que conduce a una desaceleración en la velocidad de convergencia.

Arroz. 2.10.

La tasa de convergencia de los métodos de gradiente también depende significativamente de la precisión de los cálculos de gradiente. La pérdida de precisión, que suele ocurrir en las proximidades de puntos mínimos o en una situación de barrancos, generalmente puede alterar la convergencia del proceso de descenso del gradiente. Por las razones anteriores, los métodos de gradiente se utilizan a menudo en combinación con otros métodos más eficaces en la etapa inicial de resolución de un problema. En este caso, el punto X está lejos del punto mínimo, y los pasos en la dirección del antigradiente permiten lograr una disminución significativa de la función.