Método de Powell para funciones unidimensionales. Método de direcciones conjugadas de Powell

La alta tasa de convergencia del método de Newton se debe a que minimiza la función cuadrática

Donde A es una matriz de tamaño definida positiva simétrica nxn , en un solo paso. Los métodos cuasi-Newton le permiten encontrar el mínimo de una función cuadrática en pasos. La idea del método de dirección conjugada se basa en el deseo de minimizar una función cuadrática en un número finito de pasos. Más precisamente, en los métodos de dirección conjugada se requiere encontrar direcciones tales que una secuencia de minimizaciones unidimensionales a lo largo de estas direcciones conduzca a encontrar el mínimo de la función 2.1, es decir, para cualquiera, donde

Resulta que la propiedad indicada la posee un sistema de direcciones mutuamente conjugadas con respecto a la matriz A

Sea A una matriz definida positiva simétrica de tamaño .

Definición 2.1. Los vectores (direcciones) se llaman conjugados (con respecto a la matriz A) si son distintos de cero y. Los vectores (direcciones) se llaman mutuamente conjugados (con respecto a la matriz A) si todos son diferentes de cero y. (2.3)

Lema 3.1. Sean los vectores mutuamente conjugados. Entonces son linealmente independientes.

Prueba. Que esto sea falso, claro está, para algunos. Entonces , lo cual solo es posible cuando, dado que la matriz A es definida positiva. La contradicción resultante prueba el lema.

Considere el problema de minimización en R n funciones 2.1. Lo resolveremos usando el método 2.2. Si los vectores son mutuamente conjugados, entonces el método 3.2 puede denominarse método de direcciones conjugadas. Sin embargo, este nombre se suele utilizar sólo para aquellos métodos en los que es el deseo de alcanzar la condición de conjugación mutua lo que determina la elección de las direcciones. La implementación de una idea completamente nueva también puede conducir al cumplimiento de la misma condición.

Teorema 3.1. Si los vectores h k en el método 2.2 son mutuamente conjugados, k=0,1,…, metro-1 , entonces para la función F, dado por la fórmula 2.1,

, (2.4)

Dónde - subespacio lineal, abarcado por los vectores indicados.

Prueba. Teniendo en cuenta 2.2 y la Definición 2.1 tenemos

(2.5)

Usando esta igualdad, obtenemos

(2.6)

Consecuencia. Si los vectores h k en el método 2.2 son mutuamente conjugados, k=0,1,…, norte-1 , entonces para la función F, dado por la fórmula 2.1, y un punto arbitrario

Así, el método 2.2 nos permite encontrar el punto mínimo. función cuadrática 2.1 en no más de n pasos.

2.2. Método de direcciones conjugadas de orden cero.

El algoritmo consta de una secuencia de bucles, k- del cual está determinado por el punto de partida t 0 (k) y direcciones de minimización pag 0 (k), pag 1 (k), …, pag norte -1 (k) . En el ciclo cero como t 0 (0), Se selecciona un punto arbitrario como pag 0 (0), pag 1 (k), …, pag norte -1 (k) – direcciones de los ejes de coordenadas.

Próximo k-El ciclo consiste en resolver secuencialmente problemas unidimensionales.

Esto determina el paso de un punto a otro.

donde estan los que

Despues de terminar k-ésimo punto de inicio del ciclo y direcciones de minimización (k+1) -El ciclo está determinado por las fórmulas.

El criterio de parada puede ser el cumplimiento de la desigualdad , donde hay un pequeño número positivo preseleccionado.

Teorema 3.2. Si los vectores en el método 2.5-2.7 son distintos de cero, entonces para la función F, dado por la fórmula 2.1

Prueba. Teniendo en cuenta el corolario del teorema 3.1, basta demostrar que los vectores son mutuamente conjugados. Permitir. Suponiendo que los vectores son mutuamente conjugados, demostramos que un vector es conjugado con vectores.

Tenga en cuenta que y, por lo tanto, el punto t norte (k) , según las fórmulas 2.5, se obtiene del punto t norte - k (k) utilizando una secuencia de minimizaciones unidimensionales a lo largo de las direcciones. Esto, en virtud del teorema 2.1, significa que

Para concluir el estudio de métodos aproximados para buscar el extremo de la FMF sin restricciones, consideremos el método de direcciones conjugadas, que está ganando cada vez más popularidad en la práctica.

Primero damos el concepto de conjugación. Tengamos dos direcciones, que se caracterizan por vectores y . Direcciones Y se llaman conjugados con respecto a alguna matriz definida positiva H si la relación

, (7)

CON la tensión está asociada con la ortogonalidad. Si H es la matriz identidad, entonces cuando
tenemos dos vectores mutuamente perpendiculares. La relación (7) se puede interpretar de la siguiente manera: matriz H aplicada al vector , cambia su longitud y lo gira en un cierto ángulo para que el nuevo vector
debe ser ortogonal al vector .

