ou sr.sk

Otimização de Processos
Capítulo 4:
Otimização Unidimensional
Sem Restrições (OUSR)
.
1
1
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ância
P3. Aplique o método selecionado até atingir a
tolerância, certificando-se que: f(x k+1) < f(xk)
2
2
Tolerância ou
Critério de Parada
  f x   
k 1
Erro absoluto na FO:
f x

Erro relativo na FO:
f x   f x 

f x 

Erro absoluto no ponto ótimo: xik 1  xik   3


ou
k 1
i
x
k
k 1
k
k
x 
k
i
 x
n
k 1
i
1

k 2
i
x
2
  4.
i 1
3
3

Erro relativo no ponto ótimo:
xik  1  xik
 5
k
xi

Erro absoluto na direção de busca:
 
f x
k
2
 f  x  

   6.

i 1 
  x x k 
n
4
4
Taxa de convergência



Norma euclidiana:
Linear:
k 1
x x
x x
k
x 
2
i
 0  1
x
Ordem p:
k 1
x
x x
k

x
i 1


n

 p
 0  1
Superlinear:
x
lim
k 
k 1
x
x x
k


  k  0.
5
5
Métodos para OUSR

Motivação:
M1. Problemas unidimensionais sem restrições
M2. Incorporação da(s) restrições à FO
M3. Técnicas OMSR e OMCR se originam em OUSR
M4. 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).
6
6
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 busca
G1.2. Método da seção áurea
G2. Métodos por aproximação polinomial da FO:
G2.1. Interpolação quadrática
G2.2. Interpolação cúbica.
7
7
Métodos por Diminuição
da Região de Busca

Algoritmo
P1. Escolha uma região viável (a,b) que
contenha uma função unimodal
P2. 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) .
8
8
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
k
 2 0
L   L
 3
k

A cada iteração é necessário avaliar duas
vezes a função f(x) .
9
9
Método da seção áurea

O intervalo eliminado manterá sempre
uma mesma proporção com o intervalo
original
a
b
x
c
y

x  y 1
x y  y

y
x
y
1 y
 
y x 1 y


y  0,618
L   0,618 L0
k
k
10
10
Seção Áurea
11
11
Algoritmo Seção Áurea
P1. determine ak e bk , e a tolerância e
P2. Calcule Lk = bk - ak
x1k = ak + 0,382.Lk
x2k = bk - 0,618.Lk
P3. Calcule f(x1k) e f(x2k)
P4. Se f(x1k) > f(x2k) =>
ak+1 = x1k
bk+1 = bk
x1k+1 = x2k
Se f(x1k) < f(x2k) =>
bk+1 = x2k
ak+1 = ak
x2k+1 = x1k
P5. Volte ao passo P2 até atingir a
tolerância.
12
12
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
f  x1   g  x1   a  b.x1  c.x12
f  x2   g  x2   a  b.x2  c.x2
2
f  x3   g  x3   a  b.x3  c.x32 .
13
13

Mínimo de uma função quadrática g(x) :

b
x

2c
Resolvendo g(x1) , g(x2) e g(x3) que
formam um sistema de 3 eq’s e 3
incog’s:
*
g x
x

g( x)

x

f ( x)









2
2
2
2
2
2


x

x
g
x

x

x
g
x

x

x




1
2
3
1
3
1
2
1
2 g x 3 

 
2   x 2  x 3  g  x1    x 3  x1  g x 2    x1  x 2  g x 3  


ou



2
2
2
2
2
2


x

x
f
x

x

x
f
x

x

x




1
2
3
1
3
1
2
1
2 f  x3 

 
2   x 2  x 3  f  x1    x 3  x1  f  x 2    x1  x 2  f  x 3  


14
14
MD: Interpolação Cúbica

f(x) aproximada por um polinômio cúbico
f ( x )  g ( x )  a1 x 3  a 2 . x 2  a 3 . x  a 4



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.
15
15

SEAL:
FXA
 x13
 3
x
X   23
 x3
 3
 x4
x12
2
x2
2
x3
2
x4
F   f x1 
T
A  a1
T


A X
a2
x1 1

x2 1
x3 1

x4 1
f  x2 
a3
f  x3 
a4 
f  x4 
1
F
logo
Derivando g(x) e igualando a zero:
f  x
dx
 3a 1 . x 2  2a 2 . x 1  a 3  0

x apr

