Otimização
Estrutura
• Introdução
• Métodos baseados no gradiente
–
–
–
–
Método de Newton
Método de Gauss-Newton
Método de Steepest Decent
Método de Levenberg-Marquardt
• Métodos Heurísticos
– Simulated Annealing
– Método das Formigas
Introdução
 p1 
 
p  
 pM 
M 1
parâmetros
 d1 
 
d   
d N 
N 1
 g1 ( p ) 


g ( p)    
 g N ( p )
N 1
dados
observados
dados
preditos
Introdução
 p1 
 
p  
 pM 
M 1
parâmetros
 d1 
 
d   
d N 
N 1
 g1 ( p ) 


g ( p)    
 g N ( p )
N 1
dados
observados
dados
preditos
 ( p)  [d  g ( p)]T [d  g ( p)]
norma L2
(função escalar)
Introdução
 p1 
 
p  
 pM 
M 1
parâmetros
 d1 
 
d   
d N 
N 1
 g1 ( p ) 


g ( p)    
 g N ( p )
N 1
dados
observados
dados
preditos
 ( p)  [d  g ( p)]T [d  g ( p)]
norma L2
(função escalar)
 ( p* )  0M 1
Introdução
 p1 
 
p  
 pM 
M 1
parâmetros
 d1 
 
d   
d N 
N 1
 g1 ( p ) 


g ( p)    
 g N ( p )
N 1
dados
observados
dados
preditos
 ( p)  [d  g ( p)]T [d  g ( p)]
norma L2
(função escalar)
 ( p* )  0M 1
Problema linear
Problema não-linear
Introdução
 p1 
 
p  
 pM 
M 1
parâmetros
 d1 
 
d   
d N 
N 1
 g1 ( p ) 


g ( p)    
 g N ( p )
N 1
dados
observados
dados
preditos
 ( p)  [d  g ( p)]T [d  g ( p)]
norma L2
(função escalar)
 ( p* )  0M 1
Problema linear
Problema não-linear
Introdução
 p1 
 
p  
 pM 
M 1
parâmetros
 d1 
 
d   
d N 
N 1
 g1 ( p ) 


g ( p)    
 g N ( p )
N 1
dados
observados
dados
preditos
 ( p* )  0M 1
Problema linear
g ( p)  B p  b
1
T
 T 
*
p   B B  B [ d  b ]


Problema não-linear
 ( p)  [d  g ( p)]T [d  g ( p)]
g ( p)  B p  b
norma L2
(função escalar)
p   G( p0 ) T G( p0 )  G( p0 ) T [d  g ( p0 )]


1
Introdução
 ( p)
Problema linear
p1
p2
Introdução
 ( p)
p1
p2
mínimo
Introdução
 ( p)
O mínimo pode
ser calculado
diretamente
p1
p2
p*
Introdução
 ( p)
Ou a partir de
uma aproximação
inicial
p0
p1
p2
p0
Introdução
 ( p)
p0
p1
p2
p
p0
Introdução
 ( p)
p0
p1
p2
p*
p
p0
Nesse caso, o
mínimo é
encontrado com
apenas um
“passo” a partir
da aproximação
inicial
Introdução
 ( p)
Por outro lado, em
um problema nãolinear, o mínimo é
encontrado após
sucessivos “passos” a
partir de uma
aproximação inicial
p0
p1
p2
p*
p0
Introdução
 ( p)
p1
p2
p*
Introdução
 ( p)
p1
p2
p*
Introdução
p1
 ( p)
p1
p2
p2
Curvas de nível
p*
Introdução
p1
p2
Aproximação
inicial
Introdução
p1
p2
Introdução
p1
p2
Introdução
p1
p2
Introdução
p1
Estimativa do
ponto mínimo
obtida após a
otimização
p2
Introdução
p1
p2
A partir de um
determinado ponto,
é necessário
estabelecer uma
direção e o
comprimento do
passo que será
dado
Introdução
p1
p2
Introdução
p1
p2
Introdução
p1
Direção
p2
Introdução
p1
Tamanho do passo
p2
Introdução
Existem dois grupos principais de
métodos para estimar o mínimo
de uma função:
Introdução
Existem dois grupos principais de
métodos para estimar o mínimo
de uma função:
Métodos que se baseiam no
gradiente da função
Métodos Heurísticos
Introdução
• Métodos baseados no gradiente
– Método de Newton
– Método de Gauss-Newton
– Método de Steepest Decent
– Método de Levenberg-Marquardt
• Métodos Heurísticos
– Simulated Annealing
– Método das Formigas
Métodos baseados no gradiente
Vamos às contas!
Métodos baseados no gradiente
 ( p)