Usando el método de direcciones conjugadas, encontraremos el extremo de una función separable con un punto inicial.
.

1) Se hace una selección y en esta dirección se busca un extremo.

Tomemos un vector con direcciones Y . Vector se puede elegir arbitrariamente, así que tomemos ==1. Vector da la dirección L 1.

Dibujemos un plano que pase por L 1 perpendicular al plano (x 1, x 2). El plano interceptará la superficie extrema y(x 1, x 2) y resaltará una línea extrema en ella. Determinemos las coordenadas del mínimo en esta recta (parábola), para lo cual calculamos las proyecciones del gradiente en el punto x 0:

,

y usando la fórmula (6) encontramos :

Naturalmente, la recta L 1 toca en el punto x (1) la recta de igual nivel de la función y.

2) buscadode la condición de conjugación
.

Obtenemos el vector conjugado con proyecciones
Y
, usando la fórmula (7):

PAG
Obtuvimos una ecuación con dos incógnitas. Porque solo necesitamos la dirección del vector , y no su longitud, entonces una de las incógnitas puede especificarse arbitrariamente. Dejar
=1, entonces
= –4.

3) Desde el punto x (1) en la direcciónSe busca un extremo.

El vector conjugado debe pasar por x(1). Demos un paso en la dirección conjugada:

Tamaño del paso  (1) en x (1):

,

Entonces, en dos iteraciones se encontró valor exacto extremo de la función y. Como primer vector fue posible seleccionar un gradiente en el punto de partida, el procedimiento de búsqueda sigue siendo el mismo.

En matemáticas, está demostrado que el método de la dirección conjugada converge para funciones cuadráticas en no más de n iteraciones, donde n es el número de variables. Esta circunstancia es especialmente valiosa para la práctica, por lo que este método se utiliza cada vez más.

Para funciones de forma más general, el método de direcciones conjugadas aún se está desarrollando. La principal dificultad aquí es que la matriz de Hesse resulta funcional, es decir contiene una variable.

Problema extremo condicional de Lagrange clásico (restricciones de igualdad).

PAG
Sea la función objetivo dada
y restricción de igualdad (ecuación de conexión)
. Necesitamos encontrar el mínimo.
en un set
. Creemos que las funciones
Y
tienen primeras derivadas continuas y son convexas o cóncavas.

Consideremos la interpretación geométrica del problema clásico. En el plano (x 1 ,x 2 ) construimos una función
, así como líneas de igual nivel de función
con valores N 1 , la línea N 3 tiene 2 puntos comunes con
y no pueden ser una solución al problema, ya que N 3 >N 2 . Lo que queda es la línea de nivel N 2, que tiene un único punto de tangencia con
. El mínimo absolutoN 0 puede no pertenecer a la restricción
y por lo tanto no puede ser una solución al problema. De ahí que el nombre “extremo condicional” sea claro, es decir un extremo que sólo se alcanza bajo determinadas restricciones.

En el punto de contacto
con función
Dibujemos una recta tangente L. Afinamos los gradientes de funciones.
Y
en el punto de contacto, estarán en la misma línea, porque ambos son perpendiculares a L y dirigidos en diferentes direcciones. Determinemos las proyecciones de los gradientes en los ejes x1 y x2 en el punto de tangencia:

De la semejanza de triángulos podemos escribir:

– Multiplicador de Lagrange.

o

Ahora compongamos la función.
de la siguiente manera:

– Función de Lagrange.

Escribamos las relaciones para encontrar el extremo de la función F.

Como puede ver, obtuvimos las mismas relaciones que se obtuvieron con base en la interpretación geométrica del problema. La constante  se llama multiplicador de Lagrange. Usando este multiplicador, el problema es extremo condicional se reduce al problema de un extremo incondicional.

En el caso general, tomamos el número de variables como n y el número de restricciones como m. Entonces la función de Lagrange se escribirá como:

o en forma vectorial

Para resolver el problema se escribe un sistema de ecuaciones:

, (8)

aquellos. para n+m variables tendremos n+m ecuaciones. Si el sistema es consistente, entonces el problema de Lagrange tiene una solución única.

Porque Para determinar el extremo solo se utilizaron las primeras derivadas, luego solo serán necesarias las condiciones resultantes. Si las funciones
Y
convexo o cóncavo, entonces solo hay un extremo condicional. Si una de las funciones no es convexa, entonces el extremo puede no ser el único. Además, queda la cuestión de si lo encontrado es un mínimo o un máximo, aunque en la práctica de la ingeniería esto suele quedar claro a partir de consideraciones físicas.

