Conf 6 Metodos de Descenso-Resumen

ALGORITMOS PARA PROBLEMAS DE

OPTIMIZACIÓN SIN RESTRICCIONES

MULTIDIMENSIONALES

Prof. Jaime CarrascoMétodos de Optimización

Clase 7

Primavera 2014

Prof. Jaime Carrasco Métodos de Optimización Clase 7 Universidad Mayor

TEOREMA DE TAYLOR MULTIDIMENSIONAL

El teorema de Taylor a�rma que si

f : Rn ! R es de clase C1 en x , entonces

f (x + d) � f (x) +rf (x)T d + o (kdk)

f : Rn ! R es de clase C2 en x , entonces

f (x + d) � f (x) +rf (x)T d + 12dTr2f (x) d + o

�kdk2

�La notación o (�) signi�ca:

limkdk!0

o (kdk)kdk = 0, lim

kdk!0

o�kdk2

�kdk2

= 0.


DIRECCIÓN DE DESCENSO

Si x es un mínimo local de f 9ε > 0, tal que

f (x + d) < f (x) , 8d 2 B (0, ε) ,

luego, por Taylor,

f (x + d) � f (x) +rf (x)T d + o (kdk) < f (x), rf (x)T d + o (kdk) < 0.

Tomando kdk su�cientemente pequeña, va ha implicar querf (x)T d < 0.Por otro lado, si rf (x)T d < 0, para cierta dirección d 2 Rn ,vamos a tener

f (x + d)� f (x)kdk � rf (x)T d

kdk +o (kdk)kdk � rf (x)T d

kdk < 0,

f (x + d)� f (x)kdk < 0, kdk < ε , f (x + d)� f (x) < 0, 8d 2 B (0, ε)


DIRECCIÓN DE DESCENSO

DEFINICIÓN

Diremos que d es una dirección de descenso en x si cumplerf (x)T d < 0.

Dos ejemplos clásicos:

Dirección de Máximo Descenso:

d = �rf (x)

Dirección de Newton:

d = �hr2f (x)

i�1rf (x) , r2f (x) � 0

¿Se le ocurre alguna otra?


MÉTODO GENERAL DE DESCENSO

ALGORITMO

1 Tomamos x0 2 Rn y una tolerancia ε > 0, k = 0.

2 Hacemos gk = rf (xk ).Si kgkk < ε. Entonces xk lo tomamos como la aproximación almínimo.Si kgkk > ε. Entonces vamos al paso 3.

3 Dado un punto xk 2 Rn , hallar una dirección de descenso dk , i.e.,tal que

rf (xk ) dk < 0Esta dirección siempre existe, a no ser que rf (xk ) = 0. En tal casoxk es posible mínimo

4 Hallar un paso λk tal que

f (xk + λdk ) < f (xk )

5 Hacer, xk+1 = xk + λkdk



ALGORITMO

1 Tomamos x0 2 Rn y una tolerancia ε > 0, k = 0.2 Hacemos gk = rf (xk ).Si kgkk < ε. Entonces xk lo tomamos como la aproximación almínimo.Si kgkk > ε. Entonces vamos al paso 3.




f (xk + λdk ) < f (xk )




ALGORITMO





f (xk + λdk ) < f (xk )




ALGORITMO





f (xk + λdk ) < f (xk )




ALGORITMO





f (xk + λdk ) < f (xk )



MÉTODOS DE DESCENSODISTINTAS ELECCIONES DE DIRECCIÓN

La condición, kgkk < ε (numéricamente) () gk = rf (xk ) = 0(teóricamente).

La dirección de descenso da a origen a distintos métodos:

dk =

8>>>>>>>><>>>>>>>>:

�rf (xk ) �! Máximo Descenso

�hr2f (xk )

i�1rf (xk ) �! Newton Puro

�hr2f (xk ) + αI

i�1rf (xk ) ,α > 0 �! Newton Modi�cado

�Hkrf (xk ) �! Quasi-Newton

