Módulo 17 - Otimização

Prévia do material em texto

Métodos 
Numéricos para 
Engenharia
MÓDULO 18 – OTIMIZAÇÃO 
PROFESSOR LUCIANO NEVES DA FONSECA
 A otimização compreende a busca de máximos (globais) de uma função.
x
f(x)
 Ou a busca de mínimos (globais) de uma função.
x
y=f(x)
f(x)
𝑀á𝑥𝑖𝑚𝑜 (𝐺𝑙𝑜𝑏𝑎𝑙)
𝑓′ 𝑥 = 0; 𝑓′′ 𝑥 < 0
Máximos locais
𝑧𝑒𝑟𝑜𝑠 ∶ 𝑓 𝑥 = 0
𝑧𝑒𝑟𝑜𝑠 ∶ 𝑓 𝑥 = 0
𝑀í𝑛𝑖𝑚𝑜(𝐺𝑙𝑜𝑏𝑎𝑙)
𝑓′ 𝑥 = 0; 𝑓′′ 𝑥 > 0
y=f(x)
Otimização em 1 dimensão
Raízes de 𝑓′(𝑥)
 Como vimos, os pontos ótimos de uma função 𝑓(𝑥) serão os zeros da sua 
primeira derivada 𝑓′(𝑥).
 Então, se 𝑓′ 𝑥 puder ser calculada ou avaliada, analítica ou numericamente, 
qualquer método utilizado para o cálculo de raízes de equações poderá ser 
utilizado.
 Poderão ser utilizados tantos os métodos intervalares quanto os abertos.
 Um método bastante eficiente é o método aberto de Newton-Raphson
(Secante Modificado) para se encontrar as raízes de 𝑓′(𝑥).
Métodos Abertos - Newton Raphson
(ou também secante modificado)
Algoritmo:
 Escolha uma estimativa inicial 𝑥1 para a raiz da função 𝑓′(𝑥)
 Defina uma tolerância (precisão) desejada
1 – Faça uma estimativa para o máximo da equação
𝑥𝑜 = 𝑥1
𝑥1 = 𝑥0 −
𝑓′ 𝑥0
𝑓′′(𝑥0)
2 – Se (𝑥1 > 0) erro = (𝑥1−𝑥0)/𝑥1
3 – Se erro < tolerância
Raiz =𝑥1 (com número de casas decimais de tolerância +1)
Pare
4 – Repita passo 1
• Notar que precisamos de estimativas para 𝑓′′(𝑥)
𝑦 = 𝑓 𝑥 = 𝑒 sin 2𝑥 −3 sin 3𝑥 −2 ≤ 𝑥 ≤ 6
Exemplo: Encontrar o máximo da seguinte função:
𝑥1 = 3.8
No entanto, a escolha de x1 irá impactar o resultado final. O algoritmo pode convergir para um 
máximo local ou para um mínimo (local ou global) 
𝑥1 = −0.5 𝑥1 = 1.5 𝑥1 = 2.5
Método Intervalares: Proporção Áurea (Golden ratio)
 A proporção áurea ∅ é definida com sendo: ∅ =
5 − 1
2
≅ 0.61803
 O algoritmo da proporção áurea é semelhante ao método da bisseção. Contudo, o próximo intervalo de 
busca não reduzido pela metade a cada iteração, mas reduzido segundo a proporção áurea.
 Se o intervalo inicial de busca for [a,b], então serão introduzidos dois pontos interiores 𝑥1 𝑒 𝑥2 de acordo com a 
proporção áurea: 𝑥2 = 𝑎 + ∅ b − a e 𝑥1 = 𝑏 − ∅ b − a
 A função é avaliada nos pontos interiores 𝑥1 𝑒 𝑥2 . Se 𝑓(𝑥1) > 𝑓(𝑥2) , o próximo intervalo será [a,b ]=[a, 𝑥2] , 
senão o próximo intervalo será [a,b ]=[𝑥1, 𝑏]
 O procedimento é repetido enquanto o intervalo for maio que um tolerância 𝑏 − 𝑎 > 𝜖
a 𝑥1 𝑥2 b 
Novo intervalo
a 𝑥1 𝑥2 b 
Novo intervalo
𝑓(𝑥2) > 𝑓(𝑥1)
𝑓(𝑥1) > 𝑓(𝑥2)
Método Intervalares: Proporção Áurea (Golden ratio)
 Pode ficar preso em um mínimo local
𝑦 = 𝑓 𝑥 = 𝑒 sin 2𝑥 −3 sin 3𝑥 −2 ≤ 𝑥 ≤ 5
 Deve ser dada um intervalo contendo somente um máximo/mínimo (semelhante à 
bisseção!!)
𝑦 = 𝑓 𝑥 = 𝑒 sin 2𝑥 −3 sin 3𝑥 −2 ≤ 𝑥 ≤ 5
Busca aleatória
 Solução através a força bruta
 A função f(x) é avaliada em um número muito grande de pontos no intervalo [a,b]. 
 Escolhemos como o máximo (ou mínimo) o ponto 𝑥𝑜 com maior (ou menor) 𝑓(𝑥𝑜)
 Com um número suficiente de pontos, a busca aleatória sempre encontra o ótimo global.
