Matemática Superior aplicada
Optimización Unidimensional
Profesor: Dr. Alejandro S. M. Santa CruzJTP: Dr. Juan Ignacio ManassaldiAux. 1ra: Ing. Juan Pablo CamponovoAux. 2da: Sr. Alejandro J. Ladreyt
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
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
2''( ) 3 14 10f x x x
''( ) 0 Mínimo Relativo'( ) 0
''( ) 0 Máximo Relativo
f xf x
f x
Optimización Unidimensional
Método de Newton
si
no
0
0; 0x k
1k k
rk
x x
x
1es un extremo
kx
1k k
1'
''
k
k k
k
f xx x
f x
Método de interpolación parabólica sucesivas
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?
1x2x
3x
4 3 21 7( ) 5 2
4 3max f x x x x
Método de interpolación parabólica sucesivas (1)
¿Cómo elegir los tres valores de arranque?
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 sucesivas (1)
1x2x
3x
4 3 21 7( ) 5 2
4 3max f x x x x
Método de interpolación parabólica sucesivas (1)
Encontramos la parábola que pasa por los tres puntos. El nuevo punto corresponde al extremo de la misma.
4x
2y ax bx c
2
2
2
2.5 2.5 1 2.55729
3 3 1 0.25
3.5 3.5 1 3.27604
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
2.5 ( ) 2.55729
3 ( ) 0.25
3.5 ( ) 3.27604
x f x
x f x
x f x
2.5;2.55729
3;0.25
3.5; 3.27604
2
2
2
2.5 2.5 2.55729
3 3 0.25
3.5 3.5 3.27604
a b c
a b c
a b c
Ax b Sistema 3x3
Método de interpolación parabólica sucesivas (1)
2
2
2
2.5 2.5 1 2.55729
3 3 1 0.25
3.5 3.5 1 3.27604
a
b
c
Resolvemos
2.4375
8.791667
4.1875
a
b
c
22.4375 8.791667 4.1875y x x
Método de interpolación parabólica sucesivas (1)
1x2x
3x
¿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
8.7916671.803418
2 2.4375x
Método de interpolación parabólica sucesivas (1)
1x2x
3x
4x
1x2x
3x
Método de interpolación parabólica sucesivas (1)
4x
¿Cómo elijo los nuevos puntos?Nos quedamos con los tres últimos
1x2x
3x
4 3 21 7( ) 5 2
4 3max f x x x x
Método de interpolación parabólica sucesivas (2)
¿Cómo elijo los nuevos puntos?Nos quedamos con los tres últimos
1x2x
3x
4 3 21 7( ) 5 2
4 3max f x x x x
Método de interpolación parabólica sucesivas (2)
Continuamos… hasta satisfacer la tolerancia
4x
1x
2x3x
4 3 21 7( ) 5 2
4 3max f x x x x
Método de interpolación parabólica sucesivas (2)
¿Cómo elijo los nuevos puntos?Nos quedamos con los tres últimos
no
Método de interpolación parabólica sucesivas (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 3maximode 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
¿Cómo elegir los tres valores de arranque?
4 3 21 7( ) 5 2
4 3max f x x x x
1x2x
3x
Método de interpolación parabólica sucesivas (2)
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 sucesivas (2)
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 sucesivas (2)
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
1x2x 3x
Método de interpolación parabólica sucesivas (2)
¿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 sucesivas (2)
¿Cómo elijo los nuevos puntos?
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 sucesivas (2)
Nuevo intervalo:
1x2x
3x
Método de interpolación parabólica sucesivas (2)
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
1x 2x4x
3x
4 3.3219f x
Método de interpolación parabólica sucesivas (2)
¿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 sucesivas (1)
si
no
Método de interpolación parabólica sucesivas (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 3maximode 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
¿Cuál es la diferencia?
Método de interpolación parabólica sucesivas (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) puede llevarnos a un extremo que no
corresponde al que estamos buscando.• La metodología (2) converge a un máximo o mínimo
según lo que estemos buscando. Podemos decidir que buscar.
2 2 2 2 2 2
1 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 sucesivas (1) y (2)
Método de interpolación parabólica sucesivas
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 2
1 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 y como una fracción 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 y :
b b a
a b a
¿ ?
Método de la relación dorada
0a 0b0 0
1b1a1 1
1b1a 1 1
Intervalo original
Nuevo Intervalo (caso 1)
Nuevo Intervalo (caso 2)
Método de la relación dorada
Valor aleatorio: 0.7:
No se utiliza cualquier valor porque cada iteración requeriría calcular y
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 de manera que se cumpla lo siguiente:
El valor de que estamos buscando permite que en cada iteración solo se calcule o
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
2
0 0 0 0 0 0a b a b b a
Método de la relación dorada
2
0 0 0 0 0 0a b a b b a
2
0 0 0 0 0 0 0b a b a b a
12
2
0.6181 0
1.618
¡Encontramos el !
Analizando el Caso 2 se llega a la misma conclusión
Método de la relación dorada
0.618
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
a b tol extremo
b b a
a b a
a a
b
b b a
Método de la relación dorada (minimizar)
f f sino
a
b b
a b a
Método de interpolación parabólica sucesivas
Ejemplo: 2
min 210
xsen x
a b f() f()
0 4
Método de interpolación parabólica sucesivas
Ejemplo: 2
min 210
xsen x
a b f() f()
0 1.528 2.472 4 -1.76469035 -0.6302549
0 0.944304 1.528 2.472 -1.53100712 -1.76469035
0.944304 1.528 1.88842013 2.472 -1.76469035 -1.54334736
0.944304 1.30495636 1.528 1.88842013 -1.75945322 -1.76469035
1.30495636 1.528 1.66553697 1.88842013 -1.76469035 -1.71362958
1.30495636 1.44269815 1.528 1.66553697 -1.77547549 -1.76469035
a b f() f()
0 1.528 2.472 4 -1.76469035 -0.6302549
0 0.944304 1.528 2.472 -1.53100712 -1.76469035
0.944304 1.528 1.88842013 2.472 -1.76469035 -1.54334736
0.944304 1.30495636 1.528 1.88842013 -1.75945322 -1.76469035
1.30495636 1.528 1.66553697 1.88842013 -1.76469035 -1.71362958
1.30495636 1.44269815 1.528 1.66553697 -1.77547549 -1.76469035
Método de interpolación parabólica sucesivas
Ejemplo: 2
min 210
xsen x
Método de la relación dorada
Plantear Caso de
Maximización
Método de interpolación parabólica sucesivas
Ejemplo: 2
210
xmax sen x
a b f() f()
0 4