Date post: | 31-Jan-2016 |
Category: |
Documents |
Upload: | yoel-barreto |
View: | 253 times |
Download: | 0 times |
UNIVERSIDAD NACIONAL“SANTIAGO ANTUNEZ DE MAYOLO”
FACULTAD DE CIENCIAS
ESCUELA ACADEMICO PROFESIONAL DE MATEMATICA
RESUMEN DE LA EXPOSICION
“Metodos basicos de descenso”
CURSO: Programacion no lineal
ESTUDIANTES:
1. BORJA APENA, Marcelino
2. LOPEZ MAGUINA, David
PROFESOR: PACHECO CASTILLO, Alexander
HUARAZ - PERU
2015
Indice
1. Busqueda de Fibonacci 2
2. Busqueda lineal mediante ajuste de curvas 5
2.1. Metodo de newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1. Algoritmo del metodo de newton . . . . . . . . . . . . . . . . . . . 7
2.2. Ajuste cuadratico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3. Ajuste cubico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3. Metodo de descenso de mayor pendiente 14
3.1. Caso general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2. Caso cuadratico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1
Metodos basicos de descenso
1. Busqueda de Fibonacci
Permite resolver el problema de busqueda lineal, este metodo determina el mınimo va-
lor de una funcion f sobre un intervalo cerrado [a0, b0].Esta funcion puede estar definida
en un dominio mas amplio, pero el metodo requiere que dicho intervalo de busqueda sea
definido.
Se asume que f es unimodal, el mınimo es determinado(al menos aproximadamente) me-
diante la evaluacion en un cierto numero de puntos. Se pretende definir una estrategia de
busqueda que seleccione la observacion siguiente basada en los valores funcionales de las
observaciones anteriores.
Esto se define segun el siguiente problema:
Encontrar como seleccionar sucesivamente n observaciones, sin contar con un conoci-
miento explıcito de la funcion, de forma tal que podamos encontrar la mas pequena region
de incertidumbre posible en donde se encuentre el dominio,esta region de incertidumbre
es determinada en cualquier caso por las observaciones(sus valores funcionales) y la su-
posicion de que f es unimodal.
La busqueda de Fibonacci se basa en la secuencia de los numeros de Fibonacci que se
definen por las ecuaciones F0 = F1 = 1;Fn = Fn−1 + Fn−2, n = 2, 3, . . ..
Supongamos que se nos da una funcion f(x) que es unimodal en el intervalo [a0, b0].
de los puntos interiores c0 y d0 se utilizo el siguiente subintervalo y solo habra una nueva
evaluacion de la funcion.
Si f(c0) 6 f(d0), entonces el mınimo debe ocurrir en el subintervalo [a0, d0], y reemplaza-
mos a1 = a0 y b1 = b0 y continuar la busqueda en el nuevo subintervalo [a1, b1] = [a0, b0].
Si f(c0) > f(d0) entonces el mınimo debe ocurrir en el subintervalo [c0, b0] y reemplazamos
a1 = c0 y b1 = b0 y continuar la busqueda en el nuevo subintervalo [a1, b1] = [c0, b0] .
2
Es necesario el uso de n iteraciones, donde n es el numero mas pequeno tal que
Fn >b0 − a0
ϵ. Los puntos interiores ck y dk del subintervalo [ak, bk] se encuentran, segun
sea necesario, utilizando las siguientes formulas:
ck = ak +
(1− Fn−1−k
Fn−k
)(bk − ak) (1)
dk = ak +
(Fn−1−k
Fn−k
)(bk − ak) (2)
Ejemplo 1.1. Encontrar el mınimo de la funcion unimodal, f(x) = x2 − sin(x) en el
intervalo [0, 1] usando el metodo de Fibonacci. Utilice la tolerancia ε = 0,0001.
Solucion
Fn >b0 − a0
ε=
1− 0
0,0001= 10000 =⇒ n = 21 =⇒ F21 = 10946, F20 = 6765
Primera iteracion:
[a0, b0] = [0, 1]
c0 = a0 + (1− F20
F21
)(b0 − a0) = 0 + (1− 0,618034)(1) = 0,381966
d0 = a0 + (F20
F21
)(b0 − a0) = 0 + (0,618034)(1) = 0,618034
f(c0) = f(0,381966) = −0,226847
f(d0) = f(0,618034) = −0,197468 =⇒ f(c0) 6 f(d0) =⇒ minf(x) esta en [a0, d0].
Figura 1: Primera interaccion.
Segunda interacion:
[a1, b1] = [a0, d0] = [0; 0,618034]
3
c1 = a1 + (1− F19
F20
)(b1 − a1) = 0 + (1− 0,618034)(0,618034) = 0,236068
d1 = a1 + (F19
F20
)(b1 − a1) = 0 + (0,618034)(0,618034) = 0,381966
f(c1) = f(0,236068) = −0,178153
f(d1) = f(0,381966) = −0,226847 =⇒ f(c1) > f(d1) =⇒ minf(x) esta en [c1, b1].
Figura 2: Segunda interaccion.
Tercera interacion:
[a2, b2] = [c1, b1] = [0,236068; 0,618034]
c2 = a2 + (1− F18
F19
)(b2 − a2) = 0,236068 + (1− 0,618034)(0,381966) = 0,381966
d2 = a2 + (F18
F19
)(b2 − a2) = 0,236068 + (0,618034)(0,381966) = 0,472136
f(c2) = f(0,381966) = −0,2268475
f(d2) = f(0,472136) = −0,2318772 =⇒ f(c2) > f(d2) =⇒ minf(x) esta en [c2, b2].
Figura 3: Tercera interaccion.
Cuarta interacion:
4
[a3, b3] = [c2, b2] = [0,381966; 0,618034]
c3 = a3 + (1 − F17
F18
)(b3 − a3) = 0,381966 + (1 − 0,618034)(0,618034 − 0,381966) =
0,4721359
d3 = a3+(F17
F18
)(b3− a3) = 0,381966+ (0,618034)(0,618034− 0,381966) = 0,5278641
f(c3) = f(0,4721359) = −0,2318772
f(d3) = f(0,5278641) = −0,2250488=⇒ f(d3) > f(c3) =⇒ minf(x) esta en [a3, d3].
Figura 4: Cuarta interaccion.
...
Decimo noveno interaccion:
Tenemos la aproximacion:
c = 0,45021012
f(c) = f(0,45021012) = −0,232465574
2. Busqueda lineal mediante ajuste de curvas
2.1. Metodo de newton
Metodo para funciones dos veces diferenciables, de una sola variable en donde lo que
se quiere es encontrar:
minf(x) (3)
con f ′(x) y f ′′(x) conocidas.
5
Sea xk un punto factible, se puede aproximar f(x) al rededor de xk, a travez del
polinomio de taylor de segundo grado:
q(x) = f(xk) + f ′(x)(x− xk) +1
2f ′′(xk)(x− xk)
2 (4)
Figura 5: Aproximacion de segundo orden.
La funcion q(x) construida, es una buena aproximacion de segundo grado para f(x)
ya que:
q(xk) = f(xk)
q′(xk) = f ′(xk)
q′′(xk) = f ′′(xk)
Si:
f ′′(xk) > 0 → q(x) es convexa.
f ′′(xk) < 0 → q(x) es concava.
Resolvemos minq(x), en vez de minf(x), entonces se puede calcular y estimar xk+1 del
punto mınimo de f(x) hallando el punto en el que se anula la derivada de q(x).[condicion
del primer orden]
De (4), al derivar se tiene:
q′(x) = f ′(xk) + f ′′(xk)(x− xk)
6
Ahora como en xk+1 se anula q(x).
q′(xk+1) = f ′(xk) + f ′′(xk)(xk+1 − xk) = 0
Del anterior al despejar xk+1 obtenemos el metodo iterativo de newton:
xk+1 = xk −f ′(xk)
f ′′(xk)(5)
2.1.1. Algoritmo del metodo de newton
Paso inicial: Seleccionar la tolerancia ϵ ≈ 0, encontrar por inspeccion una solucion
de prueba inicial, x0, para k = 0
Paso iterativo: Evaluar f ′(xk) y f ′′(xk), luego minimizar q(x) y obtener una nueva
solucion xk+1,usando:
xk+1 = xk −f ′(xk)
f ′′(xk)
Criterio de parada: si |xk+1 − xk| ≤ ϵ, parar, y el mınimo en este caso resultaria
x∗ ≈ xk+1. Sino, avanzar k = k + 1, ir al paso iterativo.
Ejemplo 2.1. Encontrar el minf(x) = 2x3 − 21x2 + 60x− 7
Solucion
Hallamos las derivadas:
f ′(x) = 6x2 − 42x+ 60
f ′′(x) = 12x− 42
Aqui aprovechamos hallando los puntos de inflexion de la funcion f(x) asi:
f ′′(x) = 12x− 42 = 0
7
x =42
12= 3,5
Esto significa que:
Si x > 3,5 → f ′′(x) > 0, luego diremos que f(x) es escrictamente convexa esto nos
garantiza para haya un mınimo.
Si x < 3,5 → f ′′(x) < 0, luego diremos que f(x) es escrictamente concava esto nos
garantiza para haya un maximo.
Observacion 2.1. De esta manera nosotros podemos elegir facilmente para una funcion
polinomica un valor inicial x0 = 4, es decir estamos escogiendo un punto cercano a x >
3,5. por conveniencia ya que si elegimos un valor tan grande para x0, el metodo de newton
estaria convergiendo en varias iteracciones y eso no nos conviene.
Ahora usamos el algoritmo del metodo de newton:
Paso inicial: Escogemos ϵ = 0,0000000001, x0 = 4.
Paso iterativo:
Hallando las derivadas en el punto xk asi:
f ′(xk) = 6x2k − 42xk + 60
f ′′(xk) = 12xk − 42
Luego reemplazando f ′(xk) y f ′′(xk) en (5) obtenemos la formula de newton para
iterar de la siguiente forma:
xk+1 = xk −6x2
k−42xk+60
12xk−42
Ahora:
para k = 0 → x1 = x0 − 6x20−42x0+60
12x0−42
para k = 1 → x2 = x1 − 6x21−42x1+60
12x1−42
para k = 2 → x3 = x2 − 6x22−42x2+60
12x2−42...
Remplazando x0 = 4 se comienza la interacion como se muestra en la siguiente
tabla:
8
Figura 6: Tabla de valores.
Criterio de parada: Si calculamos |xk+1 − xk| = 6,98491930961609−10 < ϵ, parar
en este caso el minimo es x∗ = 5, en este caso efectivamente se ha encontrado
exactamete el mınimo para la funcion.
Observacion 2.2. Una de las formas mas sencillas de ver el metodo de newton es con-
siderarlo como una tecnica de resolucion iterativa de ecuaciones de la forma:
g(x) = 0
donde al aplicarla a la minimizacion, se hace g(x) = f ′(x), luego al reemplazar en (5)
adapta la forma
xk+1 = xk −g(xk)
g′(xk)(6)
A continuacion vemos un preliminar del Teorema de Taylor para poder demostrar la
siguiente proposicion que, nos dice que bajo ciertas condiciones, una funcion puede ser
expresarse como un polinomio de Taylor mas un cierto error, es decir
g(x) = Pn(x) + En
Teorema 2.1 (Teorema de taylor). Sea g continua en [a, b] y con derivadas hasta de
orden n continuas tambien en este intervalo cerrado; supongase que g(n+1)(x) existe en
< a, b >, entonces para x y xk ∈< a, b > se tiene:
g(x) = g(xk) + g′(xk)(x− xk) +g′′(xk)(x− xk)
2
2!+ . . .+
gn(xk)(x− xk)n
n!+ En (7)
donde En = gn+1(ξ)(x−xk)n+1
(n+1)!y ξ es un punto que se encuentra entre x y xk.
9
Observacion 2.3. Al construir el polinomio de taylor de primer grado al rededor de xk
es de segundo grado,
g(x) = g(xk) + g′(x)(x− xk) +1
2g′′(ξ)(x− xk)
2, ξ ∈< x, xk >
despejando el termino error,
1
2g′′(ξ)(x− xk)
2 = g(x)− g(xk)− g′(x)(x+ xk)
Si x = x∗ obtenemos:
1
2g′′(ξ)(x∗ − xk)
2 = g(x∗)− g(xk)− g′(x)(x∗ − xk) (8)
Proposicion 2.1. sea g(x) una funcion con segunda derivada continua, y g(x∗) que se-
tisface g(x∗) = 0, g′(x∗) = 0. Entonces, si x0 esta suficientemente cerca de x∗, la sucesion
{xk}∞x=0, generada por el metodo de newton (6), converge a x∗ con un orden de conver-
gencia de al menos dos.
Demostracion. Para los puntos ξ en una region proxima a x∗
∃k1 : |g′′(ξ)| < k1
∃k2 : |g′(ξ)| > k2
Entonces como, g(x∗) = 0, se puede escribir
xk+1 − x∗ = xk − x∗ − g(xk)− g(x∗)
g′(xk)
=g′(xk)(xk − x∗)− g(xk) + g(x
∗)
g′(xk)
=
[g(x∗)− g(xk)− g′(xk)(x
∗ − xk)
g′(xk)
](9)
El termino entre corchetes, por el teorema de taylor, es de cero a primer orden. de
hecho, utilizando el termino residuo en una expancion en serie al rededor de xk, se obtiene:
Ahora reemplazando la expresion (8) en (9) tenemos:
10
=
[ 12g′′(ξ)(x∗ − xk)
2
g′(xk)
]=
1
2
g′′(ξ)(x∗ − xk)2
g′(xk)
=1
2
∣∣∣∣ g′′(ξ)g′(xk)
∣∣∣∣ ∣∣(x∗ − xk)2∣∣
Para algun ξ entre x∗ y xk. Ası, en la region proxima a x∗,
|xk+1 − x∗| ≤ k12k2
|(x∗ − xk)|2
=k12k2
|(x∗ − xk)| |(x∗ − xk)|
se observa que si,
k12k2
|(x∗ − xk)| < 1
entonces,
|xk+1 − x∗| < 1 · |(x∗ − xk)|
|xk+1 − x∗| < |x∗ − xk| , ∀k ∈ N
|x∗ − xk| → 0
xk → x∗
y asi se concluye que, comenzando suficientemente cerca de la solucion, el metodo con-
vergera a x∗ con un orden de convegencia de al menos dos.
2.2. Ajuste cuadratico
Si comenzamos con tres puntos, por ejemplo x1, x2, x3 en orden creciente, y no necesa-
riamente igualmente espaciados, pero contenidos dentro de la zona de busqueda < a, b >,
podemos aproximarlos a un polinomio de grado 2, f(x) = a+ bx+ cx2 de tal manera que
dicho polinomio pasa exactamente por esos tres puntos y debe presentar un mınimo en:
11
x∗ = − b
2c(10)
Observacion 2.4. La ecuacion (10) se obtiene completando el cuadrado a,f(x) = a +
bx+ cx2 asi:
f(x) = a+ bx+ cx2
= cx2 + bx+ a
= c
[x2 +
b
cx+
a
c
]= c
[(x+
b
2c
)2
− 4ac− b2c
4c2
]
= c
(x− b
2c
)2
+4ac− b2c
4c
De este anterior se consigue el vertice de la parabola (−b2c, 4ac−b2c
4c), la cual es la primera
componente el optimo(mınimo) x∗ = −b2c
para dicha curva la parabola.
Si suponemos que f(x) se evalua en los tres puntos, podrıamos calcular los valores de
a, b, c resolviendo el sistema de tres ecuaciones lineales:f(x1) = a + bx1 + cx2
1
f(x2) = a + bx2 + cx22
f(x3) = a + bx3 + cx23
(11)
Al resolver el sistema (11), encontramos los valores de a, b y c. Luego al reemplazar en
(10) lo que nos lleva a obtener:
x∗ =1
2
[(x2
2 − x23)f1 + (x2
3 − x21)f2 + (x2
1 − x22)f3
(x2 − x3)f1 + (x2 − x3)f2 + (x2 − x3)f3
](12)
Donde:
f(x1) = f1, f(x2) = f2 y f(x3) = f3
Para ilustrar la primera etapa del procedimiento de busqueda examinaremos en la
Figura Senalar que solamente una nueva evaluacin de la funcion objetivo se lleva a cabo
en cada etapa de busqueda. Este metodo utiliza evaluaciones de la funcion, y solo un
nuevo valor de funcion debe ser calculado en cada iteracion.
12
Figura 7: Ajuste cuadratico
Ejemplo 2.2. Minimizar usando el metodo de aproximacion cuadratica la siguiente fun-
cion: f(x) = 2x2 + 16x
Solucion
Tomando los puntos iniciales x1 = 1, x2 = 2,5 y x3 = 5, el metodo converge en cuatro
iteraciones, el valor optimo obtenido es x∗ = 1,60.
Figura 8: Valores por aproximacion cuadratico
2.3. Ajuste cubico
Este metodo esta basado en la aproximacion polinomial mediante un polinomio de
tercer grado de la funcion que se quiere minimizar. El esquema es similar al metodo
cuadratico. Se necesitan cuatro puntos iniciales, o cuatro valores de f(x), o valores de
f(x) y sus derivadas cada dos puntos.
13
Este metodo es de convergencia rapida, pero puede presentar errores en funciones no
unimodales.
Dados xk−1 y xk junto a f(xk−1), f′(xk−1), f(xk), y f ′(xk) es posible ajustar una
ecuacion cubica en los puntos. El punto xk+1 (mınimo) puede ser determinado como el
punto mınimo relativo de esta ecuacion cubica.
xk+1 = xk − (xk − xk−1)
[f ′(xk) + u2 − u1
f ′(xk)− f ′(xk−1) + 2u2
](13)
Donde:
u1 = f ′(xk−1) + f(xk)− 3f(xk−1)−f(xk)
xk−1−xk
u2 =√u21 − f ′(xk−1)f ′(xk)
La aplicacion de este metodo requiere que xk − 1 < xk y f ′(xk) > f ′(xk−1).
3. Metodo de descenso de mayor pendiente
Tambien se conoce como metodo del gradiente. Este metodo se pretende encontrar el
mınimo de la funcion f : Rn −→ R continua en sus primeras derivadas parciales .
3.1. Caso general
La direccion de busqueda utilizada en este metodo es el negativo de la pendiente en
cualquier punto particular xk ∈ Rn.
Sk = −∇f(xk) (14)
Desde esta direccion ofrece el descenso maximo en valores de la funcion, se le llama metodo
de maxima pendiente. En cada iteracion, se calcula la derivada en el punto actual y una
busqueda unidireccional se realiza en la negativa a esta direccion derivado para encontrar
el punto mınimo a lo largo de esa direccion. El punto mınimo se convierte en el punto
actual y la busqueda continua desde este punto. El procedimiento continua hasta que
se encuentre un punto que tiene una pequena pendiente suficiente vectorial. Los pasos
seguidos en el presente metodo se menciona a continuacion secuencialmente:
1. Comience con un punto inicial arbitraria xk ∈ Rn.
14
2. Encuentre la direccion de busqueda Sk comoSk = −∇f(xk)
3. Determinar la duracion optima paso λk en la direccion Sk y establecer xk+1 =
xk + λkSk = xk − λk∇f(xk)
4. Pruebe el nuevo punto xk+1, de optimalidad. Si xk+1 es el optimo, detener el proceso,
alternativamente ir al paso 5.
5. Ajuste el nuevo numero de la iteracion k = k + 1 y ir al paso 2.
Ejemplo 3.1. Minimize f(x) = 2x21 + x2
2 +2x1x2 + x1 − x2 a partir del punto x1 =
0
0
Solucion
Primera interacıon:
El gradiente de f viene dado por
∇f =
∂f
∂x1∂f
∂x2
=
1 + 4x1 + 2x2
−1 + 2x1 + 2x2
∇f(x1) =
1
−1
Por lo tanto,
S1 = −∇f(x1) =
−1
1
A continuacion , tenemos que encontrar la longitud optima paso λ1 para encontrar
x2. Para ello debemos minimizar f(x1+λ1S1) = f(
−λ1
λ1
) = λ21−2λ1 con respecto
a λ1. Desdedf
dλ1
= 0 en λ1 = 1 obtendrıamos
x2 = x1 + λ1S1 =
0
0
+ 1
−1
1
=
−1
1
Desde ∇f(x2) =
−1
−1
=
0
0
, el x2 no es optimo y, por tanto se requiere mas
iteraciones.
15
Segunda interaccion:
S2 = −∇f(x2) =
1
1
Para reducir al mınimo, debemos primero evaluar,
f(x2 + λ2S2) = f(
−1 + λ2
1 + λ2
) = 5λ22 − 2λ2 − 1. A continuacion establecemos
df
dλ2
= 0 y obtenemos λ2 =1
5, y entonces
x3 = x2 + λ2S2 =
−1
1
+1
5
1
1
=
−0,8
1,2
puesto que los componentes del gradiente en x3,
∇f(x3) =
0,2
−0,2
=
0
0
se procede a la siguiente iteracion.
Tercera interaccion:
S3 = −∇f(x3) =
−0,2
0,2
desde,
f(x3 + λ3S3) = f(
−0,8− λ3
1,2 + 0,2λ3
) = 0,04λ23 − 0,08λ3 − 1,2 establecemos ,
df
dλ3
= 0
que conduce a λ3 = 1.Por lo tanto
x4 = x3 + λ3S3 =
−0,8
1,2
+ 1
−0,2
0,2
=
−1
1,4
el gradiente en x4 esta dada por
∇f(x4) =
−0,2
−0,2
Desde ∇f(x4) =
0
0
, x4 no es el optimo y, por lo tanto debemos pasar a la
siguiente iteracion....
Este proceso se continua hasta que el punto optimo en, x∗ =
−1
1,5
es encontrado.
es decir, en x∗ =
−1
1,5
el ∇f(x∗) =
0
0
. Por lo tanto en x∗ la funcion f alcanza su
16
mınimo.
3.2. Caso cuadratico
Esencialmente, todas las caracterısticas importantes de convergencia local del metodo
de descenso de mayor pendiente se revelan investigando el metodo al aplicarlo a problemas
cuadraticos. Tengase la funcion cuadratica:
f(x) =1
2xTAx− xT b (15)
donde A es una matriz de nxn simetrica definida positiva, x ∈ Rn y b es un vector
tambien de Rn. Como A es definida positiva, todos sus valores propios son positivos.
Adems como A es definida positiva, resulta que f es estrictamente convexa.
El unico punto mınimo de f se puede hallar directamente, resolviendo el sistema lineal
Ax = b.
Ejemplo 3.2. Minimize f(x) = 2x21 + x2
2 + 2x1x2 + x1 − x2.
Solucion
Figura 9: Grafica del paraboloide.
f(x) = 2x21 + x2
2 + 2x1x2 + x1 − x2 =1
2
(x1 x2
)4 2
2 2
x1
x2
−(x1 x2
)−1
1
=⇒ x =
x1
x2
; b =
−1
1
;A =
4 2
2 2
17
se observa que△1 = 4 > 0 y△2 = 4 > 0 entoces la matriz A es definida positiva , entonces
la funcion f es estrictamente convexa. Para encontrar el mınimo de f bastara resolver el
sistema lineal Ax = b.4 2
2 2
x1
x2
=
−1
1
=⇒
4x1 + 2x2
2x1 + 2x2
=
−1
1
resolviendo se obtiene
x1
x2
=
−1
1, 5
en la cual la funcion f alcanza su mınimo.
18
Referencias
[1] Luenberger, D., (1989) Programacion lineal y no lineal, Mexico, Ed. Addison-Wesley
Iberoamericana.
[2] nptel.ac.in/courses/112101/dowloads/module-5-lecture-final
[3] http://agamenon.tsc.uah.es/Asignaturas/master/optimizacion/Programacion-no-
lineal.pdf
[4] http://intrawww.ing.puc.cl/siding/public/ingcursos/cursos-pub/descarga.phtml?id-
curso-ic=375yid-archivo=12407
19