𝑛 = 200
Busca aleatória
𝑛 = 1000
𝑛 = 1000
𝑛 = 100000
Visualização deu um função de 2 dimensões
𝑧 = 𝑓 𝑥, 𝑦 = exp(sin 2𝑥 − 𝑦 − 3 sin 3𝑥 cos(2𝑦)
 A otimização 2d compreende a busca de máximos (globais) de uma função y=f(x,y).
Otimização em 2 dimensões
Busca aleatória 2D
Solução através a força bruta
A função 𝑧 = 𝑓 𝑥, 𝑦 é avaliada em um número muito grande de pontos no intervalo 𝑥 ∈ 𝑥𝑖 , 𝑥𝑓 𝑒 𝑦 ∈
[𝑦𝑖 , 𝑦𝑓]
Escolhemos como o máximo (ou mínimo) o ponto (𝑥𝑜, 𝑦𝑜) com maior (ou menor) 𝑓(𝑥𝑜, 𝑦𝑜)
Com um número suficiente de pontos, a busca aleatória sempre encontra o mínimo global.
𝑧 = 𝑓 𝑥, 𝑦 = exp(sin 2𝑥 − 𝑦 − 3 sin 3𝑥 cos(2𝑦)
Busca aleatória 2D
𝑧 = 𝑓 𝑥, 𝑦 = exp(sin 2𝑥 − 𝑦 − 3 sin 3𝑥 cos(2𝑦)
3 ≤ 𝑥 ≤ 7
−2 ≤ 𝑦 ≤ 2
Influência do número pontos
Steepest Ascent - Subida pelo Gradiente
O Algoritmo Steepest Ascent se baseia no Gradiente de uma função. 
Seja uma função 𝑧 = 𝑓 𝑥, 𝑦 = 𝑓( Ԧ𝑝), com Ԧ𝑝 = 𝑥, 𝑦 , de duas variáveis. 
O seu vetor Gradiente será :
𝛻𝑧 = 𝑔𝑟𝑎𝑑(𝑧) =
𝜕𝑧
𝜕𝑥
Ƹ𝑖 +
𝜕𝑧
𝜕𝑦
Ƹ𝑗
Exemplo:
𝑧 = 𝑓 𝑥, 𝑦 = exp(sin 2𝑥 − 𝑦 − 3 sin 3𝑥 cos(2𝑦)
𝛻𝑧 = 𝑔𝑟𝑎𝑑(𝑧) =
𝜕𝑧
𝜕𝑥
Ƹ𝑖 +
𝜕𝑧
𝜕𝑦
Ƹ𝑗
O vetor Gradiente avaliado em um ponto Ԧ𝑝 = 𝑥, 𝑦 aponta sempre para a direção de maior 
inclinação da função em Ԧ𝑝 = 𝑥, 𝑦 .
O Gradiente forma um campo de vetores 𝑧 = 𝑓 𝑥, 𝑦 = exp(sin 2𝑥 − 𝑦 − 3 sin 3𝑥 cos(2𝑦)
𝛻𝑧 = 𝑔𝑟𝑎𝑑(𝑧) =
𝜕𝑧
𝜕𝑥
Ƹ𝑖 +
𝜕𝑧
𝜕𝑦
Ƹ𝑗
Algoritmo para o Método Steepest Ascent
1. Seja uma função 𝑧 = 𝑓 𝑥, 𝑦 = 𝑓( Ԧ𝑝), com Ԧ𝑝 = 𝑥, 𝑦 , que se queira encontrar um máximo 
(ou mínimo), 
2. Escolha um ponto inicial 𝑝1 = 𝑥1, 𝑦1
3. Faça 𝑝𝑜 = 𝑝1
4. (i) Calcule o vetor Gradiente neste ponto 𝛻𝑓(p0), e siga na direção de busca Ԧ𝑑 =
𝛻𝑓(𝑝0)
𝛻𝑓(p0)
5. Escolha um passo h decrescente a cada iteração ; ou faça uma otimização de um parâmetro 
na direção Ԧ𝑑, para encontrar o passo h com o qual 𝑓 𝑝0 + ℎ Ԧ𝑑 seja máximo (ou mínimo)
6. Vá para o próximo ponto na direção Ԧ𝑑 𝑝1 = 𝑝0 + ℎ Ԧ𝑑
7. Se 𝑝1 − 𝑝0 < 𝜖 Pare
8. Senão vá para o passo 2
𝑝1 = (5.5, 1.2)
𝑝1 = (5.5, 1.2) 𝑝1 = (5.5, 1.2)
Otimização de h a cada iteração
h é dividido por 2 a cada iteração
𝑝1 = (5.5, 1.2)
𝑝2 = (5.9,−1.0)
𝑝1 = (5.5, 1.2)
𝑝2 = (5.9,−1.0)
𝑝3 = (4.7, 0.0)
𝑝4 = (5.5,−1.0)
	Slide 1: Métodos Numéricos para Engenharia 
	Slide 2: Otimização em 1 dimensão 
	Slide 3: Raízes de f plica , abre parêntese x fecha parêntese 
	Slide 4: Métodos Abertos - Newton Raphson (ou também secante modificado)
	Slide 5
	Slide 6
	Slide 7: Método Intervalares: Proporção Áurea (Golden ratio)
	Slide 8: Método Intervalares: Proporção Áurea (Golden ratio)
	Slide 9
	Slide 10: Busca aleatória
	Slide 11: Busca aleatória
	Slide 12: Visualização deu um função de 2 dimensões 
	Slide 13: Otimização em 2 dimensões 
	Slide 14: Busca aleatória 2D
	Slide 15: Influência do número pontos
	Slide 16: Steepest Ascent - Subida pelo Gradiente
	Slide 17
	Slide 18: Algoritmo para o Método Steepest Ascent
	Slide 19
	Slide 20
	Slide 21
	Slide 22