2a 2  4a 22  12a 1 . a 3
6a 1
16
16
Comparação MD’s x MI’s
Métodos Diretos
Métodos Indiretos
Utilizam apenas f(x)
+ lentos
Tratamento + fácil das
descontinuidades
Tratamento + fácil das
restrições
Preferido
Utilizam f'(x) e f”(x)
+ rápidos
Tratamento + difícil das
descontinuidades
Tratamento + difícil das
restrições
Recaem em SENL
17
17
Algoritmos MI’s
P1. Intervalo de busca contendo o ponto de
mínimo com FO unimodal neste intervalo
P2. Defina uma tolerância
P3. 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) .
18
18
MI: Método de Newton


Baseado no método de Newton p/ SEANL
Expandindo g(x k+1)= 0 em torno de x k :
   g x  x
gx

k 1
k
k 1
  
 x .g ' x  0  x
k
k
k 1
 
 
g xk
x 
g' xk
k
Como podemos escrever g(x)= f‘(x)= 0 
 
 
 
 
k
k
g
x
f
'
x
k 1
k
x k 1  x k 
x
x



k
g' x
f " xk
19
19
Vantagens do Método de
Newton
V1. Convergência quadrática se f "(x*)  0
V2. Se FO é quadrática o mínimo é obtido em
uma iteração, pois a expansão em série de
Taylor 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].
20
20
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 inicial
D4. Se f”(x) tende a 0 a convergência é lenta
D5. Se existe mais de um extremo o método
pode não convergir para o ponto desejado
ou pode oscilar.
21
21
Método de QuasiNewton

f’(x) aproximada por diferenças finitas

DF1. Diferença finita para trás:
f  x   f  x  x 
x
f  x   2 f  x  x   f  x  2 x 


f x  
x 2
f  x  
22
22
DF2. Diferenças finitas para frente:
f  x  
f  x  
f  x  x   f  x 
x
f  x  2 x   2 f  x  x   f  x 
x 2
DF3. Diferenças finitas central:
f  x  x   f  x  x 
2 x
f  x  x   2 f  x   f  x  x 
f x  
x 2
f  x  
23
23

x
k 1
Portanto definindo h=x e obtemos
x 
k
   x   f  x  h   f  x  h  / 2 h
f  x 
 f  x  h   2 f  x   f  x  h  / h
f  xk
k
k
2
Esse método tem duas desvantagens
em relação ao método de Newton:
D1. Necessidade de definir o passo h
D2. Avaliação de uma função a mais a
cada iteração.

24
24
Método da Secante

Expandindo f(x) = 0 em série de Taylor e
truncando no terceiro termo:
  
f x   f x k  x  x k


x  x  . f x 

. f x  
2!
k 2
k
k
Diferenciando em relação a x e igualando
a 0: f x 
k
k
k
x
  
   0
 f '  x   f  x  x  x f  x
25
25

Em lugar de utilizar a f"(xk) usamos
m


 
xq  x p



 f   x   f   x  /  x
Ponto ótimo aproximado
x

 
f  xq  f  x p

apr
x
q
f  xq
q
p
q
 xp

O x* é encontrado após algumas iterações
A derivada f'(x) pode ser obtida por
diferenças finitas.
26
26
Representação geométrica
do método da secante ou
regula falsi ou falsa posição
f’(x)
f’(x)
Secante
xp
~
x*
x*
xq
x
A sua ordem de convergência é de aproximadamente 1,6
Requer menos esforço computacional que o quasi-Newton,
pois precisa avaliar um número menor de funções
27
27
Algoritmo da Secante
a. Escolha dois pontos xp e xq com derivadas
de sinal contrário
b. Calcule xapr*
c. Calcule f’(xapr *)
d. Escolha o novo par de pontos que mantém o
sinal contrário entre as derivadas
e. Volte à etapa b até que a tolerância admitida
seja alcançada.
28
28
Avaliação dos Métodos
Unidimensionais de Otimização
Requisitos desejados:
R1. FO seja unimodal
R2. Conhecer a região de busca que contenha o
extremo da FO
R3. Nos MI’s dar boa estimativa inicial
R4. Nos MI's, existir f’(x*) e/ou f”(x*)
 Conhecer as idiossincrasias dos programas.

29
29
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).
30
30
Exercício:
max L  x 
x

L  x  R  C  x