Cuando r2f (xk ) � 0, escogemos α > 0 tal que r2f (xk ) + αI � 0(Newton Modi�cado).





dk =

8>>>>>>>><>>>>>>>>:


�hr2f (xk )


�hr2f (xk ) + αI








dk =

8>>>>>>>><>>>>>>>>:


�hr2f (xk )


�hr2f (xk ) + αI





MÉTODOS DE DESCENSOMÉTODOS DE QUASI-NEWTON

En los métodos de Quasi-Newton, la matriz Hk es una aproximación de

la matrizhr2f (xk )

i�1.

DFP (Davidon-Fletcher-Powell)

Hk+1 = Hk +pkpTkpTk qk

�HkqkqTk HkqTk Hkqk

,

BFGS (de Broyden-Fletcher-Goldfarb-Shanno)

Hk+1 = Hk +

1+

qTk HkqkqTk pk

!pkpTkpTk qk

�pkqTk Hk +Hkqkp

Tk

pTk qk

donde pk+1 = xk+1 � xk y qk+1 = gk+1 � gk .


MÉTODOS DE DESCENSO¿COMÓ CALCULAMOS EL PASO?... DOS FORMAS...

Llamemos ϕ (λ) = f (xk + λdk ), luego ϕ : R �! R

1 Busqueda lineal exacta (BLE):

minλ�0

ϕ (λ) = minλ�0

f (xk + λdk ) �! λk

2 Busqueda lineal Inexacta (BLI):Dados 0 < α < β < 1. Se busca un λ tal que satisfaga (A) y (W ):

(A) Armijo:ϕ (λ) � ϕ (0) + αλϕ0 (0)

(W ) Wolfe:ϕ0 (λ) � βϕ0 (0) .

Obtenemos un conjunto de valores para λk , acotados inferior ysuperiormente.


EJEMPLOANÁLISIS DEL PROBLEMA

EJEMPLO

Consideremos el siguiente problema:

min f (x1, x2) = x21 + x

22 x1 � 3x1

Busquemos los puntos críticos:

rf (x1, x2) =�2x1 + x22 � 3

2x1x2

�=

�00

�

�! x1 = 0 o x2 = 0

�!�0,�

p3�,�32, 0�.


EJEMPLOANÁLISIS DEL PROBLEMA

Además

r2f (x1, x2) =�

2 2x22x2 2x1

�r2f

�0,�

p3�=

�2 �2

p3

�2p3 0

�� 0 (ni � 0)

r2f�32, 0�=

�2 00 3

�� 0

Por lo tanto, el punto�32 , 0�satisface condiciones su�cientes de segundo

orden, luego es un mínimo.


EJEMPLOAPLICANDO EL MÉTODO DE MÁXIMO DESCENSO

Recordemos que f (x1, x2) = x21 + x22 x1 � 3x1.

Primera Iteración (k = 0)

1 Tomemos x0 = (0, 1).

2 d0 = �rf (0, 1) = � (�2, 0)T = (2, 0), krf (0, 1)k = 2 (sepuede comparar con una tolerancia ε).

3 Hagamos una BLE:ϕ (λ) = f ((0, 1) + λ (2, 0)) = 4λ2 � 4λ

minλ�0

ϕ (λ) �! ϕ0 (λ) = 8λ� 4 = 0 �! λ0 =12

4 x1 = x0 + λ0d0 = (0, 1) + 12 (2, 0) = (1, 1).





1 Tomemos x0 = (0, 1).



minλ�0

ϕ (λ) �! ϕ0 (λ) = 8λ� 4 = 0 �! λ0 =12

4 x1 = x0 + λ0d0 = (0, 1) + 12 (2, 0) = (1, 1).





1 Tomemos x0 = (0, 1).



minλ�0

ϕ (λ) �! ϕ0 (λ) = 8λ� 4 = 0 �! λ0 =12

4 x1 = x0 + λ0d0 = (0, 1) + 12 (2, 0) = (1, 1).





1 Tomemos x0 = (0, 1).



