Newton

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1685 palavras )
  • Download(s) : 0
  • Publicado : 20 de novembro de 2012
Ler documento completo
Amostra do texto
´
Analise do M´todo de Newton com
e
Busca Linear Hibridizado com o M´todo
e
de Gradiente para Otimiza¸˜o de
ca
Problemas Bidimensionais
Raimundo Augusto Rego Rodrigues J´nior
u
rjunior@iprj.uerj.br
Nova Friburgo-RJ, Brazil

11 de Setembro - 2012

1

Introdu¸˜o
ca

O trabalho mostrar´ o desempenho do M´todo de Newton com Busca Linear
a
e
Hibridizado com o M´todo deGradiente. Este m´todo ´ classificado como detere
e
e
min´
ıstico pelo fato de fazer uso das informa¸oes de derivada (Vetor Gradiente e

Matriz Hessiana. Segundo Brand˜o (2010), os melhores resultados destes m´todos
a
e
s˜o para fun¸oes cont´
a

ınuas, convexas e semi-modais. Os m´todos determin´
e
ısticos
possuem uma grande vantagem que ´ o baixo n´mero de avalia¸oes da fun¸˜o objee
uc˜
ca
tivo, fazendo com que tenham convergˆncia r´pida e baixo custo computacional. O
e
a
m´todo ser´ analisado de acordo com os resultados obtidos atrav´s de problemas de
e
a
e
teste conhecidos na literatura.

2

Busca Linear

Dados uma fun¸ao f : Rn → R e um ponto qualquer x ∈ Rn , dizemos que o vetor

→ ∈ Rn ´ uma dire¸ao de descida de f a partir de x, se existe α > 0 tal que−
p
e


f (x + α→) < f (x), ∀α ∈ (0, α]
p
onde α ´ o tamanho do passo.
e
1

Este m´todo possui um passo muito interessante denominado de Busca Linear
e
Exata, trata-se da minimiza¸ao de uma fun¸ao de uma variav´l


e

min g (x) = f (xk + α→)
pk
com α > 0.

2.1

Dire¸˜o M´xima de Descida
ca
a




Dados f : Rn → R de classe C 1 e x ∈ Rn , determine P ∈ Rntal que D− f (x)
P
representa a menor taxa de varia¸ao de f a partir de x.

Solu¸ao:

Note que


D− f (x)
P





f (x)T P
=


P

1
→.

P

f (x)T

.



P

cos θ =

f (x)T

. cos θ,


logo o menor valor para D− f (x) ocorre quando cos θ = −1, ou seja, quando
P
θ = 180o .

Logo

→=

u



P


P

=

− f (x)
f (x)

Emoutras palavras: − f (x) ´ a dire¸˜o de m´xima descida de f a partir de x.
e
ca
a
Algoritmo 1: M´todo de m´ximo descida (Steepert descent method)
e
a
Dados: x0 ∈ Rn e
>0
Passo 1: Fa¸a k = 0
c
Passo 2: Se
f (xk ) < ; pare


− f (xk )
Passo 3: Fa¸a P =
c
f ( xk )
Passo 4: Entre com αk > 0 tal que


αk = arg min f (xk + αk Pk )
com α > 0.


Passo 5: Fa¸a xk+1 = xk + αkPk
c
Passo 6: Fa¸a k = k + 1 e volte para o Passo 2.
c

2

3

M´todo de Newton
e

Este m´todo ´ iterativo. Assim, dado x0 ∈ Rn , gera-se uma sequˆncia {xk }∞ .
e
e
e
k=1
Dado xk , obtido na itera¸ao k , a chamada da dire¸ao de Newton (denotada por


→N



P k ) ´ obtida aproximando-se f (xk + P ) pelo modelo quadr´tico:
e
a




1
f (xk + P ) ≈ mk ( P ) =f (xk ) + P T f (xk ) + P T 2 f (xk )P
2
Considerando-se que a matriz Hessiana 2 f (xk ) ´ sim´trica positiva definida.
e
e
Neste caso, pode-se mostrar que a forma quadratica


1
mk ( P ) = f (xk + P T f (xk )) + P T 2 f (xk )P
2
´ uma fun¸ao convexa, a qual possu´ um unico minimizador.
e

ı
´
Assim a dire¸˜o de Newton ´ obtida minimizando-se mk (P ). Para isso, faz-se
ca
e
→−
mk (P ) = 0


mk (P ) =

2

f (xk )P +



f ( xk ) = 0

N
Logo, Pk ´ obtido resolvendo-se o seguinte sistema linear.
e
2

N
f (xk )Pk = − f (xk )

ou seja,
N
Pk = −[

2

f (xk )]−1 f (xk ).

Como 2 f (xk ) ´ positiva definada, ent˜o 2 f (xk ) ´ invers´
e
a
e
ıvel. logo a dire¸ao de

Newton est´ bem definida.
a
Neste momento mostraremos que de fato adire¸ao definida ´ de descida.

e
Solu¸ao:


como

N
f (xk )T Pk = − f (xp )T [


f (xk ) = 0 , ent˜o
a
N
f (xk )T Pk = −( f (xk )T [

2

2

f (xk )]−1 f (xk )

f (x0 )]−1 f (x0 )) < 0.

Como queriamos mostrar. Assim, o pr´ximo ponto toma a forma:
o

3

N
xk+1 = xk + αPk
= xk − αk [ 2 f (xk )]−1 f (xk )

4

M´todo do Gradiente
e

Segundo Kalid o...
tracking img