362Kb - DComp

c
PAVF
1
Otimizac~ao Numerica Irrestrita
Algoritmos - aspectos gerais
Busca unidimensional
Metodos do Gradiente e Newton
Metodos de direc~oes conjugadas
Metodos quasi-Newton
c
PAVF
2
Algoritmos - aspectos gerais
Algoritmo
Grande parte dos algoritmos de otimizac~ao (minimizac~ao) se
enquadra na seguinte denic~ao:
Processo iterativo de descida que gera uma sequ^encia
de pontos de acordo com um conjunto de instruc~oes
pre-denidas
Iterativo: Cada novo ponto da sequ^encia e gerado a partir dos
pontos anteriores
Descida: O valor de alguma func~ao de descida no novo ponto
decresce em relac~ao ao ponto anterior
Notas
Idealmente, a sequ^encia gerada pelo algoritmo converge
num numero nito ou innito de iterac~oes para um ponto
do conjunto soluc~ao do problema
Um algoritmo e globalmente convergente se converge
para um ponto do conjunto soluc~ao a partir de qualquer
ponto inicial especicado
c
PAVF
3
Algoritmos - aspectos gerais
Algoritmo como mapeamento
Um algoritmo denido num espaco X pode ser visto como
um mapeamento A : X ! X , que a partir de x0 gera a
sequ^encia
x
k+1 = A(xk )
k
=0 1 2
:::
Conjunto soluc~ao
O conjunto soluc~ao pode ser denido de varias maneiras.
Exemplo:
; := fx 2 Rn :
x
e um mnimo local de f em g
ou se f 2 C 1 e convexa em = Rn,
; := fx 2 Rn : rf (x) = 0g
Func~ao de descida
Normalmente e a propria func~ao objetivo do problema, mas
existem excec~oes. Se z e uma func~ao de descida e xk 62 ;,
ent~ao z (xk+1) < z (xk )
Exemplo: no caso convexo e irrestrito acima, seria possvel
denir z (x) := krf (x)k
c
PAVF
4
Algoritmos - aspectos gerais
Converg^encia global
Existem condic~oes gerais para converg^encia global de algoritmos iterativos de descida (Luenberger, 1984)
Se (xk ) converge para x e z : X ! R e contnua, ent~ao
(zk ) := (z (xk )) converge para z := z (x )
Se z e uma func~ao de descida, ent~ao a converg^encia do
algoritmo esta associada a converg^encia de (zk )
Ordem de converg^encia
Seja (zk ) uma sequ^encia em R convergente para z . A ordem de converg^encia de (zk ) e o supremo dos numeros n~aonegativos p satisfazendo
j zk+1 ; z j < 1
0 klim
!1 j z ; z jp
k
Notas
Ordem de converg^encia esta relacionada ao comportamento assintotico (isto e, quando k ! 1) de (zk )
c
PAVF
5
Algoritmos - aspectos gerais
Notas (cont)
Assintoticamente, a dist^ancia ao limite z e reduzida pela
p-
esima pot^encia num unico passo quanto maior p, mais
rapida a converg^encia. Se o limite existe, ent~ao, assintoticamente,
j
z
k+1 ; z
j = j k ; jp
z
z
Exemplos
a) ( k ) := ( k ) 0
k+1 k = z
z
=z
a
k
! 0 com ordem 1, pois
k
! 0 com ordem 2, pois
1
z
1
z
a
b) ( k ) := ( 2k ) 0
2
k+1 k = 1
z
z
< a <
a
< a <
=z
Converg^encia linear
Se a sequ^encia (zk ) converge para z e
j zk+1 ; z j = < 1
lim
k!1 j zk ; z j
diz-se que (zk ) converge linearmente com taxa de con-
verg^encia
c
PAVF
6
Algoritmos - aspectos gerais
Converg^encia superlinear
Entre duas sequ^encias que convergem linearmente, converge mais rapido a de menor . Quando = 0, diz-se que a
converg^encia e superlinear
Exemplo
(zk ) := ((1=k)k) e de ordem 1, pois zk+1=zkp ! 1 se p > 1.
Como zk+1=zk ! 0, (zk ) converge superlinearmente
Converg^encia quadratica
Se (zk ) converge para z com p > 1 e < 1, ent~ao a
converg^encia de (zk ) e superlinear
Se p = 2 e < 1, diz-se que (zk ) possui taxa de con-
verg^encia quadratica
Algoritmos - outros aspectos
Generalidade, robustez e precis~ao
Sensibilidade a par^ametros e dados
Esforco de preparac~ao e computac~ao
c
PAVF
7
Busca unidimensional
Busca linear
Considere o problema irrestrito
minimizar ( )
f x
x
2 Rn
Muitos algoritmos de otimizac~ao irrestrita assumem a seguinte estrutura geral:
Escolha > 0, x0 e faca k = 0
while kr ( k)k f x
end
=
x
1: Encontre 2 Rn tal que rf (xk )T dk < 0
2: Determine k := arg min >0 f (xk + dk )
3: Faca xk+1 := xk + k dk e k := k + 1
x
k
d
k
Notas
No passo 1 determina-se uma direc~ao de descida. A condic~ao rf (xk )T dk < 0 garante que f decresce na direc~ao
k
k
d a partir de x para > 0
No passo 2 e realizada uma busca linear para encontrar
o tamanho de passo k que minimiza f na direc~ao dk a
partir de xk
No passo 3 um novo ponto e calculado. O criterio de
parada e krf (xk)k < (idealmente, krf (xk)k = 0)
c
PAVF
8
Busca unidimensional
Exemplo
No metodo do gradiente, se krf (xk )k , ent~ao dk :=
;rf (xk) e tal que rf (xk)T dk < 0 e a busca linear assume a
forma
k
k
k
:= arg min
f (x ; rf (x ))
>
0
k
Notas
Dena () := f (xk +dk ). Ent~ao () = (0)+0(0)+
0
k T k
o(), onde (0) = rf (x ) d < 0
Portanto, () < (0) se > 0 for sucientemente pequeno. Na busca linear, minimiza-se para > 0
MATLAB
Func~ao de Rosenbrock. Em x0 = (0 0), rf (x0) = (;2 0)
alfa=0:0.01:0.2] m,n]=size(alfa)
x0=0 0]' g0=-2 0]' d0=-g0 fi=]
for i=1:n,
x1=x0+alfa(i)*d0
fi(i)=100*(x1(2)-x1(1)^2)^2+(1-x1(1))^2
end
plot(alfa,fi) grid on
c
PAVF
9
Busca unidimensional
3
2.5
( )
2
1.5
1
0.5
0
0.02
0.04
0.06
0.08
0.1
0.12
0.14
0.16
0.18
0.2
Note que 0(0) < 0. O mnimo de ocorre em 0 =
0:08 e (0) = 0:77 = f (x1) < f (x0) = (0) = 1
Notas
Buscas lineares exatas s~ao computacionalmente onerosas
e de certa forma desnecessarias
E necessario apenas garantir uma reduc~ao suciente da
func~ao objetivo a cada iterac~ao
A simples reduc~ao no valor da func~ao (f (xk+1) < f (xk ))
n~ao garante converg^encia
Exemplo: f (x) = x2 x0 = 2. A sequ^encia ((;1)k(1 +
2;k ) e tal que f (xk+1) < f (xk ), mas limk!1 f (xk ) = 1,
enquanto que o mnimo de f e 0
c
PAVF
10
Busca unidimensional
x
1
3
x
4
x
2
x
0
x
Condic~oes de Wolfe
Uma primeira condic~ao imposta ao passo e este satisfazer
a desigualdade
( k + dk ) f (xk ) + c1rf (xk )T dk =: l()
para algum c1 2 (0 1)
f x
( )
l
0
Aceitavel
c
PAVF
11
Busca unidimensional
Notas
A condic~ao estabelece que a reduc~ao f (xk+1) ; f (xk) deve
ser proporcional a e a rf (xk )T dk
A inclinac~ao de l() = c1rf (xk )T dk + f (xk ) e negativa
(rf (xk)T dk < 0) e superior a rf (xk )T dk (c1 2 (0 1))
A desigualdade, conhecida como condic~ao de Armijo,
sempre sera satisfeita para valores de > 0 pequenos
Para evitar a escolha de passos muitos pequenos, a seguinte
condic~ao de curvatura deve tambem ser satisfeita:
r ( k + k )T k 2r ( k)T
para algum 2 2 ( 1 1)
f x
c
d
d
c
f x
d
k
c
( )
Inclinac~ao
desejada
l
0
Aceitavel
c
PAVF
12
Busca unidimensional
Teorema
Seja f : Rn ! R, f 2 C 1, e dk uma direc~ao de descida
em xk . Se f e limitada inferiormente ao longo do raio fxk +
k : > 0g e 0 < c < c < 1, ent~ao existem intervalos
d
1
2
para satisfazendo as condic~oes de Wolfe
( k + dk ) f (xk ) + c1rf (xk )T dk
f x
r ( k+
f x
k )T dk
d
2r ( k)T
c
f x
k
d
Backtracking
O uso da condic~ao de curvatura, que exige novos calculos de
gradiente, pode ser evitado atraves do procedimento conhecido
como backtracking
2 (0 1). Faca := while ( k + k ) ( k ) + r ( k)T k
Escolha > 0 e f x
end
k=
d
:= c
> f x
c
f x
d
O passo maximo e reduzido a taxa constante () apenas
o suciente para satisfazer a condic~ao de Armijo
O passo k n~ao sera muito pequeno, pois a dist^ancia ao
passo anterior (que n~ao satisfaz a condic~ao) e k =
c
PAVF
13
Busca unidimensional
MATLAB
O uso de backtracking e ilustrado abaixo com a func~ao de
Rosenbrock. Um valor tpico para c = c1 e 0.0001
alfab=1 ro=0.5 c=0.0001
x0=0 0]' fdx0=1 g0=-2 0]'
d0=-g0 dd=g0'*d0 alfa=alfab
x1=x0+alfa*d0
fdx1=100*(x1(2)-x1(1)^2)^2+(1-x1(1))^2
while fdx1>fdx0+c*alfa*dd
alfa=ro*alfa
x1=x0+alfa*d0
fdx1=100*(x1(2)-x1(1)^2)^2+(1-x1(1))^2
end
alfa0=alfa
alfa0 = 0.1250
O valor 0 = 0:1250 fornece f (x1) = 0:9531 < 1:000 =
0
f (x ). O resultado e sensvel a escolha de . Se = 0:6 ent~ao
0 = 0:0778, mais pr
oximo do valor ideal
Interpolac~ao
E possvel desenvolver um procedimento de busca atraves de
interpolac~ao de valores e derivadas de . A condic~ao de Armijo
e escrita como
( ) (0) + c10 (0)
c
PAVF
14
Busca unidimensional
Procedimento
1. Se o passo inicial 0 n~ao satisfaz a condic~ao, ent~ao o intervalo 0 0] contem um passo aceitavel
2. Constroi-se uma aproximac~ao quadratica para a partir
de (0), (0) e 0(0):
0
1
0
(0 ) ; (0) ; (0)0
A 2 + 0(0) + (0)
q () := @
2
0
Note que q (0) = (0) q (0) = (0) e 0q (0) = 0(0).
O mnimo de q ocorre em
2
(0)
0
1 = ;
2(0) ; (0) ; 0(0)0]
0
Se 1 satisfaz a condic~ao, ent~ao encerra-se a busca. Caso
contrario aumenta-se a ordem da interpolac~ao
3. Constroi-se uma aproximac~ao cubica para a partir de
0
(0), (0 ), (1 ) e (0):
c () := a
3
2
2 3
a
66
66 77
1
64
64 75 = 2 2
0 1 (1 ; 0 )
b
+ b2 + 0(0) + (0)
;
2
0
;
2
1
3
0
3
1
32
3
0
(1 ) ; (0) ; (0)1
77 66
77
75 64
75
0
( ) ; (0) ; (0)0
0
c
PAVF
15
Busca unidimensional
Procedimento (cont)
4. O mnimo da cubica ocorre em
2
= ;b +
q
2
b
; 3 0(0)
3a
a
A interpolac~ao cubica e repetida usando-se (0) 0(0) e os
valores mais recentes de ate que a condic~ao seja satisfeita
5. Se i esta muito proximo ou distante de i;1, faz-se i =
i;1 =2. Assegura-se progresso razo
avel a cada iterac~ao e
evita-se que o valor nal de seja muito pequeno
Exemplo - Func~ao de Rosenbrock
x0=0 0]' fdx0=1 g0=-2 0]'
d0=-g0 dd=g0'*d0
fi0=fdx0 dfi0=dd alfa0=0.2
x1=x0+alfa0*d0
fia0=100*(x1(2)-x1(1)^2)^2+(1-x1(1))^2
% Interpolacao quadratica
%
alfa1=-(dfi0*alfa0^2)/(2*(fia0-fi0-dfi0*alfa0))
alfa1 = 0.0294 % => Condicao satisfeita !
Note que 1 e bem menor do que 0 e que 1 = 0=2 = 0:1
tambem satisfaz a condic~ao de Armijo
c
PAVF
16
Busca unidimensional
3
2.5
2
1.5
q
1
0.5
0
0.02
0.04
0.06
0.08
0.1
0.12
0.14
0.16
0.18
0.2
Se 0 = 1:0, ent~ao 1 = 0:0012 (verique !) satisfaz a
condic~ao, mas 1 << 0 . O novo ponto 1 = 0 =2 =
0:5 n~ao satisfaz a condic~ao
% Interpolacao cubica
%
alfa1=0.5 x1=x0+alfa1*d0
fia1=100*(x1(2)-x1(1)^2)^2+(1-x1(1))^2
A=1/(alfa0^2*alfa1^2*(alfa1-alfa0))
B=alfa0^2 -alfa1^2 -alfa0^3 alfa1^3]
C=fia1-fi0-dfi0*alfa1 fia0-fi0-dfi0*alfa0]
V=A*B*C a=V(1) b=V(2)
alfa2=(-b+sqrt(b^2-3*a*dfi0))/(3*a)
alfa2 = 0.2236
Como 2 = 0:2236 n~ao satisfaz a condic~ao, deve-se repetir
a interpolac~ao com 0 := 1 e 1 := 2 ate converg^encia
c
PAVF
17
Busca unidimensional
Busca sem derivadas
Os metodos de busca que n~ao usam informac~oes baseadas
em derivadas pressup~oem que
Conhece-se um intervalo de incerteza I := a b] contendo um mnimo de A func~ao e unimodal no intervalo I
Func~ao unimodal
: R ! R e unimodal num intervalo I se existe um mnimo
de em I , e n~ao-decrescente em f : g e e
n~ao-crescente em f : g
Teorema
Se : R ! R atinge um mnimo num intervalo I , ent~ao e unimodal se e somente se e quasi-convexa em I
a
b
x
c
PAVF
18
Busca unidimensional
Unimodalidade
Os metodos de busca sem derivadas produzem sucessivas
reduc~oes do intervalo de incerteza a partir de I0 := I
A reduc~ao e feita supondo-se que e estritamente quasiconvexa em I : para todos 1 2 2 I tais que (1) 6=
( )
2
(
1
+ (1 ; )2) < maxf(1) (2)g
para todo 2 (0 1)
A exig^encia de estrita quasi-convexidade exclui a possibilidade de que possua plat^os, exceto nos pontos de mnimo
Teorema
: R ! R estritamente quasi-convexa no intervalo
a b] e 2 a b] tais que < .
Seja
1. Se () > ( ), ent~ao (z ) ( ) p/ todo z 2 a )
2. Se () ( ) ent~ao (z ) ( ) p/ todo z 2 ( b]
O intervalo de incerteza e reduzido eliminando-se o subintervalo a ) (ou ( b])
c
PAVF
19
Busca unidimensional
Raz~ao A urea
E a soluc~ao do seguinte problema geometrico:
:= cb=ac = ac=ab
ac
a
c
b
cb
Logo, ac2 = cb ab, onde ac e obtido resolvendo-se
ac
ac
2
+ ab ac ; ab2 = 0
=; ab
q
p
0
1
+ 4ab2 = @ ;1 5 A ab
2
2
2
ab
e a soluc~ao do problema e
= ac=ab
p
;
1
+
= 2 5 ' 0 618
:
A raz~ao aurea ' 0:618 era considerada na Antiguidade
como a mais estetica para os lados de um ret^angulo
O metodo da sec~ao aurea utiliza um esquema de reduc~ao
do intervalo de incerteza baseado na raz~ao aurea
c
PAVF
20
Busca unidimensional
Algoritmo Sec~ao Aurea
p
Escolha > 0, faca r := ( 5 ; 1)=2
= a + (1 ; r )d, = a + rd
= f () y2 = f ( )
while (b ; a) > y1
if
y1 > y2
then =
=
2 =
else =
=
1 =
a
y
b
y
end
= y1 = y2
a + r (b ; a)
f ( )
= y2 = y1
a + (1 ; r )(b ; a)
f ()
end
=( + ) 2
b
a =
Notas
Se d1 := b ; a, d2 = b ; ou d2 = ; a, ent~ao d2=d1 = ,
d3 =d2 = , : : : . Em geral, dk +1 =dk = . O algoritmo
converge linearmente com taxa ' 0:618
Observe que dN =d1 = N ;1. Para um intervalo nal dN
dado, pode-se determinar o menor inteiro N tal que
N
d
d1
N ;1
Exemplo: se d1 = 1 e dN = 0:01, ent~ao 0:01 (0:618)N ;1
implica N = 11
c
PAVF
21
Busca unidimensional
MATLAB
function fi,alfa]=aurea(fun,I,tol)
a=I(1) b=I(2) r=(sqrt(5)-1)/2
alfa=a+(1-r)*(b-a) beta=a+r*(b-a)
y1=feval(fun,alfa) y2=feval(fun,beta)
while (b-a)>tol
if y1>y2
a=alfa alfa=beta y1=y2
beta=a+r*(b-a)
y2=feval(fun,beta)
else
b=beta beta=alfa y2=y1
alfa=a+(1-r)*(b-a)
y1=feval(fun,alfa)
end
end
alfa=(b+a)/2 fi=feval(fun,alfa)
function fi=f002(alfa)
fi=exp(-alfa)+alfa^2
fi,alfa]=aurea('f002',-1 1],0.01)
fi=0.8272
alfa=0.3506
4
3.5
;
e
3
+ 2
2.5
2
1.5
1
0.5
−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
c
PAVF
22
Metodos do Gradiente e Newton
Metodo do Gradiente
Assume-se que f 2 C 1. Por conveni^encia,
num ponto qualquer xk 2 Rn
g
k
:= rf (xk )
Algoritmo Gradiente Otimo
Escolha > 0 e x0. Calcule g0 = rf (x0) e faca k = 0
while k k k ( k;
k = arg min
>0
k+1 = k ;
k
k
k+1 = r ( k+1)
:= + 1
end
= k
g
f x
x
x
g
k
x
g
k)
g
f x
k
x
Notas
O criterio de converg^encia kgk k < e muitas v^ezes
inadequado. Na pratica, utilizam-se criterios mais realistas
Algoritmo de maior descida: a cada iterac~ao minimizase f ao longo da direc~ao de maior descida, ;rf
O algoritmo e globalmente convergente: converge para
um mnimo local de f a partir de qualquer ponto inicial x0
c
PAVF
23
Metodos do Gradiente e Newton
Func~oes quadraticas
Suponha que f (x) = (1=2)xT Qx ; bT x, onde Q = QT
Neste caso,
( k ; gk ) = 12 (xk ; gk )T Q(xk ; gk ) ;
>
0.
f x
;( k;
x
g
k )T b
Derivando-se em relac~ao a , obtem-se o passo otimo
k T k
(
g ) g
k =
(gk )T Qgk
e o algoritmo assume a forma explcita
2 kT k 3
k+1 = xk ; 4 (g ) g 5 g k
x
(gk )T Qgk
g
k
= Qxk ; b
Notas
As superfcies de nvel de f s~ap
o elipsoides, cujos eixos s~ao
inversamente proporcionais a i i = 1 2 : : : n, onde
i i = 1 2 : : : n s~
ao os autovalores (positivos) de Q
Os autovetores de Q determinam as direc~oes dos eixos dos
elipsoides e b produz uma translac~ao em relac~ao a origem
c
PAVF
24
Metodos do Gradiente e Newton
Interpretac~ao do algoritmo
1
x
x
x
0
A taxa de converg^encia do algoritmo do gradiente depende da excentricidade dos elipsoides
Teorema
Seja f : Rn ! R, f 2 C 2. Suponha que a sequ^encia (xk )
gerada pelo algoritmo do gradiente otimo converge para x e
que F (x ) > 0. Ent~ao
k+1) ; f (x
f (x
)
M
M
;
m
+ m
!2
f (xk ) ; f (x )]
onde m M s~ao os autovalores mnimo e maximo de F (x ).
O algoritmo do gradiente otimo converge linearmente com taxa
n~ao superior a
=
M
M
;
m
+ m
!2
c
PAVF
25
Metodos do Gradiente e Newton
Nota
A taxa piora com o aumento da difer^enca entre M e m .
Denindo r := M =
m,
=
r ; 1 !2
r
+1
e dependera de r, o numero de condic~ao de F (x )
Exemplo (Luenberger, pg. 219)
2
66 0:78
6 ;0:02
Q = 6
66 ;0:12
4
;0 02 ;0 12
0 86 ;0 04
;0 04 0 72
;0 14 0 06 ;0 08
:
:
:
:
:
:
:
:
:
3
0:06 777
;0:08 775
;0 14 7
:
0:74
Sequ^encia gerada:
k
0
1
2
3
4
5
6
( k)
0:0000000
;2:1563625
;2:1744062
;2:1746440
;2:1746585
;2:1746595
;2:1746595
f x
2
3
0
:76
66
7
66 0:08 777
b = 6
64 1:12 775
0:68
c
PAVF
26
Metodos do Gradiente e Newton
Exemplo (cont)
x
0
=0
x
= (1:534965 0:1220097 1:975156 1:412954)
Numero de condic~ao: r = M =
m = 0:94=0:52 = 1:8 a
taxa de converg^encia e (r ; 1)=(r + 1)]2 = 0:081
Cada iterac~ao reduz o erro por um fator maior do que 10
adiciona cerca de um dgito de precis~ao ao valor anterior
Escalamento
O desempenho do algoritmo e dependente da escolha das
variaveis. Suponha T y = x, onde T e n~ao-singular
Pode-se mostrar que a Hessiana de h(y) := f (T y) no ponto
y = Tx e
( ) = T T F (x )T
H y
pode ser escolhida tal que H (y ) possua autovalores
aproximadamente iguais, melhorando o desempenho do algoritmo
T
O escalamento proposto e difcil de implementar, pois pressup~oe algum conhecimento de x
c
PAVF
27
Metodos do Gradiente e Newton
Metodo de Newton
Uma func~ao f pode ser aproximada em torno de xk pela serie
de Taylor truncada:
( ) ' f (xk ) + rf (xk )T (x ; xk ) +
+ 12 (x ; xk )T F (xk )(x ; xk )
f x
O lado direito e minimizado em
x
k+1 = xk ; hF (xk )i;1 rf (xk )
Notas
Generalizac~ao do metodo unidimensional n~ao envolve determinac~ao de passos otimos
Sup~oe-se F (x ) > 0 num mnimo local x . Por continuidade, F (x) > 0 em torno de x e o algoritmo esta denido
proximo de x
Teorema
Seja f 2 C 3 e assuma que F (x ) > 0 num mnimo local x
de f . Ent~ao, se inicializada sucientemente proxima de x ,
a sequ^encia gerada pelo metodo de Newton converge para x
com ordem de no mnimo 2
c
PAVF
28
Metodos do Gradiente e Newton
Introduc~ao do passo
Minimizac~oes unidimensionais evitam que
aos termos n~ao-quadraticos:
k+1 = xk ; k
x
h
f
cresca devidos
i
( k ) ;1 rf (xk )
F x
onde k minimiza f na direc~ao
num mnimo local)
h
i
( k ) ;1 rf (xk ) (k 1
F x
Generalizac~ao
x
k+1 := xk ; M g k
k
g
k
= rf (xk )
Metodo do gradiente: Mk := I
Metodo de Newton: Mk := F (xk )];1
Como f e diferenciavel em xk ,
(
k+1)
f x
= f (xk ) + rf (xk )T (xk+1 ; xk ) + o(kxk+1 ; xk k)
= f (xk ) ; (gk )T Mk gk + o()
Quando ! 0, a func~ao decresce se (gk )T Mk gk > 0
Condic~ao suciente:
M
k
>
0
c
PAVF
29
Metodos do Gradiente e Newton
Notas
:= I Metodo do gradiente, converg^encia linear
h k i;1
Mk := F (x )
Metodo de Newton, converg^encia quak
M
dratica proxima ao mnimo local
h
i
Problema: num ponto qualquer, ( k ) ;1 pode n~ao ser
denida positiva ou mesmo existir
k
M
:=
h
i
( k ) + k I ;1
F x
k
F x
0, estabelece um compro-
misso entre os metodos do gradiente (k muito grande) e
de Newton (k = 0)
Algoritmo Newton Modicado
Escolha > 0
e faca k = 0
while k k k g
>
0 e x0. Determine g0, F0 = F (x0)
k minimo t.q. m (Fk + k I ) > k
;1 k
d = ;(Fk + k I )
g
k
k
k = arg min f (x + d )
>0
k+1 = xk + dk , g k+1 = rf (xk+1), F
k+1
x
k
k+1 = F (x )
end
=
x
k
x
k
:= k + 1
c
PAVF
30
Metodos do Gradiente e Newton
Notas
Com a modicac~ao, o metodo de Newton torna-se globalmente convergente, com converg^encia quadratica na
vizinhanca de x
Se for muito pequeno, (Fk + k I ) tornar-se proxima de
singular. Se for muito grande, compromete-se a ordem
de converg^encia 2
Determinac~ao de k e dk
Dado k > 0, se (Fk + k I ) > 0, ent~ao existe uma matriz L
triangular inferior com lii > 0 i = 1 2 : : : n tal que
k + k I
F
= LLT
Fatorac~ao de Choleski
Caso contrario, aumenta-se k . Como LLT dk =
direc~ao dk pode ser obtida da seguinte forma:
; k, a
g
1. Resolva Ly = ;gk
2. Resolva LT dk = y
Como os sistemas lineares s~ao triangulares, y e dk s~ao facilmente obtidos
c
PAVF
31
Metodos do Gradiente e Newton
Relac~ao Newton-Gradiente
Suponha F (xk ) > 0. Ent~ao
Fatorac~ao de Choleski
( k );1 = LLT
F x
Denindo x := Ly, obtem-se h(y) := f (Ly). Se
ent~ao yk = L;1xk e
r ( k ) = T r ( k) = T r ( k) =
h y
L
f Ly
L
f x
x
= xk ,
T k
L g
O metodo do gradiente aplicado a h com k = 1 leva a
y
k+1
= yk ; LT gk
ou pre-multiplicando por L,
x
k+1 = xk ; F (xk );1g k
Conclus~ao
O metodo de Newton equivale ao metodo do gradiente com
escalamento am de variaveis (x = Ly)
c
PAVF
32
Metodos de direc~oes conjugadas
Direc~oes conjugadas
Seja
Q
=
Q
T
2 Rnn. Dois vetores
x y
2 Rn s~ao -
ortogonais ou conjugados em relac~ao a , se
Q
T
x Qy
Q
=0
Notas
Se Q = I , ent~ao Q-ortogonalidade implica ortogonalidade
fd0 d1 : : : dk g e Q-ortogonal se (di)T Qdj = 0 para i 6= j
Teorema
Se Q = QT > 0 e d0 d1 : : : dk s~ao vetores n~ao-nulos Qortogonais, ent~ao d0 d1 : : : dk s~ao linearmente independentes
Aplicac~ao
A soluc~ao (unica) x do problema
minimizar 21
T
x Qx
;
T
b x
Q
= QT > 0
satisfaz Qx = b. A soluc~ao x pode ser expressa atraves de b
e de n vetores Q-ortogonais
c
PAVF
33
Metodos de direc~oes conjugadas
Obtenc~ao de x
Se d0
1
d
0 1 : : :
:::
d
n;1
x
n;1 s~ao Q-ortogonais, ent~ao existem escalares
tais que
= 0d0 + 1d1 + + n;1dn;1
Pre-multiplicando a express~ao por
obtem-se
i T
i T
(
d ) Qx
(
d ) b
i =
(di)T Qdi = (di)T Qdi
i
Q
e depois por (di)T ,
=0 1
:::
n
;1
Portanto,
x
=
nX
;1
i=0
2 iT 3
4 (d ) b 5 di
(di)T Qdi
Notas
Usando apenas ortogonalidade (Q = I ), os i's cariam
dependentes de x (desconhecido)
Usando Q-ortogonalidade, os i's dependem de b (conhecido) e de quaisquer n ; 1 vetores Q-ortogonais
Problema: na pratica n~ao e t~ao simples obter e trabalhar
com um conjunto de vetores Q-ortogonais
c
PAVF
34
Metodos de direc~oes conjugadas
Algoritmos
Considere o problema de minimizar
( ) = 21 xT Qx ; bT x
f x
Q
= QT > 0
a partir de x0 atraves de gradiente otimo. A taxa de converg^encia e func~ao de r = M =
m
Transformac~ao
Dena
D
:=
d
0
...
d
1
...
...
n;1
d
D
2 Rnn
onde d0 d1 : : : dn;1 s~ao Q-ortogonais. Ent~ao D e n~ao-singular
e a mudanca x := Dy leva a
( ) := f (Dy) = 12 yT (DT QD)y ; (DT b)T y
h y
Lema
D
T QD
h
= diag (d0)T Qd0 (d1)T Qd1
:::
(dn;1)T Qdn;1
i
c
PAVF
35
Metodos de direc~oes conjugadas
Problema transformado
minimizar
n
X
( ) = 21 q~iiyi2 ; ~biyi
h y
i=1
f := DT QD e ~b :=
a partir de y0 = D;1x0, onde Q
problema e separavel em n problemas do tipo
minimizar 12 ~ii i2 ; ~i
q y
b y
D
T b.
O
i
Interpretac~ao
A mudanca y = Dx elimina os termos cruzados de f , isto e,
a rotac~ao dos elipsoides, colocando-os na posic~ao padr~ao
x2
0
y2
y2
0
x2
y2
x2
x1
0
x1
x1
y1
0
y1
y1
As minimizaco~es individuais podem ser vistas como minimizac~oes nas direc~oes unitarias e0 e1 : : : en;1
c
PAVF
36
Metodos de direc~oes conjugadas
Procedimento
Comecando em y0 = D;1x0, obtem-se o mnimo de h na
direc~ao e0, isto e, ao longo de y0 + e0 2 R
Determina-se y1 = y0 + 0e0. Minimiza-se h na direc~ao e1
a partir de y1 e assim sucessivamente ate se obter yn
O procedimento converge para y em no maximo n passos.
Como x = Dy, pre-multiplicando yk+1 = yk + k ek k =
0 1 : : : n ; 1 por D, obtem-se
x
k+1 = xk + dk
k
pois Dek = dk
Minimizar h nas direco~es unitarias e equivalente a minimizar
f nas dire
co~es conjugadas
Teorema (Algoritmo de direc~oes conjugadas)
Sejam d0 d1 : : : dn;1 vetores n~ao-nulos Q-ortogonais. Para
qualquer x0, a sequ^encia (xk ) gerada pelo algoritmo
g
k
= Qxk ; b !
(gk )T dk !
=
;
k
(dk )T Qdk
k+1 = xk + dk
k
x
converge para a soluc~ao x de Qx = b em no maximo n passos
c
PAVF
37
Metodos de direc~oes conjugadas
Teorema (Expanding Subspace Theorem)
Seja x0 qualquer ponto inicial e (xk ) a sequ^encia gerada pelo
algoritmo de direc~oes conjugadas. Ent~ao xk minimiza f (x) =
(1=2)xT Qx ; bT x na variedade linear
n
Vk := 2 Rn : = 0 + span f
x
x
e (gk )T di = 0
i
=0 1
x
:::
0
d
k
1
d
:::
d
k;1go
;1
Vk
k
x
d
g
k
k;1
k;1
x
k;2
d
k;2
x
No algoritmo de direc~oes conjugadas, o gradiente corrente e
ortogonal a todas as direco~es anteriores
c
PAVF
38
Metodos de direc~oes conjugadas
Notas
Os resultados anteriores se aplicam a qualquer conjunto
de n vetores Q-ortogonais
Uma das formas de se obter um conjunto Q-conjugado e
adaptar o processo de ortogonalizac~ao de Gram-Schmidt
Q-ortogonalizac~ao de Gram-Schmidt
Seja Q = QT > 0 e fp0 p1 : : : pn;1g um conjunto LI.
Ent~ao o conjunto fd0 d1 : : : dn;1g denido por
d
0
= p0
k (pk+1)T Qdi
X
k
i
+1
k
+1
d
=p ;
d
i
T
i
i=0 (d ) Qd
e Q-ortogonal
Notas
Para n grande, n~ao e pratico calcular e armazenar um conjunto de direc~oes conjugadas
Algortimos ecientes calculam iterativamente dk a partir de
k;1. Apenas a direc~ao corrente e calculada e armazenada
d
c
PAVF
39
Metodos de direc~oes conjugadas
Algoritmo Gradientes Conjugados
Escolha x0, dena d0 := ;g0 e faca k = 0
while k k k 6= 0
k T k ( k )T k
k = ;( )
k+1 = k +
k
k
k+1 =
k+1 ;
if
; 1 then
k+1)T k ( k )T
k=(
k+1 = ; k+1 +
k
k
end
:= + 1
end
= k
g
g
x
x
g
Qx
d = d
Qd
d
b
k < n
d
k
x
g
Qd = d
g
k
Qd
d
k
x
Notas
A primeira iterac~ao e igual ao do algoritmo do gradiente:
0
0
d = ;g e o 0 e o passo otimo da direc~ao ;g0
A direc~ao conjugada corrente e uma combinac~ao linear do
gradiente corrente e da direc~ao anterior
Func~oes n~ao-quadraticas
Uma quadratica denida positiva e uma boa aproximac~ao
para f numa vizinhanca de um mnimo local estrito
c
PAVF
40
Metodos de direc~oes conjugadas
Algoritmo
Escolha > 0 e x0. Calcule g0 = rf (x0)
while k 0k 0
=; 0
for = 0 : ; 1
k T k ( k )T ( k ) k
k = ;( )
k+1 = k +
k
k+1 = r ( k+1)
k ,
if
; 1 then
k+1)T ( k ) k ( k )T ( k )
k=(
k+1 = ; k+1 +
k
k
end
end
0
= n , 0 = r ( 0)
end
= 0
g
d
g
k
n
g
x
x
d = d
d
F x
g
d
f x
k < n
d
x
x
x
g
g
F x
g
d = d
F x
d
k
d
f x
x
Notas
Converg^encia nita n~ao e assegurada. A direc~ao do gradiente e restaurada apos n passos
Cada n passos resolvem um problema quadratico com gk rf (xk) e Q F (xk )
Como no metodo de Newton classico, buscas unidimensionais n~ao s~ao utilizadas
k
F (x ) precisa ser calculada em cada ponto. Converg^
encia
global n~ao e garantida
c
PAVF
41
Metodos de direc~oes conjugadas
Metodo de Fletcher-Reeves
Substitui calculos de Hessianas por buscas unidimensionais
Algoritmo Fletcher-Reeves
Escolha > 0 e x0. Calcule g0 = rf (x0)
while k 0k 0
=; 0
for = 0 : ; 1
( k + k)
k = arg min
0
k+1 = k +
k
k+1 = r ( k+1)
k ,
if
; 1 then
k+1)T k+1 ( k )T k
k=(
k+1 = ; k+1 +
k
k
end
end
0
= n , 0 = r ( 0)
end
= 0
g
d
g
k
n
f x
x
x
d
d
g
f x
k < n
d
x
x
x
g
g
g
g
= g
g
d
f x
x
Converg^encia global
Garantida: a cada n passos, uma iterac~ao de gradiente e
executada. Passos intermediarios n~ao aumentam o valor de f
Converg^encia n-passos quadratica: cada n passos em torno
de x equivalem a uma iterac~ao de Newton.
c
PAVF
42
Metodos quasi-Newton
Motivac~ao
Desenvolver metodos intermediarios entre os metodos do gradiente e Newton
Como no metodo do gradiente, apenas o gradiente de f e
necessario a cada iterac~ao
Utilizam aproximaco~es da inversa da Hessiana de f , ao inves
da Hessiana verdadeira
Medidas da variac~ao do gradiente fornecem um modelo para
f capaz de produzir converg^
encia superlinear
Metodo classico
x
k+1 = xk ; k F (x
)] rf (xk )
0 ;1
k
=0 1
:::
A Hessiana permanece igual a F (x0). A eci^encia do algoritmo depende de qu~ao rapido F (x) varia
Construc~ao da inversa
Seja f 2 C 2 e dena g(x) := rf (x), onde gi(x) = @ f (x)=@ xi.
Como gi e diferenciavel, para dois pontos xk e xk+1,
k+1) ' g (xk ) + rg (xk )T (xk+1 ; xk )
i
i
i (x
g
i
=1 2
:::
n
c
PAVF
43
Metodos quasi-Newton
Notando que rgi(xk )T e a i-esima linha de F (xk ),
(
k+1) = g (xk ) + F (xk )(xk+1 ; xk )
g x
Dena qk := g(xk+1) ; g(xk ) e pk :=
Hessiana fosse constante e igual a F , ent~ao
q
k
k+1
x
; k . Se a
x
= F pk
Sejam as matrizes
h
:= h p0
0
Q :=
q
P
1
p
q
1
p
q
n;1
n;1
i
i
vetores pk LI's
vetores qk associados
n
Ent~ao F e unicamente determinada como F = QP ;1
Notas
Constroem-se sucessivas aproximac~oes Hk para F ;1 baseadas nos k primeiros passos do processo iterativo
Se F fosse constante, Hk+1 deveria satisfazer Hk+1qi =
i
p
i
=0 1
:::
k
Apos n passos (direc~oes) linearmente independentes, seria
possvel obter Hn = F ;1
c
PAVF
44
Metodos quasi-Newton
Notas
Para k < n, a matriz Hk que aproxima F ;1 pode ser obtida
de varias maneiras
Como F e F ;1 s~ao simetricas, deve-se impor que Hk tambem
seja simetrica
Correc~ao de rank 1
k+1 = Hk + ak z
H
k (z k )T
onde ak e z k devem ser tais que Hk+1qi = pi
(F constante). Para i = k,
k
p
=01
i
= Hk+1qk = Hk qk + ak z k (z k )T qk
e pre-multiplicando por qk ,
(qk )T pk ; (qk )T Hk qk = ak (z k )T qk ]2
Logo,
k
k k
k T
(
p ; Hk q )(p ; Hk q )
Hk +1 = Hk +
k T k2
ak (z ) q ]
:::
k
c
PAVF
45
Metodos quasi-Newton
Lembrando que pk ; Hk qk = ak z k (z k )T qk , obtem-se
k
k k
k T
(
p ; Hk q )(p ; Hk q )
Hk +1 = Hk +
(qk )T (pk ; Hk qk )
Teorema
= F T e p0 p1 : : : pk vetores dados. Dena qi :=
T
i = 0 1 : : : k . Para qquer H0 = H0 , seja
Seja
i
Fp
F
i
i i
i T
(
p ; Hi q )(p ; Hi q )
Hi+1 = Hi +
(qi)T (pi ; Hiqi)
Ent~ao pi = Hk+1qi
i
=0 1
:::
k
Notas
O Teorema mostra que a recurs~ao tambem satisfaz Hk+1qi =
i i = 0 1 : : : k para i < k . Converge para F ;1 em no
p
maximo n passos
A correc~ao de rank 1 garante Hk+1 > 0 apenas se (qk )T (pk ;
k
Hk q ) > 0. Gera problemas num
ericos se (qk )T (pk ; Hk qk )
for pequeno
c
PAVF
46
Metodos quasi-Newton
Metodo de Davidon-Fletcher-Powell
Baseado em correc~ao de rank 2: a cada iterac~ao a inversa
e a soma de 2 matrizes de rank 1
Algoritmo DFP
Escolha > 0, x0 e H0 = H0T
faca k = 0
>
0. Calcule g0 = rf (x0) e
while k k k k=;
k
k
( k + k)
k = arg min
0
k+1 = k +
k
k
if
; 1 then
k+1 = r ( k+1)
k = k+1 ; k ,
k=
k
k
k k T
k ( k )T
k ( ) k
=
+
;
k+1
k
( k )T k
( k )T k k
= +1
else
0
= n , 0 = r ( 0 ),
=0
end
end
g
d
H g
x
f x
x
d
d
k < n
g
q
f x
g
H
k
x
g
p
p
H
p
d
H q
p
q
q
f x
k
q
H
H q
k
x
g
Se Hk > 0, ent~ao Hk+1 > 0. Se F (x) = F , os pk 's s~ao
;1
F -ortogonais e Hn = F
. Se F (x) = F e H0 = I , obtem-se
o algoritmo dos gradientes conjugados
c
PAVF
47
Metodos Quasi-Newton
Complementariedade
Ao inves de se aproximar a inversa da Hessiana por
k+1q
H
i
= pi
i
=0 1
:::
(1)
k
e possvel aproximar a propria Hessiana atraves de
q
i
= Bk+1pi
i
=0 1
:::
(2)
k
As formulas (1) e (2) s~ao complementares: a partir de (1),
trocando-se H por B e q por p chega-se a (2), e vice-versa
Atualizac~ao BFGS
Se Hk e atualizada pela formula DFP, ent~ao
B
k k T B pk (pk )T B
q (q )
k
k
=
B
+
;
k+1
k
(qk )T pk (pk )T B pk
k
conhecida como atualizac~ao Broyden-Fletcher-Goldfarb-Shanno da Hessiana
Outra forma de obter uma atualizac~ao para H a partir de B
e vice-versa e calculando a inversa
c
PAVF
48
Metodos Quasi-Newton
Atualizac~ao da inversa
Como Bk;1+1 satisfaz (2), realizando a inversa obtem-se
BFGS
Hk +1
0
k T
k 1 pk (pk )T
(
q ) Hk q
A
= Hk + @1 +
(qk )T pk
(pk )T qk ;
k k T
; ( ) ( k +)T
p
q
k
k
qk
p
H
H q
k (pk )T
Notas
DFP
k+1
e HkBFGS
s~ao simetricas, baseadas em correc~ao de
+1
rank 2 e construdas a partir de pk e Hk qk
BFGS do tipo
Combinac~oes lineares de HkDFP
+1 e Hk +1
H
H
= (1 ; )H DFP + H BFGS
2R
s~ao da mesma natureza e constituem a classe Broyden
Metodo Broyden: cada n passos utilizam um elemento
da classe Broyden
Converg^encia global
Caractersticas similares ao dos metodos de direc~oes conjugadas com reinicializac~oes pelo gradiente a cada n passos
c
PAVF
49
Metodos Quasi-Newton
MATLAB (fminunc)
x,fval,exitflag,output]=fminunc(fun,x0,options)
options
Declaradas atraves da func~ao optimset. As opc~oes default
de fminunc s~ao obtidas atraves de
options=optimset('fminunc')
ActiveConstrTol:
DerivativeCheck:
Diagnostics:
DiffMaxChange:
DiffMinChange:
Display:
GoalsExactAchieve:
GradConstr:
GradObj:
Hessian:
HessMult:
HessPattern:
HessUpdate:
Jacobian:
JacobMult:
JacobPattern:
LargeScale:
LevenbergMarquardt:
]
'off'
'off'
0.1000
1.0000e-08
'final'
]
]
'off'
'off'
]
'sparse(ones(numberOfVariables))'
'bfgs'
]
]
]
'on'
]
c
PAVF
50
Metodos Quasi-Newton
options
(cont)
LineSearchType:
MaxFunEvals:
MaxIter:
MaxPCGIter:
MeritFunction:
MinAbsMax:
Preconditioner:
PrecondBandWidth:
ShowStatusWindow:
TolCon:
TolFun:
TolPCG:
TolX:
TypicalX:
'quadcubic'
'100*numberOfVariables'
400
'max(1,floor(numberOfVariables/2))'
]
]
]
0
]
]
1.0000e-06
0.1000
1.0000e-06
'ones(numberOfVariables,1)'
Notas
A func~ao fminunc suporta duas classes de problemas: Large Scale e Medium Scale. A instruc~ao
options=optimset('LargeScale','off')
informa a func~ao fminunc que metodos para problemas de
medio porte devem ser usados
Os metodos para medio porte s~ao do tipo quasi-Newton.
Opc~oes: 'bfgs' (default), 'dfp' e 'steepdesc'
c
PAVF
51
Metodos Quasi-Newton
Exemplo
Minimizac~ao da func~ao de Rosenbrock:
( ) = 100(x1 ; x22)2 + (1 ; x1)2
f x
x
2 R2
Func~ao .m
function f=rsbrck(x)
f=100*(x(1)-x(2)^2)^2+(1-x(1))^2
Metodo do gradiente
x0=-1.9 2]
options=optimset(options,'HessUpdate','steepdesc')
x,fval,exit,outp]=fminunc('rsbrck',x0,options)
Maximum number of function evaluations exceeded
increase options.MaxFunEvals
x = 0.5386
0.7324
fval = 0.2134
exit = 0
outp =
iterations: 31
funcCount: 202
stepsize: 0.0509
firstorderopt: 0.6429
algorithm: 'medium-scale: Quasi-Newton line
search'
c
PAVF
52
Metodos Quasi-Newton
3
2.5
2
Start Point
1.5
x2
Solution
1
0.5
0
−0.5
−1
−2
−1.5
−1
−0.5
0
0.5
1
x1
Notas
A Hessiana da func~ao no ponto x = (1 1) e
2
802
F (x ) = 4
3
;400 5
;400 200
O numero de condic~ao de F (x ) e
r
:6
3
= M = 1001
=
2
:5 10
0:4
m
A taxa de converg^encia do metodo e
r ; 1 !2
r
+ 1 = 0:9984
1.5
2
c
PAVF
53
Metodos Quasi-Newton
Metodo DFP
options=optimset(options,'HessUpdate','dfp')
x,fval,exit,outp]=fminunc('rsbrck',x0,options)
x = 1.0000
1.0000
fval = 1.7380e-09
exit = 1
outp =
iterations: 23
funcCount: 144
stepsize: 1
firstorderopt: 0.0026
algorithm: 'medium-scale: Quasi-Newton line
search'
3
2.5
2
Start Point
1.5
x2
Solution
1
0.5
0
−0.5
−1
−2
−1.5
−1
−0.5
0
x1
0.5
1
1.5
2
c
PAVF
54
Metodos Quasi-Newton
Metodo BFGS
options=optimset(options,'HessUpdate','bfgs')
x,fval,exit,outp]=fminunc('rsbrck',x0,options)
x = 1.0000
1.0000
fval = 3.9222e-10
exit = 1
outp =
iterations: 19
funcCount: 113
stepsize: 1.0001
firstorderopt: 0.0030
algorithm: 'medium-scale: Quasi-Newton line
search'
3
2.5
2
Start Point
1.5
x2
Solution
1
0.5
0
−0.5
−1
−2
−1.5
−1
−0.5
0
x1
0.5
1
1.5
2