Diana Aldea Mendeshome.iscte-iul.pt/~deam/html/slidesa4.pdf · Mestrado Matemática Financeira, Optimização, Aula 4 1 . Optimiza¸c˜ao multi-dimensional-M´etodos gradiente (gradiente

ISCTE/FCUL - Mestrado Matematica Financeira

Aula 4

15 de Janeiro de 2009 Ano lectivo: 2008/2009

Diana Aldea Mendes

Departamento de Metodos Quantitativos, IBS - ISCTE Business School

Gab. 207 AA, [email protected], http://iscte.pt/˜deam

Mestrado Matemática Financeira, Optimização, Aula 4

1

Optimizacao multi-dimensional

- Metodos gradiente (gradiente descendente, gradiente conjugado)

- Metodos de Newton e quase-Newton

- Metodo de Powell (non-gradiente search)

- Metodo dos mınimos quadrados (nao-linear) (Levenberg-Marquardt)


2

Nota-se que:

- Os computadores nao podem encontrar todas as solucoes

- Os computadores nao podem provar a ausencia de solucoes

- Os computadores nao podem provar a existencia de solucoes

- Os computadores nao podem provar a unicidade de uma solucao

http://www2.imm.dtu.dk/˜hbn/Software/ (Software by Hans Bruun Nielsen)


3

minx∈D

f (x) ←→ ∇f (x) = 0, ∇2f (x) definida positiva

x ∈ Rn, f : D ⊂ Rn→ R (1)

f (x) funcao objectivo (2)

∇f (x) =

"∂f

∂xi

#i=1,...,n

vector gradiente (3)

(derivadas parciais de primeira ordem) (4)

∇2f (x) = H (x) =

"∂2f

∂xi∂xj

#i,j=1,...,n

matriz Hessiana (5)

(derivadas parciais de segunda ordem) (6)


4

• A formulacao do problema de mınimo e muito simples, mas, apesar disto,nao existe um algoritmo perfeito. A arte de minimizar funcoes nao-lineares

consta em saber qual e o metodo a utilizar e como determinar se o metodo

escolhido converge para a solucao correcta. Em geral

- Utilizamos metodos iterativos que calculam uma sequencia de pontos x0, x1, ..... ∈Rn tal que f

¡xk+1

¢< f (xk) . O algoritmo termina quando ∇f (xk) < ε

para ε pre-definido

- Se f e fortemente convexa, isto e, ∃m > 0 tal que ∇2f (x) >> mI, ∀x ∈ Rn,entao existe um criterio de paragem definido por

k∇f (x)k ≤ 2mε ⇒ f (x)− f (x∗) ≤ ε


5

• Classificacao dos metodos de optimizacao nao-condicionada multidimen-sional

- Metodos analıticos: resolver ∇f (x) = 0 analiticamente

- Metodos directos: precisam so a computacao de f (x) em cada passo (Powellou DogLeg, Nelder-Mead)

- Metodos gradiente: requerem a computacao de ∇f (x) e f (x) em cada passo(gradiente descendente, gradiente conjugado)

- Metodos de segunda ordem: requerem a computacao de ∇2f (x) , ∇f (x) ef (x) em cada passo (Newton e quase-Newton)

- Outros metodos: arrefecimento simulado, algoritmos geneticos, etc...


6

Metodo de Powell

- Requere apenas o calculo de f (x) . Necessita de um grande numero de avaliacoes

da funcao objectivo, o que aumenta o custo computacional

- Ideia basica: considerar um numero elevado de vectores x e calcular o f (x)

associado. O vector correspondente ao menor valor f (x) sera considerado como

o valor optimo x.

- Melhor: seja x0 o ponto que aproxima inicialmente o minimizante de f (x) .

O proximo valor do minimizante, o ponto x1, obtem-se procurando sucessiva-

mente um minimizante de f ao longo de cada um dos vectores da base canonica

{e1, ..., en} de Rn. Este processo gera a sequencia de pontos

x0 = P0, P1, ..., PN = x1.


7

Ao longo de cada um dos vectores da base canonica, a funcao f torna ser so deuma variavel. Assim, minimizar f signifique aplicar os metodos de optimizacaounidimensional sobre intervalos onde a funcao e unimodal. O ponto x1 e deter-minado como sendo o ponto em qual o mınimo de f ocorre ao longo do vectorPN − P0. Como o vector PN − P0 e considerado ser uma direccao de inves-tigacao viavel, vai substituir um dos vectores direccao para a proxima iterada. Aiteracao e repetida para gerar uma sequencia de pontos {xk}k≥0 .

Algoritmo

1. P0 = xi

2. Para k = 1, ..., n encontre o valor de γk que minimiza f (P0 + γkUk) eescolha

Pk = Pk−1 + γkUk


8

3. i = i+ 1

4. Uj = Uj+1 para j = 1, ..., n− 1. Seja

Un = Pn − P0

5. Encontre o valor γ que minimiza f (P0 + γUn) . Escolha

xi = P0 + γUn

6. Repetir os passos (1)-(5).

onde

U = [UT1 ...U

Tn ] = [e

T1 ...e

Tn ].


9

Exemplo: Seja f (x, y) = cosx+sin y e seja x0 = (5.5, 2) . Determine os pontos

x1 e x2.

0

5

10

15

0

5

10

15-2

-1

0

1

2

2 4 6 8 10 12 14

2

4

6

8

10

12

14


10

Seja

U =

"1 00 1

#e P0 = x0 = (5.5, 2) . Para i = 1, a funcao f (P0 + γ1U1) = f ((5.5, 2) + γ1 (1, 0)) =

cos (5.5 + γ1)+sin 2 tem um mınimo em γ1 = −2.3584. Logo P1 = (3.1415, 2) .

Para i = 2, a funcao f (P1 + γ2U2) = f ((3.1415, 2) + γ2 (0, 1)) = cos (3.1415)+

sin (2 + γ2) tem um mınimo em γ2 = 2.7123. Logo P2 = (3.1415, 4.7123) .Seja

agora

UT2 = (P2 − P0)

T e U =

"0 −2.35841 2.7123

#.


11

A funcao

f (P0 + γU2) = f ((5.5, 2) + γ (−2.3584, 2.7123))= cos (5.5− 2.3584γ) + sin (2 + 2.7123γ)

tem um mınimo em γ = 0.9816. Logo x1 = (3.1848, 4.6626) .

Seja P0 = x1. Quando i = 1, a funcao

f (P0 + γ1U1) = f ((3.1848, 4.6626) + γ1 (0, 1))

= cos (3.1848) + sin (4.6626 + γ1)

tem um mınimo em γ1 = 0.0497. Logo P1 = (3.1484, 4.7123) .

Quando i = 2, a funcao

f (P1 + γ2U2) = f ((3.1848, 4.7123) + γ2 (−2.3584, 2.7123))= cos (3.1848− 2.3584γ2) + sin (4.7123 + 2.7123γ2)


12

tem um mınimo em γ2 = 0.0078. Logo P2 = (3.1662, 4.7337) .

Seja

UT2 = (P2 − P0)

T e U =

"−2.3584 −0.01852.7123 0.0710

#.

A funcao

f (P0 + γU2) = f ((3.1848, 4.6626) + γ (−0.0185, 0.0710))= cos (3.1848− 0.0185γ) + sin (4.6626 + 0.0710γ)

tem um mınimo em γ = 0.8035. Logo x2 = (3.1698, 4.7197) .

A funcao f (x, y) = cosx+ sin y tem um mınimo no ponto P = (π, 3π/2) .


13

Metodos gradiente ou metodos descendentes

Minimizacao ao longo de uma direccao - Problema geral

Minimizar uma funcao real de n variaveis reais, f , onde: f e regular, o seu

gradiente g = ∇f e conhecido e e dada um direccao descendente u.

Uma direccao u diz-se descendente para a funcao f em x se uTf 0 (x) < 0.

- Consideram-se iteracoes de forma

xk+1 = xk + λkuk,

onde uk e a direccao descendente investigada e λk e o comprimento de passo

obtido por uma procura unidimensional (faz decrescer a funcao f). Em todos


14

os metodos consideremos que f¡xk+1

¢< f (xk) , (descending condition) o que

obriga a convergencia para um ponto de mınimo, caso existe. O algoritmo ter-

mina quando satisfaz o crıterio de paragem. Tem convergencia linear e portanto

e um algoritmo bastante lento.

Problema: Dada uma funcao f (x) , x = (x1, ..., xn) ∈ Rn, um ponto inicial

x0 ∈ Rn e uma direccao u = (u1, ..., un) ∈ Rn, como minimizar a funcao f aolongo da direccao u?

Resposta: Comecamos com um ponto inicial x0 e procuramos um novo ponto

x = x0 + λ∗u

tal que a funcao

F (λ) = f (x0 + λu)


15

e minimizada quando λ = λ∗. Nesta situacao F (λ) e uma funcao so de uma

variavel (λ).

• Como escolher a direccao descendente:

• Nos metodos do gradiente conjugado nao linear, a direccao de investigacaoe de forma

uk = −gk + βkuk−1

ou seja hk = −∇f (xk) = gk, onde o escalar βk e escolhido de tal maneira

que o metodo reduz-se ao metodo linear dos gradientes conjugados, quando

a funcao e quadratica e a linha de investigacao e exacta.


16

• Uma outra classe de metodos define a linha (direccao) de investigacao por

uk = −B−1k gk

onde Bk e uma matriz regular (|Bk| 6= 0) e simetrica (bij = bji). Casosespeciais sao dados quando

Bk = I the steepest descent method

Bk = ∇2f (xk) = H (f (xk)) o metodo de Newton.

• Os metodos quase-Newton ou metricos variaveis sao tambem deste tipo,mas neste caso Bk depende ainda de Bk−1 e de xk−1.

Matlab: m-file opt steep.m

[xo,fo] = opt steep (f, x0, TolX, TolFun, alpha0, MaxIter)


17

Minimizacao ao longo de uma direccao - exemplo

Seja f (x) = f (x1, x2) = 1 + x1 − x2 + x21 + 2x22. Minimize f na direccao

u = (−2, 1) para o ponto inicial x0 = (0, 0) .

Definimos a linha de investigacao

x = x0 + λu = (0, 0) + λ (−2, 1) = (−2λ, λ)

e a nova funcao F, isto e

F (λ) = f (x0 + λu) = f (−2λ, λ) = 1− 3λ+ 6λ2.

O minimizante de F (λ) e obtido de F 0 (λ) = 0, isto e

F 0 (λ) = 12λ− 3 = 0⇒ λ∗ =1

4,


18

e como F 00 (λ∗) = 12 > 0, temos que λ∗ = 14 e um mınimo.

Tem-se entao que x∗ = x0 + λ∗u =³−12,

14

´e o mınimo de f (x) ao longo da

linha x = x0 + λu.

Mais, podemos mostrar que x∗ e o mınimo global da funcao f (x) . Escrevendo

f (x) = f (x1, x2) = 1 + x1 − x2 + x21 + 2x22 =

µx1 +

1

2

¶2+ 2

µx2 −

1

4

¶2+5

8

a ultima funcao tem curvas de nıvel (contorno) definidas por elipses centradas no

ponto de mınimo x∗ =³−12,

14

´. Observa-se que o mınimo ao longo da direccao


19

x = x0 + λu passa pelo centro³−12,

14

´.

05

1015

2025

0

10

20

300

100

200

300

400

Funco f (x1, x2) = 1 + x1 − x2 + x21 + 2x22


20

Metodo do gradiente conjugado (Fletcher-Reeves)

A introducao do metodo do gradiente conjugado por Fletcher-Reeves nos anos

1960 conduz a possibilidade de optimizar problemas nao lineares de larga es-

cala, pois so sao precissos O (n) operacoes por iteracao e pouco espaco para

armazenagem. Sao metodos simples e bastante faceis de implementar. Sao su-

periores aos metodos que nao utilizam informacao sobre o gradiente, mas sao

inferiores aos metodos de tipo Newton.

Considerando uma equacao da forma f(x) = 0, e claro que f(x) = 0 sse

f(x)f(x) = 0. Logo, se existirem, os zeros de f, sao os pontos de mınimo

absoluto de f2.


21

De forma semelhante, no caso de funcoes com varias variaveis, usando a norma

euclidiana, obtemos:

F (x) = 0 <=> ||F (x)||2 = 0 <=> F (x).F (x) = 0

e, se existirem, as solucoes de F (x) = 0 sao os pontos de mınimo absoluto de

f(x) = F (x).F (x).

Seja A uma matriz simetrica e definida positiva, e consideremos uma forma

quadratica auxiliar:

f (x) = a− bTx+1

2xTAx

que transforma vectores em numeros reais. Como a forma e quadratica, ha

apenas um vector que minimiza f e e exactamente o ponto crıtico, ou seja, a


22

solucao de f 0(x) = 0, e neste caso,

f 0(x) =1

2(AT +A)x− b = Ax− b.

Assim, se encontrarmos o ponto de mınimo, ele sera solucao do sistema linear

Ax = b.

Consideramos metodos iterativos de optimizacao de tipo investigacao de linha,

ou seja:

xn+1 = xn + anhn

de forma que haja uma direccao descendente, ou seja, f(xn+1) < f(xn). O

vector hn define a direccao de investigacao descendente.


23

Metodo do Gradiente

No caso do metodo do gradiente (ou declive maximo - steepest descent), a

direccao de descida escolhida e

hn = −∇f(xn) = b−Axn,

e neste caso (de sistemas lineares) e tambem designado por resıduo.

Resta encontrar o valor an que minimiza f , de entre os possıveis valores xn+ahn.

Encontramos o ponto de mınimo, derivando f (nesses pontos) em ordem a a,

ou seja,

d

da(f (xn + ahn)) = f 0(xn + ahn).hn

= (b−A(xn + ahn)).hn

= hn.hn − aAhn.hn


24

Assim, o valor mınimo an sera obtido com o zero da derivada,

hn.hn − anA hn.hn = 0 <=> an =hn.hn

A hn.hn.

Em conclusao, dado um vector inicial x0, o metodo do gradiente resume-se a

iteracao

xn+1 = xn + anhn = xn +hn.hn

hn.A hnhn com hn = b−Axn

Um criterio de paragem consiste em exigir que

||hn||2 = hn.hn < ε

com ε pequeno, notando que isso implica que Axn e proximo de b.


25

Metodo das Direccoes Conjugadas

Comecamos por definir direccoes conjugadas: Um conjunto de direccoes {h1, h2, ...}diz-se conjugado com respeito a uma matriz A simetrica e definida positiva se

hTi Ahj = 0 para qualquer i 6= j.

Com este produto interno, dois vectores dizem-se A-ortogonais se < hi, hj >

A = hi.Ahj = hTi Ahj = 0, como sinonimo diz-se que as direccoes hi e hj sao

conjugadas.

Seja N a dimensao da matriz A e sejam h1, h2, ..., hN direccoes conjugadas, que

constituem uma base A-ortogonal em RN. Se considerarmos hn como direccoesde descida, temos a iteracao

xn+1 = xn + anhn


26

e queremos agora encontrar o valor an que minimiza f , de entre os possıveis

valores xn + ahn.

De forma, semelhante, podemos obter

an =rn.hn

hn. A hn, com rn = b−Axn

e portanto o metodo de direccoes conjugadas e

xn+1 = xn +rn.hn

hn. A hnhn

Teorema: Um metodo de direccoes conjugadas atinge a solucao ao fim de N

iteracoes.


27

Metodo dos Gradientes Conjugados

Consideramos agora o caso particular do metodo das direccoes conjugadas, em

que elas sao obtidas atraves do gradiente. Recordamos que no caso linear o

gradiente e dado pelo resıduo rn = b−Axn.

Atraves de um processo de ortogonalizacao (ou melhor, A-ortogonalizacao) de

Gram-Schmidt, atraves dos sucessivos resıduos (gradientes) podemos construir

as direccoes hn que serao conjugadas (A-ortogonais).

Assim, podemos resumir o Metodo dos Gradientes Conjugados,

1. Dado x0 definimos h0 = r0 = b−Ax0 ,


28

2. Definimos xn+1 = xn + anhn com

an =rn.hn

hn. A hn

3. Definimos rn+1 = rn − anAhn e

hn+1 = rn+1 + bnhn, com bn =rn+1.rn+1rn.rn

.

4. Regressamos ao 2o passo, ate que sejam efectuados N passos.

Nota: Apesar de termos dito que o metodo atinge a solucao exacta ao fim de

N passos, um mau condicionamento da matriz podera impedir que a solucao

seja efectivamente obtida. Nesse caso ha que utilizar um criterio de paragem,

por exemplo, exigindo que o resıduo seja suficientemente pequeno.


29

(a). Metodo de Fletcher-Reeves (1964)

bn =rn+1.rn+1rn.rn

=f 0 (xn+1)

T f 0 (xn+1)

f 0 (xn)T f 0 (xn)

onde xprev e a iterada previa.

(b). Metodo de Polak-Ribiere (1971)

bn =(rn+1 − rn) .rn+1

rn.rn=

¡f 0 (xn+1)− f 0 (xn)

¢T f 0 (xn+1)f 0 (xn)T f 0 (xn)

Para uma funcao quadratica os dois metodos sao identicos.


30

Mtodo do gradiente conjugado


31

Em Matlab o programa mincg.m esta baseado neste metodo de optimizacao.

[res, noiter]=mincg(f, derf, ftau, x, tol)

onde f e a funcao a optimizar, derf sao as derivadas paciais de 1a ordem da

funcao (gradiente), ftau represente o metodo de investigacao de linhas, x a

condicao inicial e tol a tolerancia permitida.

De forma alternativa tem-se o m-file opt conjg.m

[xo,fo] = opt conjg(f,x0,TolX,TolFun,alpha0,MaxIter,KC)

Exemplo: Seja

A =

"2 −1−1 2

#.


32

Determine os vectores proprios de A e motra que sao A-conjugados.

Primeira vez determinam-se os valores proprios, isto e |A− λI| = 0⇐⇒ λ1 = 1

e λ2 = 3. Logo

(A− λI) v = 0⇐⇒"2− 1 −1−1 2− 1

# "v1v2

#=

"00

#⇐⇒ v1 =

³v11, v

12

´=³v11, v

11

´= v11 (1, 1) , ∀v11 ∈ R

⇐⇒"2− 3 −1−1 2− 3

# "v1v2

#=

"00

#⇐⇒ v2 =

³v21, v

22

´=³v21,−v21

´= v21 (1,−1) , ∀v21 ∈ R


33

Agora ³v1´T

Av2 =h1 1

i " 2 −1−1 2

# "1−1

#= 0

Exemplo: Aplicando o metodo das direccoes conjugadas, minimiza a seguinte

funcao quadratica minx1,x2∈R f (x1, x2) =12x

TAx− bTx+ c, onde

A =

"2 −1−1 2

#, b =

"38

#, c = 5 e x0 =

"00

#.

Calculamos os vectores conjugados de A (exemplo anterior) h0 = (1, 1) e h1 =

(1,−1).


34

Agora

r0 = b−Ax0 =

"38

#−"2 −1−1 2

# "00

#=

"38

#6= 0

a0 =rT0 h0

hT0Ah0=11

2

x1 = x0 + a0h0 =h112

112

iTr1 = b−Ax1 =

"38

#−"2 −1−1 2

# "112112

#=

"−5252

#

a1 =rT1 h1

hT1Ah1=5

6

x2 = x1 + a1h1 =

"112112

#−"5656

#=

"143143

#

r2 = b−Ax2 =

"38

#−"2 −1−1 2

# "143143

#=

"−53103

#.


35

Exemplo: Aplicando o metodo do gradiente conjugado (Fletcher-Reeves), min-

imiza a seguinte funcao quadratica

minx1,x2∈R

f (x1, x2) = x21 − x1x2 + 3x22,

onde o ponto inicial e x0 = (1, 2) .

Calculamos o vector gradiente

∇f (x) = f 0 (x) =

"2x1 − x2−x1 + 6x2

#logo

f 0 (x0) =

"011

#e r0 = h0 =

"011

#


36

Agora

x1 = x0 + a0h0 =h1 1

6

iTe f 0 (x1) =

"1160

#

b1 =f 0 (x1)

T f 0 (x1)

f 0 (x0)T f 0 (x0)

=1

36

h1 = f 0 (x1) + b1h0 =

"116−1136

#

x2 = x1 + a1h1 =

"00

#.

Exemplo: Determinar um mınimo local da funcao

f (x, y) = 0.5(x4 − 16x2 + 5x) + 0.5(y4 − 16y2 + 5y)


37

-4 -3 -2 -1 0 1 2 3 4-4

-3

-2

-1

0

1

2

3

4

05

1015

20

05

10

1520

-80

-60

-40

-20

0

20

Funcao f801.m

>> x1=mincg(’f801’,’f801pd’,’ftau2cg’, x0, 0.000005)


38

> number of iter= 6, > Solution 2.7468 -2.9035

>> x=-4:0.1:4;y=-4:0.1:4; [X,Y]=meshgrid(x,y);

>> z=0.5.*(X.ˆ4-16.*X.ˆ2+5.*X)+0.5.*(Y.ˆ4-16.*Y.ˆ2+5.*Y);

>> x1=[0 1.691 -2.560 -2.909 -2.903 -2.903]; y1=[0.5 -2.948 -3.210 -2.893

-2.903 -2.903];

>> figure; axis([-4 4 -4 4 -80 20]); contour(-4:0.1:4, -4:0.1:4, z,15)

>> hold on; plot(x1,y1,x1,y1,’o’)


39

Metodo de Newton

O metodo de Newton inicıa uma classe importante de algoritmos que, para serem

aplicados, requerem a computacao do vector gradiente

g = ∇f (x) =

⎡⎢⎢⎢⎢⎢⎣∂f

∂x1(x)

...∂f

∂xn(x)

⎤⎥⎥⎥⎥⎥⎦ , onde f : D ⊂ Rn→ R e x = (x1, ..., xn)


40

e da matriz Hessiana

H (f (x)) = ∇2f (x) =

⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

∂2f

∂x21(x)

∂2f

∂x1∂x2(x) ...

∂2f

∂x1∂xn(x)

∂2f

∂x2∂x1(x)

∂2f

∂x22(x) ...

∂2f

∂x2∂xn(x)

... ... . . . ...∂2f

∂xn∂x1(x)

∂2f

∂xn∂x2(x) ...

∂2f

∂x2n(x)

⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦.

Teorema: Suponhamos que f : D ⊂ Rn → R e duas vezes diferenciavel e

x∗ ∈ Rn satisfaz

1. ∇f (x∗) = 0


41

2. ∇2f (x∗) e definida positiva (em particular, nao-singular)

3. ∇2f e Lipschitz contınua numa vizinhanca do ponto x∗.

Entao x∗ e um mınimo local de f e para qualquer x0 suficientemente proximo

de x∗, o metodo de Newton define uma sequencia que converge (local) quadrati-camente para x∗.

Nota: O metodo ainda converge se a matriz Hessiana e semidefinida positiva e

singular.

O metodo de Newton determina um modelo quadratico para a funcao objectivo

em torno da iterada corrente xk definida por

qk (hk) = f (xk) +∇Tf (xk)hk +1

2hTk∇2f (xk)hk.


42

Na versao basica do metodo de Newton, a proxima iterada e obtida a partir

do minimizante de qk. Quando a matriz Hessiana e definida positiva, o modelo

quadratico tem um unico minimizante que pode ser obtido resolvendo o seguinte

sistema simetrico (n× n)

∇2f (xk)hk = −∇f (xk) ⇔ hk = −³∇2f (xk)

´−1∇f (xk)Agora, a nova iterada vai ser

xk+1 = xk + hk = xk −³∇2f (xk)

´−1∇f (xk)Como ja referido a convergencia (local) e garantida se o ponto de partida e

suficientemente proximo de um minimizante local x∗. O criterio de paragem e

dado por

α2

2≤ ε onde α (x) =

µ∇Tf (x)

³∇2f (x)

´−1 ∇f (x)¶1/2 = kx− x∗k


43

Figura 1: Metodo de Newton. Caso (a), convergencia imediata para p mınimo

(1 iterada) e caso (b) convergencia ao fim de 10 iteradas.


44

O algoritmo de Newton se funciona bem, funciona muito bem. Com tudo isto

nao e o metodo ideal, pois requere a computacao da matriz hessiana em cada

iterada, tambem como a resolucao do sistema linear que envolve a hessiana.

Falha facilmente se a matriz hessiana nao e definida positiva ou regular.

Nestes casos (quando a matriz hessiana nao e definida positiva ou regular)

convem substituir a matriz Hessiana H por uma nova matriz H = H + E.

O metodo de Levenberg-Marquardt pode ser utilizado com sucesso, fazendo a

substituicao: H = H + γI, com I matriz identidade. O papel de γ e manter a

matriz H definida positiva.

Matlab: m-file newtons.m

[x,fx,xx] = newtons(f,x0,TolX,MaxIter,varargin)


45

Exemplo: Minimizar a funcao

f (x) = f (x1, x2) =1

2x21

Ãx216+ 1

!+ x2 arctanx2 −

1

2ln³x22 + 1

´.

010

2030

05101520250

10

20

30

40

50

60

70


46

Precisamos do gradiente e da matriz Hessiana

∇f (x) =

⎡⎢⎢⎢⎣x313+ x1

arctanx2

⎤⎥⎥⎥⎦ e ∇f (x) =

⎡⎢⎣ x21 + 1 0

01

1 + x22

⎤⎥⎦

A tabela seguinte da os resultados de iteracao quando x0 = (1, 0.7) . Ha con-

vergencia local quadratica.


47

Mudando a condicao inicial, nomeadamente x0 = (1, 2) , o metodo de Newton

comporta-se muito mal (nao ha convergencia global), como pode ser visto na

proxima tabela

Na maioria dos casos, o metodo basico de Newton nao converge e para se obter

bons resultados e preciso modificar o algoritmo. Basicamente, ha dois metodos

para modificar o algoritmo de Newton em ordem a obter convergencia:


48

1. Abordagem baseada numa investigacao de linhas (direccoes) (modifica a

direccao da linha de investigacao para obter uma outra direccao descendent

para f)

2. Abordagem baseada numa regiao de confianca (utiliza a funcao quadratica

original, mas condiciona-se que a nova iterada pertencer a uma vizinhanca

da iterada corrente)

Estas tecnicas sao adequadas se o numero de variaveis da funcao objectivo nao e

muito elevado e se a matriz Hessiana e acessıvel e facil de calcular. Os algoritmos

ficam nao-alterados se a matriz Hessiana vem substituıda por uma boa aprox-

imacao sua. Existem dois tipos de metodos que aproximam a matriz Hessiana,

nomeadamente: Aproximacoes com diferencas e Metodos quase-Newton


49

Metodos Quase-Newton ou metodos metricos variaveis

Podem ser utilizados quando a matriz Hessiana e difıcil de calcular ou demoramuito tempo para ser avaliada. Este metodo constroi gradualmente uma matrizHessiana aproximada utilizando informacoes a partir do gradiente avaliado paraquase todas as iteradas anteriores visitadas pelo algoritmo. Consta de dois passosfundamentais

- Determinacao de uma direccao de investigacao

- Escolha do metodo de investigacao da linha

Dada a iterada corrente xk e a matriz Hessiana aproximada Bk em xk, a solucaodo sistema linear

Bkhk = −∇f (xk) ⇔ hk = −B−1k ∇f (xk)


50

gera uma direccao hk. A proxima iterada encontra-se fazendo uma investigacao

linear sobre hk e considerando

xk+1 = xk + αkhk,

onde o comprimentos de passo αk satisfaz as condicoes de Wolfe, isto e,

f (xk + αkhk) ≤ f (xk) + σ1αk∇Tf (xk)hk∇Tf (xk + αkhk)hk ≤ σ2∇Tf (xk)hk

onde 0 < σ1 < σ2 < 1.

Para obter a aproximacao Bk+1 a partir de Bk e precisso considerar o Teorema

Fundamental de Calculo Integral. Se definimos

sk = xk+1 − xkyk = ∇f

¡xk+1

¢−∇f (xk)


51

entao (Z 10∇2f (xk + tsk) dt

)media da Hessiana sobre o segmento [xk,xk+sk]

sk = yk.

A partir dessa observacao podemos obter a aproximacao Bk+1 imitando o com-portamento da matriz ∇2f e considerando a condicao de quase-Newton

Bk+1sk = yk.

Ao fim de cada passo a aproximacao da matriz Hessiana vem actualizada. Amais comum (e utilizada) famılia de actualizacoes consideradas no metodo dequase-Newton (para determinacao da direccao de investigacao) e a de Broydende rang 2, isto e

Bk+1 = Bk −Bksk (Bksk)

T

sTk Bksk+yky

Tk

yTk sk+ φk[s

Tk Bksk]vkv

Tk ,


52

onde

φk ∈ [0, 1] e vk ="

ykyTk sk

− BksksTk Bksk

#.

Para φk = 0 tem-se a actualizacao de Broyden-Fletcher-Goldfarb-Shanno (BFGS)

e para φk = 1 tem-se a actualizacao de Davidon-Fletcher-Powell (DFP).

Aplicando qualquer uma dessas actualizacoes a matriz Hessiana aproximada per-

manence definida positiva e portanto a direccao de procura e sempre uma di-

reccao descendente. Sao algoritmos que convergem rapidamente e evitam a

computacao das derivadas de segunda ordem.


53

Matlab

fminunc e o m-file que determine extremos livres de uma funcao real de varias

variaveis reais.

>> x=fminunc(’fname’,x0)

Inicia em x0 e tenta encontrar o mınimo local x da funcao ’fname’ (definida

como m-file tambem)

Exemplo

>>x = fminunc(’ffdi’,[2 3]) % sem gradiente


54

> f = -0.2750

...

> f = -2.0000

Optimization terminated: relative infinity-norm of gradient less than options.TolFun.

x = 3.1416 4.7124

Para minimizar esta funcao ja com o gradiente dado modificamos a funcao

como a seguir (indicando no comando fminunc que o gradiente esta disponıvel

utilizando OPTIONS)


55

>>x = fminunc(’fname’, x0, options);

>> options=optimset(’GradObj’,’on’); x0=[2 3]

>> [x,fval]=fminunc(’dffdi’, x0, options)

Optimization terminated: first-order optimality less than OPTIONS.TolFun,

and no negative/zero curvature detected in trust region model.

x = 3.1416 10.9956

fval = -2


56

Metodo dos mınimos quadrados (problema nao-linear)

Consideremos, de novo, um conjunto de pontos x0, ..., xn a que estao associados,

respectivamente, os valores f(x0), ..., f(xn). Temos que considerar agora uma

classe de funcoes, entre as quais vamos tentar encontrar a que ”melhor aproxima”

aquele conjunto de valores, nos pontos dados. Vamos concentrar em funcoes da

forma:

g(x) = a0f0(x) + ...+ amfm(x)

em que f0, ..., fm sao funcoes base (linearmente independentes), e sao conheci-

das.

Neste caso, apenas teremos que determinar os parametros a0, ..., an, de forma

que a soma quadratica das diferencas entre os f(xi) e os g(xi) seja mınima. Faz


57

entao sentido introduzir a distancia ||f − g|| em que

||u||2 =nXi=0

u2 (xi)

a que esta associada o produto interno

< u, v >=nXi=0

u (xi) v (xi) .

A norma e o produto interno estao bem definidos para funcoes que assumem

quaisquer valores nos pontos x0, ..., xn.

Pretende-se pois encontrar os parametros a0, ..., an que minimizem a distancia

entre f e g , isto e:

Q = ||f − g||2 =< f − g, f − g >


58

Para obtermos esse mınimo, comecamos por procurar os valores a0, ..., am tais

que todas as derivadas parciais de Q sejam nulas, isto e:

∂Q

∂aj(a0, ..., am) = 0, para j = 0, ...,m.

Calculamos a derivada parcial, usando as propriedades de derivacao do produto

interno:

∂Q

∂aj=

∂

∂aj< f − g, f − g >=

*∂

∂aj(f − g) , f − g

++

*f − g,

∂

∂aj(f − g)

+

= 2

*f − g,

∂

∂aj(f − g)

+= −2

*f − g,

∂

∂ajg

+.

Por outro lado∂g

∂aj=

∂

∂aj(a0φ0 + ...+ amφm) = φj


59

e assim obtemos, para cada j de 0 ate m:Df − g, φj

E= 0

Podemos ainda substituir a expressao de g e obtemos um sistema linear:

nXi=0

ai < φi, φj >=< f, φj > para cada j = 0, ...,m

designado por sistema normal.

Teorema: Se as funcoes base φ0, ..., φm forem linearmente independentes, a

matriz do sistema normal e definida positiva.

Observacoes:

1) A matriz Hessiana de Q coincide justamente com a matriz do sistema normal.