minλ�0

ϕ (λ) �! ϕ0 (λ) = 8λ� 4 = 0 �! λ0 =12

4 x1 = x0 + λ0d0 = (0, 1) + 12 (2, 0) = (1, 1).



Segunda Iteración (k = 1)

2. k = 1, rf�x1�= rf (1, 1) = (0, 2), krf (1, 1)k = 2,

d1 = � (0, 2) = (0,�2).

3. Hagamos una BLI: (A) : Tomemos α = 0.1 y β = 0.9ϕ (λ) = f

�x1 + λd1

�= f (1, 1� 2λ) = (1� 2λ)2 � 2,

ϕ0 (λ) = �4 (1� 2λ)

ϕ (λ) � ϕ (0) + αλϕ0 (0)

(1� 2λ)2 � 2 � �1+ 0.1λ (�4)

De aquí se concluye que

4λ2 � 3. 6λ � 0() λ1 � 3.64= 0. 9




2. k = 1, rf�x1�= rf (1, 1) = (0, 2), krf (1, 1)k = 2,

d1 = � (0, 2) = (0,�2).3. Hagamos una BLI: (A) : Tomemos α = 0.1 y β = 0.9

ϕ (λ) = f�x1 + λd1

�= f (1, 1� 2λ) = (1� 2λ)2 � 2,

ϕ0 (λ) = �4 (1� 2λ)

ϕ (λ) � ϕ (0) + αλϕ0 (0)

(1� 2λ)2 � 2 � �1+ 0.1λ (�4)

De aquí se concluye que

4λ2 � 3. 6λ � 0() λ1 � 3.64= 0. 9




3. ...Para la condición de Wolfe (W ), tenemos:

ϕ0 (λ) � βϕ0 (0)

�4 (1� 2λ) � 0.9 � (�4)

4λ� 0.2 � 0() λ1 � 0.24= 0.05

Se concluye que λ1 2 [0.05, 1. 05]. Tomemos λ1 = 12 (que justamente

ϕ�

λ1�= 0, i.e. es el paso de BLE).

4. x2 = x1 + λ1d1 = (1, 0).




3. ...Para la condición de Wolfe (W ), tenemos:

ϕ0 (λ) � βϕ0 (0)

�4 (1� 2λ) � 0.9 � (�4)

4λ� 0.2 � 0() λ1 � 0.24= 0.05

Se concluye que λ1 2 [0.05, 1. 05]. Tomemos λ1 = 12 (que justamente

ϕ�

λ1�= 0, i.e. es el paso de BLE).

4. x2 = x1 + λ1d1 = (1, 0).


EJEMPLOAPLICANDO EL MÉTODO DE NEWTON

A partir del último punto encontrado con el método de máximo descenso,apliquemos Newton Puro:


1 Hacemos x0 = (1, 0)T , k = 0.

2 rf�x0�= (�1, 0),

rf �x0� = 1, x0 no es un punto crítico,luego vamos al paso 3.

3 Calculamos x1:

r2f�x0�=

�2 00 2

�� 0

x1 = x0 �hr2f

�x0�i�1

rf�x0�

x1 =

�10

��2 00 2

��1 � �10

�=

� 320

��! x1 = x�.





1 Hacemos x0 = (1, 0)T , k = 0.2 rf

�x0�= (�1, 0),


3 Calculamos x1:

r2f�x0�=

�2 00 2

�� 0

x1 = x0 �hr2f

�x0�i�1

rf�x0�

x1 =

�10

��2 00 2

��1 � �10

�=

� 320

��! x1 = x�.





1 Hacemos x0 = (1, 0)T , k = 0.2 rf

�x0�= (�1, 0),


3 Calculamos x1:

r2f�x0�=

�2 00 2

�� 0

x1 = x0 �hr2f

�x0�i�1

rf�x0�

x1 =

�10

��2 00 2

��1 � �10

�=

� 320

��! x1 = x�.


EJEMPLOAPLICANDO EL MÉTODO DE NEWTON MODIFICADO