sujeito a : 
R  constante
C  x   20 x 2  10 x 3  x 4

31
31
Dica:
max L  x   max  R  C  x    max  C  x  
x
x
x
max  C  x    min   C  x    min  C  x  
x
x
x

min  C  x    min 20 x 2  10 x 3  x 4
x
x

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
Ou
1º: faça o mapeamento da função objetivo no EXCEL
2º: use o solver do para encontrar o ponto ótimo
32
32
Otimização
Capítulo 5:
Otimização Multidimensional
Sem Restrições (OMSR)
.
33
33
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 inicial
P2. 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.
34
34
Tolerância ou
Critério de Parada
  f x   
k 1
Erro absoluto na FO:
f x

Erro relativo na FO:
f x   f x 

f x 

Erro absoluto no ponto ótimo: xik 1  xik   3


ou
k 1
i
x
x 
k
i
k
k 1
k
k
 x
n
k 1
i
1

k 2
i
x
2
  4.
i 1
35
35

Erro relativo no ponto ótimo:
xik  1  xik
 5
k
xi

Erro absoluto na direção de busca:
 
f x
k
2
 f  x  

   6.

i 1 
  x x k 
n
36
36
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)
37
37
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 é
 
s  f x
k

k
O ponto ótimo é atualizado por
x
k 1
 
 x   x  x   k  s  x   k  f x
k
k
k
k
k
k
38
38
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:
k 1
k
k
k
T
f x
 f x  f x s
   
 
mas f  x   f  x    f  x   s  0
onde  f  x   s   f  x   s  cos 
k 1
T
k
k
k
T
k
k
T
e para minimizar  90o    180o  cos   0
39
39

f x
pois
k 1

 
 f x
 
k
 
 T f x . s  0
k
k
 T f x . s   T f  x  . s . cos 
k
k
e para minimizar  90 o    180 o  cos   0
40
40
cte
  k = opt
 k=
 
 opt    s

k T
 
1
 
k
k
 H x  s  T f x  s 

 
k
k
 Características
do gradiente descendente:
C1. Eficiente nas iterações iniciais
C2. Baixa taxa de convergência qdo x  x*
C3. Bom qdo ñ existe interação entre as VD’s
C4. Determina apenas pontos estacionários.
41
41
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
42
42
Algoritmo do Grad. Conjugado
P1. 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
 
 
T
T
0
0
1
1


0 





s  f x   f x
 f x   s   f x
 f x  
 

 



1
1
43
43
para a k-ésima iteração
s
k 1

 f x
k 1

 
 
1
T
k
k
k
  f x   f x    s
 



  f x

k 1



T
  f x k 1  
 
 
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.
44
44
MI: Método de Newton
MI de 2a ordem
 Aproximar f(x) por série de Taylor
T
1
k
k
k
k T
k
k
f  x   f x  f x    x   x  H x   x


2
 Derivando em relação a x e igualando a zero:

 
Portanto
 
 
f x
k

 
 H x  x
k

k
 

0
Esta eq. define a direção e amplitude do passo.
x  x
k
k 1
 
1
 
k


x  H x
 f x


k
k
45
45

Podemos alterar o passo por:
x  x
k

k 1


k
k
 
Para avaliar o passo não é necessário
inverter a Hessiana, basta resolver o SEAL
1

 
1
k
k
 x     H x   f x   k  s


k
k
 
 H x  x
k
k

 
 f x
k
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.
46
46
Desvantagens do Newton
D1. Requer a inversão de uma matriz, ou pelo
menos a solução de um sistema linear a
cada iteração
D2. Requer a avaliação analítica das derivadas
de 1a e 2a ordem
D3. Pode convergir para um ponto de sela se
H(x) não é positiva definida
D4. Tem desempenho fraco ou não converge
quando a estimativa inicial é ruim.
47
47
MI: LevenbergMarquardt





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 positivadefinida;
48
48







~
A cada iteração faço: H  x   H  x   I
Ou:

~
H  x
   H  x 
1
1
 I
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.
49
49
Algoritmo de Marquardt
P1. Defina uma estimativa inicial xo e uma tolerância
P2. Para k = 0 faça  0 = 103 .
P3. Calcule f(xk).
P4. Verifique se a tolerância foi atingida, se não
continue
1
k
k
k
k


s


H


I