Fica assim justificado que a solucao do sistema normal, tratando-se de um ponto


60

crıtico de Q, e como a matriz Hessiana e definida positiva, seja o mınimo do

funcional Q.

2) Como a matriz e simetrica e definida positiva, um metodo apropriado para

resolver o sistema normal e o metodo de Cholesky.

Mais geral: Seja f : Rn→ Rm, com m ≥ n. Objectivo: minimizar kf (x)k , ouequivalente, encontrar um x∗, tal que x∗ = minx {F (x)} onde

F (x) =1

2

mXi=1

(fi (x))2 =

1

2kf (x)k2 = 1

2fT (x) f (x) .

Os problemas dos mınimos quadrados podem ser resolvidos pelos metodos usuais

de optimizacao ou pelos metodos dos mınimos quadrados que se tornam mais

efficientes


61

Temos F 0 (x) = J (x)T f (x) e

F 00 (x) = J (x)T J (x) +mXi=1

fi (x) f00i (x) .

Metodo de Levenberg-Marquardt

O passo hlm e definido por³JTJ + μI

´hlm = −JTf.

A principal dificuldade em implementar este algoritmo consta em encontrar uma

estrategia efectiva para controlar o tamanho de μ em cada iteracao de tal forma

que sera eficiente para um conjunto grande de problemas. O metodo utilizado