Métodos baseados no gradiente
 ( p)
1 T
 ( p0   p)   ( p0 )   ( p0 )  p   p  ( p0 ) p
2
T
Métodos baseados no gradiente
 ( p)
1 T
 ( p0   p)   ( p0 )   ( p0 )  p   p  ( p0 ) p
2
T
 ( p0 ) p   ( p0 )
Métodos baseados no gradiente
 ( p)
1 T
 ( p0   p)   ( p0 )   ( p0 )  p   p  ( p0 ) p
2
T
 ( p0 ) p   ( p0 )
Diferença entre os métodos
Métodos baseados no gradiente
 ( p)
1 T
 ( p0   p)   ( p0 )   ( p0 )  p   p  ( p0 ) p
2
T
Newton
 ( p0 )
Gauss - Newton
 ( p0 )
Steepest Decent
1
Levenberg - Marquardt
 ( p0 )   
 ( p0 ) p   ( p0 )
Diferença entre os métodos
Métodos baseados no gradiente
Método
Convergência
Steepest Decent
0
Levenberg - Marquardt
1
Gauss - Newton
2
Newton
3
0 – lento

3 – rápido
Métodos baseados no gradiente
Método
Aproximação
inicial
Steepest Decent
Pode ser distante
Levenberg - Marquardt
Pode ser distante
Gauss - Newton
Deve ser próxima
Newton
Deve ser próxima
Métodos baseados no gradiente
Método
Direção
Steepest Decent
É a do gradiente
Entre a do gradiente e a do
Levenberg - Marquardt produto hessiana-gradiente
Gauss - Newton
Predita pelo produto
hessiana-gradiente
Newton
Predita pelo produto
hessiana-gradiente
Métodos baseados no gradiente
Método
Tamanho do passo
Steepest Decent
Depende de um parâmetro
e do gradiente
Depende de um parâmetro,
Levenberg - Marquardt do gradiente e da hessiana
Gauss - Newton
Depende do gradiente e da
hessiana
Newton
Depende do gradiente e da
hessiana
Métodos baseados no gradiente
Método
Custo
computacional
Steepest Decent
0
Levenberg - Marquardt
2
Gauss - Newton
1
Newton
3
0 – baixo

3 – alto
Métodos Heurísticos
(Simulated Annealing)
temp_inicial, temp_final, kappa, itmax, pinferior, psuperior, pinicial
iteracao = 0, p1 = pinicial, calcula f(p1), fminimo = f(p1), pminimo = p1
temperatura = temp_inicial
FAÇA {
• iteracao = iteracao + 1
• sorteia p2, calcula f(p2)
• SE [f(p2) < fminimo]  fminimo = f(p2), pminimo = p2
• probabilidade de sobrevivência ps
• SE [f(p2) < f(p1)]  ps = 1
• SE [f(p2) ≥ f(p1)]  ps = exp {[f(p1) - f(p2)]/temperatura}
• SE{[ps = 1] OU [ps ≠ 1] E [moeda ≤ ps]}  p1 = p2
• temperatura = kappa*temperatura
} ENQUANTO [(iteracao <= itmax) E (temperatura >= temp_final)]
Métodos Heurísticos
(Simulated Annealing)
temp_inicial, temp_final, kappa, itmax, pinferior, psuperior, pinicial
iteracao = 0, p1 = pinicial, calcula f(p1), fminimo = f(p1), pminimo = p1
temperatura = temp_inicial
FAÇA {
• iteracao = iteracao + 1
• sorteia p2, calcula f(p2)
• SE [f(p2) < fminimo]  fminimo = f(p2), pminimo = p2
• probabilidade de sobrevivência ps
• SE [f(p2) < f(p1)]  ps = 1
• SE [f(p2) ≥ f(p1)]  ps = exp {[f(p1) - f(p2)]/temperatura}
• SE{[ps = 1] OU [ps ≠ 1] E [moeda ≤ ps]}  p1 = p2
• temperatura = kappa*temperatura
} ENQUANTO [(iteracao <= itmax) E (temperatura >= temp_final)]
Métodos Heurísticos
(Simulated Annealing)
1,0
λ alto
0,8
λ baixo
f(p1) ≤ f(p2)
exp [-x/λ]
f(p2) - f(p1) = x
λ médio
0,6
0,4
temperatura = λ
0,2
0,0
0
20
40
60
x
80
100
Métodos Heurísticos
(Método das Formigas)
Modificada de Dorigo e Gambardella, 1997)