Ejemplo: Mostraremos la técnica para resolver el problema utilizando el método de Lagrange.

D
Para el ejemplo anterior con dos bombas, se especifica el volumen de líquido bombeado:

Con esta limitación, es necesario encontrar el consumo de energía de las bombas.
. Sean los coeficientes  1 = 2 =1, K 1 =1, K 2 =1,5. Entonces la función objetivo es encontrar el mínimo bajo la restricción:.

Procedimiento de solución:

Compilando la función de Lagrange

Se compila un sistema de ecuaciones (8):

Q i se escriben hasta  y se sustituyen en la tercera expresión:

,
,
,

Entonces las coordenadas del extremo son:

,

Ejemplo 2:

Dejemos que se dé una conexión en serie de compresores.
Se establece la relación de compresión requerida: que debe garantizarse con un consumo mínimo de energía:

2.

3.
,
, sustituye en la expresión por :

,
,
. Por razones físicas, descartamos la raíz positiva, por lo tanto  = –0,98.

Entonces las coordenadas del extremo son:

,

Como puede verse en los ejemplos dados, al resolver el problema de Lagrange, generalmente obtenemos un sistema de ecuaciones no lineales, que a veces es difícil de resolver analíticamente. Por tanto, es recomendable utilizar métodos aproximados para resolver el problema de Lagrange.

Descripción del algoritmo

El método está enfocado a la resolución de problemas con funciones objetivo cuadráticas. La idea principal del algoritmo es que si una función cuadrática:

la suma de cuadrados perfectos se reduce a la forma

luego, el procedimiento para encontrar la solución óptima se reduce a una búsqueda unidimensional a lo largo de las direcciones de coordenadas transformadas.

En el método de Powell, la búsqueda se implementa como:

a lo largo de direcciones llamadas -conjugadas cuando estas direcciones son linealmente independientes.

Las direcciones conjugadas se determinan algorítmicamente. Para encontrar el extremo de una función cuadrática de variables, es necesario realizar búsquedas unidimensionales.

Paso 1. Establezca los puntos de partida y la dirección. En particular, la dirección puede coincidir con la dirección del eje de coordenadas;

Paso 2. Realice una búsqueda unidimensional desde un punto en la dirección para obtener un punto que sea un punto extremo en una dirección determinada;

Paso 3. Realice una búsqueda unidimensional desde el punto en la dirección para obtener el punto;

Paso 4. Calcular la dirección;

Paso 5. Realice una búsqueda unidimensional desde el punto (o) en la dirección que conduce al punto.

Encontrar el mínimo de la función objetivo utilizando el método de direcciones conjugadas de Powell.

Función objetiva:

Punto de partida:

El valor de la función objetivo en este punto:

Paso 1. Establezca los puntos iniciales S(1) y S(2):

S(1) = S(2) =

Paso 2. Encuentre el valor en [X(0)+2S(2)]. Un punto arbitrario en el rayo desde el punto X(0) en la dirección S(2) se define como

X = X(0) + S(2) = [-9;-10] +

desde donde X 1 = -9 X 2 = - 10

Desde aquí encontramos:

X(1) = [-9;-10] + 15,5 = [-9;5,5]

De manera similar, encontramos el valor de [X(1)+S(1)].

X = X(1) + S(1) = [-9;5,5] +

de donde X1 = -9 X2 =5.5

Sustituyendo estos valores en la función objetivo, obtenemos

Diferenciamos esta expresión por y la igualamos a cero:

Desde aquí encontramos:

X(2) = [-9;5,5] + 10,5 =

También encontraremos el valor en [X(2)+2S(2)].

X = X(2) + S(2) = +

de donde X 1 = 3 X 2 = 5,5+

Sustituyendo estos valores en la función objetivo, obtenemos

Diferenciamos esta expresión por y la igualamos a cero:

Desde aquí encontramos:

X(3) = -6 =

Paso 3. Poner

S(3) = X(3) - X(1) =

La dirección S(3) resulta ser conjugada con la dirección S(2). Dado que N = 2, la optimización a lo largo de la dirección S(3) da el resultado deseado. Paso 4. Encuentra el valor cuando

X = X(3) + = +

X 1 = 3+ 12 X 2 = -0,5 -6

X(4) = +0,0278* =

Así, obtuvimos un punto x = T, el valor de la función en el que f(x) = -3,778 coincide con el punto estacionario.

Conclusión: El método de dirección conjugada de Powell es muy preciso con pocas iteraciones en comparación con los métodos anteriores.

Explicación gráfica del método de dirección conjugada de Powell:

