El gradiente de la función diferenciable f(x) en el punto X llamado norte-vector dimensional f(x)) , cuyos componentes son derivadas parciales de la función f(x), calculado en el punto X, es decir.

f"(x ) = (gl(x)/dh 1 , …, df(x)/dx n) T .

Este vector es perpendicular al plano que pasa por el punto X, y tangente a la superficie nivelada de la función. f(x), pasando por un punto X.En cada punto de dicha superficie la función f(x) toma el mismo valor. Igualando la función a varios valores constantes C 0 , C 1 , ..., obtenemos una serie de superficies que caracterizan su topología (Fig. 2.8).

El vector gradiente se dirige hacia el aumento más rápido de la función en un punto determinado. Vector opuesto al gradiente (-f’(x)) , llamado anti-gradiente y está dirigido a la disminución más rápida de la función. En el punto mínimo, el gradiente de la función es cero. Los métodos de primer orden, también llamados métodos de gradiente y de minimización, se basan en las propiedades de los gradientes. El uso de estos métodos en el caso general le permite determinar el punto mínimo local de una función.

Obviamente, si no hay información adicional, entonces desde el punto de partida X es sabio ir al grano X, que se encuentra en la dirección del antigradiente: la disminución más rápida de la función. Elegir como dirección de descenso. R[k] anti-gradiente - f'(x[k] ) en el punto X[k], obtenemos un proceso iterativo de la forma

X[ k+ 1] = X[k]-akf"(x[k] ) , y k > 0; k=0, 1, 2, ...

En forma de coordenadas, este proceso se escribe de la siguiente manera:

x yo [ k+1]=xyo[k] - akf(x)[k] ) /x yo

yo = 1, ..., norte; k= 0, 1, 2,...

Como criterio para detener el proceso iterativo, ya sea el cumplimiento de la condición de pequeño incremento del argumento || X[k+l] - X[k] || <= e , либо выполнение условия малости градиента

|| f'(x[k+l] ) || <= g ,

Aquí e y g reciben pequeñas cantidades.

También es posible un criterio combinado, consistente en el cumplimiento simultáneo de las condiciones especificadas. Los métodos de gradiente se diferencian entre sí en la forma en que eligen el tamaño del paso. y k.

En el método con paso constante, se selecciona un determinado valor de paso constante para todas las iteraciones. Un paso bastante pequeño y k asegurará que la función disminuya, es decir, la desigualdad

f(x[ k+1]) = f(x)[k] – akf’(x[k] )) < f(x)[k] ) .

Sin embargo, esto puede llevar a la necesidad de realizar un número inaceptablemente grande de iteraciones para alcanzar el punto mínimo. Por otro lado, un paso demasiado grande puede provocar un aumento inesperado de la función o provocar oscilaciones alrededor del punto mínimo (cíclico). Debido a la dificultad de obtener la información necesaria para seleccionar el tamaño del paso, en la práctica rara vez se utilizan métodos con pasos constantes.

Los gradientes son más económicos en términos de número de iteraciones y confiabilidad. métodos de paso variable, cuando, dependiendo de los resultados de los cálculos, el tamaño del paso cambia de alguna manera. Consideremos las variantes de tales métodos utilizados en la práctica.