neste algoritmo consta na medicao da nao linearidade relativa de f (x) utilizando

uma soma linear de quadrados. Nao procura explicitamente a direccao de inves-

tigacao o que torna o algoritmo bastante rapido e exacto.


62

Algoritmo

Iniciar k = 0; υ = 2; x = x0; A = J (x)T J (x) ; g = J (x)T f (x)

found = (kgk∞ ≤ ε1) ; μ = τ max {aii}while (not found) e (k < kmax)

k = k + 1; resolver (A+ μI)hlm = −gif khlmk ≤ ε2 (kxk+ ε2)

found = true // else

xnew = x+ hlm; ρ =F (x)− F (xnew)

L (0)− L (hlm)if ρ > 0

x = xnew; A = J (x)T J (x) ; g = J (x)T f (x)

found = (kgk∞ ≤ ε1)

μ = μ maxn1/3, 1− (2ρ− 1)3

o; υ = 2

else μ = μν; ν = 2ν

end


63

Matlab Optimization Toolbox - lsqnonlin.m

>> x=lsqnonlin(fun,x0)

>> function F = lsqDi(x,a)

>> F = [ 2*x(1) - exp(a*x(1)) -x(1) - exp(a*x(2)) x(1) - x(2) ];

>> a = -1; x = lsqnonlin(@(x) lsqDi(x,a),[1;1])

Optimization terminated: relative function value changing by less than OP-

TIONS.TolFun.


64

x = 0.2983 0.6960

05

1015

20

0

20

40

60-80

-60

-40

-20

0

20

Funcao lsqDi.m


65

Documents

Diana Aldea Mendeshome.iscte-iul.pt/~deam/html/slidesa4.pdf · Mestrado Matemática Financeira, Optimização, Aula 4 1 . Optimiza¸c˜ao multi-dimensional-M´etodos gradiente (gradiente