Upload
cesar-pacheco
View
15
Download
3
Embed Size (px)
DESCRIPTION
MetodosDescenso empinado,Newton para varias variables ,Gradientes Conjugados,Cuasi Newton (Rango 1, DFP, BFGS)
Citation preview
INSTITUTO POLITECNICO NACIONAL
ESCUELA SUPERIOR DE FISICA Y
MATEMATICAS
OPTIMIZACIÓN NO LINEAL
Proyecto
Alumnos:
Pacheco Chávez Cesar Augusto
Martínez Cordero Víctor Ramón
Martínez Bravo Fernando
Profesora: Adriana Lara López
GRUPO: 6MM1
Introducción:
En este proyecto aplicaremos los métodos que hemos visto a lo largo del curso de
Optimización no lineal los cuales son:
Descenso empinado
Newton para varias variables
Gradientes Conjugados
Cuasi Newton (Rango 1, DFP, BFGS)
Las funciones de prueba serán las siguientes
( )
( ) ( ) ( )
( )
( )
( )
( )
( )
( ) | | | |
( ) ( ) ( ) ( ( ) ( ) )
En este proyecto que realizamos tiene como objetivo encontrar los óptimos locales de las
funciones de prueba, también observaremos que algunos métodos son más eficientes que
otros tal y como lo vimos en el curso de optimización lineal.
Así como también pondremos las gráficas de las funciones de prueba
Los resultados que pondremos en las tablas, son el número de iteraciones que tardó en
llegar al óptimo para cada función de prueba, así como cuánto vale el óptimo de la función
en dicho intervalo.
Método del Descenso Empinado:
El método del descenso empinado es un algoritmo que utiliza información de primer orden
(gradientes). En este método se calcula una dirección de descenso y se avanza sobre
esta de manera que se obtenga el máximo decremento en esa dirección, a cada paso.
Descenso empinado con la condición de Armijo y backtracking
La condición de Armijo no es suficiente para un buen tamaño de paso, sin embargo al
combinarse con el procedimiento de backtracking se pueden obtener buenos resultados
ALGORITMO DE BÚSQUEDA CON ARMIJO Y BACKTRACKING:
PASO 1.- α>0, ρ, C(0,1)
PASO 2.- α <= α’
PASO 3.- Repite hasta que:
(f(x^k+αρk)≤f(Xk)+CαρkYfk), α <= αρ
PASO 4.- Terminar con αk = α
Método de Newton para varias variables.
El método de Newton es más eficiente que el método del descenso máximo, sin embargo
requiere el cálculo de información de segundo orden (segundas derivadas).
Este método requiere de un punto de inicio “cercano” al optimo y en ciertos casos no se
puede garantizar convergencia.
La idea principal consiste en construir una aproximación cuadrática de la función objetivo
en el punto , tal que su derivada y segunda derivada coincidan con la función objetiva.
Una vez hecho esto calculamos el óptimo de dicha aproximación.
Algoritmo:
1. Calcular f( )
2. Evaluar en f( )
3. Si f( ) ( ) hemos acabado
4. Si f( ) ( ) calcular
5. Calcular
6. Evaluar en f( )
7. Si f( ) ( ) hemos acabado , sino regresar al paso 5
Método de Gradiente Conjugados
Este método no requiere predefinir las direcciones, pues las va calculando su ejecución. A
cada etapa del algoritmo la dirección se calcula en función de las direcciones anteriores y
el gradiente de la función, evaluando en el punto actual de manera que la nueva dirección
resulta ser Q-conjugada respecto a las anteriores.
Algoritmo:
1) ( )= f( ( )), si ( ) terminar, sino = ( )
2) ( ) ( )
( ) ( )
3) ( )= +
4) ( ) f( ( ) si ( ) Terminar
5) ( ) ( )
( ) ( )
6) ( ) ( )
7) ir al paso 2
Métodos de Cuasi Newton
Los métodos de Cuasi Newton surgen de la idea de aproximar la matriz inversa de la
Hessiana, mediante una multiplicación sucesiva de matrices, llamaremos a estas matrices
.
Para empezar a proponer las matrices del método se requiere empezar definida
positiva.
Existen varios métodos, la única diferencia entre estos se deriva de la forma de calcular
matrices pero a todos se les llama Cuasi-Newton por que utilizan la misma idea es
decir:
( ) ( )
( ( ) ( ))
( ) ( ) ( )
Donde las matrices son simétricas.
Algoritmo para el método de Rango uno:
1) Hacer k=0, seleccionar ( ) el punto de inicio y
2) Si ( ) terminar sino, ( ) ( )
3) Calcular:
( ( ) ( )
( ) ( ) ( ) , ( ) ( ( ))
4) Calculamos
( ) ( ), ( ) ( ) ( )
( ( )
( ))( ( ) ( ))
( ) ( ( ) ( ))
5) Hacer k=k+1 e ir al paso 2
El método de Rango uno fue propuesto en 1959 y fue posteriormente modificado por
Fletcher y Powel en 1963 para desarrollar el método conocido como DFP: También se
conoce como el método de métrica variable.
Algoritmo DFP:
1) Hacer k=0, seleccionar ( ) el punto de inicio y
2) Si ( ) terminar sino, ( ) ( )
3) Calcular:
( ( ) ( )
( ) ( ) ( ) , ( ) ( ( ))
4) Calculamos
( ) ( ), ( ) ( ) ( )
( ( ) ( ) )
( ) ( ( ) ( )) (
( )) ( ( ))
( ) ( )
5) k= k+1, ir al paso 2
El algoritmo de DFP se propuso como una mejora al método de rango uno en el sentido
de que DFP garantiza que las son definidas positivas, mientras que en el de rango uno
no necesariamente se tiene tal cosa.
Sin embargo, para problemas con muchas variables iniciales (incluso cuadráticas) el DFP
puede llegar a quedarse “atorado” y no llegar al óptimo.
Generalmente esto se debe a que la matriz se va volviendo conforme pasan las
iteraciones una matriz no singular.
Una alternativa más notable se da con el método de BFGS.
Algoritmo BFGS:
1) Hacer k=0, seleccionar ( ) el punto de inicio y
2) Si ( ) terminar sino, ( ) ( )
3) Calcular:
( ( ) ( )
( ) ( ) ( ) , ( ) ( ( ))
4) Calculamos:
( ) ( ), ( ) ( ) ( )
( ( ( )
( ))
( ) ( )) ( ) ( )
( ) ( )
( ) ( ) ( ( ) ( ) )
( ) ( )
5) k=k+1 ir al paso 2
A continuación pondremos las gráficas de las funciones de prueba:
1. ( )
Vemos que esta función es una función que es una parábola que abre hacia arriba y solo
existe un mínimo global.
2. ( ) ( ) ( )
En función vemos que es cóncava hacia arriba, por eso es importante escoger bien el
intervalo para que converge rápido al optimo que deseamos encontrar; y no tendrá ningún
tipo de problema con los métodos vistos por ser una función cuadrática.
5. ( )
Esta función se ve que tiene un óptimo mientras que los x sean menor que cero y los
crezcan partir del cero, se acercara al optimo cuadráticamente o dependiendo del
método que utilicemos en ciertas iteraciones.
7. ( )
( )
En función vemos que es cóncava hacia arriba, por eso es importante escoger bien el
intervalo para que converge rápido al optimo que deseamos encontrar; y no tendrá ningún
tipo de problema con los métodos vistos por ser una función cuadrática.
8. ( )
En función vemos que es cóncava hacia arriba, por eso es importante escoger bien el
intervalo para que converge rápido al optimo que deseamos encontrar; y no tendrá ningún
tipo de problema con los métodos vistos por ser una función cuadrática.
9. ( )
Esta función depende de tres variables se podría ver como una esfera y solo tiene un
punto mínimo el cual sería (0,0,0)
10. ( ) | | | |
Esta función es de dos variables en la que “y” podría tomar valores negativos por ser una
función impar lo manda ser una función que abre hacia arriba con el valor absoluto y tiene
solo un punto mínimo el cual es (0,0) como se ve en dicha gráfica.
13. ( ) ( ) ( ) ( ( ) ( ) )
Esta función existe un único punto local y esta función crece muy rápido por eso es
importante escoger bien el punto de inicio para que converja rápidamente.
Procederemos con las tablas para saber cómo se comportaron las funciones con cada
método:
( )
x^2+y^2
Descenso Empinado
Newton Gradientes Conjugados
Cuasi Newton
F Calls 4 27 85 86
G Calls 3 2 4 4
x* optimo
[0,0] [-5.0000e-007, -5.0000e-007]
[-4.8635e-007, -4.8635e-007]
[-4.8635e-007, -4.8635e-007]
F(x*) 0 5.00E-13 4.73E-13 4.7308E-13
Para esta función para todos los intervalos que poníamos nos da los mismos resultados,
excepto para el método de newton ya que para intervalos mayores a [49,49] el programa
fallaba, esto se debe a que el punto está demasiado alejado del óptimo.
( ) ( ) ( )
100(x^2-y)^2+(1-x)^2
Descenso Empinado
Newton Gradientes Conjugados
Cuasi Newton
F Calls 8 27 47587 86
G Calls 3 2 2266 4
x* optimo [0.99970, 0.99940]
[0.99970, 0.99940]
[0.92003, 0.84590]
[2.2424e+012 , 5.0841e+007]
F(x*) -9.0235E-08 -9.02E-08 6.43E-03 2.53E+51
Para esta función el método de gradientes conjugados para intervalos pequeños como
[1,1] realizaba demasiadas iteraciones, pero al dar intervalos más grandes ejemplo [20,20]
las iteraciones disminuían notoriamente. Para los Cuasi Newton siguen siendo las mismas
llamadas que para la anterior función.
( )
x^2+2y^2-2x-8y Descenso Empinado
Newton Gradientes Conjugados
Cuasi Newton
F Calls 221 27 253 86
G Calls 2 2 12 4
x* optimo [1, -0.25] [1, -0.25] [1.00233, 0.24737]
[1, -0.25]
F(x*) -9.125 -9.13E+00 -9.13E+00 -9.125
En esta función el método de descenso empinado tardo demasiado en llegar al óptimo, al
igual que el de gradientes conjugados, mientras que los de Cuasi Newton se siguen
manteniendo en las llamadas de F.
( )
( )
1/4 (x^4-4xy+y^4 )
Descenso Empinado
Newton Gradientes Conjugados
Cuasi Newton
F Calls 92 27 85 86
G Calls 86 2 4 4
x* optimo [-1.0327 -1.0327]
[-0.000000029758, -0.000000031596]
[ -0.11718 , -0.11718]
[ -8.4394e-009 , -8.4394e-009]
F(x*) -0.1646 -1.00E+00 -9.96E-01 -1
Para el método de descenso empinado tardo más tiempo en encontrar el óptimo, para
cada intervalo más alejado del óptimo hacia más iteraciones, para los demás métodos
arrojaba los mismos resultados, en el de Newton recordemos que debemos de dar un
punto cercano al optimo sino el método no funciona.
( )
x^4-4xy+y^4 Descenso Empinado
Newton Gradientes Conjugados
Cuasi Newton
F Calls 135 27 127 86
G Calls 127 2 6 4
x* optimo [-1.0086 ,-1.0086]
[1,1] [1,1] [ 1,1]
F(x*) -1.9994 -2 -2 -2
En esta función el método de descenso empinado tardo demasiado en llegar al óptimo, al
igual que el de gradientes conjugados, mientras que los de Cuasi Newton se siguen
manteniendo en las llamadas de F y G
( )
x^2+y^2+z^2
Descenso Empinado
Newton Gradientes Conjugados Cuasi Newton
F Calls 4 51 93 86
G Calls 3 2 4 4
x* optimo
[0,0,0] [ -5.0000e-007 ,-5.0000e-007 ,-5.0000e-007]
[ -4.8635e-007 ,-4.8635e-007 ,-4.8635e-007]
[ -5.0000e-007 ,-5.0000e-007 ,-5.0000e-007]
F(x*) 0 7.50E-13 7.10E-13 7.5E-13
En esta función el método del Descenso empinado fue más eficiente que los demás ya
que además de solo hacer 4 iteraciones llego al punto óptimo de la función, en caso
contrario los otros métodos solo llegaron a un óptimo local de dicha función.
( ) | | | |
|x|^2+|y|^3
Descenso Empinado
Newton Gradientes Conjugados
Cuasi Newton
F Calls 136 27 127 86
G Calls 123 2 6 4
x* optimo
[ -0.017272 ,-0.087907]
[-5.0000e-007 1.2206e-004]
[ -0.017272 ,-0.087907]
[-2.5046e-007 ,-5.3774e-004]
F(x*) 0.00097764 2.07E-12 9.78E-04 1.56E-10
El intervalo en el que tiene que ser tomada esta función es [-1,1] , el método del descenso
empinado es el que tarda más en encontrar el óptimo local, mientras que los métodos de
Cuasi Newton siguen siendo constantes en relación a que en todas las funciones
anteriores hace las mismas iteraciones.
( ) ( ) ( ) ( ( ) ( ) )
-cos(x)*cos(y)*exp(-(x-pi)²*(y-pi)²
Descenso Empinado
Newton Gradientes Conjugados
Cuasi Newton
F Calls 4202 43 43 86
G Calls 4202 2 2 4
x* optimo [-100,100] [-100,100]
[-100,100] [-100,100]
F(x*) 0 0 0 0
A partir del intervalo [-19,19] genera otros valores para el óptimo, para el descenso
empinado hace más iteraciones y va aumentando conforme el intervalo se va reduciendo.
Conclusiones:
Los métodos Cuasi Newton son los más eficaces y constantes para cualquier
función de prueba.
El método de Newton se llega a ciclar si no damos un punto cercano al óptimo y
en estos casos el método no funciona.
El método de Gradientes conjugados es el que tarda más ya que hace
demasiadas iteraciones, esto se debe a que a cada paso calcula la dirección
donde se encuentra el óptimo local.
El método de Descenso Empinado para funciones fáciles como las primeras 2
funciones de prueba es muy eficiente ya que llega en menos paso al optimo local,
pero para las demás funciones se llegó a tardar demasiado y si das un punto muy
alejado del optimo el programa se cicla y falla.
Bibliografía:
Apuntes de Clase