Cuando se utiliza el método de descenso más pronunciado en cada iteración, el tamaño del paso y 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 yo [ k+ 1]= xi[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:

DJ (a)/da = -f’(x[k+ 1]f'(x[k]) = 0.

Los métodos de gradiente convergen a un mínimo a alta velocidad (velocidad 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.

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.

Los métodos de gradiente discutidos anteriormente encuentran el punto mínimo de una función en el caso general solo en un número infinito de iteraciones. El método del gradiente conjugado genera direcciones de búsqueda que son más consistentes con la geometría de la función que se minimiza. Esto aumenta significativamente la velocidad de su convergencia y permite, por ejemplo, minimizar la función cuadrática.

f(x) = (x, Hx) + (b, x) + a

con una matriz definida positiva simétrica norte en un número finito de pasos PAG, igual al número de variables de función. Cualquier función suave en las proximidades del punto mínimo puede aproximarse bien mediante una función cuadrática; por lo tanto, los métodos de gradiente conjugado se utilizan con éxito para minimizar funciones no cuadráticas. En este caso dejan de ser finitos y se vuelven iterativos.

Por definición, dos norte-vector dimensional X Y en llamado conjugado relativo a la matriz h(o h-conjugado), si el producto escalar (X, Bueno) = 0. Aquí norte - matriz definida positiva simétrica de tamaño PAG X PAG.

Uno de los problemas más importantes en los métodos de gradiente conjugado es el problema de construir direcciones de manera eficiente. El método Fletcher-Reeves resuelve este problema transformando el antigradiente en cada paso. -f(x[k]) en la dirección pag[k], h-conjugar con direcciones encontradas previamente R, R, ..., R[k-1].

Consideremos primero este método en relación con el problema de minimizar una función cuadrática. R[k Direcciones

] se calcula utilizando las fórmulas: k] = -f'(x[k]) pag[ pag[k+bk-1 k>= 1;

-l], pag = -’(X) .

F k valores b pag[k], R[k-1 se eligen para que las direcciones h-1] eran :

(pag[k], -conjugado[caballos de fuerza 1])= 0.

k-

,

Como resultado, para la función cuadrática

el proceso de minimización iterativo tiene la forma k+l] X[[k]=x[k],

+a k p R[k] - Dónde caballos de fuerza dirección de descenso a m paso; y k- Numero de pie. Este último se selecciona de la condición mínima de la función. A f(x)

f(x[ k] + Por[k]) = f(x)[k] + en la dirección del movimiento, es decir, como resultado de resolver el problema de minimización unidimensional: [k]) .

a k r

Arkansas

Para una función cuadrática X El algoritmo del método del gradiente conjugado de Fletcher-Reeves es el siguiente. pag = -f'(x) .

1. En el punto caballos de fuerza calculado A 2. encendido . m paso, usando las fórmulas anteriores, el paso se determina X[k+ 1].

k f(x)[k+1]) y punto f'(x[k+1]) .

3. Se calculan los valores. f'(x) Y X[k 4. Si = 0, entonces punto+1] es el punto mínimo de la función pag[k f(x).

De lo contrario, se determina una nueva dirección. PAG+l] de la relación y se lleva a cabo la transición a la siguiente iteración. Este procedimiento encontrará el mínimo de una función cuadrática en no más de pasos. X Al minimizar funciones no cuadráticas, el método de Fletcher-Reeves pasa de ser finito a iterativo. En este caso, después X[PAG(p+

el proceso de minimización iterativo tiene la forma k+l] La 1)ª iteración del procedimiento 1-4 se repite cíclicamente con reemplazo[k]=x[k],

] se calcula utilizando las fórmulas: k] en[k])+ +1] y los cálculos terminan en , donde es un número determinado. En este caso, se utiliza la siguiente modificación del método: caballos de fuerza 1 pag[k+bk-1 k>= 1;

=x X);

f(x[ k] + = -f’(x[k]) = f(x)[k] b[k];

.

p = -f'( a k p+ap a k p Aquí I- muchos índices: PAG= (0, norte, 2

p, salario, ...) X, es decir, el método se actualiza cada R = pasos. El significado geométrico del método del gradiente conjugado es el siguiente (figura 2.11). Desde un punto de partida determinado X El descenso se realiza en dirección. -f"(x). En el punto X se determina el vector gradiente R, f"(x f'(x) ). Porque el R es el punto mínimo de la función en la dirección R , h Eso R ortogonal al vector R. Entonces se encuentra el vector

etc. PAG= (0, norte, 2

Arroz. 2.11 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 un 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)

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 que la elección óptima de parámetros es: , 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 por 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 incondicional 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.

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]La 1)ª iteración del procedimiento 1-4 se repite cíclicamente con reemplazo 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.

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 hacia el 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. Tras el reinicio se vuelve a buscar en la dirección del descenso más pronunciado.