1 x0 = (0, 1), k = 0.

2 Sabemos que este punto no es óptimo, así que vamos al paso 3.3 Tenemos que:

r2f�x0�=

�2 22 0

�� 0 y es singular

Luego debemos encontrar un α0 > 0, tal que�2 22 0

�+ α0

�1 00 1

�� 0 �! α0 = 2

d0 = ��4 22 2

��1 � �20

�=

�1�1

�




1 x0 = (0, 1), k = 0.2 Sabemos que este punto no es óptimo, así que vamos al paso 3.

3 Tenemos que:

r2f�x0�=

�2 22 0



�+ α0

�1 00 1

�� 0 �! α0 = 2

d0 = ��4 22 2

��1 � �20

�=

�1�1

�




1 x0 = (0, 1), k = 0.2 Sabemos que este punto no es óptimo, así que vamos al paso 3.3 Tenemos que:

r2f�x0�=

�2 22 0



�+ α0

�1 00 1

�� 0 �! α0 = 2

d0 = ��4 22 2

��1 � �20

�=

�1�1

�



...Primera Iteración (k = 0)

4. Hagamos una BLE:ϕ (λ) = f

�x0 + λd0

�= f (λ, 1� λ) = λ2 + (1� λ)2 λ� 3λ

Detengámonos un momento, para encontrar el paso λ0, debemosresolver ecuación

ϕ0 (λ) = 0 (�! λ0 = 1. 548 6)

ϕ0 (λ) no siempre es sencilla (por ejemplo, un polinomio, cuyo gradoes � 2), y por ende encontrar los ceros en forma algebraica, puedeser muy di�cultoso. Ahora bién, existen una cantidad de métodosunidimensionales para resolver este problema muy e�cientes.Algunos de ellos son: Método de Bisección, Método deNewton-Bisección, Método de Falsa posición, entre otros. Tarea:Investigar los métodos mencionados.


MÉTODO DE BISECCIÓN

ALGORITMO

1 Encontrar a0 y b0 en [a, b] tales que f (a0) < 0 y f (b0) > 0. Si esono es posible, el mínimo de f se encuentra en uno de los extremos ao b. Poner k = 0.

2 Calcular el punto medio xkm =ak+bk2 y calcular f 0

�xkm�.

3 Si f 0�xkm�> 0, poner ak+1 = ak , bk+1 = xkm , e ir al paso 4.

Si f 0�xkm�< 0, poner ak+1 = xkm , bk+1 = bk , e ir al paso 4.

Si f 0�xkm�= 0, xkm es el mínimo de f en [a, b]. Parar.

4 Poner k + 1 �! k, e ir al paso 2.



ALGORITMO



�xkm�.







ALGORITMO



�xkm�.







ALGORITMO



�xkm�.






MÉTODO DE BISECCIÓNBUSCANDO EL PASO

El grá�co de la función g (λ) := ϕ0 (λ) = 3λ2 � 2λ� 2 es:

4 2 0 2 4

20

40

60

80

x

y

Puesto que ϕ0 (0) = �2 < 0 y ϕ0 (2) = 6 > 0,1 Tomamos a0 = 0 y b0 = 2, i.e., buscamos el cero de ϕ0 en [0, 2],k = 0.

2 Luego calculamos x0 = a0+b02 = 1. Calculamos ϕ0

�x0�= �1 < 0.

3 Si ϕ0�x0�= �1 < 0, hacemos a1 = x0 = 1 y b1 = b0 = 2. (Ir al

paso 2)4 k = k + 1.




4 2 0 2 4

20

40

60

80

x

y



�x0�= �1 < 0.


paso 2)4 k = k + 1.




4 2 0 2 4

20

40

60

80

x

y



�x0�= �1 < 0.


paso 2)

4 k = k + 1.




4 2 0 2 4

20

40

60

80

x

y



�x0�= �1 < 0.


paso 2)4 k = k + 1.


Documents

Conf 6 Metodos de Descenso-Resumen