f
x
P5. 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/ P9
P8.  k+1 = 0,25 k , e k = k+1 . Volte ao passo P3
P9.  k = 2 k. Volte ao passo P3.
50
50
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)
0
0

P3. Calcule H  H x 0 . Se H não for
positiva definida faça

 
0

H I
51
51
Passo k
P1. Calcule a amplitude do passo k
P2. Calcule xk+1 que minimiza f(x) por uma
busca unidimensional na direção sk
x
k 1
 
 x   H
k
k
k
1
s
k
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
k 1
k
k



H
H  H
 
52
52
P6. Calcule a nova direção de busca através de
s
ou de
k 1
 
  H
k  1 1

f x

k 1 k 1
k 1

H s  f x
k 1


Passo k+1
P1. Verifique se a tolerância foi atingida
P2. Se o critério de parada foi atingido, pare.
Se não, volte ao passo k
 Broyden, DFP, BFGS, etc.
53
53
Desvantagens Quasi-Newton
 
D1. H ou H
k
 
D2.  H
k
k 1
pode deixar de ser > 0
 
ou  H
k 1
pode ser ilimitada
54
54
Desvantagens Quasi-Newton
 H 
k 1
D1. H ou
k
 
D2.  H
k
D3. Se  x
pode deixar de ser > 0
  pode ser ilimitada
    H  f  x  tem a
ou  H
k
k
k 1
k 1
k
mesma direção da iteração anterior, então
H
k 1
ou
 H 
k 1 1
é singular ou indeterminada.
55
55
Métodos Diretos (MD) para OMSR
Não utilizam as derivadas:
MD1. Busca randômica
MD2. Grade de busca
MD3. Busca unidirecional
MD4. Método simplex ou do poliedro flexível
 MI’s tem taxa de convergência maior.

56
56
Busca Randômica
Algoritmo
P1. Fazer k = 0
P2. 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.

57
57
Grade de busca
Mapeamento da FO segundo uma
geometria definida
 Requer elevado esforço computacional
 Algoritmo:
P1. Definir a topologia da grade
P2. Em torno do ponto mínimo
encontrado,
repetir a grade e/ou torná-la mais fina.

58
58
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âncias
P2. Escolher um componente j do vetor
P3. Na direção de j fazer uma OUSR
P4. Voltar a P3 até percorrer todos os j
P5. Verificar se as tolerâncias foram atingidas.
Se não ir para P2.
59
59
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.
60
60
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 OMSR
MD’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 inicial
Encontram apenas mínimos locais
Fornecem solução aproximada
61
61
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ção
Taxa de Convergência
longe da
solução
perto da
solução
Gauss-Seidel
do modelo
lenta
alta
Gradiente
(descendente ou
conjugado)
da função
objetivo
alta
lenta
Marquardt
combina a
linearização do
modelo com a da
função objetivo
inicia conforme o
método do gradiente e
depois se comporta
como o de Gauss-Seidel
Fórmula de
Recorrência
análoga à
Equação 6-31
análoga à
Equação 5-5 ou
5-8
análoga à
Equação 5-14
62
62
Procedimento Geral para
Resolver Problemas de
Otimização
1.
2.
3.
4.
5.
6.
7.
8.
9.
Definição dos objetivos
Estudo Qualitativo
Desenvolvimento da FO e das FR’s
Mapeamento da FO
Manipulação, normalização e simplificação da FO
e da FO e das FR’s
Aplicação do algoritmo de otimização
Análise de sensibilidade e
validação da solução encontrada
Implementação da solução
Manutenção preditiva e Auditoria continuada.
63
63
Exercício:
Qual o valor máximo de f(y, z) ?
Qual o valor da variável de decisão no ponto
ótimo?
f  y, z  

seno 1.5242  1014 y 2  10 12 z 2

1.5242  1014 y 2  10 12 z 2
 Faça
o mapeamento
 Encontre o ponto ótimo utilizando uma rotina de
otimização
64
64
Mapeamento no MATLAB
clear all
close all
clc
y = [ -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')
65
65
Algoritmo no MATLAB
% Programa principal: arquivo Programa_principa;.m
X0 = [ -0.1 0.1 ] ; % Estimativa inicial
opcoes = optimset('TolFun',1e-8,'TolX',1e-8,'Display','iter');
X=fminunc(@funcao_objetivo,X0,opcoes)
% Função (subrotina): arquivo funcao_objetivo.m
function [ 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 ;
66
66