Post on 15-Aug-2020
Matemática Superior Aplicada
Optimización Unidimensional
Profesor: Dr. Alejandro S. M. Santa CruzAuxiliares: Dr. Juan Ignacio Manassaldi
Srta. Amalia Rueda
-1 0 1 2 3 4 5 6 7
-14
-12
-10
-8
-6
-4
-2
0
2
4
6
4 3 21 7( ) 5 2
4 3f x x x x
Mínimos Relativos
Máximo Relativo
Mínimo Absoluto
Encontrar el valor mínimo o máximo de una función en una variable
Optimización Unidimensional
-1 0 1 2 3 4 5 6 7
-14
-12
-10
-8
-6
-4
-2
0
2
4
6
4 3 21 7( ) 5 2
4 3f x x x x
3 2'( ) 7 10f x x x x
'( ) 0f x
Condición necesaria de mínimo o máximo: '( ) 0f x
Optimización Unidimensional
-1 0 1 2 3 4 5 6 7
-14
-12
-10
-8
-6
-4
-2
0
2
4
6
2''( ) 3 14 10f x x x
''( ) 0 Mínimo Relativo'( ) 0
''( ) 0 Máximo Relativo
f xf x
f x
Optimización Unidimensional
Se basa en encontrar la raíz de aplicando el método de Newton-Rhapson.
'( ) 0f x
Método de Newton
af
afab
''
'
xfyxfa ''',
si tolbf '
no
extremob
ba
Método de interpolación parabólica sucesiva
Este método encuentra la parábola que pasa por tres puntos de la función y encuentra el extremo de la misma. Luego se eligen tres nuevos puntos y se repite el procedimiento hasta satisfacer la tolerancia.
¿Cómo elegir los tres valores de arranque?
¿Cómo encontrar la parábola?
¿Cómo encontrar el extremo de la parábola?
¿Cómo elijo los nuevos puntos?
¿Cuál es el criterio de tolerancia?
Método de interpolación parabólica sucesiva
Ejemplo:
4 3 21 7( ) 5 2
4 3max f x x x x
-1 0 1 2 3 4 5 6 7-20
-10
0
10
20
30
40
50
¿Cómo elegir los tres valores de arranque?
4 3 21 7( ) 5 2
4 3max f x x x x
-1 0 1 2 3 4 5 6 7-20
-10
0
10
20
30
40
50
1x2x
3x
Método de interpolación parabólica sucesiva (1)
-1 0 1 2 3 4 5 6 7-20
-10
0
10
20
30
40
50
1 1
2 2
3 3
0 ( ) 2
1 ( ) 0.9167
3 ( ) 0.25
x f x
x f x
x f x
El valor de la función en el punto intermedio mayor que el de los extremos
4 3 21 7( ) 5 2
4 3max f x x x x
1x2x
3x
Método de interpolación parabólica sucesiva (1)
2y ax bx c
2
2
2
0 0 1 2
1 1 1 0.9167
3 3 1 0.25
a
b
c
Los tres puntos deben cumplir esta ecuación
¿Cómo encontrar la parábola?
La parábola debe pasar por los siguientes puntos:
1 1
2 2
3 3
0 ( ) 2
1 ( ) 0.9167
3 ( ) 0.25
x f x
x f x
x f x
0; 2
1;0.9167
3;0.25
2
2
2
0 0 2
1 1 0.9167
3 3 0.25
a b c
a b c
a b c
Ax b Sistema 3x3
Método de interpolación parabólica sucesiva (1)
2
2
2
0 0 1 2
1 1 1 0.9167
3 3 1 0.25
a
b
c
Resolvemos
-1.0833
4
2
a
b
c
21.0833 4 2y x x
-1 0 1 2 3 4 5 6 7-30
-20
-10
0
10
20
30
40
50
1x2x 3x
Método de interpolación parabólica sucesiva (1)
-1 0 1 2 3 4 5 6 7-30
-20
-10
0
10
20
30
40
50
¿Cómo encontrar el extremo de la parábola?2y ax bx c ' 2y ax b ' 0
2
bx y
a
El nuevo punto corresponde al extremo de la parábola:
4
41.846154
2 -1.0833x
1x2x 3x4x
Método de interpolación parabólica sucesiva (1)
¿Cómo elijo los nuevos puntos?
-1 0 1 2 3 4 5 6 7-20
-10
0
10
20
30
40
50
Debemos quedarnos con el nuevo punto y dos de los anteriores.
¿Cuáles son los nuevo tres puntos?
1x2x 4x 3x
El valor de la función en el punto intermedio mayor que el de los extremos
Método de interpolación parabólica sucesiva (1)
Nuevo intervalo:
-1 0 1 2 3 4 5 6 7-20
-10
0
10
20
30
40
50
1x2x
3x
Método de interpolación parabólica sucesiva (1)
2
2
2
1 1 1 0.9167
1.8461 1.8461 1 3.2636
3 3 1 0.25
a
b
c
-2.6928
10.4378
-6.8284
a
b
c
4
10.43781.9381
2 -2.6928x
-1 0 1 2 3 4 5 6 7-20
-10
0
10
20
30
40
50
1x 2x 4x3x
4 3.3219f x
Método de interpolación parabólica sucesiva (1)
¿Cuál es el criterio de tolerancia?
El nuevo punto encontrado va convergiendo al valor optimo
x1 f(x1) x2 f(x2) x3 f(x3) x4 f(x4)
0 -2 1 0.91666667 3 0.25 1.84615385 3.26368124
1 0.91666667 1.84615385 3.26368124 3 0.25 1.93810657 3.32192365
1.84615385 3.26368124 1.93810657 3.32192365 3 0.25 1.99575822 3.33327938
1.93810657 3.32192365 1.99575822 3.33327938 3 0.25 1.99894161 3.33332997
1.99575822 3.33327938 1.99894161 3.33332997 3 0.25 1.99992747 3.33333332
1.99894161 3.33332997 1.99992747 3.33333332 3 0.25 1.99998467 3.33333333
1.99992747 3.33333332 1.99998467 3.33333333 3 0.25 1.99999881 3.33333333
Método de interpolación parabólica sucesiva (1)
si
no
Método de interpolación parabólica sucesiva (1)(maximizar)
si
no
no
si
si
1 2 3 1 2 3 2 1 2 3, ,x x x x x x f x f x f x f x
4 2x x tol 4 extremox
4
1 1 2 2 3 3maximo de la parabola que pasa por , , , y ,
x
x f x x f x x f x
4 1 4 2x x x x
4 2f x f x
1 4 2 2 3 3; ;x x x x x x
4 2f x f x 1 2 2 4 3 3; ;x x x x x x
1 1 2 2 3 4; ;x x x x x x
1 1 3 2 2 4; ;x x x x x x
no
-1 0 1 2 3 4 5 6 7-20
-10
0
10
20
30
40
50
1x2x
3x
4 3 21 7( ) 5 2
4 3max f x x x x
Método de interpolación parabólica sucesiva (2)
¿Cómo elegir los tres valores de arranque?
-1 0 1 2 3 4 5 6 7-20
-10
0
10
20
30
40
50
1x2x
3x
Solo necesitamos tres puntos del dominio
4 3 21 7( ) 5 2
4 3max f x x x x
Método de interpolación parabólica sucesiva (2)
-1 0 1 2 3 4 5 6 7-20
-10
0
10
20
30
40
50
1x2x
3x
4 3 21 7( ) 5 2
4 3max f x x x x
Método de interpolación parabólica sucesiva (2)
Encontramos la parábola que pasa por los tres puntos. El nuevo punto corresponde al extremo de la misma.
4x
-1 0 1 2 3 4 5 6 7-20
-10
0
10
20
30
40
50
1x2x
3x
4 3 21 7( ) 5 2
4 3max f x x x x
Método de interpolación parabólica sucesiva (2)
¿Cómo elijo los nuevos puntos?Nos quedamos con los tres últimos
-1 0 1 2 3 4 5 6 7-20
-10
0
10
20
30
40
50
1x2x
3x
4 3 21 7( ) 5 2
4 3max f x x x x
Método de interpolación parabólica sucesiva (2)
Continuamos… hasta satisfacer la tolerancia
4x
no
Método de interpolación parabólica sucesiva (1)(maximizar)
si
1 2 3 1 2 3, ,x x x x x x
4 3x x tol 4 extremox
4
1 1 2 2 3 3maximo de la parabola que pasa por , , , y ,
x
x f x x f x x f x
1 2 2 3 3 4; ;x x x x x x
¿Cuál es la diferencia?
Método de interpolación parabólica sucesiva (1) y (2)
En funciones de un solo máximo (o mínimo) ambos llegan al mismo resultado.Para funciones con varios extremos:• La metodología (1) converge a un máximo o mínimo
según lo que estemos buscando. Podemos decidir que buscar.
• La metodología (2) puede llevarnos a un extremo que no corresponde al que estamos buscando.
2 2 2 2 2 21 2 3 2 3 1 3 1 2
4
1 2 3 2 3 1 3 1 22 2 2
f x x x f x x x f x x xx
f x x x f x x x f x x x
Tip: Existe una formula directa para el calculo del nuevo punto
Método de interpolación parabólica sucesiva (1) y (2)
Método de interpolación parabólica sucesiva
Ejemplo: 2
210
xmax sen x
x1 f(x1) x2 f(x2) x3 f(x3) x4 f(x4)0 1 4
2 2 2 2 2 21 2 3 2 3 1 3 1 2
4
1 2 3 2 3 1 3 1 22 2 2
f x x x f x x x f x x xx
f x x x f x x x f x x x
IntervaloNuevoIntervaloNuevo
( )f
( )f
a ba b
( )f
( )f
Método de la relación dorada
Sea , , tal que
Si , luego ,
Si , luego ,
a b
f f f x f x b
f f f x f x a
(Minimización)
Expresamos a l y m como una fracción a del intervalo [a,b]:
a b
b a 1 b a
b a 1 b a
Analizando la grafica anterior encontramos las siguientes expresiones de l y m :
b b a
a b a
¿ ?
Método de la relación dorada
0a 0b0 0
1b1a 1 1
1b1a 1 1
Intervalo original
Nuevo Intervalo (caso 1)
Nuevo Intervalo (caso 2)
Método de la relación dorada
Valor aleatorio: a0.7:
En cada iteración debemos calcular l y m
0a 0b0 0
1b1a 1 1
1b1a 1 1
Intervalo original
Nuevo Intervalo (caso 1)
Nuevo Intervalo (caso 2)
1 0 Caso 1:
1 0 Caso 2:
Método de la relación dorada
Buscamos a de manera que se cumpla lo siguiente:
En cada iteración solo debemos calcular l o m
0a 0b0 0
1b1a 1 1
Intervalo original
Nuevo Intervalo (caso 1)
0 0 0 0
1 1 1 1
a b a
b b a
1 0 Caso 1:
0 0 0 1 1 1a b a b b a
1 0
1 0 0 0 0
b b
a b b a
De la grafica:
Reemplazando:
0 0 0 0 0 0 0 0a b a b b b b a
0 0 0 0 0 0 0 0a b a b b b b a
20 0 0 0 0 0a b a b b a
Método de la relación dorada
20 0 0 0 0 0a b a b b a
20 0 0 0 0 0 0b a b a b a
12
2
0.6181 0
1.618
¡Encontramos el a!
Analizando el Caso 2 se llega a la misma conclusión
Método de la relación dorada
Golden Ratio
( )f
( )f
a b
IntervaloNuevo
Método de la relación dorada
Si f f
(Minimización)
0a 0b0 0
1b1a 1 1
1 0
1 0
1 0
1 1 1 1
a a
b
b b a
Método de la relación dorada
Si f f
(Minimización)
0a 0b0 0
1b1a 1 1
( )f
( )f
a b
IntervaloNuevo
1 0
1 0
1 0
1 1 1 1
a
b b
a b a
no
si
0 0, intervalo de busqueda original a b
k ka b tol extremo
0 0 0 0
0 0 0 0
0
b b a
a b a
k
1
1
1
1 1 1 1
1
k k
k k
k k
k k k k
a a
b
b b a
k k
Método de la relación dorada (minimizar)
k kf f sino
1
1
1
1 1 1 1
1
k k
k k
k k
k k k k
a
b b
a b a
k k
Método de la relación dorada
Plantear Caso de
Maximización