Los métodos de búsqueda directa son convenientes para funciones objetivas simples o cuando es necesario encontrar el óptimo con un bajo grado de precisión. Pero requieren mucho tiempo y recursos computacionales, debido a la gran cantidad de iteraciones realizadas: el método de búsqueda simplex - 15 iteraciones, el método de Hook-Jeeves - 5 iteraciones, el método de direcciones conjugadas de Powell - 4 iteraciones.

El método está enfocado a la resolución de problemas con funciones objetivo cuadráticas y se basa en resultados teóricos fundamentales. Aunque los algoritmos del mundo real que son eficientes para funciones objetivo cuadráticas pueden funcionar mal para funciones objetivo más complejas, este enfoque todavía parece razonable.

Definición. Sea una matriz simétrica de orden.
. Vectores
son llamados
- conjugado, si son linealmente independientes y se cumple la condición
en
.

Ejemplo. Considere la función

como una matriz
puedes tomar la matriz de Hesse

.

Como una de las direcciones elegiremos.
. Entonces la dirección
debe satisfacer la igualdad

.

Cabe señalar que las direcciones conjugadas se eligen de forma ambigua. Sin embargo, si agregamos una condición de normalización, entonces se pueden determinar sin ambigüedades:

Declaración. Cualquier función cuadrática Las variables que tienen un mínimo se pueden minimizar en pasos, siempre que la búsqueda se realice en direcciones conjugadas con respecto a la matriz de Hesse.

Una función arbitraria puede representarse bastante bien en la vecindad del punto óptimo mediante su aproximación cuadrática. Por tanto, las direcciones conjugadas pueden resultar útiles para su optimización. Sin embargo, más de pasos. Para determinar las direcciones conjugadas, se utiliza un método basado en la siguiente afirmación.

Declaración. Sea una función cuadrática dada
, dos puntos arbitrarios
y direcciónS..Si punto es el punto mínimo de la función
a lo largo de la direcciónSdesde el punto , A - el punto mínimo de la función a lo largo de la direcciónSdesde el punto
, entonces la dirección
asociado con la direcciónS.

Algoritmo.

Paso 1. Establecer punto de partida y sistema direcciones linealmente independientes
(inicialmente pueden coincidir con las direcciones de los ejes de coordenadas). Minimizar función
con movimiento secuencial a lo largo direcciones; utilizando algún tipo de búsqueda unidimensional; y tomar como inicial el punto mínimo obtenido anteriormente.

Paso 2. Realizar un paso adicional
, correspondiente al movimiento completo en el paso 1. Calcula el punto
(Figura 12). Consultar el criterio (*) para incluir una nueva dirección en el sistema de direcciones conjugadas.

Paso 3. Dejar – la mayor disminución de la función objetivo en una de las direcciones
:

Y es la dirección correspondiente .

Si se cumplen las condiciones

(*)

luego continúe la búsqueda siguiendo las direcciones originales
desde el punto
o
(desde el punto donde el valor de la función es menor).

Etapa 4. Si condiciones no se cumplen, entonces minimizar la función
a lo largo de la dirección
. Tome el punto de este mínimo como punto de partida en la siguiente etapa. En esta etapa, utilice el sistema de referencia.

aquellos. dirección reemplazado por , que debe colocarse en la última columna de la matriz de dirección.

Paso 5. Si
, entonces se encuentra el mínimo. De lo contrario, siga el paso 1.

Ejemplo. Al hacer clic en el icono se abrirá un documento del método de dirección conjugada de Mathcad en el que podrá realizar cálculos.

Minimizar una función

método de direcciones conjugadas

Puede parecer irracional desechar la mejor dirección de la iteración actual e instalar una nueva dirección prometedora al final en lugar de al principio. Sin embargo, no es difícil ver que la dirección más exitosa probablemente se haya agotado, y se acaba de utilizar una nueva dirección prometedora para la optimización unidimensional y no tiene sentido aplicarla de inmediato, ya que simplemente no habrá progreso. .

Powell demostró que el determinante de la matriz de direcciones toma un valor máximo si y sólo si las direcciones ,
son conjugados con respecto a la matriz de Hesse. Concluyó que la dirección de un movimiento completo debe reemplazar a la anterior sólo si esta dirección aumenta el determinante de la matriz de direcciones, ya que sólo entonces el nuevo conjunto de direcciones será efectivo.

Está demostrado que el procedimiento de Powell converge a un punto en el que el gradiente es cero si la función objetivo es estrictamente convexa. Este punto es un mínimo local. El método es muy sensible a la forma en que se construyen las direcciones conjugadas y, por tanto, depende de la precisión de la búsqueda unidimensional utilizada. Powell propuso utilizar una secuencia de interpolaciones cuadráticas con un procedimiento especial para ajustar los parámetros de esta búsqueda lineal. Sin embargo, los estudios numéricos han demostrado que el método de dirección conjugada de Powell no debe usarse para dimensiones mayores que 20.