View
225
Download
0
Category
Preview:
Citation preview
1
1
Otimização de ProcessosCapítulo 4:
Otimização Unidimensional Sem Restrições (OUSR)
.
2
2
Algoritmos de Otimização
P1. Estabeleça o intervalo de busca ou estimativa inicial que contenha o ponto de mínimo da FO
O mapeamento fornece esse intervalo ou estimativa inicial
P2. Defina uma tolerânciaP3. Aplique o método selecionado até atingir a
tolerância, certificando-se que: f(x k+1) < f(xk)
3
3
Tolerância ou Critério de Parada
Erro absoluto na FO:
Erro relativo na FO:
Erro absoluto no ponto ótimo:
ou
11 kk xfxf
2
1
k
kk
xfxfxf
31 k
iki xx
.41
211
n
i
ki
ki
ki
ki xxxx
4
4
Erro relativo no ponto ótimo:
Erro absoluto na direção de busca:
x xx
ik
ik
ik
1
5
.6
2
1
n
i x
k
kxxfxf
5
5
Taxa de convergência Norma euclidiana:
Linear:
Ordem p:
Superlinear:
101
xx
xxk
k
x xii
n
2
1
101
pk
k
xx
xx
.0lim1
kk
k
k xx
xx
6
6
Métodos para OUSR Motivação:
M1. Problemas unidimensionais sem restriçõesM2. Incorporação da(s) restrições à FOM3. Técnicas OMSR e OMCR se originam em OUSRM4. Auxilia em problemas onde desconhecemos a
região de busca Classificação dos métodos para OUSR:
MD - Métodos Diretos (utilizam apenas as funções)MI - Métodos Indiretos (utilizam as derivadas).
7
7
Métodos Diretos (MD) p/ OUSR Não utilizam derivadas
G1. Métodos por diminuição da região de busca:G1.1. Dois intervalos iguais de buscaG1.2. Método da seção áurea
G2. Métodos por aproximação polinomial da FO:G2.1. Interpolação quadráticaG2.2. Interpolação cúbica.
8
8
Métodos por Diminuição da Região de Busca
AlgoritmoP1. Escolha uma região viável (a,b) que
contenha uma função unimodalP2. Calcule f(x) em dois ou mais pontos.P3. Compare os valores de f(x) eliminando as
regiões que tem maiores valores de f(x) .
9
9
Três intervalos iguais de busca x1 - a = b - x2 = x2 - x1 neste caso o intervalo
é reduzido de 1/3 a cada iteração L0 é o intervalo de busca original (b - a) e Lk
é o intervalo após k interações, então
A cada iteração é necessário avaliar duas vezes a função f(x) .
L Lkk
23
0
10
10
Método da seção áurea O intervalo eliminado manterá sempre
uma mesma proporção com o intervalo original
x yx y
yyx y
yx
yy
y
11
10 618,
x ya b c
L Lk k 0 618 0,
11
11
Seção Áurea
12
12
Algoritmo Seção ÁureaP1. determine ak e bk , e a tolerância eP2. CalculeLk = bk - ak
x1k = ak + 0,382.Lk
x2k = bk - 0,618.Lk
P3. Calcule f(x1k) e f(x2
k)P4. Se f(x1
k) > f(x2k) => ak+1 = x1
k
bk+1 = bk
x1k+1 = x2
k
Se f(x1k) < f(x2
k) => bk+1 = x2k
ak+1 = ak
x2k+1 = x1
k
P5. Volte ao passo P2 até atingir a tolerância.
13
13
MD: Interpolação Quadrática f(x) aproximada por um polinômio
quadrático Seja f(x) unimodal e um intervalo de
busca que contenha o extremo Avalie f(x1) , f(x2) e f(x3) Aproxime f(x) no ponto ótimo (x*) por uma
função quadrática g(x) , então ...
..
..
23333
22222
21111
xcxbaxgxf
xcxbaxgxf
xcxbaxgxf
14
14
Mínimo de uma função quadrática g(x) :
Resolvendo g(x1) , g(x2) e g(x3) que formam um sistema de 3 eq’s e 3 incog’s:
ou
x bcg x
* 2
xx x g x x x g x x x g x
x x g x x x g x x x g xg x( )
12
22
32
1 32
12
2 12
22
3
2 3 1 3 1 2 1 2 3
xx x f x x x f x x x f x
x x f x x x f x x x f xf x( )
12
22
32
1 32
12
2 12
22
3
2 3 1 3 1 2 1 2 3
15
15
MD: Interpolação Cúbica f(x) aproximada por um polinômio cúbico
Seja f(x) unimodal e um intervalo de busca que contenha o extremo
Avalie f(x1) , f(x2) , f(x3) e f(x4) Aproxime f(x) no ponto ótimo (x*) por uma
função cúbica g(x), então podemos escrever um sistema de 4 equações lineares.
f x g x a x a x a x a( ) ( ) . . 13
22
3 4
16
16
SEAL:
logo Derivando g(x) e igualando a zero:
4321
4321
424
34
323
33
222
32
121
31
1111
aaaaA
xfxfxfxfF
xxxxxxxxxxxx
X
AXF
T
T
A X F 1
f xdx
a x a x a
xa a a a
aapr
3 2 0
2 4 126
12
21
3
2 22
1 3
1
. .
.
17
17
Comparação MD’s x MI’sMétodos Diretos Métodos IndiretosUtilizam apenas f(x) Utilizam f'(x) e f”(x)
+ lentos + rápidosTratamento + fácil das
descontinuidadesTratamento + difícil das
descontinuidadesTratamento + fácil das
restriçõesTratamento + difícil das
restriçõesPreferido Recaem em SENL
18
18
Algoritmos MI’sP1. Intervalo de busca contendo o ponto de
mínimo com FO unimodal neste intervaloP2. Defina uma tolerânciaP3. Aplique o MI até atingir a tolerância,
certificando-se que: f(x k+1) < f(xk) Quanto mais positivo for f"(xk) mais
rapidamente f(x) diminuirá Para maximizar f(x) , minimize -f(x) .
19
19
MI: Método de Newton
Baseado no método de Newton p/ SEANL Expandindo g(x k+1)= 0 em torno de x k :
Como podemos escrever g(x)= f‘(x)= 0
k
kkkkkkkk
xgxgxxxgxxxgxg
'0'. 111
k
kkk
k
kkk
xfxfxx
xgxgxx
"'
'11
20
20
Vantagens do Método de Newton
V1. Convergência quadrática se f "(x*) 0V2. Se FO é quadrática o mínimo é obtido em
uma iteração, pois a expansão em série deTaylor da função f(x) é exata
V3. Converge rapidamente p/ bom chute inicial Temos sempre que assegurar que a cada
iteração f(xk+1) < f(xk) para que o mínimo seja alcançado [f(xk+1) > f(xk) para o máximo].
21
21
Desvantagens do Método de Newton
D1. Só se aplica qdo existem f’(x) e f”(x)D2. Calcular a cada iteração f’(x) e f”(x)D3. Sensível à estimativa inicialD4. Se f”(x) tende a 0 a convergência é lentaD5. Se existe mais de um extremo o método
pode não convergir para o ponto desejadoou pode oscilar.
22
22
Método de Quasi-Newton
f’(x) aproximada por diferenças finitas DF1. Diferença finita para trás:
2
22x
xxfxxfxfxf
xxxfxfxf
23
23
DF2. Diferenças finitas para frente:
DF3. Diferenças finitas central:
f xf x x f x
x
f xf x x f x x f x
x
2 22
2
22
xxxfxfxxfxf
xxxfxxfxf
24
24
Portanto definindo h=x e obtemos
Esse método tem duas desvantagens em relação ao método de Newton:
D1. Necessidade de definir o passo hD2. Avaliação de uma função a mais a
cada iteração.
x x
f x
f xx
f x h f x h hf x h f x f x h h
k kk
kk
1
2
22
//
25
25
Método da Secante
Expandindo f(x) = 0 em série de Taylor e truncando no terceiro termo:
Diferenciando em relação a x e igualando a 0:
!2..
2 kkkkk xfxxxfxxxfxf
0'
kkk xfxxxfxfxxf
26
26
Em lugar de utilizar a f"(xk) usamos
Ponto ótimo aproximado
O x* é encontrado após algumas iterações A derivada f'(x) pode ser obtida por
diferenças finitas.
m
f x f x
x x
q p
q p
x xf x
f x f x x xapr
q p q p
/
27
27
Representação geométricado método da secante ou
regula falsi ou falsa posição
f’(x) f’(x)
xp
xq
Secante
x* xx*~
A sua ordem de convergência é de aproximadamente 1,6Requer menos esforço computacional que o quasi-Newton,pois precisa avaliar um número menor de funções
28
28
Algoritmo da Secantea. Escolha dois pontos xp e xq com derivadas
de sinal contráriob. Calcule xapr*c. Calcule f’(xapr *)d. Escolha o novo par de pontos que mantém o
sinal contrário entre as derivadase. Volte à etapa b até que a tolerância admitida
seja alcançada.
29
29
Avaliação dos Métodos Unidimensionais de Otimização
Requisitos desejados:R1. FO seja unimodalR2. Conhecer a região de busca que contenha o
extremo da FOR3. Nos MI’s dar boa estimativa inicialR4. Nos MI's, existir f’(x*) e/ou f”(x*) Conhecer as idiossincrasias dos programas.
30
30
Problemas da otimização Múltiplos extremos Erros de arredondamento FO com gradiente grande FO com gradiente próximo a zero Descontinuidades da FO Descontinuidades das FR
(para problemas com restrições) Interação entre as VD’s
(para multivariável).
31
31
Exercício:
2 3 4
max
:20 10constante
xL x
L x R C xsujeito a R
C x x x x
32
32
Dica:
1º: use a instrução fplot ou plot do MATLAB para mapear a função objetivo
2º: use a instrução fminbnd para encontrar o ponto ótimo
Ou1º: faça o mapeamento da função objetivo no EXCEL2º: use o solver do para encontrar o ponto ótimo
2 3 4
max max max
max min min
min min 20 10
x x x
x xx
x x
L x R C x C x
C x C x C x
C x x x x
33
33
Otimização Capítulo 5:
Otimização Multidimensional Sem Restrições (OMSR)
.
34
34
Métodos para OMSR Devem ser eficientes e robustos Formulação geral de problemas de OMSR:encontrar x* = [x1 *,x2 *,...,xn *] que minimiza f(x) Algoritmo geral:P1. Escolha ponto(s) de partida ou estimativa inicialP2. Calcule a direção de busca sk
P3. Obtenha a nova aproximação do ponto ótimo:xk+1 = xk + xk , onde xk = k.sk
P4. Verifique se a tolerância foi atingida, se não volte p/ P2.
35
35
Tolerância ou Critério de Parada
Erro absoluto na FO:
Erro relativo na FO:
Erro absoluto no ponto ótimo:
ou
11 kk xfxf
2
1
k
kk
xfxfxf
31 k
iki xx
.41
211
n
i
ki
ki
ki
ki xxxx
36
36
Erro relativo no ponto ótimo:
Erro absoluto na direção de busca:
x xx
ik
ik
ik
1
5
.6
2
1
n
i x
k
kxxfxf
37
37
Métodos Indiretos Métodos de 1a ordem: gradiente gradiente conjugado
Métodos de 2a ordem: Newton Levenberg-Marquardt
Métodos da secante ou quasi-Newton: Broyden Davidson-Fletcher-Powell (DFP) Broyden-Fletcher-Goldfarb-Shano (BFGS)
38
38
MI: Gradiente Descendente Utiliza a derivada de 1a ordem O gradiente aponta para a direção de
maior variação de f(x) Na minimização a direção de busca é
O ponto ótimo é atualizado por
s f xk k
1k k k k k k kk kx x x x s x f x
39
39
MI para OMSR Utilizam as derivadas de 1a e/ou 2a
A direção de pesquisa s é denominada direção descendente (para minimização), pois s < 0. Demonstração:
1
1mas 0
onde cos
e para minimizar 90 180 cos 0
k k k kT
k k k kT
k kT T
o o
f x f x f x s
f x f x f x s
f x s f x s
40
40
f x f x f x s
f x s f x s
k k T k k
T k k T
o o
1 0
90 180 0
.
. . . cos
cos
pois
e para minimizar
41
41
k = cte k = opt
Características do gradiente descendente:C1. Eficiente nas iterações iniciaisC2. Baixa taxa de convergência qdo x x*C3. Bom qdo ñ existe interação entre as VD’sC4. Determina apenas pontos estacionários.
1Tk k k k kopt Ts H x s f x s
42
42
MI: Gradiente Conjugado
Utiliza a derivada de 1a ordem Combina o gradiente da iteração anterior
com o gradiente da iteração atual Desempenho superior ao gradiente
descendente Tem taxa de convergência quadrática
43
43
Algoritmo do Grad. ConjugadoP1. Defina uma estimativa inicial xo
P2. Calcule f(xo), f(xo), so = - f(xo)P3. Compute x1 = xo + o.so . o é o escalar que
minimiza f(x) na direção so , ou seja, éobtido através de uma busca unidimensional
P4. Calcule f(x1) e f(x1). A nova direção de busca é combinação linear entre so e f(x1).
1
1 1 0 0 1 10T T
s f x f x f x s f x f x
44
44
para a k-ésima iteração
P5. Teste se a FO esta sendo minimizada,se não volte ao passo P4.
P6. Termine o algoritmo quando ||sk|| < tolerância Problema se a razão entre os produtos internos
dos gradientes entre as iterações k+1 e k for pequena recaimos no gradiente descendente.
1
1 1 1 1T Tk k k k k k ks f x f x f x s f x f x
45
45
MI: Método de Newton MI de 2a ordem Aproximar f(x) por série de Taylor
Derivando em relação a x e igualando a zero:
Portanto
Esta eq. define a direção e amplitude do passo.
12
T Tk k k k k kf x f x f x x x H x x
0k k kf x H x x
11k k k k kx x x H x f x
46
46
Podemos alterar o passo por:
Para avaliar o passo não é necessário inverter a Hessiana, basta resolver o SEAL
Método rápido quando converge Taxa de convergência rápida perto do ponto
ótimo, exatamente o comportamento contrário do método gradiente.
11k k k k k kk kx x x H x f x s
1 k k kk H x x f x
47
47
Desvantagens do NewtonD1. Requer a inversão de uma matriz, ou pelo
menos a solução de um sistema linear acada iteração
D2. Requer a avaliação analítica das derivadasde 1a e 2a ordem
D3. Pode convergir para um ponto de sela seH(x) não é positiva definida
D4. Tem desempenho fraco ou não convergequando a estimativa inicial é ruim.
48
48
MI: Levenberg-Marquardt
Combina o método do gradiente descendente com o de Newton
No início se comporta como o MI gradiente No final como o MI de Newton Matriz Hessiana modificada para sempre ser
positiva-definida e bem-condicionada Acrescento a Hessiana uma matriz positiva-
definida;
49
49
A cada iteração faço:
Ou:
Onde é um valor positivo que torna H(x) > 0 e bem-condicionada
Se = 0 Método de Newton Se Método Gradiente Descendente > min(autovalor da Hessiana) Marquardt aproveita as melhores características do
Gradiente Descendente e do Newton.
~H x H x I
~H x H x I
1 1
50
50
Algoritmo de MarquardtP1. Defina uma estimativa inicial xo e uma tolerânciaP2. Para k = 0 faça 0 = 103 . P3. Calcule f(xk).P4. Verifique se a tolerância foi atingida, se não
continueP5. Calcule P6. Compute xk+1 = xk + k .sk ; k vem da Eq. 5-F P7. Se f(xk+1) < f(xk) vá ao p/ P8, se não vá p/ P9P8. k+1 = 0,25 k , e k = k+1 . Volte ao passo P3P9. k = 2 k. Volte ao passo P3.
kkkk xfIHs 1
51
51
MI: Secante ou Quasi-Newton Análogo ao Método da Secante para OUSR Algoritmo:Passo 0 (zero):P1. Defina uma estimativa inicial e uma toler.P2. Selecione uma direção de busca inicial.
Usualmente so = - f(x)P3. Calcule . Se não for
positiva definida faça H H x
0 0
H I0
H0
52
52
Passo kP1. Calcule a amplitude do passo k
P2. Calcule xk+1 que minimiza f(x) por umabusca unidimensional na direção sk
P3. Calcule f(xk+1) e f(xk+1)P4. Calcule xk = xk+1 - xk e
g(xk) = f(xk+1) - f(xk)P5. Calcule
x x H sk k k k k
11
H H Hk k k
1
53
53
P6. Calcule a nova direção de busca através de
ou de
Passo k+1P1. Verifique se a tolerância foi atingidaP2. Se o critério de parada foi atingido, pare.
Se não, volte ao passo k Broyden, DFP, BFGS, etc.
s H f xk k k 1 1 1
1
H s f xk k k
1 1 1
54
54
Desvantagens Quasi-NewtonD1. pode deixar de ser > 0
D2. pode ser ilimitada
H Hk k
ou1
H Hk k
ou1
55
55
Desvantagens Quasi-NewtonD1. pode deixar de ser > 0
D2. pode ser ilimitada
D3. Se tem a
mesma direção da iteração anterior, então
é singular ou indeterminada.
H Hk k
ou1
H Hk k
ou1
x H f xk k k k
1
H Hk k 1 1 1
ou
56
56
Métodos Diretos (MD) para OMSR
Não utilizam as derivadas:MD1. Busca randômicaMD2. Grade de buscaMD3. Busca unidirecionalMD4. Método simplex ou do poliedro flexível MI’s tem taxa de convergência maior.
57
57
Busca Randômica AlgoritmoP1. Fazer k = 0P2. Randomicamente escolher um vetor xk
P3. Avaliar f(xk) P4. Verificar se a tolerância foi atingida,
se não retornar ao passo P2 Ponto de partida para outro algoritmo Cheque do mínimo local.
58
58
Grade de busca Mapeamento da FO segundo uma
geometria definida Requer elevado esforço computacional Algoritmo:P1. Definir a topologia da gradeP2. Em torno do ponto mínimo
encontrado,repetir a grade e/ou torná-la mais fina.
59
59
MD: Busca Unidimensional Estabelecida uma direção, fazer uma
OUSR nesta direção Eficiente para FO quadráticas sem
interações entre as VP’s Algoritmo:P1. Definir um vetor de partida e tolerânciasP2. Escolher um componente j do vetorP3. Na direção de j fazer uma OUSRP4. Voltar a P3 até percorrer todos os jP5. Verificar se as tolerâncias foram atingidas.
Se não ir para P2.
60
60
MD: Simplex ou Poliedro Flexível Utiliza uma figura geométrica regular (simplex)
para selecionar o ponto em k+1 Em 2 dimensões o simplex é um triângulo Em 3 dimensões o simplex é um tetraedro.
61
61
Comparação MD’s x MI’s Os métodos precisam: Definição de uma região de busca convexa Na região de busca a FO seja unimodal Ponto(s) de partida
Métodos Numéricos para OMSRMD’s MI’s
Usam f(x) f(x), f’(x), f”(x)> no iterações < no iterações
< tempo p/ iteraç. > tempo p/ iteraç.Pto(s) de partida Estimativa inicialEncontram apenas mínimos locais
Fornecem solução aproximada
62
62
MD’s x MI’s O POMSR pode ser resolvido por métodos
diretos ou indertos No MATLAB: help fmins (poliedro flexível) MI: linearizando a FO (métodos do gradiente) MI: linearizand o modelo (método de Newton).
Método LinearizaçãoTaxa de Convergência
Fórmula delonge dasolução
perto dasolução
Recorrência
Gauss-Seidel do modelo lenta alta análoga àEquação 6-31
Gradiente(descendente ou
conjugado)
da funçãoobjetivo
alta lenta análoga àEquação 5-5 ou
5-8
Marquardtcombina a
linearização domodelo com a dafunção objetivo
inicia conforme ométodo do gradiente e
depois se comportacomo o de Gauss-Seidel
análoga àEquação 5-14
63
63
Procedimento Geral para Resolver Problemas de
Otimização1. Definição dos objetivos2. Estudo Qualitativo3. Desenvolvimento da FO e das FR’s4. Mapeamento da FO5. Manipulação, normalização e simplificação da FO
e da FO e das FR’s6. Aplicação do algoritmo de otimização7. Análise de sensibilidade e
validação da solução encontrada8. Implementação da solução9. Manutenção preditiva e Auditoria continuada.
64
64
Exercício:Qual o valor máximo de f(y, z) ?Qual o valor da variável de decisão no ponto
ótimo?
Faça o mapeamento Encontre o ponto ótimo utilizando uma rotina de
otimização
212214
212214
10101.5242
10101.5242seno,
zy
zyzyf
65
65
Mapeamento no MATLABclear allclose allclcy = [ -10 : 0.5 : +10 ] ;z = y ;[Y,Z] = meshgrid(y,z) ;aux = sqrt(1.5242*1e14*Y.^2+1e-12*Z.^2) + eps ;f = sin(aux)./aux ;surfc(Y,Z,f)xlabel('y')ylabel('z')zlabel('f')
66
66
Algoritmo no MATLAB% Programa principal: arquivo Programa_principa;.mX0 = [ -0.1 0.1 ] ; % Estimativa inicialopcoes = optimset('TolFun',1e-8,'TolX',1e-8,'Display','iter');X=fminunc(@funcao_objetivo,X0,opcoes)
% Função (subrotina): arquivo funcao_objetivo.mfunction [ f ] = funcao_objetivo(X)Y = X(1) ;Z = X(2) ;% aux = sqrt(1.5242*1e14*Y.^2+1e-12*Z.^2) + eps ;aux = sqrt(Y.^2+Z.^2) + eps ;f = sin(aux)./aux ;f = -f ;
Recommended