aula_otimizacao_impressao (1)

Prévia do material em texto

09/08/2013
1
Curso de Engenharia Química – Campus de Alegre
Esly CostaOtimização Não Linear
Prof. Esly Ferreira da Costa Junior
Departamento de Eng. Rural
Engenharia Química
2o Semestre de 2012
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização �ão Linear
Objetivos do Curso
• Familiarizar o graduando:
– com montagem de problemas de otimização
– com os fundamentos das principais técnicas de 
otimização
– com o uso das rotinas de otimização na 
resolução de problemas
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Bibliografia Básica
Edgar, T. F.; Himmelblau, D. M.; Lasdon, 
L. S.; Optimization of Chemical 
Process. 2ed, Ed. McGraw Hill, 2001. 
Otimização �ão Linear
Bibliografia Complementar
Bazarra, M. S.; Sherali, H. D.; Shetty, C. M.; Nonlinear Programming: Theory and 
Algorithms. 3ed, Ed. Wiley Interscience, 2006.
Luenberger, D. G.; YINYU, Y. E.; Linear and Nonlinear Programming. 3ed, Ed. Springer, 
2008. 
Bertsekes, D. P.; Nonlinear Programming. 2ed, Ed. Athena Scientific, 1999. 
Avriel, M.; Nonlinear Programming: Analysis and Methods. Ed. Dover Publications, 2003. 
Curso de Engenharia Química – Campus de Alegre
Esly Costa
O que é Otimizar?
“Um é pouco, 
dois é bom,
três é 
demais.”
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly CostaFormulação do Problema 
de Otimização
• Para a formulação do problema é necessário 
um modelo matemático que correlacione as 
variáveis do processo.
• Deve-se determinar uma expressão 
matemática entre as variáveis do processo 
que quantifique a adequação das soluções 
possíveis.
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
• A formulação do problema de otimização 
envolve:
1 – Pelo menos uma função objetivo 
(quantificação matemática da adequação de 
uma solução) 
2 – Restrições de igualdade 
3 – Restrições de desigualdade 
Formulação do Problema 
de Otimização
Otimização �ão Linear
09/08/2013
2
Curso de Engenharia Química – Campus de Alegre
Esly Costa
• Notação geral para 1 função objetivo:
Minimizar: f(x) – Função Objetivo
Sujeito a: h(x) = 0 – restrições de igualdade
g(x) ≥ 0 – restrições de 
desigualdade
onde: x é o vetor com n variáveis
h(x) e g(x) são vetores de equações que 
representam as restrições
Formulação do Problema 
de Otimização
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
• Conceitos:
– Uma solução viável satisfaz a todas as 
restrições do problema de otimização
– A região do espaço de busca n-dimensional 
composta pelas soluções viáveis é dita região 
viável
– Se uma restrição de desigualdade for atendida 
quando com o sinal de igualdade, esta restrição 
está ativa
Formulação do Problema 
de Otimização
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
• Conceitos:
– Se a região viável se restringir a um único 
ponto do espaço de busca n-dimensional, não 
há problema de otimização e sim a resolução do 
sistema de equações algébricas (restrições de 
igualdade e de desigualdade ativas).
– �úmero de graus de liberdade é o número de 
variáveis menos o número de restrições de 
igualdade (acrescido do número de restrições de 
desigualdade que estiverem ativas em toda a 
região viável).
Formulação do Problema 
de Otimização
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
• Analisar o processo, fazendo uma lista de 
todas as variáveis e características de 
interesse.
• Determinar o critério de otimização e 
construir a função objetivo como função das 
variáveis previamente levantadas. Neste 
passo, os coeficientes que compõem a 
função devem ser arbitrados pelo analista 
ou engenheiro.
Passos para otimizar processos 
(EDGAR et al., 2001)
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
• Desenvolver o modelo do processo e incluir 
os coeficientes da função objetivo. 
Determinar todas as relações de igualdade e 
desigualdade que em geral são provenientes 
de princípios físicos (balanços de massa, 
energia, quantidade de movimento), 
relações empíricas, conceitos implícitos e 
restrições externas. 
Passos para otimizar processos 
(EDGAR et al., 2001)
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
• Caso a dimensão e/ou complexidade do 
problema seja muito grande:
– Divida-o em partes que possam ser resolvidas
– Simplifique o modelo ou a função objetivo
• Aplicar a técnica de otimização
• Checar a resposta e a sensibilidade do 
resultado com os coeficientes da função 
objetivo ou com as suposições adotadas.
Passos para otimizar processos 
(EDGAR et al., 2001)
Otimização �ão Linear
09/08/2013
3
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Continuidade de Funções
• f(x) é contínua em um ponto x0 se:
– f(x0) existe
– lim f(x0) existe lim f(x0) = f(x0)
x→ x0 x→ x0
f(x)
xx0
f(x)
xx0
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Continuidade de Funções
• Se f(x) é contínua em todos os pontos de 
uma região R, f(x) é contínua na região R.
• Além da análise da continuidade da função, 
é importante a análise da continuidade da 
derivada:
2 4 6
0
10
20
30
f x
i
x
i
f( )x x2 16
Ex:
2 4 6
10
0
10
20
dfdx x
i
x
i
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Continuidade de Funções
• Um caso importante de descontinuidade de 
funções na análise de processos ocorre quando 
uma variável independente é inerentemente 
descontínua. Ex:
– Número de um bombas
– Diâmetro de uma tubulação
• Essas variáveis poderão ou não ser tratadas como 
contínuas. Em geral, esta decisão depende da 
dimensão desta variável.
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaFunções Unimodais e 
Multimodais
• Uma função unimodal f(x), numa 
determinada faixa especificada para x, é 
aquela que apresenta apenas um extremo 
(máximo ou mínimo) nesta faixa. Ex:
2 0 2 4 6 8 10 12
1
0
1
sin x
i
x
i
0 ≤ x ≤ 10 - multimodal
0 ≤ x ≤ 4 - unimodal
2 ≤ x ≤ 6 - unimodal
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
• O ponto estacionário de f(x) é aquele para o 
qual f’(x) = 0.
• O extremo de uma função pode ser um 
ponto estacionário ou não:
Funções Unimodais e 
Multimodais
f(x)
x1 x2 x3 x4 x5
Extremos: x1,x2,x3,x5
Estacionários: x2,x3,x4,x5
Sela: x4
x
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
• Uma função f(x) é chamada côncava numa 
região R se para dois vetores quaisquer 
desta região xa e xb:
f(θxa +(1-θ)xb) ≥ θf(xa) + (1-θ)f(xb)
Onde θ é um escalar entre 0 e 1. 
• Esta função será estritamente côncava se o 
sinal ≥ for trocado por >.
• Trocando-se o sinal ≥ por ≤, ter-se-á uma 
função convexa (estritamente ou não).
Funções Côncavas e Convexas
Otimização �ão Linear
09/08/2013
4
Curso de Engenharia Química – Campus de Alegre
Esly Costa
• Outra forma de determinar se a função é 
côncava ou convexa, consiste na análise das 
derivadas de segunda ordem de f(x):∇2f(x)
• ∇2f(x) é também chamado de matriz 
hessiana H(x):
Funções Côncavas e Convexas






















∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
=
2
n
2
2n
2
1n
2
n2
2
2
2
2
12
2
n1
2
21
2
2
1
2
x
f
xx
fxx
f
xx
f
x
f
xx
f
xx
f
xx
f
x
f
L
MOMM
L
L
H(x)
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
• Se H(x) for positiva definida (todos os 
valores característicos são positivos), a 
função é estritamente convexa.
– Se for positiva semidefinida (algum valor 
característicos nulo) a função é convexa
• Se H(x) for negativa definida (todos os 
valores característicos são negativos), a 
função é estritamente côncava.
– Se for negativa semidefinida (algum valor 
característicos nulo) a função é côncava
Funções Côncavas e Convexas
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly CostaAnálise da Concavidade em 
Pontos Estacionários
• Determine os pontos estacionários e a 
natureza da função (côncava ou convexa) 
em cada um destes pontos.
2
x
3
x
2
x
4
x
xxf
2
2
3
2
2
1
4
1
21 ++−=),(
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaAnálise da Concavidade em 
Pontos Estacionários
x1 x2 Valores 
característicos
-1 -1 2 e –1 Ponto de sela
-1 0 2 e 1 Convexa
0 -1 -1 e –1 Côncava
0 0 -1 e 1 Ponto de sela
1 -1 2 e –1 Ponto de sela
1 0 2 e 1 Convexa 1 0 1
1.5
1
0.5
0
0.5
0.148
0.148
0.068
0.068
0.068
0.068
 0.011
 0.011
 0.011
 0.011
 0.011
 0.011
 0.091
 0.091
 0.091
 0.091
 0.091
 0.091
 0.091
 0.091
 0.17
 0.17
 0.17
 0.17
 0.17
A
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Região Convexa
• Em uma região convexa, todos os pontos 
que formam a reta (x=θxa+(1-θ)xb, 0≤θ≤1) 
que liga quaisquer dois pontos xa e xb da 
região, pertencem à região.
x2
x1
xa
xb
x2
x1
xa
xb
região convexa região não convexa
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Região Convexa
• Uma região delimitada por restrições de 
desigualdade na forma g(x) ≥ 0 é convexa 
se todas as funções gi(x) forem côncavas.
• Uma região delimitada por restrições de 
desigualdade na forma g(x) ≤ 0 é convexa 
se todas as funções gi(x) forem convexas.
• Classifique as regiões abaixo e esboce-as:




≥−+−−
≥−−−
0x4x2x
01xxx
21
2
1
1
2
12




≥−++
≥−−
0x2xx
0x2x2x
21
2
1
1
2
12
Otimização �ão Linear
09/08/2013
5
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Região Convexa




≥−+−−
≥−−−
0x4x2x
01xxx
21
2
1
1
2
12
2.5 1.5 0.5 0.5 1.5
1
0
1
2
3
4
5
6
x2_1 x1
i
x2_2 x1
i
x1
i




≥−++
≥−−
0x2xx
0x2x2x
21
2
1
1
2
12
2.5 1.5 0.5 0.5 1.5
1
0
1
2
3
4
5
6
x2_1 x1
i
x2_2 x1
i
x1
i
região convexa Região não convexa
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Região Convexa e Otimização
• A região delimitada pelas restrições é 
denominada região viável.
• Os pontos no espaço de busca são:
– Interiores se satisfazem as restrições de 
desigualdade realmente como desigualdade
– Pontos de contorno se satisfazem as restrições 
de desigualdade como igualdade
– Pontos exteriores se não pertencem à região 
viável.
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Região Convexa e Otimização
• Quando uma restrição de desigualdade está 
ativa, ela faz com que o ótimo viável seja 
diferente do ótimo irrestrito.
Ótimo irrestrito e viável
2.5 1.5 0.5 0.5 1.5
1
0
1
2
3
4
5
6
x1
x2
2.5 1.5 0.5 0.5 1.5
1
0
1
2
3
4
5
6
x1
x2
Ótimo irrestrito
Ótimo viável
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
• Se a região viável for não convexa, pode 
haver ótimos locais mesmo que a função 
irrestrita seja unimodal.
2.5 1.5 0.5 0.5 1.5
1
0
1
2
3
4
5
6
Região Não Convexa e 
Otimização
Ótimo irrestrito
Ótimo viável local
Ótimo viável global
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
• A condição necessária para que um ponto 
seja um extremo é que o gradiente da 
função zere neste ponto.
• As condições suficientes para que um ponto 
seja um extremo são: o gradiente da função 
é nulo no ponto; a matriz hessiana da 
função é positiva definida (mínimo) ou 
negativa definida (máximo) neste ponto.
Condições Necessárias e 
Suficientes Para um Extremo de 
uma Função Irrestrita
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Análise de Funções Quadráticas
• Uma translação de eixos permite criar um 
novo conjunto de variáveis no qual a origem 
coincida com o extremo de uma função 
quadrática.
• Estando o extremo da função na origem, os 
os vetores característicos fornecem uma 
transformação de variáveis (rotação) que 
permite a eliminação dos termos cruzados 
de uma função quadrática.
Otimização �ão Linear
09/08/2013
6
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Análise de Funções Quadráticas
• Encontre o extremo da função abaixo
• Escreva a função em termos de novas 
variáveis (w1 e w2) nas quais o extremo 
está na origem.
• Utilizando os vetores característicos, realize 
uma transformação de variáveis (z1 e z2) 
que faça coincidir o eixo da função com os 
eixos das variáveis novas
f( ),x1 x2 .
7
5
x12 .
11
5
x1
12
5
..3
5
x2 x1 .
3
5
x2 .
3
5
x22
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaInterpretação da Função Objetivo 
usando Aproximação Quadrática
• A aproximação quadrática da função 
objetivo em torno de um extremo x* é:
– f(x) = f(x*) + ∇∇∇∇Tf(x*)∆∆∆∆x +½(∆∆∆∆xT)∇∇∇∇2f(x*)∆∆∆∆x
• Sendo o gradiente nulo no extremo:
– f(x) = f(x*) + ½(∆∆∆∆xT)H(x*)∆∆∆∆x
• Esta aproximação pode ser utilizada para 
caracterizar a função no entorno do ponto 
x*
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
x1 x2 Valores 
característicos
-1 -1 2 e –1 Ponto de sela
-1 0 2 e 1 Convexa
0 -1 -1 e –1 Côncava
0 0 -1 e 1 Ponto de sela
1 -1 2 e –1 Ponto de sela
1 0 2 e 1 Convexa
Interpretação da Função Objetivo 
usando Aproximação Quadrática
2
x
3
x
2
x
4
x
xxf
2
2
3
2
2
1
4
1
21 ++−=),(
1 0 1
1.5
1
0.5
0
0.5
0.148
0.148
0.068
0.068
0.068
0.068
 0.011
 0.011
 0.011
 0.011
 0.011
 0.011
 0.091
 0.091
 0.091
 0.091
 0.091
 0.091
 0.091
 0.091
 0.17
 0.17
 0.17
 0.17
 0.17
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaInterpretação da Função Objetivo 
usando Aproximação Quadrática
x1 x2 Valores 
característicos
-1 -1 2 e –1 Ponto de sela
f( ),x1 x2 .8.33310 2 ...
1
2
( )x1 1 x2 1
2
0
0
1
x1 1
x2 1
f( ),x1 x2 x1
2 .2 x1 .41667 .
1
2
x2
2
x2
f( ),∆x1 ∆x2 ∆x1
2 .1
2
∆x2
2 .8.333 10 2
1.1 1 0.9 0.8
1.1
1
0.9
0.8
 0.062
 0.066
 0.066
 0.066
 0.07
 0.07
 0.07
 0.07
 0.075
 0.075
 0.075
 0.075
 0.075
 0.079
 0.079
 0.079
 0.079
 0.079
 0.084
 0.084
 0.084
 0.084
 0.084
 0.084
 0.088
 0.088
 0.088 0.088
 0.093
 0.093
A
1.1 1 0.9 0.8
1.1
1
0.9
0.8
 0.066
 0.066
 0.066
 0.07
 0.07
 0.07
 0.07
 0.073
 0.073
 0.073
 0.073
 0.077
 0.077
 0.077
 0.077
 0.077
 0.081
 0.0810.081
 0.081
 0.081
 0.085
 0.085
 0.085
 0.085
 0.088
 0.088
 0.088
 0.088
 0.092
 0.092
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly CostaInterpretação da Função Objetivo 
usando Aproximação Quadrática
x1 x2 Valores 
característicos
-1 0 2 e 1 Convexa
f( ),∆x1 ∆x2 ∆x1
2 .1
2
∆x2
2
.25
1.1 1 0.9 0.8
0.2
0.1
0
0.1
0.2
1.1 1 0.9 0.8
0.2
0.1
0
0.1
0.2
f( ),x1 x2 .2.5 10 1 ...
1
2
( )x1 1 x2
2
0
0
1
x1 1
x2
f( ),x1 x2 x12 .2 x1 .75 .
1
2
x22
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaInterpretação da Função Objetivo 
usando Aproximação Quadrática
x1 x2 Valores 
característicos
0 -1 -1 e –1 Côncava
0.2 0.1 0 0.1 0.2
1.1
1
0.9
0.8
A
0.2 0.1 0 0.1 0.2
1.1
1
0.9
0.8
f( ),x1 x2 .1.66710 1 ...
1
2
( )x1 x2 1
1
0
0
1
x1
x2 1
f( ),x1 x2 .
1
2
x12 .
1
2
x22 x2 .3333
f( ),∆x1 ∆x2 .
1
2
∆x1
2 .1
2
∆x2
2
.1667
Otimização �ão Linear
09/08/2013
7
Curso de Engenharia Química – Campus de Alegre
Esly CostaOtimização Unidimensional:
Importância
• Muitos problemas de otimização podem ser 
formulados em termos de uma única variável.
• Problemas multidimensionais podem ser reduzidos 
a problemas unidimensionais por meio das 
restrições
• A maioria dos algoritmos de otimização 
multidimensionais utilizam buscas 
unidimensionais em cada iteração. 
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaOtimização Unidimensional:
Classificação
• Métodos diretos: utilizam apenas o cômputo 
da função objetivo.
– O valor da função é comparado em diversos 
pontos de avaliação na busca pelo extremo.
• Métodos indiretos: utiliza-se a condição 
necessária de um extremo.
– A expressão analítica da derivada é utilizada 
para o cômputo da mesma, sendo também 
usado o cômputo da função objetivo. 
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Intervalo que Contém o Extremo
• Grande parte dos métodos de otimização 
unidimensional necessitam de um intervalo no 
qual o extremo da função esteja incluído.
• Diversas estratégias podem ser empregadas na 
localização deste intervalo. Ex:
– xk+1 = xk + δ
– xk+1 = xk + 2k-1δ
onde x0 e δ são valores previamente estipulados
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Intervalo que Contém o Extremo
• Para a função (x-10)2, com x0=0 e δ = 0.1:
– xk+1 = xk + δ
k=101, [9,9 10,1]
– xk+1 = xk + 2k-1δ
k=8, [6,3 25,5]
0 6.5 13 19.5 26
0
75
150
225
300
f x
i
f x1
j
,x
i
x1
j
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Método de Newton
• O Método de Newton é um método 
indireto que consiste em resolver 
f’(x)=0 pelo método de Newton-
Raphson:
• Ressalta-se que o método de Newton 
utiliza uma aproximação quadrática da 
função a ser minimizada.
)(
)(
''
'
k
k
k1k
xf
xf
xx −=+
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
• No método de Quasi-Newton, as 
derivadas primeira e segunda da 
função objetivo são aproximadas por 
diferenças finitas
[ ]
[ ])()()(
)()(
hxfxf2hxf2
hxfhxfh
xx
kkk
kk
k1k
−+−+
−−+
−=+
Método de Quasi-Newton
Otimização �ão Linear
09/08/2013
8
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Método da Secante
• Utilizando-se uma aproximação 
quadrática da função minimizada:
f(x) = f(xq) + f’(xq)(x-xq)+ ½f’’(xq)(x-xq)2
• Derivando-se:
f’(x) = f’(xq)+f’’(xq)(x-xq)
• No extremo f’(x) é nula:
f’(xq)+m(x-xq) = 0
onde m é a derivada segunda
m
xf
xx
q
q )('* −=
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Método da Secante
• O método da Secante pressupõe a 
existência de um intervalo [xq xp] que 
contenha o mínimo da função.
• Considerando-se o gráfico de f’(x) versus x 
no intervalo [xq xp], a inclinação da reta que 
une estes pontos se iguala à derivada 
segunda de f(x) quando xq → xp.
pq
pq
xx
xfxf
m
−
−
=
)(')('
)(')('
))(('
*
pq
pqq
q
xfxf
xxxf
xx
−
−
−=
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Método da Secante
• Como o método é iterativo, o valor de x* 
estimado em cada iteração se tornará xp ou 
xq, fazendo-se com que os valores de f’(xq) 
e f’(xp) tenham sempre sinais opostos.
• Se a f’(x*) for nula, o problema convergiu 
(raro ser obtido).
• Um critério de parada é o módulo da 
diferença entre x* de duas iterações ser 
menor que a tolerância.
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Exercícios
• Resolver pelos métodos de Newton, 
Quase Newton, Secante e Secante 
com aproximação por diferenças 
finitas (h=10-4):
– f(x)=x2 –20x +100; x0=0; [6,3 25,5] 
– F(x)= exp(x) + exp(1/x); x0=0,3; δ = 0,1;
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly CostaMétodos de Eliminação de 
Região (Diretos)
• Os métodos de eliminação de região não 
envolvem o cômputo ou aproximação da 
derivada da função (diretos)
• Na busca unidimensional, inicia-se com um 
intervalo onde o mínimo da função se 
encontra.
• A função deve ser unimodal
• Em cada iteração, o intervalo é reduzido
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaBusca de Dois Pontos com Iguais 
Intervalos
• São escolhidos dentro do intervalo dois 
pontos x1 e x2, que dividem a região em três 
partes iguais.
• Avalia-se f(x1) e f(x2) e tem-se:
a bx1 x2
f(x)
f1 > f2
a bx1 x2
f(x)
f1 = f2
a bx1 x2
f(x)
f1 < f2
Otimização �ão Linear
09/08/2013
9
Curso de Engenharia Química – Campus de Alegre
Esly CostaBusca de Dois Pontos com Iguais 
Intervalos
• Fazer 3 iterações iniciando-se com [6 13]:
a bx1 x2
f(x)
f1 > f2
a bx1 x2
f(x)
f1 < f2
a b a b
Região 
eliminada
Novo 
intervalo
100x20xxf 2 +−=)(
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaBusca de Dois Pontos com Iguais 
Intervalos
6 8.33 10.67 13
0
5
10
15
20
f x
i
x
i
a x1 x2 b
f(x1)=2,778
f(x2)=0,444
a x1 x2 b
f(x1)=0,012
f(x2)=2,086
a x1 x2 b
f(x1)=0,396
f(x2)=0.166
8.33 9.89 11.44 13
0
2.5
5
7.5
10
f x
i
x
i
8.33 9.37 10.41 11.44
0
1
2
3
4
f x
i
x
i
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Busca Dicotômica
• Como no método anterior, em cada iteração 
é avaliada a função em dois pontos x1 e x2, 
que estão infinitesimalmente separados e 
estão no centro do intervalo.
• Fazer 2 iterações iniciando-se com [6 13] e 
sendo os pontos do centro do intervalo 
separados de 10-6:
100x20xxf 2 +−=)(
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
a b a b
6 9.5 13
0
5
10
15
20
f x
i
x
i
=f
xmax xmin
2
10
6
2
0.2500005
9.5 11.25 13
0
2.5
5
7.5
10
f x
i
x
i
=f
xmax xmin
2
10
6
2
0.2499995
=f
xmax xmin
2
10
6
2
1.56249875
=f
xmax xmin
2
10
6
2
1.56250125
Busca Dicotômica
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Seção Áurea
• A localização dos pontos no subintervalo é 
realizada de tal forma, que um dos pontos 
seja possa ser utilizado como ponto interior 
na próxima iteração:
a bx1 x2
x y
y
x1 x2 ba
x1 x2a
y
x
yx
y=
+
Tem-se que:
Fazendo-se x+y = 1:
x1
x
1
x1
−
=
−
2
53
x
−
=
2
51
y
+−
=b
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Seção Áurea
• Observa-se que o método de eliminação 
Seção Áurea é mais eficiente que os dois 
métodos prévios:
• Intervalos iguais: 
• Busca dicotômica:
• Seção Áurea:
• Fazer 4 iterações iniciando-se com [6 13]
( ) 0kk L32L =
( ) 0kk L21L =
( ) 0kk L251L )( +−=
Avaliações de f(x):
2k+2
2k+2
k+2
100x20xxf 2 +−=)(
Otimização �ão Linear
09/08/2013
10
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Seção Áurea
k a b L x1 x2 f(x1) f(x2)
0 6 13 7 8.674 10.326 1.759 0.106
1 8.674 13 4.326 10.326 11.348 0.106 1.816
2 8.674 11.348 2.674 9.695 10.326 0.093 0.106
3 8.674 10.326 1.652 9.305 9.695 0.483 0.093
4 9.305 10.326 1.021 9.695 9.936 0.093 0.004
Trabalho: Implementação do método da Seção Áurea. 
Dados: a, b, tol (=Lfinal), função
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaMétodos de Aproximação 
Polinomial
• A função é aproximada por um polinômio no 
intervalo no qual o mínimo é procurado
• O intervalo inicial deve conter o mínimo
• A função deve ser unimodal
• Em cada iteração, o intervalo que contêm o 
mínimo é reduzido
• Podem ser utilizados apenas os valores da função 
(direto) ou também das derivadas na construção 
do polinômio
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Interpolação Quadrática
• Considerando-se um método direto, o valor 
da função é calculado em três pontos do 
intervalo [x1 x2 x3]
• Pode-se mostrar que o valor ótimo da 
aproximação polinomial é:
(((( )))) (((( )))) (((( ))))
(((( )))) (((( )))) (((( )))) 




−−−−++++−−−−++++−−−−
−−−−++++−−−−++++−−−−
====
321213132
3
2
2
2
12
2
1
2
31
2
3
2
2
fxxfxxfxx
fxxfxxfxx
2
1
*x~
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Interpolação Quadrática
• Se a função é unimodal, está no intervalo
• O novo intervalo é escolhido de forma que 
o mínimo continue no intervalo
• Uma nova interpolação quadrática é 
realizada e o intervalo novamente reduzido
• O critério de parada pode ser a distância 
entre o valor de entre duas iterações:
*~x
*~x
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Interpolação Quadrática
• Se está entre x1 e x2:
• Se está entre x2 e x3:*~x
*~x
x1
f(x)
*~x x2 x3 x1
f(x)
*~x x2 x3
x1
f(x)
*~x x2 x3
� para f(x) 
unimodal
x1
f(x)
*~xx2 x3 x1
f(x)
*~xx2 x3 x1
f(x)
*~xx2 x3
� para f(x) 
unimodal
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Interpolação Quadrática
• Resolver o problema de otimização abaixo 
usado interpolação quadrática, com 
tolerância de 0,04, Usar x1 = 0,1, x2 = 1, e 
x3 = 3, 
Min f(x) = exp(x) + 1/x
Otimização �ão Linear
09/08/2013
11
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Interpolação Quadrática
Min f(x) = exp(x) + 1/x
x1 x2 x3 f1 f2 f3
0,1 1 3 11,105 3,718 20,419 1,269 4,345
0,1 1 1,269 11,105 3,718 4,345 1,005 3,727
*~x *)~(xf
1 2 3
10
20
f x
i
pol x
i
fi
j
,,x
i
x
i
xi
jOtimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Interpolação Quadrática
x1 x2 x3 f1 f2 f3
0,1 1 1,269 11,105 3,718 4,345 1,005 3,727
0,1 1 1,005 11,105 3,718 3,727 0,924 3,601
*~x *)~(xf
Min f(x) = exp(x) + 1/x
0.5 1
5
10
f x
i
pol x
i
fi
j
,,x
i
x
i
xi
jOtimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Interpolação Quadrática
x1 x2 x3 f1 f2 f3
0,1 1 1,005 11,105 3,718 3,727 0,924 3,601
0,1 0,924 1 11,105 3,601 3,718 0,897 3,567
*~x *)~(xf
0.5 1
5
10
f x
i
pol x
i
fi
j
,,x
i
x
i
xi
j
Min f(x) = exp(x) + 1/x
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Interpolação Quadrática
Min f(x) = exp(x) + 1/x
x1 x2 x3 f1 f2 f3
0,1 1 3 11,105 3,718 20,419 1,269 4,345
0,1 1 1,269 11,105 3,718 4,345 1,005 3,727
0,1 1 1,005 11,105 3,718 3,727 0,924 3,601
0,1 0,924 1 11,105 3,601 3,718 0,897 3,567
*~x *)~(xf
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly CostaUso da Busca Unidimensional 
em Problemas Multidimensionais
• Vários algoritmos de otimização 
multidimensionais determinam em cada 
iteração uma direção de busca s
• Uma busca unidimensional é realizada nesta 
direção com o objetivo de determinar o 
valor ótimo (λ∗) do “tamanho do passo”, λ: 
kk1k sxx λ+=+
kk s∆x *λ=
)s(x)(' kkff λλ +=Min
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaUso da Busca Unidimensional 
em Problemas Multidimensionais
• Usar, s = –∇∇∇∇f(x) na otimização da função 
abaixo
• Partindo de x0, limitar um intervalo de 
busca para λ e determinar λ∗ por 
interpolação quadrática
5x2xxxx2xf 1
2
1
2
2
2
12
4
1 +−++−=(x)Min






=
2
10x δ = 0,05
Otimização �ão Linear
09/08/2013
12
Curso de Engenharia Química – Campus de Alegre
Esly CostaUso da Busca Unidimensional 
em Problemas Multidimensionais














−
+





=
2
4
x
x
ff
2
1 λλ)('Min








+−
−+−
=∇
2
2
1
121
3
1
x2x2
2x2xx4x4
f (x) 





−
=∇
2
4
f 0 )(x
Busca Unidimensional:
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaUso da Busca Unidimensional 
em Problemas Multidimensionais
Busca do Intervalo:
00 =λ 50f =)('
05001 ,=+= δλλ 4,2516050f =),('
150212 ,=+= δλλ 5,0996150f =),('
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Interpolação Quadrática
λ1 λ2 λ3 f1 f2 f3
0 0,05 0,15 5 4,252 5,1 0,073 4,12
0,05 0,073 0,15 4,252 4,12 5,1 0,077 4,113
*
~
λ *)
~
(λf














−
+





=
2
4
x
x
ff
2
1 λλ)('Min
0 0.05 0.1 0.15
4.5
5
g x
i
pol x
i
fi
j
,,x
i
x
i
xi
jOtimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Busca Multidimensionais
• Vários algoritmos de otimização 
multidimensionais determinam em cada 
iteração uma direção de busca s
• Uma busca unidimensional é realizada nesta 
direção com o objetivo de determinar o 
valor ótimo (λ∗) do “tamanho do passo”, λ: 
kk1k sxx λ+=+
kk s∆x *λ=
)s(x)(' kkff λλ +=Min
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly CostaPasso Ótimo da Aproximação 
Quadrática
• Sendo a aproximação quadrática:
f(x) = f(xk) + ∇∇∇∇Tf(xk)(x-xk) + ½(x-xk)TH(xk)(x-xk)
• Na busca do passo, a função minimizada é:
f(λ)=f(x+λsk)=f(xk)+∇∇∇∇Tf(xk)(λsk)+½(λsk)TH(xk)(λsk)
• Diferenciando-se em relação a λ:
• Desta forma:
( ) ( ) ( ) λ
λ
λ kkkkk sxssx
)(
Hf
d
f TT +∇=
( )
( ) ( ) kkk
kk
*
sxs
sx
H
f
T
T∇
−=λ
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaEixos Coordenados como 
Direção de Busca
• Os eixos coordenados podem ser utilizados 
como direções de busca
• Observa-se que os eixos coordenados são 
mutuamente ortogonais
• Para funções quadráticas sem termos 
cruzados, este procedimento seria bastante 
eficiente
• O número de buscas seria igual à dimensão 
do problema
Otimização �ão Linear
09/08/2013
13
Cursode Engenharia Química – Campus de Alegre
Esly CostaEixos Coordenados como 
Direção de Busca
• Observa-se, entretanto, que se houver 
termos cruzados, o conjunto de eixos 
coordenados deve ser empregado diversas 
vezes
x0 x0
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaDireções Ortogonais como 
Direções de Busca
• Ainda que se considere uma função 
quadrática sem termos cruzados, o uso de 
direções ortogonais não sempre permite 
encontrar a solução com n buscas
1 0.5 0 0.5 1
1
0.5
0
0.5
1
22
22
1.61.6
1.61.6
1.4
1.4
1.4
1.4
1.2
1.2
1.2
1.2
1.2
1.2
1 1
1
11
1
0.8
0.8
0.8
0.8
0.8
0.8
0.6
0.6
0.6
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.4
0.2
0.2
0.2
A
x0
0.5
1
f( ),x y x2 .2 y2
x1
0.333
0.167
x2
0.111
0.056
1 0.5 0 0.5 1
1
0.5
0
0.5
1
22
22
1.61.6
1.61.6
1.4
1.4
1.4
1.4
1.2
1.2
1.2
1.2
1.2
1.2
1 1
1
11
1
0.8
0.8
0.8
0.8
0.8
0.8
0.6
0.6
0.6
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.4
0.2
0.2
0.2
A
x0
0.5
1
x1
0.5
0.5
x2
0
0
H
2
0
0
4
s0
1
1
s1
1
1
s0
2
1
s1
1
1
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Direções Conjugadas
• Dado um conjunto de direções de busca s0, 
s1, ..., sn-1 linearmente independente, elas 
são conjugadas em relação a uma matriz Q, 
positiva definida, se:
(si)TQsj = 0 0 ≤ i ≠ j ≤ n-1
• Este conceito é uma extensão do conceito 
de ortogonalidade, válido se Q=I.
• No caso da otimização de uma função 
quadrática, Q = H.
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Direções Conjugadas
• Considerando-se uma função objetivo 
quadrática com termos cruzados, os eixos 
coordenados do sistema transformado (com 
ponto estacionário na origem e eixos 
correspondente aos vetores característicos 
da matriz hessiana) consiste num conjunto 
de direções conjugadas no eixo original (os 
próprios vetores característicos).
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Direções Conjugadas
• Encontrar os valores e vetores 
característicos da função:
• f(x) = 3x12 + 2x1x2 + x22
• Verificar se as direções e são 
conjugadas no espaço transformado.
• Encontrar as direções acima no espaço 
original (x1, x2) e verificar se elas são 
conjugadas
1
1
λ
4 2
4 2
V
1
2 1
1 2
1
2
6 .4 2
2 2
2
4 .2 2
.2 2 8
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Busca Multidimensional
• Numa otimização n-dimensional, sendo s
um vetor unitário, o módulo do vetor 
deslocamento é dado por λ.
• Pela regra da cadeia, tem-se:
• O que se igual ao produto escalar:
λλλλ ∂
∂
∂
∂
++
∂
∂
∂
∂
+
∂
∂
∂
∂
= n
n
2
2
1
1
x
x
fx
x
fx
x
f
d
df
...






∂
∂
++
∂
∂






∂
∂
++
∂
∂
= n
n1
n
n1
xx
x
f
x
f
d
df
e...ee...e 11 λλλ
Otimização �ão Linear
09/08/2013
14
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Busca Multidimensional
• Assim, sendo θ o ângulo entre ∇∇∇∇f(xk) e sk:
• Geometricamente:
θ
λ
coss.)(xs).(x kkkk ff
d
df
∇=∇=
∇∇∇∇f(xk)
xk
sk
θθθθ
Hiperplano (n=2 ⇒reta)
tangente à função no ponto xk
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Busca Multidimensional
• Observa-se que se θ = 90o, tem-se um incremento 
nulo na função ao se dar um incremento 
diferencial no passo (o vetor gradiente é 
perpendicular à superfície de nível no ponto xk).
• Se θ = 0o, sk =∇∇∇∇f(xk) e tem-se, localmente, um 
incremento máximo da função (cosθ = 1).
• Se θ = 180o, sk =-∇∇∇∇f(xk) e tem-se , localmente, um 
incremento máximo da função em módulo, mas 
com sinal negativo (cosθ = -1).
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Método do Gradiente
• No método do Gradiente, a direção de busca 
em cada iteração é o vetor oposto ao 
gradiente da função no ponto xk: sk =-∇∇∇∇f(xk) 
• Observa-se que o método é indireto (utiliza-
se das derivadas da função)
• As derivadas parciais do gradiente podem 
ser calculadas por diferenças finitas
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Método do Gradiente
• Resolver pelo método do gradiente, 
calculando o tamanho do passo analiticamente
1 0.5 0 0.5 1
1
0.5
0
0.5
1
A
f(x) = x12 + 10x22






−
=
1
1
0x
=yi
1
8.991 10 3
0.074
6.614 10
4
5.411 10
3
4.865 10
5
=xi
1
0.899
0.074
0.066
5.411 10
3
4.865 10
3
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Método do Gradiente
• O método do Gradiente pode levar a um ponto 
de sela






=
50
0
,
x02
x
3
x
2
x
4
x
xxf
2
2
3
2
2
1
4
1
21 ++−=),(
1 0 1
1.5
1
0.5
0
0.5
0.148
0.148
0.068
0.068
0.068
0.068
 0.011
 0.011
 0.011
 0.011
 0.011
 0.011
 0.091
 0.091
 0.091
 0.091
 0.091
 0.091
 0.091
 0.091
 0.17
 0.17
 0.17
 0.17
 0.17
A
Resultado da 1a busca:






=
0
0
x
Ex: Resolver achando o passo 
ótimo por Quasi Newton
Deve-se checar se o 
ponto encontrado é 
realmente um mínimo
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Método do Gradiente Conjugado
• Consiste numa melhora do método do 
Gradiente, cujo objetivo é fazer com que 
cada direção seja conjugada em relação à 
anterior (para uma função quadrática)
• A direção sk+1 consiste numa combinação 
linear entre o -∇∇∇∇f(xk+1) e sk
)(x)(x
)(x)(x
s)(xs
kkT
1k1kT
k1k1k
ff
ff
f
∇∇
∇∇
+−∇=
++
++
Otimização �ão Linear
09/08/2013
15
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Método do Gradiente Conjugado
• A primeira direção de busca é -∇∇∇∇f(x0)
• É interessante reiniciar o método após n iterações, 
fazendo-se x0 = xn+1, para evitar que sejam obtidas 
direções linearmente dependentes.
• Resolver pelo Gradiente Conjugado, calculando o 
λ analiticamente (a primeira iteração já foi 
calculada no método do Gradiente)






−
=
1
1
0xf(x) = x1
2 + 10x22
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Métodos de Segunda Ordem
• Observa-se que o método do Gradiente (1a
ordem) corresponde a uma aproximação 
linear da função.
• Nos métodos de segunda ordem, utiliza-se a 
informação da curvatura da função por meio 
de sua aproximação quadrática:
f(x) = f(xk) + ∇∇∇∇Tf(xk)(x-xk) + ½(x-xk)TH(xk)(x-xk)
ou
f(x) = f(xk) + ∇∇∇∇Tf(xk)∆∆∆∆xk + ½(∆∆∆∆xk)TH(xk)∆∆∆∆xk
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Método de Newton
• Derivando-se a aproximação quadrática e 
igualando-se o gradiente a zero (mínimo):
∇∇∇∇Tf(x) = ∇∇∇∇f(xk) + H(xk)∆∆∆∆xk = 0
• Assim:
xk+1 – xk = ∆∆∆∆xk = - [H(xk)]-1∇∇∇∇f(xk)
• Esta equação consiste no Método de Newton. 
Observa-se que o procedimento de inversão da 
matriz hessiana pode ser substituído pela 
resolução de um sistema de equações lineares:
H(xk)∆∆∆∆xk = -∇∇∇∇f(xk)
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Método de Newton
• Em problemas quadráticos, o método de 
Newton leva à soluçãoem 1 passo:
1 0.5 0 0.5 1
1
0.5
0
0.5
1
A
f(x) = x12 + 10x22






−
=
1
1
0x
- [H(xk)]-1∇∇∇∇f(xk)
Otimização �ão Linear
Curso de Engenharia Química – Campus de Alegre
Esly Costa
• O método de Newton é iterativo para 
problemas não quadráticos






−
=
40
31
,
,
x0
2
x
3
x
2
x
4
x
xxf
2
2
3
2
2
1
4
1
21 ++−=),(
Ex:
Método de Newton






=
50
20
,
,
x0
2
x
3
x
2
x
4
x
xxf
2
2
3
2
2
1
4
1
21 ++−=),(
=Txi 1.3 1.0796 1.008 1.0001 1( )
=
T
yi 0.4 0.8 0.246 0.041 1.525 10
3
( )
=Txi 0.2 0.018 1.203 10 5 3.485 10 15( )
=Tyi 0.5 0.125 0.012 1.524 10 4( )
Pode-se obter um ponto de sela !! 1 0 1
1.5
1
0.5
0
0.5
0.148
0.148
0.068
0.068
0.068
0.068
 0.011
 0.011
 0.011
 0.011
 0.011
 0.011
 0.091
 0.091
 0.091
 0.091
 0.091
 0.091
 0.091
 0.091
 0.17
 0.17
 0.17
 0.17
 0.17
AOtimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly CostaTamanho do Passo no Método 
Newton
• No método de Newton, tem-se a seguinte 
direção de busca:
sk = - [H(xk)]-1∇∇∇∇f(xk)
• O passo de Newton é λ = 1.
• Pode-se utilizar uma busca unidimensional 
para determinar o passo ótimo para funções 
que não sejam quadráticas.
Otimização �ão Linear
09/08/2013
16
Curso de Engenharia Química – Campus de Alegre
Esly CostaForçando-se a Matriz Hessiana 
ser Positiva Definida
• Se a Matriz Hessiana não for positiva 
definida, o método de Newton pode resultar 
num ponto de sela.
• Mais além, se esta matriz for mal 
condicionada, erros numéricos podem surgir
• Assim, alguns autores sugerem fazer:
IH(x)(x)H
~
β+=
Observa-se que β deve ser um número positivo, cujo módulo 
é maior do que o módulo do menor autovalor de H(x)
Otimização �ão Linear Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
Métodos Secante ou 
Métodos da Métrica Variável
• Derivando-se a aproximação quadrática da função 
e igualando-se o gradiente a zero (mínimo):
∇∇∇∇Tf(x) = ∇∇∇∇f(xk) + H(xk)(x-xk ) = 0
• Fazendo-se x = xk+1:
H(xk)∆∆∆∆xk = ∇∇∇∇Tf(xk+1) - ∇∇∇∇f(xk) = ∆∆∆∆gk
• A idéia dos métodos da métrica variável, ou da 
secante consiste em calcular apenas o gradiente da 
função em cada iteração e utilizar a expressão 
acima para fazer uma aproximação de H(xk).
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
Métodos Secante ou 
Métodos da Métrica Variável
• A equação vetorial base destes métodos é:
H(xk)∆∆∆∆xk = ∆∆∆∆gk
• Observa-se que H(xk) possui n2 incógnitas (n é 
a dimensão do problema)
• A equação vetorial base possui apenas n 
equações e portanto, existem infinitas 
soluções para o problema e portanto 
infinitos possíveis métodos secante
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
Métodos Secante ou 
Métodos da Métrica Variável
• Os métodos secante são métodos de quasi-
Newton e, em cada iteração, uma 
aproximação da hessiana (Ĥ(xk) = Ĥk) é 
atualizada.
• A direção de busca é dada por:
sk = -(Ĥk)-1∇∇∇∇f(xk)
• Em cada iteração o tamanho do passo é 
determinado por uma busca unidimensional 
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
Métodos Secante ou 
Métodos da Métrica Variável
• Se f(x) for uma função quadrática, o passo 
ótimo possui solução analítica:
• Após n iterações, ter-se-a uma Ĥ igual à 
matriz hessiana do sistema e assim o 
mínimo será atingido em n iterações.
( )
( ) ( ) kkk
kk
*
sxs
sx
H
f
T
T∇
−=λ
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
Métodos Secante ou 
Métodos da Métrica Variável
• Uma das relações para atualização da matriz 
hessiana mais eficiente é BFGS (Broyden, 
1970, Fletcher, 1970, Goldfarb, 1970, 
Shanno, 1970): 
( )
( )
( )
( ) kk
kk
kk
kk
xHˆx
HˆxxHˆ
xg
gg
HˆHˆHˆ
∆∆
∆∆
−
∆∆
∆∆
=−=∆ +
kT
kTk
T
T
k1kk
09/08/2013
17
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
Métodos Secante ou 
Métodos da Métrica Variável
• O procedimento de inversão de matrizes 
pode ser evitado se no lugar da aproximação 
da hessiana for utilizada a aproximação de 
sua inversa (BFGS):
( ) ( ) ( )
( ) ( ) ( ) ( )
( )
( ) ( )
( ) ( ) 


 ∆∆


 ∆∆
∆∆∆




 ∆−∆
−
∆∆





 ∆−∆∆+∆




 ∆−∆
=−=∆
−
−−
−−+−
kkkk
kkkkk
kk
kkkkkk
xgxg
xxggHˆx
xg
gHˆxxxgHˆx
HˆHˆHˆ
TT
TT1k
T
T1kT1k
1k11k1k
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
Métodos Secante ou 
Métodos da Métrica Variável
• Resolver o problema abaixo utilizando-se a 
fórmula BFGS de atualização da inversa da 
hessiana:
f(x) = 3x12 +2x1x2 +1,5x22
( ) IHˆ =−10





−
=
1
1
x0
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Notação geral para 1 função objetivo:
Minimizar: f(x) – Função Objetivo
Sujeito a: h(x) = 0 – restrições de igualdade
g(x) ≥ 0 – restrições de 
desigualdade
onde: x é o vetor com n variáveis
h(x) e g(x) são vetores de equações que 
representam as restrições
Formulação do Problema 
de Otimização
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Conceitos:
– Uma solução viável satisfaz a todas as 
restrições do problema de otimização
– A região do espaço de busca n-dimensional 
composta pelas soluções viáveis é dita região 
viável
– Se uma restrição de desigualdade for atendida 
quando com o sinal de igualdade, esta restrição 
está ativa
Formulação do Problema 
de Otimização
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Conceitos:
– Se a região viável se restringir a um único 
ponto do espaço de busca n-dimensional, não 
há problema de otimização e sim a resolução do 
sistema de equações algébricas (restrições de 
igualdade e de desigualdade ativas).
– �úmero de graus de liberdade é o número de 
variáveis menos o número de restrições de 
igualdade (acrescido do número de restrições de 
desigualdade que estiverem ativas em toda a 
região viável).
Formulação do Problema 
de Otimização
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• O método dos Multiplicadores de Lagrange 
consiste na transformação do problema de 
otimização com restrições de igualdade num 
problema de resolução de equações 
algébricas.
• Para o uso das restrições de desigualdade, 
são utilizadas as variáveis de folga que 
transformam estas restrições em restrições 
de igualdade.
Método dos Multiplicadores de 
Lagrange
09/08/2013
18
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Para demonstrar o método, considere um 
problema bidimensional com um restrição:
Minimizar f(x1,x2) 
Sujeito a: h(x1,x2) = 0
• Observa-se que a restrição de igualdade 
pode sempre ser escrita na forma:
• onde e é uma constante
Método dos Multiplicadores de 
Lagrange
0exxhxxh 2121 =−= ),(),( exxh 21 =),(
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Observa-se que se f é diferenciável no 
mínimo (x*), qualquer variação 
infinitesimal viável em x* deve provocar 
uma variação nula na função.Assim:
• dh é nula porque é uma constante
Método dos Multiplicadores de 
Lagrange
2
2
1
1
dx
x
f
dx
x
f
0df
∂
∂
+
∂
∂
==
2
2
1
1
dx
x
h
dx
x
h
0dh
∂
∂
+
∂
∂
==
h
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Observa-se que dx1 e dx2 no ponto ótimo 
devem obedecer a um sistema linear de 
equações na forma:
a11dx1 + a12 dx2 = 0
a21dx1 + a22 dx2 = 0
• Este sistema sempre possui a solução trivial 
(dx1 = dx2 = 0) e para que outras soluções 
existam, seu determinante deve ser nulo:
Método dos Multiplicadores de 
Lagrange
0aaaa 12212211 =− ka
a
a
a
22
12
21
11 == k
a
a
a
a
22
21
12
11 ==ou
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• A constante k é definida como sendo –ω: 
• Além das duas equações acima, o valor de 
x* deve obedecer a restrição de igualdade:
h(x1,x2) = 0
Método dos Multiplicadores de 
Lagrange
2111 aa ω−= 2212 aa ω−=e
0
x
h
x
f
11
=
∂
∂
+
∂
∂
ω 0
x
h
x
f
22
=
∂
∂
+
∂
∂
ωe
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Observa-se que o problema de otimização 
restrita com duas variáveis foi transformado 
num sistema de equações algébricas com 
três variáveis (sendo a nova variável ω)
• A determinação destas equações algébricas 
é facilitada por meio do uso da função 
objetivo aumentada chamada Lagrangeano:
Método dos Multiplicadores de 
Lagrange
h(x)ω(x)ω)(x, ⋅+= TfL
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• O sistema de equações a ser resolvido para a 
solução do problema consiste nas derivadas 
parciais da função Lagrangeano em relação a cada 
uma das variáveis dos vetores x e ωωωω
• Ressalta-se que para cada restrição de igualdade, 
deve-se adicionar um multiplicador de lagrange.
• Um problema deste método é que qualquer ponto 
estacionário viável pode ser encontrado (mínimo, 
máximo ou sela). Mais além, pode haver mais que 
uma solução para o problema e elas devem ser 
diferenciadas.
Método dos Multiplicadores de 
Lagrange
09/08/2013
19
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Exemplos:
– Determinar a menor distância da função 
x2-x1-1 = 0 da origem
– Determinar a menor a a maior distância da 
origem da função 5x12 + 6x1x2 + 5x22 = 8
Método dos Multiplicadores de 
Lagrange
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• As restrições de desigualdade podem ser 
transformadas em restrições de igualdade por meio 
da inserção de variáveis de folga:
gj(x) ≥ 0 gj(x) – σj2 = 0
• Após esta inserção de variáveis, o problema passa 
a ter apenas restrições de igualdade
• O problema é então transformado num sistema de 
equações algébricas, cuja montagem é facilitada 
pela função Lagrangeano
Método dos Multiplicadores de 
Lagrange
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• O Lagrangeano é:
• Onde m é o número de restrições de 
igualdade e r é o número total de restrições.
• Conforme já discutido, a derivada de L em 
relação a cada variável de x, s, w e u deve 
ser nula no extremo.
Método dos Multiplicadores de 
Lagrange
∑∑∑∑∑∑∑∑
++++========
σσσσ−−−−−−−−++++====
r
1mj
2
jjj
m
1j
jj )(x)g(u(x)hw(x)fu)w,σ,(x,L
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Mais além, tem-se como condições necessárias 
para que x* seja um mínimo:
– Os gradientes das restrições de igualdade e de 
desigualdade ativas devem ser linearmente 
independentes
– uj ≥ 0
– A matriz hessiana de L (em relação a x) deve ser 
positiva semidefinida para qualquer direção de busca 
que seja viável, ou seja qualquer vetor v tal que: 
vT∇∇∇∇hj(x*)=0, (vT∇∇∇∇gj(x*)=0 se gj(x*)=0) e (vT∇∇∇∇gj(x*) ≥
0 se gj(x*)≠0), tem-se que vT∇∇∇∇2[L(x*,s*,w*,u*)]v ≥ 0
Método dos Multiplicadores de 
Lagrange
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• As condições suficientes para que x* seja 
um mínimo local, consistem nas anteriores, 
trocando-se a última por:
– A matriz hessiana de L (em relação a x) deve 
ser positiva definida para qualquer direção de 
busca que seja viável, ou seja qualquer vetor v
tal que: vT∇∇∇∇hj(x*)=0, (vT∇∇∇∇gj(x*)=0 se 
gj(x*)=0) e (vT∇∇∇∇gj(x*) ≥ 0 se gj(x*)≠0), tem-se 
que vT∇∇∇∇2[L(x*,s*,w*,u*)]v > 0
Método dos Multiplicadores de 
Lagrange
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• A programação quadrática é a forma mais simples 
de programação não linear restrita
• Nestes problemas, a função objetivo é quadrática e 
as restrições (de igualdade e/ou desigualdade) são 
lineares
• O uso dos multiplicadores de Lagrange transforma 
este problema numa Programação Linear
• Notação:
Minimizar f(x) = cTx +½xTQx
Sujeito a: Ax ≥ b (ou Ax = b)
x ≥ 0
Programação Quadrática
09/08/2013
20
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• O Lagrangeano é dado por (cTx = xTc):
L(x,v,y,u) = xTc +½xTQx – vT(Ax-b-y) – uTx 
• Observa-se que a variável de folga y não é está ao 
quadrado, o que implica que a restrição y ≥ 0 deve 
ser respeitada
• Ressalta-se que não forma inseridas variáveis de 
folga para a restrição x ≥ 0
• Observa-se que no mínimo, as derivadas do 
Lagrangeano em relação a x e a v deve se nulas 
(não foram consideradas as derivadas em relação a 
y,u)
Programação Quadrática
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Utilizando-se as condições necessárias para o 
mínimo, tem-se:
LxT = c + Qx –ATv – u = 0 (1)
LvT = Ax – b – y = 0 (2)
x ≥ 0 u ≥ 0 v ≥ 0 y ≥ 0 (3)
uTx = 0 vTy = 0 (4)
• Observa-se que no mínimo da função, as 
condições (1) a (4) devem ser satisfeitas
• Utilizando-se estas condições, a função objetivo 
pode ser reduzida a uma função linear em x = x*
Programação Quadrática
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Substituindo-se Qx de (1) em f(x), tem-se:
f(x) = cTx + ½xT(ATv + u – c) 
= cTx + ½xTATv + ½xTu – ½xTc
• De (4) uTx = 0:
f(x) = ½cTx + ½xTATv = ½cTx + ½vTAx
• De (2) Ax = b + y 
f(x) = ½cTx + ½ vT(b + y) = ½cTx + ½vTb + ½ vTy
• De (4) vTy = 0:
f(x) = ½(cTx + bTv)
Programação Quadrática
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Problemas práticos de otimização podem ser 
escrito na forma de Programação Quadrática
• Outros tipos de problemas podem ser resolvidos 
pelo método de Programação Quadrática 
Seqüencial (método iterativo):
– A função objetivo é aproximada por uma função 
quadrática (com Q uma aproximação positiva definida 
da matriz hessiana)
– As restrições são linearizadas
– A resolução do problema de programação quadrática 
resultante fornece a direção de busca de cada iteração 
Uso da Programação Quadrática
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• A idéia da função penalidade é transformar 
o problema de otimização restrito num 
problema irrestrito por meio da inserção das 
restrições numa nova função objetivo 
chamada função penalidade:
Minimizar f(x) 
Sujeito a: g(x) ≥ 0 Minimizar P(f, g, h)
h(x) = 0
Função Penalidade
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Exemplo:
Minimizar f(x) = (x1-1)2 +(x2-2)2
Sujeito a: h(x) = x1 + x2 – 4 = 0
Função Penalidade1 0 1 2 3
0
1
2
3
4
55
55
4.5
4.5
4.54.5
4
4
4
4
3.5
3.5
3.5
3.5
3
3
3
3
3
3
2.5
2.5
2.5
2.5
2.52.5
2.5
2 2
2
2
2
2
1.5
1.5
1.5
1.5
1.5
1.5
1
1
1
1
1
0.5
0.5
0.5
A
x2
x1
x1 + x2 – 4 = 0
x* = 





5,2
5,1
09/08/2013
21
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Função Penalidade (irrestrita):
Minimizar P(x,r) = (x1-1)2 +(x2-2)2 + r(x1+x2- 4)2
Função Penalidade
x2
x1
1 0 1 2 3
0
1
2
3
4
18.709
14.626
12.584
10.542
10.542
8.501
8.501
8.501
6.459
6.459
6.459
6.459
4.418
4.418
4.418
4.418
4.418
2.376
2.376
2.376
2.376
2.376
A






33,2
33,1
1 0 1 2 3
0
1
2
3
4
150.006
116.778
108.47
100.163
91.856
83.549
75.242
75.242
66.934
58.627
58.627
50.32
50.32
42.013
42.013
33.706
33.706
25.398
25.398
25.398
25.398
17.091
17.091
17.091
17.091
8.784
8.784
8.784
8.784
8.784
A
x2
x1






476,2
476,1
r = 1 r = 10
Curso de Engenharia Química – Campus de Alegre
Esly Costa
Otimização de Processos
• Observa-se que quanto maior o valor do 
peso, mais precisa é a solução
• Valores elevados de r fazem com que a 
matriz hessiana se torne mal condicionalda, 
o que pode prejudicar a solução
• Para problemas com restrições de igualdade 
e desigualdade:
Função Penalidade
∑∑
+==
++=
p
1mj
2
m
1j
2
j 02
r
h
2
r
frP g(x)}],[min{(x)(x))(x,