Teoria de Otimização Clássica

Prévia do material em texto

1 
Teoria de Otimização Clássica 
(Prof. Arica) 
 
A Teoria de Otimização clássica faz uso do cálculo diferencial para encontrar pontos 
ótimos (mínimos e máximos) para funções com restrições ou sem restrições. Nestas notas, 
apresentam-se primeiro condições necessárias e suficientes para o caso de ótimos sem 
restrições, logo discutem-se as condições de Karush-Kuhn-Tucker (KKT) para ótimos com 
restrições e, finalmente, apresentam-se alguns dos principais métodos para minimização. 
 
Problemas sem restrições 
 
O problema típico de minimização sem restrições é: 
 
nx
xfP
ℜ∈ :a sujeito 
)(minimizar :)(
, (1) 
onde ℜ→ℜnf : se chama função objetivo. 
 
Diz-se que nnxxx ℜ∈= ),,( 1
0 K é um mínimo relativo da função f , se para algum 0>ε 
pequeno, cumpre-se que 
}:{)0(),()( 00 εε <=∈∀+≤ hhBhhxfxf (2). 
 
Note que a condição }:{)0( εε <=∈ hhBh , para algum 0>ε pequeno, é o mesmo que 
dizer h suficientemente pequeno. 
 
Se a condição (2) se satisfaz para qualquer 0>ε , diz-se que nx ℜ∈0 é um mínimo 
absoluto ou global (i.e., a condição se satisfaz para qualquer h , não unicamente para os 
pequenos). 
Mudando a relação ≤ por ≥ em (2), define-se máximo relativo (e absoluto ou global, se 
vale para qualquer 0>ε ). Em geral, mínimos e máximos chamam-se de pontos extremos. 
 
Exemplo 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
6x 5x 4x 3x 2x 1x 
x 
)(xf 
Figura 1. Pontos extremos para )(xf 
 2 
 
Na Figura 1, os pontos 4321 ,,, xxxx e 6x são pontos extremos. Em particular, 2x e 4x são 
pontos mínimos e 31, xx e 6x são máximos (6x é máximo absoluto). Note que 2x , a 
diferença de 4x , é o único mínimo local numa vizinhança desse ponto, pelo que diz-se ser 
um mínimo local forte (ou estrito); 4x se diz ser um mínimo local fraco (ou não estrito). 
 
Observe, também, que em todos os pontos extremos se tem que 0)( =∇ xf , mas que 
0)( 5 =∇ xf e 5x não é ponto extremo. Diz-se, neste caso, que 5x é ponto sela (i.e., ponto 
de inflexão). 
 
Resumindo, pode ser estabelecida a seguinte condição necessária: se um ponto é extremo, 
então seu gradiente é nulo. (Note que não é suficiente que o gradiente seja nulo num ponto 
para este ser extremo!). 
 
Teorema 1. (Condição necessária para ponto extremo, primeira ordem) Se nx ℜ∈0 é 
ponto extremo para a função f (do problema )(P ), então 0)( 0 =∇ xf . 
Prova: A prova desta proposição pode ser encontrada em Bazaraa et al (1993) (Nonlinear 
Programming: Theory and Algorithms, Second Edition, John Wiley & Sons). 
 
O conjunto de soluções de 0)( =∇ xf se chama conjunto de pontos estacionários. Note que 
no caso da Figura 1, 5x é estacionário, mas não é extremo. A seguinte proposição 
determina uma condição suficiente para identificar pontos extremos do conjunto de pontos 
estacionários. 
 
Teorema 2. (Condição suficiente para ponto extremo, segunda ordem) Se 0)( 0 =∇ xf e a 
matriz hessiana )( 02 xf∇ (segunda derivada) é 
(i) definida positiva, então 0x é mínimo relativo; 
(ii) definida negativa, então 0x é máximo relativo; 
(iii) indefinida, então 0x é ponto de inflexão (ponto sela). 
 
Prova: A prova desta proposição pode ser encontrada em Bazaraa et al (1993). 
 
Obs: Lembrar que uma matriz é definida positiva (negativa) se todos seus autovalores são 
positivos (negativos). Caso a matriz tenha autovalores positivos, negativos e/ou nulos é 
indefinida. 
 
Exemplo 2: 
Determinar os pontos extremos e sua natureza para a função 
2
3
2
2
2
13231 2)( xxxxxxxxf −−−++= . 
Solução: 
Para determinar os pontos extremos, aplicando a condição necessária para ponto extremo, 
deve-se solucionar o sistema 
 3 





=⇒










=










−+
−
−
=


















∂
∂
∂
∂
∂
∂
⇔=∇
3
4
,
3
2
,
2
1
0
0
0
22
2
21
)(
)(
)(
0)(
32
23
1
3
2
1
x
xx
xx
x
x
xf
x
xf
x
xf
xf . 
Logo, pela condição suficiente para ponto extremo, pode-se identificar a natureza do ponto 
encontrando os autovalores da matriz hessiana. Assim, tem-se que 
0
210
020
002
det))(det(
210
020
002
)( 22 =










−−
−−
−−
=−∇⇒










−
−
−
=∇
λ
λ
λ
λIxfxf . 
Resultando os autovalores: 1,3,2 321 −=−=−= λλλ . Portanto, a matriz )(
2 xf∇ é definida 
negativa, o que implica que o ponto 




=
3
4
,
3
2
,
2
1
x é um máximo (absoluto). 
 
Exemplo 3: 
Determinar os pontos extremos e sua natureza para a função 
2
121 28)( xxxxf += . 
Solução: 
Do sistema 0)( =∇ xf , resulta o ponto extremo )0,0(=x , sendo os autovalores para 
)0,0(2 f∇ , 8,12 21 −== λλ . Portanto, o único ponto extremo )0,0(=x é um ponto sela. 
 
Na Figura 2 se mostra a natureza dum ponto sela para uma função de duas variáveis. Note 
que na direção 1d a função aumenta seu valor (direção de subida), entanto que na direção 
2d diminui (direção de descida). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 2. Natureza de um ponto sela. 
1d 
2d 
0x 
 4 
Problemas com restrições 
 
O problema típico de minimização com restrições é: 
 
nSx
xfPR
ℜ⊂∈ :a sujeito 
)(minimizar :)(
, (3) 
onde ℜ→ℜnf : se chama função objetivo e S é um conjunto fechado (i.e., que contém 
sua borda), chama-se conjunto viável ou conjunto de restrições. 
 
Exemplo 4: Na Figura 3, para 2=n , tem-se um caso de condição necessária para que um 
ponto Sx ∈* seja ótimo para o problema (PR): 
.,0)()( ** Sxxxxf T ∈∀≥−∇ (4) 
 
Note que a desigualdade (4) trata de encontrar um ponto Sx ∈* , para o qual o vetor 
)( *xf∇ faz um ângulo agudo com todo vetor Sxxx ∈− ),( * , como se mostra na Figura 3. 
Portanto, embora (4) estabeleça uma condição para possíveis mínimos, é difícil de ser 
resolvida (métodos para solucionar (4) estão fora do objetivo desta disciplina). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Entretanto, para formas especiais do conjunto de restrições outras abordagens são possíveis. 
Para o caso em que o conjunto de restrições está dado por um conjunto de m funções de 
restrição, 
{ }0)(,,0)(: 1 ≤≤ℜ∈= xgxgxS mn K , (5) 
 
pode-se definir uma direção viável como segue. 
 
teconsxf tan)( = 
)(xf∇ 
*xx− 
)( *xf∇ 
S 
*x 
× x 
Figura 3. Uma condição necessária para ótimo de Sx ∈* , no problema (PR) 
 5 
Definição 1. Dados o conjunto de restrições S e um ponto Sx ∈ , diz-se que o vetor d é 
uma direção viável para S no ponto x , se existe 0>δ , tal que 
 
δλλ <<∀∈+ 0,Sdx . (6) 
 
O conjunto de todas as direções viáveis paraSx ∈ , será denotado por xD . 
 
A Figura 4 mostra algumas direções viáveis e não viáveis para um certo conjunto S e um 
certo ponto Sx ∈ . 
 
 
 
 
 
 
 
 
 
 
 
 
 
Definição 2. Seja ℜ→ℜnf : uma função diferenciável e um ponto nx ℜ∈ . Diz-se que o 
vetor d é uma direção de descida para f no ponto x , se existe 0>δ , tal que 
 
δλλ <<∀<+ 0),()( xfdxf . (7) 
 
O conjunto de todas as direções de descida paranx ℜ∈ , será denotado por xF . 
 
Teorema 3. (Condição necessária para direção de descida) Seja ℜ→ℜnf : uma função 
diferenciável e um ponto nx ℜ∈ . Então, se 0)( <∇ dxf T , tem-se que d é direção de 
descida para f no ponto x . 
 
Prova: A prova desta proposição pode ser encontrada em Bazaraa et al (1993). 
 
Denotando { }0)(:0 <∇ℜ∈= dxfdF Tnx , pode-se conferir que o Teorema 3 estabelece que 
xx FF ⊆
0 . 
 
Ainda é conveniente, observar que se satisfaz o seguinte: 
 
{ }0)(:00 ≤∇ℜ∈=⊆⊆ dxfdFFF Tnxxx . (8) 
 
Figura 4. O vetor d̂ é uma direção viável para Sx ∈ ; d
~
não é direção viável 
dx ˆδ+ 
0,
~ >+ λλdx 
0,ˆ >+ λλdx 
d
~
 
d̂ 
x 
S 
 6 
Quando 0)( =∇ dxf T , não se pode afirmar nada sobre o comportamento de f na direção d. 
Precisa-se de mais informação sobre f. 
 
Exemplo 5: Considere a função 422 32),( yxyxyxf +−= . Encontre direções de descida 
para f no ponto )0,0(=x . 
 
Solução: 
Desde que a função f pode ser escrita como ))(2(),( 22 yxyxyxf −−= , é claro que as 
curvas de nível 0, correspondem às parábolas 02 2 =− yxe 02 =− yx . Na Figura 5 se 
mostra o gráfico de f. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Primeiro encontremos 0xF . Para isso precisa-se encontrar )0,0(f∇ . Assim, 
 
} { } .,0)0,0(:
0
0
)0,0(
46
34
),( 20 )0,0(
0
)0,0(
0)0,0(
3
2
ℜ==<∇=⇒





=∇⇒






+−
−
=∇
=∇
FdfdFf
yxy
yx
yxf T
df T
φ
 
 
Por outro lado, desde que 






=∇⇒





+−−
−
=∇
00
04
)0,0(
1266
64
),( 22
2 f
yxy
y
yxf , 
 
tem-se que os autovalores de )0,0(2 f∇ são 4 e 0; i.e., a matriz )(2 xf∇ é semi-definida 
positiva. Portanto, combinando este resultado com a Figura 5, concluímos que dada 
qualquer direção d , saindo de )0,0(=x , esta é direção de subida; i.e., φ== 0 )0,0()0,0( FF 
(não existem direções de descida!). 
 
A seguinte proposição estabelece uma relação mais precisa que a relação (8). 
 
Figura 5. Gráfico da função ))(2(),( 22 yxyxyxf −−= 
y 
x 
0),( >yxf 
0),( <yxf 
0),( >yxf 
),( yxf∇ 
0),(02 =⇒=− yxfyx 
0),(02 2 =⇒=− yxfyx 
 7 
Lema. Seja ℜ→ℜnf : uma função diferenciável e um ponto nx ℜ∈ . Cumpre-se que, 
(i) Se f convexa em x , então xx FF =
0 . 
(ii) Se f estritamente côncava em x , então 0xx FF = . 
 
Observação: uma condição suficiente para que uma função seja convexa (estritamente 
côncava) num ponto x , é que )(2 xf∇ seja semidefinida positiva (definida negativa); i.e., 
autovalores maiores o iguais a zero (negativos). 
 
Prova: A prova desta proposição pode ser encontrada em Bazaraa et al (1993). 
 
Note que se Sx ∈ é um ponto de mínimo para o problema (PR), deve satisfazer que 
nenhuma direção de descida deve ser direção viável nesse ponto (ou equivalentemente, 
todas as direções de descida só podem ser de subida). Esta condição pode ser formulada, 
sob certas condições, como φ=xx DF I . Esta condição é difícil de verificar (por meio de 
cálculos). A proposição a seguir estabelece uma condição um pouco mais simples (e menos 
geral) que essa. 
 
Teorema 4. Considere o problema (PR) diferenciável. Cumpre-se que, se Sx ∈ é mínimo 
local, então φ=xx DF I
0 . 
Reciprocamente, se f é função convexa, φ=xx DF I
0 e existe 0>ε tal que 
)(, xBSxDxxd x εI∈∀∈−= , então x é mínimo local. 
 
Prova: A prova desta proposição pode ser encontrada em Bazaraa et al (1993). 
 
Note que para efeitos de aplicar o Teorema 4, pode ser facilmente verificado se um dado 
vetor 0xFd ∈ , mas é difícil verificar se xDd ∈ . Portanto, é conveniente encontrar 
conjuntos que se aproximem a xD , para os que seja simples determinar se um vetor d 
pertence ou não a eles, de maneira similar a o que acontece com os conjuntos xF e 
0
xF . 
 
Teorema 5. Considere o problema (PR), com S dado pela relação (5), todas as funções 
envolvidas diferenciáveis, Sx ∈ e }0)(:{)( == xgixI i (chamado conjunto de restrições 
ativas). Sejam os conjuntos 
 
{ } { })(,0)(:}0{\ ,)(,0)(: 00 xIidxgdDxIidxgdD TinxTinx ∈∀≤∇ℜ∈=∈∀<∇ℜ∈= . 
 
Então, cumpre-se que 
00
xxx DDD ⊆⊆ . 
 
Além disso, se ig é estritamente convexa, para todo )(xIi ∈ , então xx DD =
0 ; e, se ig é 
côncava, para todo )(xIi ∈ , então 0xx DD = . 
Prova: A prova desta proposição pode ser encontrada em Bazaraa et al (1993). 
 8 
A Figura 6 e Figura 7 ilustram o Teorema 5. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Teorema 6. (Condição necessária para mínimo local do problema com restrições) 
Considere o problema (PR) como no teorema anterior e Sx ∈ . Cumpre-se que, se Sx ∈ é 
mínimo local, então φ=00 xx DF I . 
Reciprocamente, se f é função convexa, φ=00 xx DF I e ig estritamente convexa para todo 
)(xIi ∈ , então x é mínimo global. 
Prova: A prova desta proposição pode ser encontrada em Bazaraa et al (1993). 
 
Condições de otimalidade de Fritz-John 
 
Nesta seção o objetivo é expressar a condição necessária φ=00 xx DF I (geométrica), 
determinada no Teorema 6, em termos algébricos. 
Figura 6. Ilustração do caso 00 xxx DDD ≠= , }.3,1{)( =xI 
xD 
0
xD 
x 
0)(3 =xg 
0)(2 =xg 
0)(1 =xg 
1g∇ 
3g∇ 
2g∇ 
Figura 7. Ilustração do caso 00 xxx DDD =≠ , }.3,1{)( =xI 
xD 
0
xD 
x 
0)(3 =xg 
0)(2 =xg 
0)(1 =xg 
1g∇ 
3g∇ 
2g∇ 
 9 
Teorema 7. (Condição necessária de Fritz-John) Considere o problema (PR) como no 
teorema anterior e Sx ∈ . Cumpre-se que, se Sx ∈ é mínimo local, então existem 
escalares 0u e iui ∀, , tal que se satisfaz o sistema (FJ): 
 








≠
=≥
==
=∇+∇ ∑
=
0),,,(
,,1,0,
,,1,0)(
0)()(
:)(
10
0
1
0
m
i
ii
m
i
ii
uuu
miuu
mixgu
xguxfu
FJ
K
K
K ⇔ 






≠
∈≥
=∇+∇
⇔
∑
∈
0),(
)(,0,
0)()(
)(
)(0
0
)(
0
xI
i
xIi
ii
uu
xIiuu
xguxfu
FJ 
Prova: A prova desta proposição está baseada no fato de provar que a condição necessária 
de mínimo, φ=00 xx DF I , pode ser escrita como a condição (FJ). Uma prova desta 
proposição pode ser encontrada em Bazaraa et al (1993). 
(Os escalares ),( )(0 xIuu denominam-se Multiplicadores de Lagrange). 
 
Exemplo 6: Usando um esboço do gráfico das funções envolvidas, determine um ponto 
candidato e verifique se pode ser o mínimo do problema indicado: 
0
0
42
5 :a sujeito
 
)2()3(minimizar 
2
1
21
2
2
2
1
2
2
2
1
≥
≥
≤+
≤+
−+−
x
x
xx
xx
xx
 
Solução: Na Figura 8 se mostra que o ponto )1,2(=x é o candidato a ser mínimo do 
problema proposto. Note que }2,1{)( =xI . 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
A seguir se verifica que )1,2(=x satisfaz a condição necessária (FJ); i.e., que existem 
escalares 10 ,uu e 2u tais que: 
42)( 212 −+= xxxg 
)(xf 
5)( 22
2
11 −+= xxxg 
13 )( xxg −= 
24 )( xxg −= 
× ( ))2,3 )0,2( 
)0,0( )0,5( 
S 
3g∇ 
4g∇ 
)(2 xg∇ 
)(1 xg∇ 
)(xf∇ 
)1,2(=x 
0)(2 =xg 
0)(3 =xg 
0)(4 =xg 
0)(1 =xg 
.)( ctexf = 
Figura 8. Esboço do Exemplo 6. 
 10 






≠
=∈≥
=∇+∇ ∑
=∈
0),,(
}2,1{)(,0,
0)()(
210
0
}2,1{)(
0
uuu
xIiuu
xguxfu
i
xIi
ii
 
Desde que: 
{ {
,,
3
2
,
30
0
2
1
2
4
2
2
0)()( 0
0
2
0
1
)(
2
)(
1
)(
0
}2,1{)(
0
21
ℜ∈==⇔





=





+





+





−
−
⇔=∇+∇
∇∇∇
=∈
∑ u
u
u
u
uuuuxguxfu
xgxgxf
xIi
ii
321
basta considerar 00 >u , para que a condição (FJ) seja satisfeita para )1,2(=x . 
 
Por um raciocínio similar, vejamos que )0,0(=x não é mínimo, pois se fosse mínimo 
deveria satisfazer (FJ) para }4,3{)( =xI . Mas considerando a primeira relação de (FJ), tem-
se: 
{ {
.,4,6
0
0
1
0
0
1
4
6
0)()( 00403
)(
4
)(
3
)(
0
}4,3{)(
0
431
ℜ∈−=−=⇔





=





−
+




−
+





−
−
⇔=∇+∇
∇∇∇
=∈
∑ uuuuuuuuxguxfu
xgxgxf
xIi
ii
321
Donde podemos observar que não existem 30 ,uu e 4u que satisfaçam (FJ). Portanto, do 
Teorema 7, se a condição (FJ) não é satisfeita por )0,0(=x , então )0,0(=x não é mínimo. 
 
Exemplo 7: Verificar que a condição (FJ) se satisfaz no ponto de mínimo do problema aqui 
indicado: 
0
4)1( 
xminimizar 
2
3
12
1
≥
≤−−
−
x
xx 
 
Solução: Na Figura 9 se mostra que o ponto )0,1(=x é o candidato a ser mínimo do 
problema proposto. Note que }2,1{)( =xI . 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
)(xf 
4)1()( 3121 −−−= xxxg 
22 )( xxg −= 
Figura 9. Esboço do Exemplo 7. 
× 
S 
)(2 xg∇ 
)(1 xg∇ 
)(xf∇ 
)0,1(=x 0)(2 =xg 
0)(1 =xg 
 11 
Para verificar que )0,1(=x satisfaz a condição de (FJ), precisa-se encontrar 10 ,uu e 2u tais 
que: 






=





+





+




−
⇔=∇+∇ ∑
=∈ 0
0
1
0
1
0
0
1
0)()( 210
}2,1{)(
0 uuuxguxfu
xIi
ii
. 
 
Então, para cumprir (FJ) deve satisfazer-se que 0,0 210 >== uuu . 
 
Note que, embora o ponto )0,1(=x seja um ponto de mínimo da função f (solução do 
problema), a função f não participa diretamente na condição (FJ), pois 00 =u elimina a 
função objetivo; i.e., tem-se uma condição para mínimo da função f onde não participa esta 
função. 
 
Para tentar evitar este caso “estranho”, no que segue se formulam condições para que não 
desapareçaa função objetivo na condição (FJ); i.e., para que 00 ≠u . É interessante indicar 
que este caso ( 00 =u ) aparece, devido ao fato de que φ=
0
xD . Portanto a condição (FJ): se 
Sx ∈ é mínimo local, então φ=00 xx DF I , cumpre-se trivialmente, pois φ=
0
xD . Note que 
neste caso o conjunto S é um conjunto “mal-comportado” ao redor de )0,1(=x . 
 
 
Condições de otimalidade de Karush-Kuhn-Tucker (K-K-T) 
 
Sabe-se que para o problema (PR), Sx ∈ cumpre-se 
φ=⇔ 00)( satisfaz xx DFFJx I . 
 
Note, como indicado no exemplo anterior, que esta condição é trivial se φ=0xD , 
permitindo que (FJ) se satisfaça trivialmente, independentemente da função objetivo. 
 
Portanto, nesta seção propõem-se condições para evitar que φ=0xD , o que obrigará a que 
00 >u para satisfazer (FJ). Condições que garantem que φ≠
0
xD chamam-se condições de 
qualificação das restrições (“constraints qualification”). A condição de qualificação das 
restrições mais simples é a independência linear das restrições ativas: Diz-se que a 
condição de independência linear se cumpre para o ponto Sx ∈ , onde S está dada pela 
relação (5), se )()}({ xIii xg ∈∇ é linearmente independente. 
 
Teorema 8. (Condição necessária de K-K-T) Considere o problema (PR) como no teorema 
anterior e Sx ∈ . Cumpre-se que, se Sx ∈ é mínimo local que satisfaz a condição de 
independência linear, então as condições de (FJ) se cumprem com 00 >u ; i.e., existem 
escalares iui ∀≥ ,0 , tal que se satisfaz o sistema: 
 12 







=≥
==
=∇+∇ ∑
=
miu
mixgu
xguxf
KKT
i
ii
m
i
ii
,,1,0
,,1,0)(
0)()(
:)(
1
K
K 
Prova: A prova desta proposição pode ser encontrada em Bazaraa et al (1993). 
 
Os coeficientes iui ∀≥ ,0 , da (KKT) se chamam multiplicadores de KKT. 
 
Note que a condição (KKT) pode ser escrita como: 




=∇+∇
∈∀≥∃
⇔ ∑
∈
0)()(
que tal),(,0
)(
)(xIi
ii
i
xguxf
xIiu
KKT 
 
Observação: Prova-se que para o caso de problemas lineares, a condição (KKT) é 
necessária e suficiente. 
 
Na Figura 10 se mostra graficamente a condição de KKT para o problema do Exemplo 6. 
Note que desde que no ponto )1,2(=x , )(xf∇− pode ser escrito como combinação linear 
não negativa de ),(),( xIixgi ∈∇ este ponto cumpre KKT; já )0,0(=x , não cumpre. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
)0,0( 
S 
)0,0(3g∇ 
)0,0(4g∇ 
)(2 xg∇ 
)(1 xg∇ 
)(xf∇ 
)1,2(=x 
Figura 10. A condição necessária de KKT para o Exemplo 6. 
O ponto )1,2(=x cumpre KKT; já )0,0(=x , não cumpre. 
)0,0(f∇ 
)(xf∇− 
)0,0(f∇− 
 13 
Teorema 9. (Condição suficiente de K-K-T) Considere o problema (PR) como no teorema 
anterior e Sx ∈ um ponto de KKT. Se )(xf e )(),( xIixgi ∈∀ , são convexas, então x é 
um mínimo global para (PR). 
Prova: A prova desta proposição pode ser encontrada em Bazaraa et al (1993). 
 
Para o caso mais geral, em que o problema de minimização tem restrições de igualdade no 
conjunto S: 
{ }0)(,,0)(,0)(,,0)(: 11 ==≤≤ℜ∈= xhxhxgxgxS lmn KK , 
as condições necessárias de KKT para Sx ∈ tem o seguinte formato: 
 







=≥
==
=∇+∇+∇ ∑ ∑
= =
miu
mixgu
xhvxguxf
KKT
i
ii
m
i
l
j
jjii
,,1,0
,,1,0)(
0)()()(
:)(
1 1
K
K 
ou 





=∇+∇+∇
∀∈∀≥∃
⇔
∑∑
=∈
0)()()(
que talj,,),(,0
)(
1)(
l
j
jj
xIi
ii
ji
xhvxguxf
vxIiu
KKT 
 
 
Métodos da minimização sem restrições 
 
O problema a ser abordado aqui é 
nx
xfP
ℜ∈ s.a 
)(minimizar :)(
 
onde ℜ→ℜnf : é uma função diferenciável. 
 
Os métodos ou algoritmos exatos propõem procedimentos iterativos, gerando uma 
seqüência de pontos nkkx ℜ⊂
∞
=1}{ , tal que 
*lim xxkk =∞→ solução (local) do problema (P). 
 
O procedimento geral tem o seguinte formato: 
Passo 1. Dado nkx ℜ∈ , determinar, mediante algum critério de parada, se kx é o ponto 
procurado (por exemplo, testar se 0)( =∇ kxf : condição necessária de primeira ordem 
para mínimo de (P)). Se o critério de parada for satisfeito, PARAR! 
 
Passo 2. Caso contrário, providenciar uma direção de descida, nkd ℜ∈ , e dar um passo 
suficientemente grande, a partir de kx na direção kd , diminuindo o valor de f; i.e., 
encontrar, supondo 1=kd , um passo de tamanho 0>kλ , tal que 
)()( kkkk xfdxf <+ λ . 
Fazer 1: += kk e voltar ao Passo 1. 
 14 
 
 
 
 
 
 
 
 
 
 
Portanto, é conveniente desenvolver métodos para determinar o tamanho de passo. Esses 
métodos são denominados Métodos de Busca Linear. 
 
Métodos de Busca Linear 
O problema a ser tratado aqui é, dados um ponto nkx ℜ∈ que não é solução do problema 
(P) e uma direção nkd ℜ∈ de descida para a função diferenciável ℜ→ℜ
nf : , determinar 
0>kλ , tal que 
434214434421
)(
0
)(
)()(
λθ
λ
λθ
λλ kkkkk dxfmínimodxf
k
+=+ > . (9) 
Isto é, dada a função )(λθ , definida como em (9), o problema da busca linear é determinar 
0>kλ , tal que 
)()( 0 λθλθ λ>= mínimok . (10) 
 
A Figura 12 mostra a natureza da função de busca linear, )(λθ . 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
× 
×kx 
kd 
kkkk dxx λ+=+1 
kλ 
Figura 11. Tamanho de passo kkk xx −= +1λ . 
× 
kx 
kd kkkk dxx λ+=+1 
)()( kk dxf λλθ += 
)( kλθ 
),( yxf 
x 
y 
kd 
)()( kk dxf λλθ += 
λ kx kλ 
Figura 12. Natureza da função de busca linear 
*x 
 15 
 
 
Uma primeira idéia para determinar o tamanho de passo kλ é introduzir o conceito de 
intervalo de incerteza, considerando-o como um intervalo que contém o ponto kλ . Assim, o 
objetivo passa a ser o de diminuir o tamanho do intervalo de incerteza até atingir certa 
aproximação desejada: 
 
 
 
 
 
Propriedade 1. Se a função θ é convexa no intervalo ℜ⊂],[ ba , dados λ e µ , com 
ba ≤≤≤ µλ , cumpre-se que 
(a) bzz ≤≤∀≤⇒≤ µθλθµθλθ ),()()()( . 
 
(b) λµθθµθλθ ≤≤∀≥⇒> zaz ),()()()( . 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Assim, em função da Propriedade 1, tomando dois pontos intermediários no intervalo de 
incerteza atual ],[ ba , comparando os valores da função θ nesses pontos, poderemos 
reduzir o intervalo de confiança; i.e., dados λ e µ , tais que ba ≤≤≤ µλ , temos as 
seguintes duas opções: 
 
 
 
 
 
 
 
 
 
 
a2 
a b 
a1 b1 
b2 
kλ 
× 
λ 
)(µθ 
)(λθ 
a µ b 
Figura 13(a). Propriedade 1. 
λ 
)(µθ 
)(λθ 
a µ b 
Novo intervalo de incerteza 
λ 
)(µθ 
)(λθ 
a µ b 
Novo intervalo de ncerteza 
λ 
)(µθ 
)(λθ 
a µ b 
Figura 13(b). Propriedade 1. 
 16 
Estratégia de busca sem derivadas 
 
Como exposto acima, por comparação de dois valores da função θ pode ser diminuído o 
tamanho do intervalo de incerteza. É conveniente, entretanto, fazer com que o próximo 
intervalo a ser considerado seja o menor possível. Uma estratégia, considerando o intervalo 
atual como ],[ ba , é tomar os pontos intermediários λ e µ , tais que se afastem uma 
distância pequena, ε , do ponto médio. Dessa forma se assegura que o novo intervalo 
diminui o anterior quase pelo fator 1/2: 
 
 
 
 
 
 
 
 
 
 
 
 
Estratégia de busca com derivadas (Método de Bisseção) 
 
Informação sobre a derivada da função θ pode usar-se para decidir sobre um novo 
intervalo de incerteza. Embora existam vários métodos que usam essa informação um dos 
mais clássicos é o método de bisseção. Este método assume que a função θ é convexa e 
diferenciável no intervalo atual ],[ kk ba e procura localizar um ponto intermediário kλ de 
forma diminuir o intervalo. O método pode ser descrito como segue: 
 
Passo 1. Considere kλ , tal que kkk ba ≤≤ λ . Se 0)( =′ kλθ , então PARAR! ( kλ é mínimo 
de θ em ],[ kk ba . 
Passo 2. Se 0)( >′ kλθ , desde que ],[),())(()( kkkkk bazzz ∈∀≤−′+ θλλθλθ , tem-se que 
kk zz λθλθ ≥∀≤ ),()( . Assim, da Propriedade 1, um novo intervalo de incerteza é 
],[],[ 11 kkkk aba λ=++ . 
Passo 3. Se 0)( <′ kλθ , um novo intervalo de incerteza é ],[],[ 11 kkkk bba λ=++ . Faça 
1: += kk e volte para o Passo 1. 
 
Observação: Na prática se considera 2
)( kk
k
ba +=λ e se substitui 0)( =′ kλθ por 
TOLk ≤′ )(λθ , para certa tolerância TOL pequena. Dessa forma cada novo intervalo de 
incerteza diminui o anterior pelo fator½. 
 
 
 
 
a b 
λ µ 
2
ba +
 
ε2 
× 
novos intervalos possíveis 
 17 
Estratégia de busca linear inexata Regra de Armijo-Goldstein) 
 
Nas duas estratégias anteriores se trata de determinar um ponto de mínimo exato. No que 
segue se apresenta um método que determina um tamanho de passo kλ para o qual não 
necessariamente se determina o mínimo, mas se assegura que existe uma descida 
suficientemente grande para a função θ . 
 
Considerem-se dados um ponto kx , que não é mínimo para a função f, uma direção de 
descida kd e, para um )1,0(∈ε , fixo, as funções )()( kk dxf λλθ += e 
)0()0()(ˆ θελθλθ ′+= , 0>λ . O método abaixo descrito encontra um passo 0>λ para o 
qual considera uma diminuição suficiente da função f, como segue: Diz-se que 0>λ é um 
ponto de descida suficiente para a função θ se: 
1) )(ˆ)( λθλθ ≤ , 
2) 1 para ),(ˆ)( >≥ αλαθλαθ . 
 
Observação: Tipicamente, usa-se 2,0=ε e 2=α . Note que k
T
kk ddxf )()( λλθ +∇=′ . 
Assim, 0)()0( <∇=′ k
T
k dxfθ , pois kd é direção de descida. 
A Figura 14 ilustra o conceito de passo de descida suficiente. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Pseudo-algoritmo de Armijo-Goldstein 
Faça 2=α e 2,0=ε ; 
Escolher 0>λ ; 
1=i ; 
Se )(ˆ)( λθλθ ≤ ; 
)(λθ 
)0(θ 
kx 
kd 
λθθ )0()0( ′+ 
λθεθλθ )0()0()(ˆ ′+= 
Pontos λ de descida suficiente 
Figura 14. Tamanhos de passo λ de descida suficiente (Armijo-Goldstein). 
λ 
 18 
 Enquanto )2(ˆ)2( λθλθ ii ≤ 
 1+= ii ; 
 Fim do enquanto 
 λλ 12: −= i ; 
C.c., 
 Enquanto )
2
(ˆ)
2
( ii λθλθ > 
 1+= ii ; 
 Fim do enquanto 
 i2
: λλ = ; 
Parar 
 
 
Minimização sem restrições: Método de descida mais rápida 
 
Entre os métodos de minimização sem restrições o primeiro a ser trabalhado é o de descida 
mais rápida, também conhecido como Método do Gradiente ou Método de Cauchy. O 
problema a ser resolvido é: 
nx
xfP
ℜ∈ s.a 
)(minimizar :)(
 
 
Para ilustrar a idéia, considere o caso de 2=n , apresentado na Figura 15. O Método de 
Cauchy, sob a consideração de um ponto 0x , que não é a solução do problema (pois a 
condição necessária 0)( 0 =∇ xf não se satisfaz), determina uma direção )( 00 xfd −∇= , 
simples de calcular, que permite diminuir o nível atual da função objetivo. 
 
Denotando a curva de nível α da função f por })(/{ αα == xfxC
f , tem-se que a curva de 
nível associada ao ponto 0x , é }()(/{ 0)( 0 xfxfxC
f
xf == . Assim, a direção )( 00 xfd −∇= 
fornece uma direção de descida para f, a partir de 0x , como ilustrado na Figura 15, para 
2=n . 
 
 
 
 
 
 
 
 
 
 
 
 
 
1d 
)( 0xf∇ 
0d 
f
xfC )( 0 
0001 dxx λ+= 
Figura 15. Ilustração do passo do Método de Cauchy 
2d 
0x 
2x 
 19 
 
Observe, na Figura 15, que seguindo a direção )( 00 xfd −∇= (chamada direção de 
Cauchy), consegue-se diminuir o valor atual da função, )( 0xf , pois se atravessam curvas 
de menor nível, até o ponto em que se tangencia a primeira curva de nível (por exemplo). 
Assim se consegue o ponto 0001 dxx λ+= , por meio de um passo 0λ , a partir do ponto 0x , 
na direção )( 00 xfd −∇= . Naturalmente, existem muitas outras direções de descida para a 
função no ponto 0x . Entretanto, a direção )( 00 xfd −∇= é muito simples de calcular. 
 
Repetindo o processo, a partir de 1x , se 0)( 1 ≠∇ xf , calcula-se a direção )( 11 xfd −∇= e 
um passo 1λ nessa direção, para determinar 1112 dxx λ+= e assim por diante. Dessa forma, 
gera-se uma seqüência de pontos kkx }{ , representada na Figura 15 pelos vértices do zigue-
zague, com a propriedade de ser kkxf )}({ uma seqüência decrescente. Pode-se provar que 
sob certas circunstâncias o método converge; i.e., xxk → e )()( xfxf k → , onde x é 
solução do problema (P) (para detalhes das provas do método ver Taha et al (1993)). 
 
Na prática, não se determinam infinitos pontos da seqüência kkx }{ , mas tantos como 
necessário para aproximar a condição necessária de otimalidade 0)( 0 =∇ xf , por 
Tolxf k <∇ )( , onde 0>Tol é um tolerância pequena. 
 
Assim, pode-se formular o algoritmo correspondente: 
 
Algoritmo de Cauchy (Gradiente ou descida mais rápida) 
 
Passo 0. (Dados do problema) 
 Definir a função f e uma tolerância pequena 0>Tol . Fazer 1:=k . 
 
Passo 1. (Critério de parada) 
 Se Tolxf k <∇ )( , PARAR! ( kx é uma aproximação de um mínimo local do 
problema (P)). 
 C.c., fazer )(: kk xfd −∇= . 
 
Passo 2. (Busca linear) 
 Determinar 0>kλ , tal que )(min)( 0 kkkkk dxfdxf λλ λ +=+ > . 
 Fazer kkkk dxx λ+=+ :1 e voltar ao Passo 1. 
 
 
Velocidade de convergência 
Da mesma forma que o Algoritmo de Cauchy gera uma seqüência de pontos }{ kx com a 
propriedade de ser )}({ kxf decrescente, outro algoritmos, providenciando outras formas de 
calcular as direções de descida kd , forneceram outras seqüências com a mesma 
 20 
propriedade. É importante estabelecer qual dessas seqüências é melhor do que outras. Para 
isso introduz-se o conceito de velocidade de convergência de uma seqüência. 
 
Definição. Seja uma nkkx ℜ⊂}{ , tal que xxk → , com kxxk ∀≠ , . A velocidade (ou 
ordem) de convergência é o maior dos números 0≥p , tal que 
 ∞<=
−
−+
∞→ βp
k
k
k
xx
xx 1lim . (11) 
 
Se 1=p e 1<β , diz-se que a taxa de convergência é linear. 
Se 1>p ou 1=p e 1<β , diz-se que a taxa de convergência é superlinear. 
Se 2=p , diz-se que a taxa de convergência é quadrática. 
 
Existem diferenças significativas entre a taxa de convergência quadrática e linear. Note, da 
relação (11), que quando k é grande, 
p
kk xxxx −≅−+ β1 , 
i.e., para k grande (digamos, 11,0 <−= xxk ) e se passa do ponto kx ao ponto 1+kx , se a 
convergência for linear, com 5,0=β , a distância ao ponto buscado, x , reduz-se pela 
metade (aproximadamente é 0,05). Já se a convergência for quadrática, a distância se reduz 
cem vezes mais, aproximadamente será 0,005. 
 
A convergência linear é a mais lenta das descritas. Prova-se que a convergência do Método 
de Cauchy é linear e pode ser muitíssimo lenta, dependendo das curvas de nível da função a 
ser minimizada. Na seguinte figura, onde as curvas de nível da função )(xf são elipses 
concêntricas, cujo mínimo está no ponto )0,0( , nota-se que se o primeiro ponto a ser 
considerado pelo método de Cauchy for o ponto 0x , os pontos seguintes (mostrados nos 
vértices do zigue-zague da figura) estão cada vez mais próximos, fazendo com que a 
aproximação destes ao ponto procurado seja muito lenta. 
 
 
 
 
 
 
 
 
 
 
Minimização sem restrições: Método de Newton 
 
Note que a direção de Cauchy pode ser interpretada da seguinte forma: Considere a Figura 
16, onde se representam graficamente as curvas de nível da função )(xf . No ponto 0x se 
aproxima a função )(xf por um modelo linear )()()()( 000 xxxfxfxl
T −∇+= . Desde que 
0x 
)(xf∇ 
(0,0) 
1x 
2x 
 21 
)(xl aproxima )(xf próximo do ponto 0x , espera-se que direções de descida para )(xl 
sejam também de descida para )(xf no ponto 0x . Desde que a direção de Cauchy 
)( 00 xfd
C
x −∇= é a direção de descida mais rápida (e fácil de encontrar) para o modelo, 
resultando ser também de descida para a função original (pois 0)(
00
<∇ Cx
T dxf ), usa-se essa 
direção para busca linear da função )(xf no ponto 0x . Encontra-se, assim, o ponto 
Cx1 na 
Figura 16. 
 
Em resumem, Cauchy substitui a função original por um modelo (linear) e encontra uma 
direção de descida simples para o modelo, que também é de descida para a função original, 
e a usa para busca linear desta. 
 
Analogamente, Newton propõe o seguinte: Desde que um modelo quadrático aproxima 
melhor uma função do que um modelo linear, substitua a função original por um modelo 
)(xq , quadrático ao invés de linear, determine uma direção de busca simples para o modelo 
e, verificando que é de descida para a função original, use-a para busca linear desta função. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Assim, desde que 
)()()(
2
1
)()()()( 00
2
0000 xxxfxxxxxfxfxq
TTT −∇−+−∇+= , 
cujas curvas de nível, sob certas circunstâncias, sãoelipses concêntricas, como mostrado na 
Figura 16, tem-se que a direção de descida mais simples de achar para o modelo 
quadrático, é aquela que leva do ponto 0x ao centro das elipses de nível (direção de 
Newton Nxd 0 ). Logo, seguindo o raciocínio anterior, realizando uma busca linear na direção 
N
xd 0 se encontra o ponto 
Nx1 . Observe que o ponto obtido por Newton, 
Nx1 , resulta sendo 
melhor que o ponto obtido por Cauchy, Cx1 , no sentido de que 
Nx1 está mais próximo do 
ponto de mínimo da função )(xf do que Cx1 . 
 
)( 0xf∇ 
Figura 16. Ilustração do passo do Método de Newton 
Cx1 × 
Nx1 
× 
0x 
)(xl 
)(xq 
 22 
Para encontrar o ponto de mínimo da função )(xq , devemos resolver a equação 0)( =∇ xq . 
Assim, de 
0)]()()(
2
1
)()()([)( 00
2
0000 =−∇−+−∇+∇=∇ xxxfxxxxxfxfxq
TTT , 
tem-se 
)()]([0))(()( 0
1
0
2
0100
2
0 xfxfxxxxxfxf ∇∇−=⇒=−∇+∇
− . 
Portanto, o ponto de mínimo, sob a hipótese de que existe 10
2 )]([ −∇ xf , é o ponto 1x . Daí 
que o vetor de descida de Newton resulta sendo 
)()]([ 0
1
0
2
010
xfxfxxd Nx ∇∇−=−=
− . 
Note que, se por acaso Ixf =∇ )( 0
2 (i.e., as curvas de nível da função )(xq no ponto 0x 
são circunferências), então Cx
N
x dxfd 00 )( 0 =−∇= . 
 
Assim, determinado o vetor Nxd 0 , por uma busca linear nessa direção, determina-se o ponto 
N
x
N dxx
0001
λ+= . 
Dessa forma, se Nx1 não for o ponto procurado, Newton determinará uma direção 
N
xd 1 e, 
por uma busca linear, o ponto Nx
N dxx
1112
λ+= . Repetindo o processo, determina-se uma 
seqüência de pontos k
N
kx }{ com a propriedade de que k
N
kxf )}({ é decrescente. Pode-se 
provar que sob certas circunstâncias xxNk → e )()( xfxf
N
k → , onde x é solução do 
problema (P) e que a convergência é quadrática (para detalhes das provas do método ver 
Taha et al (1993)). Em geral, prova-se que se o ponto inicial, 0x , estiver suficientemente 
próximo do ponto procurado, x , existe convergência. Diz-se que a convergência é local. 
 
 
Dificuldades associadas ao Método de Newton 
Observe na Figura 17 que, considerando o ponto 0x como ponto de aproximação linear e 
quadrática para a função )(xf , a direção de Newton, Nxd 0 , resulta ser uma direção de 
subida. Já a de Cauchy, Cxd 0 , continua sendo de descida. Isto é, as direções de Newton nem 
sempre são de descida. Com efeito, para que )()]([ 0
1
0
2
0
xfxfdNx ∇∇−=
− seja direção de 
descida deve satisfazer que: 
0)()]([)()(0)( 0
1
0
2
000 00
<∇∇−∇=∇⇒<∇ − xfxfxfdxfdxf TNx
TN
x
T 
 0)()]([)( 0
1
0
2
0 >∇∇∇⇒
− xfxfxf T . (12) 
Note que a desigualdade (12) pode ser garantida se a matriz hessiana )( 0
2 xf∇ for definida 
positiva em volta de 0x (i.e., ddxfd
T ∀>∇ − ,0)]([ 10
2 , equivalentemente, )(xf 
estritamente convexa em volta de 0x ), o que não acontece no caso da Figura 17. Já no caso 
da Figura 16, efetivamente, )(xf estritamente convexa em volta de 0x , (12) é satisfeita e, 
portanto, Nxd 0 é direção de descida. 
 
 23 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Assim, se não se pode garantir que a direção de Newton é de descida, também não se 
garante que o Método é convergente (i.e., que nos leva a uma solução). Considere, além 
disso, que para problemas de grande porte, com um grande número de variáveis, o cálculo 
de )( 0
2 xf∇ pode ser computacionalmente caro. 
 
Portanto, resumindo, poder-se-ia afirmar que, se o método de Newton funcionar, funciona 
bem (com convergência quadrática). Mas, diversas particularidades atentam contra o bom 
funcionamento (ponto inicial muito afastado do procurado, eventual encontra com uma 
direção de Newton que não é de descida e tamanho do problema). Para tentar corrigir essas 
dificuldades, propõem-se na seguinte seção os métodos Quase Newton. 
 
 
Métodos Quase Newton 
 
Como indicado anteriormente, este tipo de método pretende corrigir as dificuldades 
associadas ao Método de Newton, tentando conservar seu bom comportamento. Pretende-se 
um método que tenha convergência global (i.e., não interessando se o ponto inicial está 
próximo ou afastado do ponto procurado, o método sempre nos levará a ele), que sempre 
origine direções de descida (como Cauchy), que se comporte como Newton quando 
próximo da solução (convergência quadrática) e que não seja computacionalmente caro 
(que não precise calcular segundas derivadas). 
 
Existem vários desses métodos, todos eles caracterizados pelo fato de imitar o 
comportamento de Newton, calculando direções de descida que aproximem a direção de 
Newton. 
 
A idéia central é a seguinte, já que a direção de Newton num dado ponto 0x é 
C
x
N
x dxfxfxfd 00
1
0
2
0
1
0
2 )]([)()]([ −− ∇=∇∇−= , pode-se interpretá-la como que é uma 
transformação da direção de Cauchy por meio da matriz (inversa de) )( 0
2 xf∇ . Note que 
essa matriz corresponde à função quadrática 
Figura 17. Método de Newton e direções de subida. 
C
xd 0 
N
xd 0 
× 
0x 
)(xl 
)(xq 
 24 
)()()(
2
1
)()()()( 00
2
0000 xxxfxxxxxfxfxq
TTT −∇−+−∇+= , 
mas que, eventualmente, )(xq não é estritamente convexa ()(xq resulta côncava se 
)( 0
2 xf∇ for semi-definida negativa), o que pode significar que a direção Nxd 0 não seja de 
descida, além do que, devendo ser calculada por segundas derivadas, resulta 
computacionalmente cara. Portanto, parte-se para aproximar a função )(xf por meio de 
uma outra função quadrática, estritamente convexa. Assim, calculando a correspondente 
transformação da direção de Cauchy pela matriz hessiana desta aproximação quadrática, 
encontra-se uma direção de descida; i.e., considere a aproximação quadrática 
)()(
2
1
)()()()( 00000 xxBxxxxxfxfxq
TTT
B −−+−∇+= , 
onde a matriz B é uma matriz definida positiva, simples de calcular (seu cálculo não precisa 
de segundas derivadas!). Logo, a direção Cx
B
x dBxfBd 00
1
0
1 )( −− =∇−= é uma direção de 
descida, pois desde que os autovalores de B são positivos, os de 1−B também são positivos 
e 
0)()()( 0
1
00 0
<∇−∇=∇ − xfBxfdxf TBx
T , 
i.e., Bxd 0 é direção de descida. Note que se )( 0
2 xfB ∇= , então Nx
B
x dd 00 = . 
 
A estratégia desenvolvida é a seguinte: Dada a função ℜ→ℜnf : a ser minimizada sem 
restrições e um ponto kx que não é solução do problema, originar uma seqüência de 
matrizes njD j ,,1, K= , de forma a que a primeira direção fornecida pelas matrizes 
(correspondente a1D ) seja a direção de Cauchy e a última (correspondente a nD ) seja a 
direção de Newton, as intermediárias corresponderão a direções que vão sendo ajustadas, 
na medida que os passos vão sendo efetuados. Começa-se com Cauchy, termina-se com 
Newton. 
 
Vários métodos tem sido desenvolvidos para isso. Dentre desses, o que se tem provado com 
mais sucesso computacional é o conhecido como BFGS (correspondente aos autores 
Broyden, Fletcher, Goldfarb e Shanno). O método consiste no seguinte: 
 
A partir do ponto kx , gerar uma seqüência de matrizes njD j ,,1, K= , de forma que 
ID =1 e njCDD jjj ,,1,1 K=+=+ , para 
 







 +
−








+==
j
T
j
T
jjj
T
jjj
j
T
j
jj
T
j
j
T
j
T
jjBFGS
jj
qp
qDppqD
qp
qDq
qp
pp
CC
)(
1 , (13) 
onde, dados os pontos auxiliares ,kj xy = para 1=j , define-se a j-ésima direção Quase-
Newton )( jj
QN
j yfDd ∇−= e, por uma busca linear, o ponto 
n
jy ℜ∈+1 , tal que 
)(min)( 01
QN
jjj dyfyf λλ += >+ , para encontrar 
 jjj yyp −= +1 e )()( 1 jjj yfyfq ∇−∇= + . (14) 
 25 
Pode-se provar que para a função Hxxxcxf Tt
2
1
)( += , quadrática e estritamente convexa, 
se njyf j ,,1,0)( K=≠∇ , 
12
1 )(
−
+ =∇= HxfDn . 
 
Assim, tomando em consideração as relações anteriores estrutura-se o algoritmo seguinte. 
 
Algoritmo Quase-Newton (BFGS) 
Passo 0. 
Determinar um tolerância pequena 0>Tol , escolher um ponto inicial 1x , fazer 
11 xy = , ID =1 e 1:: == jk . 
Passo 1. 
Se Tolyf j <∇ )( , PARAR! ( jy é uma aproximação de um mínimo local da função 
)(xf ). 
C.c., fazer )( jj
QN
j yfDd ∇−= e encontrar jλ , tal que )(min 0
QN
jj dyf λλ +> . Fazer 
QNjjjj dyy λ+=+ :1 . Se nj < ir ao Passo 2. Se nj = , fazer 111 ++ == nk yxy , 
1: += kk e 1:=j . ID =1 , voltar ao Passo 1. 
Passo 2. 
Fazer BFGSjjj CDD +=+ :1 , 1+= jj e ir ao Passo 1. 
 
Prova-se que o algoritmo anterior tem convergência quadrática global (e convergência 
quadrática quando está próximo duma solução). Note que não precisa das segundas 
derivadas da função )(xf . 
 
Note que poderia considerar-se outra atualização para a seqüência de matrizes no algoritmo 
Q-N, considerando 
11
11 )
~
( −−++ +==+=
BFGS
jjj
BFGS
jjj CBBCDD , (14’) 
prova-se que 
jj
T
j
j
T
jjj
j
T
j
T
jjBFGS
j pBp
BppB
pq
qq
C −=~ . (14’’) 
Assim, iniciando com IB =1 e atualizando 1+jB segundo (14’), o Algoritmo Q-N, poderia 
ser aplicado mudando )( jj
QN
j yfDd ∇−= pela solução de )( j
QN
jj yfdB −∇= (onde se 
aplicariam métodos de solução eficientes para sistemas lineares). 
 
 
Minimização com restrições: Funções Penalidade e Barreira 
 
Os métodos que usam penalidade têm por objetivo transformar um problema com restrições 
num outro sem restrições ou uma seqüência destes. A estratégia consiste em anexar as 
restrições à função objetivo, via um parâmetro de penalidade, e aplicar métodos de 
minimização sem restrições, de forma a que qualquer violação das restrições por algum 
 26 
ponto em consideração, seja penalizada, aumentando o valor da função objetivo do 
problema transformado. 
 
Por exemplo, para o problema com restrições 
nx
xh
xf
ℜ∈
= 0)( s.a
)(minimizar 
, 
a idéia sugere substituir esse problema, para algum parâmetro 0>µ (grande!), pelo 
problema sem restrições 
nx
xhxf
ℜ∈
+
 s.a
)()(minimizar 2µ
 ou 
nx
xhxf
ℜ∈
+
 s.a
)()(minimizar µ
. 
Desde que 0>µ é grande, espera-se que a solução x do problema transformado satisfaça 
0)( =xh ; i.e., seja viável para o problema original. 
 
Para o caso do problema 
nx
xg
xf
ℜ∈
≤ 0)( s.a
)(minimizar 
, 
não é conveniente penalizar segundo )()( 2 xhxf µ+ ou )()( xhxf µ+ , pois em ambos os 
casos penalizam-se tanto pontos inviáveis ( 0)( >xg ), quanto inviáveis ( 0)( ≤xg ). 
Naturalmente, só interessa penalizar pontos inviáveis. 
 
Portanto, pode considerar-se o problema penalizado 
 
nx
xgxf
ℜ∈
+ +
 s.a
)()(minimizar µ
 ou 
nx
xgxf
ℜ∈
+ +
 s.a
)()(minimizar 2µ
, 
 
onde )}(,0max{)( xgxg =+ e 0>µ . Note que enquanto para o primeiro desses problemas, 
a função objetivo não é diferenciável, já para o segundo sim o é. 
 
Em geral, uma função de penalidade deve atribuir penalização positiva a pontos inviáveis e 
penalização nula a pontos viáveis. Assim, para o conjunto viável 
 
{ }0)(,,0)(,0)(,,0)(: 11 ==≤≤ℜ∈= xhxhxgxgxS lmn KK 
 
pode definir-se como função de penalidade a função ℜ→ℜn:α , como 
 
 ∑∑
==
Ψ+Φ=
l
j
j
m
i
i xhxgx
11
))(())(()(α , (15) 
onde 
 27 



≤
>
=Φ
0 ,0
0 positiva,
)(
y
y
y e 



=
≠
=Ψ
0 ,0
0 positiva,
)(
y
y
y . 
 
Tipicamente, 
pyy +=Φ )( e ℵ∈=Ψ pyy
p
,)( . 
Freqüentemente, trabalha-se com 2=p : 
∑∑
==
+ +=
l
j
j
m
i
i xhxgx
1
2
1
2 )()()(α . 
 
A função )()( xxf µα+ chama-se função penalizada e 0>µ chama-se parâmetro de 
penalização. 
 
Note que para ∑∑
==
+ +=
l
j
j
m
i
i xhxgx
1
2
1
2 )()()(α , tem-se que 
∑∑∑∑
==
+
==
+ ∇+∇=







+∇=∇
l
j
jji
m
i
i
l
j
j
m
i
i xhxhxgxgxhxgx
111
2
1
2 )()(2)()(2)()()(α . (15’) 
 
A maneira de exemplo, aplica-se o método de penalização ao problema 
ℜ∈≤+− xx
x
,02s.a
minimizar
 
para o qual a solução é 2=x . Note que, neste caso, o problema penalizado (sem restrições) 
resulta 
2)2( minimizar +ℜ∈ +−+ xxx µ . 
 
Para ilustrar como atua o método, considere o gráfico da função penalizada para diferentes 
valores de 0>µ (
2
3
,1,
2
1 === µµµ , Fig. 18 e Fig. 19). Na Fig.18, mostram-se os 
gráficos, por separado, de xxf =)( e )(xµα , para os diferentes valores de µ . Na Fig. 19, 
mostram-se os gráficos da função penalizada )()( xxf µα+ , para 
2
1=µ e 
2
3=µ . 
 
Note que os mínimos para a função penalizada )()( xxf µα+ podem ser encontrados pela 
condição necessária: 
( ) xxxxxf
dx
d =→−=⇒=+−−⇒=+
∞→
2
2
1
20}2,0max{210)()(
µµ µ
µµα ; 
i.e., como mencionado na apresentação de método de penalização, para cada valor do 
parâmetro de penalização, µ , encontra-se uma solução do problema penalizado, µx , que se 
aproxima do mínimo 2=x do problema original. De fato, na Figura 19, mostram-se os 
valores de 1
2
1 =x e 3
2
1
2
3 −=x , para 2
3
 e 
2
1=µ . 
 
 28 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Por outro lado, note que para o problema 
 
n
j
i
x
ljxh
mixg
xf
ℜ∈
==
=≤
 
,,1,0)( 
,,1,0)( s.a 
)(minimizar 
K
K
 (16) 
o método de penalização, pode ser formulado da seguinte maneira: 
 
Passo 1: Dado 0>µ , qualquer, resolva o problema penalizado sem restrições 
)()( minimizar xxfnx µα+ℜ∈ , 
onde )(xα está definida como em (15). Considere que o problema penalizado tem solução 
µx e denote o valor ótimo por 
xxf =)( 
( )22
2
1
)(
2
1
++−= xxα
 
( )22)( ++−= xxα 
2 
Figura 18. Gráficos de xxf =)( e de ( ) ( )22 ++−= xx µµα , para 2
3
 e 1,
2
1=µ . 
( )22
2
3
)(
2
3
++−= xxα 
( )22
2
1
)(
2
1
)( ++−+=+ xxxxf α
( )22
2
3
)(
2
3
)( ++−+=+ xxxxf α 
Figura 19. Gráficos da função penalizada )()( xxf µα+ , para 
2
3
 e 
2
1=µ . 
2 1 2-1/3 
 29 
))()((min)()()( xxfxxf nx µαµαµθ µµ +=+= ℜ∈ . 
 
Passo 2: Se µx é solução do problema original, parar. Caso contrário, aumente o valor de 
0>µ e volte ao Passo 1. 
 
Naturalmente, ainda deve dizer-se que os µx se encontram por um método qualquer de 
minimização sem restrições e que deverá existir algum critério para saber se algum µx 
soluciona o problema original. Nesse último sentido, dentre as propriedades satisfeitas 
pelas funções e parâmetro envolvidos na penalização, interessa-nos principalmente a 
seguinte: 
 
Teorema 10. Considere o problema (16), onde todas as funções são contínuas e )(xα é a 
função penalidade (15). Se para cada 0>µ existe µx , tal que 
))()((min)()()( xxfxxf nx µαµαµθ µµ +=+= ℜ∈ , 
então 
(i) ],0)(,,0)(:)([inf)(sup 0 jxhixgxf ji ∀=∀≤≤> µθµ ; 
 
(ii) 





≥
≤
≤
⇒<
).()(
)()(
)()(
21
21
2121
µµ
µµ
αα
µθµθµµ
xx
xfxf
 
 
Adicionalmente, se 0}{ >µµx é uma seqüência limitada, então 
].,0)(,,0)(:)([inf))()((lim)(lim)(sup 0 jxhixgxfxxf ji ∀=∀≤=+== ∞→∞→> µµµµµ θµθµθ
 
Além disso, para qualquer seqüência crescente ∞=1}{ kkµ de parâmetros positivos, tal que 
xx
kk ∞→
→µ , tem-se que x é solução do problema (16) e 0)( ∞→→kk kxµαµ . 
 
Prova: A prova desta proposição pode ser encontrada em Taha et al (1993). 
 
Note que como conseqüência do Teorema 10, ocorre que se 
0)( =µα x , para algum 0>µ , então µx é solução do problema (16). 
 
Assim, 0)( =µα x pode ser usado como critério de parada. 
 
Portanto, tendo identificado um critério de parada simples, pode formular-se o algoritmo 
como segue. 
 
 
 
 
 30 
Algoritmo de penalização 
Passo 0. (Inicialização) 
Determinar um tolerância pequena 0>Tol , escolher um ponto inicial 1x , um valor 
01 >µ para o parâmetro de penalização e um fator de crescimento deste parâmetro, 
1>β . Fazer o contador de iterações 1:=k . 
Passo 1. (Solução do problema penalizado) 
Usando como ponto inicial o ponto kx , usar algum método de minimização sem 
restrições para resolver o problema penalizado 
))()((min xxf kx n αµ+ℜ∈ . 
Seja 1+kx solução deste problema. 
Passo 2. (Critério de parada) 
Se Tolx
kk
<)( µαµ , parar. Caso contrário, fazer kk βµµ =+ :1 e 1: += kk . Voltar ao 
Passo 1. 
 
Exercício: 
Aplicar o método de penalização ao seguinte problema, começando com o ponto inicial 
)0,0(1 =x , 11 =µ e diversos valores de 2=β , 10=β e 100=β . Comente os resultados. 
 
0, 
6 
2 s.a 
54minimizar 
21
21
2
2
1
2
221
2
1
≥
≤+
−≤−
+−xx
xx
xx
xxxx
 
 
 
Métodos de penalidade exata: Lagrangeano aumentado 
 
Nos métodos de penalidade apresentados é necessário fazer ∞→µ para aproximar-se da 
solução x do problema original (com restrições). Isto causa dificuldades numéricas, pois 
envolve cálculos da função objetivo )(xf de ordem pequena ou moderada junto a valores 
do parâmetro de penalização µ e da função penalizada )(xα eventualmente grandes e 
pequenos, respectivamente, quando ∞→µ . 
 
Portanto, é natural perguntar se existem funções de penalidade )(xα que determinem o 
valor exato da solução x , ao minimizar a função penalizada )()( xxf µα+ , sem 
necessidade de que µ cresça indefinidamente. Tais funções se denominam de penalidade 
exata. A seguir, apresentam-se duas de tais funções. 
 
A função de penalidade 1l (ou valor absoluto), definida por 
∑∑
==
+ +=
l
j
j
m
i
i xhxgxl
11
1 )()]([)( . 
 
A seguinte proposição estabelece que a função 1l é de penalidade exata. 
 31 
Teorema 11. Se o problema com restrições (16) é convexo e x é um ponto de K-K-T, com 
multiplicadores miui ,,1, K= , e ljv j ,,1, K= , então para },max{ ji vu≥µ , x é solução 
ótima do problema penalizado 
)()( minimizar 1 xlxfnx µ+ℜ∈ . 
Prova: A prova desta proposição pode ser encontrada em Taha et al (1993). 
 
Note, entretanto, que a função de penalidade 1l não é diferenciável, pelo que algoritmos 
como os aqui apresentados não poderão ser aplicados. A seguir apresenta-se uma função de 
penalidade exata diferenciável. 
 
Considere-se o seguinte problema com restrições: 
 
n
j
x
ljxh
xf
ℜ∈
== ,,1,0)( s.a
)(minimizar 
K (17) 
 
A função de penalidade Lagrangeano Aumentado, associada a esse problema define-se 
por: 
∑∑
==
++=
l
j
j
vxL
l
j
jjLA xhxhvxfvxF
1
2
),(
1
)()()(),( µ
444 344 21
. (18) 
 
Os dois primeiros termos de (18) constituem o que se denomina função Lagrangeano do 
problema (17), definido por 
∑
=
+=
l
j
jj xhvxfvxL
1
)()(),( . (18’) 
 
Assim, ∑
=
+=
l
j
jLA xhvxLvxF
1
2 )(),(),( µ ; i.e., neste caso, o Lagrangeano Aumentado resulta 
de adicionar penalização quadrática das restrições ao respectivo Lagrangeano. 
 
O interessante do Lagrangeano Aumentado é que se ),( vx é um ponto de KKT para o 
problema (17) (i.e., se satisfaz a condição necessária de ótimo), então 
 
 0,0)()(2)()(),(
0
0
>∀=∇+∇+∇=∇ ∑∑
=
=
µµ xhxhxhvxfvxF j
j
jj
j
jLAx 321
444 3444 21
. (19) 
 
Note que isso significa que pontos que satisfazem a condição necessária de mínimo para o 
problema (17), independente do valor de µ , são pontos críticos de ),( vxFLA . Portanto, se 
esta função for convexa, esses pontos são de mínimo e podem ser encontrados por algum 
dos algoritmos disponibilizados para minimização sem restrições. Por outro lado, desde que 
 32 
o termo ∑
=
l
j
j xh
1
2 )(µ sempre é convexo, na função ),( vxFLA , considerando µ 
suficientemente grande, esse termo passará a ser dominante e fará com que ),(vxFLA seja 
convexa. Logo, basta com considerar µ suficientemente grande para que pontos críticos de 
),( vxFLA sejam pontos de KKT para o problema original. 
 
A seguinte proposição resume o anteriormente discutido: 
 
Teorema 12. Considere-se ),( vx um ponto de KKT para o problema (17), que satisfaz as 
condições de segunda ordem para mínimo local. Então existe, µ , tal que para todo µµ > , 
),( vxFLA atinge um ponto de mínimo local em x . 
Prova: A prova desta proposição pode ser encontrada em Taha et al (1993). 
 
A seguir apresenta-se um algoritmo para implementar o método do Lagrangeano 
Aumentado (conhecido também como Método dos Multiplicadores). Antes é conveniente 
dizer que na definição da função ),( vxFLA , relação (18), com freqüência se introduz uma 
modificação em relação ao parâmetro de penalização, ao invés de considerar um único 
parâmetro de penalização µ para todas as funções restrição ljxh j ,,1),( K= , considera-se 
um parâmetro de penalização para cada restrição: ljxj ,,1),( K=µ , de forma a monitorar a 
violação das restrições individualmente. Assim redefine-se a função de penalidade 
Lagrangeano Aumentado, como: 
 ∑∑
==
++=
l
j
jj
l
j
jjLA xhxhvxfvxF
1
2
1
)()()(),( µ . (20) 
 
Note que associado ao problema (17) pode ser definida uma medida de quanto um dado 
ponto nx ℜ∈ satisfaz ou não as restrições. Considere-se, por exemplo, a função 
)(max)( 1 xhxviol jlj ≤≤= . É claro que se o ponto for viável para (17), então 0)( =xviol e, 
reciprocamente, que se 0)( =xviol será viável. Logo, esta função mede a viabilidade de um 
ponto para (17). 
 
 
Algoritmo do Lagrangeano Aumentado (Método dos Multiplicadores) 
 
Inicialização: Selecionar um vetor de multiplicadores ),,( 1 lvvv K= , valores positivos 
lµµ ,,1 K para os parâmetros de penalização das funções restrição, um valor pequeno 
0>Tol e um ponto inicial nx ℜ∈0 . Fazer 1:=k . 
 
Iteração Interior: (Minimização da função penalizada) 
Considerando (20) e iniciando com 1−kx , resolver o problema sem restrições: 
∑∑
==
ℜ∈
++=
l
j
jj
l
j
jjLAx
xhxhvxfvxFn
1
2
1
)()()(),(minimizar µ . 
 33 
Seja kx a solução do problema anterior. 
Se Tolxviol k <)( , PARAR! ( kx é ponto de KKT para o problema (17)). 
C.c., se )(
4
1
)( 1−≤ kk xviolxviol , ir à Iteração Exterior; 
se )(
4
1
)( 1−> kk xviolxviol , para cada lj ,,1K= onde )(4
1
)( 1−> kkj xviolxh , 
 fazer jj µµ 10:= ; 
Repetir a Iteração Interior. 
 
Iteração Exterior: (Atualização dos multiplicadores) 
Fazer 
 ljxhvv kjjjj ,,1),(2: K=+= µ ; 
 1: += kk ; 
Ir à Iteração Interior. 
 
 
Para o caso em que o problema de minimização tem restrições de desigualdade: 
n
j
i
x
ljxh
mixg
xf
ℜ∈
==
=≤
 
,,1,0)( 
,,1,0)( s.a 
)(minimizar 
K
K
, 
pode-se usar o mesmo esquema que para o problema (17), introduzindo variáveis de folga. 
Assim, note que o problema anterior pode ser escrito como: 
 
 
mn
j
ii
sx
sx
ljxh
misxg
xf
+ℜ∈
==
==+
),( 
,,1,0)( 
,,1,0)( s.a 
)( minimizar
2
,
K
K
. (21) 
Portanto, o problema passa ser um problema com lm+ restrições de igualdade, nas 
variáveis mnsx +ℜ∈),( . Assim, segundo (20), tem-se que Lagrangeano Aumentado 
associado é: 
 
∑∑∑∑
=
+
===
++++++=
l
j
jmj
m
i
iii
l
j
jj
m
i
iiiLA xhsxgxhvsxguxfvusxF
1
2
1
2
11
2 )(])([)(])([)(),,,( µµ , 
 
função para a qual pode aplicar-se o algoritmo anterior. Note que este método proporciona 
pontos solução não viáveis, pois os pontos gerados pelo algoritmo não satisfazem 
necessariamente .0)( =kxviol 
 
 
 
 34 
Programação Quadrática Seqüencial ou Lagrangeano Projetado 
Os métodos de Programação Quadrática Seqüencial (PQS) – Successive Quadratic 
Programming (SQP) –, também conhecidos como programação quadrática sucessiva ou 
recursiva, empregam o Método de Newton (ou Quase - Newton) para resolver as condições 
de KKT do problema de minimização com restrições original. Como resultado, constrói-se 
uma seqüência de subproblemas que consiste na minimização de aproximações quadráticas 
do lagrangeano sobre aproximações lineares das restrições. Assim, este tipo de métodos 
também é chamado de Lagrangeano Projetado ou Métodos Lagrange-Newton. Estes 
métodos produzem boas soluções para as variáveis e seus multiplicadores KKT. 
 
Considere, para começar, um problema com restrições unicamente de igualdade: 
 
n
i
x
lixh
xf
ℜ∈
== ,,1,0)(s.a
)(minimizar:(P)
K (22) 
 
Um ponto lnvx +ℜ∈),( é ponto de KKT para o problema (P), se cumpre que: 
0
)(
),(
)(
)()(
),(
,,1,0)(
0)()(
11
=




∇
=









 ∇+∇=⇒
==
=∇+∇ ∑∑
== xh
vxL
xh
xhvxf
vxW
lixh
xhvxf x
l
i
ii
i
l
i
ii
K
, (23) 
 
onde ∑
=
+=
l
i
ii xhvxfvxL
1
)()(),( e ))(,),(()( 1 xhxhxh l
T ∇∇=∇ K . Portanto, considerado o 
sistema (23) como 0),( =vxW , pode usar-se o Método de Newton-Raphson para resolve-lo 
(ou, equivalentemente, o Método de Newton para minimizar a função ),( vxF paraa qual 
),(),( vxWvxF =∇ ). 
 
Portanto, dado o ponto ),( kk vx , que não é solução de (23), aproxima-se linearmente o 
sistema 0),( =vxW , nesse ponto, e resolve-se o sistema aproximado: 
0),(),( =





−
−
∇+
k
k
kkkk vv
xx
vxWvxW . (24) 
 
Então, considerando ),( 11 ++ kk vx solução de (24), onde W∇ denota a derivada do vetor W 
e denotando a segunda derivada da função Lagrangeano, em relação a x , no ponto ),( kk vx 
por 
∑
=
∇+∇=∇
l
i
kikkkkx xhvxfvxL i
1
222 )()(),( , 
tem-se que 








∇
∇∇
=∇
T
k
kkkx
kk
xh
xhvxL
vxW
0)(
)(),(
),(
2
. (25) 
 35 
 
Agora, de (23) e (25), a relação (24) pode ser escrita como 
 
)())((
)()()()())(,(2
kkk
k
T
kkk
T
kkkkx
xhxxxh
vxhxfvvxhxxvxL
−=−∇
∇−−∇=−∇+−∇
. 
 
Substituindo )( kxxd −= , este último sistema pode ser reescrito como 
 
)()(
)()(),(2
kk
k
T
kkkx
xhdxh
xfvxhdvxL
−=∇
−∇=∇+∇
. (26) 
 
Considere ),( 1+kk vd uma solução do sistema (26). Então, fazendo kkk dxx +=+1 e 
aumentando o índice k por 1, pode-se repetir o processo até que 0=d resolva o sistema 
(26). Observe que neste caso, (23) se satisfaz para o ponto ),( 1+kk vx e ter-se-á encontrado 
um ponto de KKT para o problema (P). 
 
No que segue, ao invés de adotar o processo anterior para encontrar um ponto KKT para o 
problema (P), empregar-se-á um subproblema quadrático de minimização, cujas condições 
de otimalidade correspondem ao sistema (26), para o qual se podem encontrar soluções 
KKT convenientes. Esse subproblema quadrático está formulado a seguir, onde a constante 
)( kxf foi adicionada por conveniência: 
lidxhxhas
dvxLddxfxfvxPQ
T
kiki
T
kkx
TT
kkkk
,,1,0)()(.
),(
2
1
)()(minimizar:),( 2
K==∇+
∇+∇+
 (27) 
 
Alguns comentários se fazem necessários em relação ao problema ),( kk vxPQ , que será 
abreviado por PQ. Primeiro, note que um ótimo de PQ, se existir, é um ponto de KKT 
para PQ e satisfaz (26), onde v resulta ser o vetor de multiplicadores de KKT associado às 
restrições de PQ. Entretanto, o processo de minimização de PQ conduz a solução para um 
ponto KKT desejável, que satisfaz (26), sempre que existam alternativas. Segundo, note 
que a função objetivo de PQ, pode ser escrita como: 
dvxLddvxLvxL
dxhvddxfddxfxf
dxhvxfddxfxf
dvxLddxfxf
T
kkx
TT
kkxkk
l
i
kik
T
k
TT
kk
l
i
kikk
TT
kk
T
kkx
TT
kk
i
i
),(
2
1
),(),( 
))((
2
1
)(
2
1
)()( 
))()((
2
1
)()( 
),(
2
1
)()(
2
1
22
1
22
2
∇+∇+=
∇+∇+∇+=
∇+∇+∇+=
∇+∇+
∑
∑
=
= 
i.e., de um lado, a função objetivo é uma aproximação quadrática da função f , 
incorporando um termo adicional relacionado à curvatura das restrições; por outro lado, é 
 36 
uma aproximação de segunda ordem do lagrangeano (que ajuda a conseguir convergência 
quadrática, embora só se tenham restrições lineares). Terceiro, note que as restrições de 
PQ são linearizações das restrições no ponto atual, kx . Quarto, o problema PQ poderia 
não ter soluções limitadas ou ser inviável, já o problema (P) poderia não ter essas 
dificuldades. Mesmo que a primeira destas dificuldades poderia ser sanada adicionando, 
por exemplo, 1≤d às restrições de PQ, a segunda precisa de um tratamento especial. 
Entretanto, supondo bom comportamento e PQ, pode-se, agora, apresentar um esquema 
para um algoritmo de Programação Quadrática Seqüencial (PQS). 
 
Esquema de Algoritmo PQS: 
Inicialização: Faça 1:=k e selecione um ponto ),( kk vx inicial. 
Passo Principal: Resolva o subproblema quadrático ),( kk vxPQ . Seja kd a solução desse 
programa e 1+kv o vetor de multiplicadores associado. Se 0=kd , então ),( 1+kk vx é ponto de 
KKT para o problema (P). Caso contrário, faça kkk dxx +=+ :1 , 1: += kk e repita o Passo 
Principal. 
 
A convergência do Esquema de Algoritmo PQS, sob condições de regularidade de uma 
solução x para o Problema (P), com multiplicadores v , é quadrática. 
 
Extensão para incluir restrições de desigualdade 
A abordagem anterior pode estender-se para o problema com restrições de igualdades e 
desigualdes. Considere-se o problema 
 
n
j
i
x
ljxh
mixg
xf
ℜ∈
==
=≤
,,1,0)(
,,1,0)(s.a
)(minimizar:(P)
K
K (28) 
Para este caso, dado um ponto ),,( kkk vux , com os vetores 0≥ku e kv sendo as 
aproximações dos multiplicadores relacionados às desigualdades e igualdades, 
respectivamente, constrói-se o subproblema quadrático como extensão direta do problema 
(27): 
ljdxhxh
midxgxg
as
dvuxLddxfxfvuxPQ
T
kjkj
T
kiki
T
kkkx
TT
kkkkk
,,1,0)()(
,,1,0)()(
.
),,(
2
1
)()(minimizar:),,( 2
K
K
==∇+
=≤∇+
∇+∇+
 (29) 
onde ∑∑
==
∇+∇+∇=∇
l
j
kjk
m
i
kikkkkkx xhvxguxfvuxL ji
1
2
1
222 )()()(),,( . Lembre que as 
condições de KKT para ),,( kkk vuxPQ , além da viabilidade do ponto solução d , 
demandam que os multiplicadores u e v cumpram: 
 37 
0
,,1,0])()([
0)()(),,()(
11
2
≥
==∇+
=∇+∇+∇+∇ ∑∑
==
u
midxgxgu
xhvxgudvuxLxf
T
kikii
l
j
kjj
m
i
kii
T
kkkxk
K . (30) 
 
Assim, se 0=kd é solução de ),,( kkk vuxPQ e ),( 11 ++ kk vu são os multiplicadores de KKT 
associados, então, de (30), tem-se que: 
0
,,1,0)(
0)()()(
1
1
1
1
≥
==
=∇+∇+∇ ∑∑
=
+
=
+
u
mixgu
xhvxguxf
kii
l
j
kjk
m
i
kikk ji
K ; 
i.e., ),,( 11 ++ kkk vux é um ponto de KKT para o problema (P) original, dado em (28). Por 
outro lado, se 0≠kd , fazer kkk dxx +=+ :1 , 1: += kk e repetir o processo. Como no caso do 
problema só com restrições de igualdade, prova-se que sob certas condições de 
regularidade de uma solução x para o Problema (P), a convergência é quadrática. 
 
Aproximação Quase-Newton para o Algoritmo PQS 
Uma desvantagem do método PQS apresentado é que precisa calcular 
∑∑
==
∇+∇+∇=∇
l
j
kjk
m
i
kikkkkkx xhvxguxfvuxL ji
1
2
1
222 )()()(),,( , 
i.e., precisa do cálculo de várias derivadas de segunda ordem para resolver o subproblema 
),,( kkk vuxPQ , além do que ),,(
2
kkkx vuxL∇ pode não ser definida positiva. Isto pode ser 
resolvido utilizando aproximações Q-N definida positivas para ),,(2 kkkx vuxL∇ . Por 
exemplo, dada uma aproximação kB para ),(
2
kkx vxL∇ no Esquema de Algoritmo PQS, 
onde se supõem unicamente restrições de igualdade, pode-se substituir no sistema (26), 





∇
−=











∇
∇∇
⇔
−=∇
−∇=∇+∇
)(
)(
0)(
)(),(
)()(
)()(),( 22
k
k
k
T
kkkx
kk
k
T
kkkx
xh
xf
v
d
xh
xhvxL
xhdxh
xfvxhdvxL
, 
),(2 kkx vxL∇ por kB para obter uma única solução ),( 1+kk vd e fazer kkk dxx +=+ :1 . Isso é 
equivalente a um passo iterativo dado por: 





∇






∇
∇
−





=





−
+
+
)(
)(
0)(
)(
0
1
1
1
k
k
k
T
kkk
k
k
xh
xf
xh
xhBx
v
x
. 
Então, usando a atualização BFGS (14’)-(14’’), pode-se calcular 
kk
T
k
k
T
kkk
k
T
k
T
kk
kk pBp
BppB
pq
qq
BB −+=+1 , (31a) 
onde 
kkk xxp −= +1 e ),(),( 111 +++ ∇−∇= kkxkkxk vxLvxLq . (31b) 
Note que estão sendo assumidos passos de tamanho 1 entre duas iterações consecutivas, 
que junto ao comportamento, sob certas propriedades de regularidade, permitem comprovar 
taxas de convergência super-linear quando o ponto inicial está próximo da solução. 
 38 
 
Uma variante globalmente convergente do Método PQS usando a função de 
penalidade l1 como Função de Mérito 
A desvantagem principal do Método PQS, descrito acima, é que converge quando o ponto 
inicial está suficientemente próximo da solução (i.e., tem convergência local). Para 
procurara convergência global, usa-se o conceito de função de mérito, que é uma função 
que é minimizada juntamente com a função e, ao mesmo tempo, serve como função de 
descida, conduzindo as iterações e servindo como medida de progresso do algoritmo. Em 
geral, deve ser mais simples de avaliar que a função original e não deve piorara a 
convergência do algoritmo. 
 
Em continuação apresenta-se o caso da função 1l como função de méritopara o problema 
n
j
i
x
ljxh
mixg
xf
ℜ∈
==
=≤
,,1,0)(
,,1,0)(s.a
)(minimizar:(P)
K
K 
 
Considere a função 






++=+= ∑∑
==
+
l
j
j
m
i
iE xhxgxfxlxfxF
11
1 )()]([)()()()( µµ (32) 
A seguinte proposição estabelece que EF é função de mérito. 
 
Lema. Dado um ponto kx , considere o subproblema ),,( kkk vuxPQ dado por (29), onde 
),,(2 kkkx vuxL∇ está substituído por qualquer aproximação definida positiva kB . Seja d a 
solução desse problema, com multiplicadores de KKT ),,( 1 m
T uuu K= e ),,( 1 l
T vvv K= 
associados às restrições de desigualdade e igualdade, respectivamente. Se 0≠d e 
},{max , jiji vu≥µ , então d é uma direção de descida em kxx = para a função de 
penalizada EF . 
Prova: A prova desta proposição pode ser encontrada em Taha et al (1993). 
 
Note que no lema anterior se tem flexibilidade na escolha de kB para obter a direção de 
descida para a função de penalidade exata. Essa matriz só precisa ser definida positiva e 
poderia ser atualizada usando qualquer estratégia Quase-Newton (tal como em (31)) ou, 
ainda, poderia manter-se constante. 
 
Resumo do Algoritmo PQS com Função de Mérito 
Inicialização: Fazer 1:=k e escolher um ponto inicial kx . Escolher uma aproximação kB 
definida positiva para ),,(2 kkkx vuxL∇ , onde 0≥ku e kv são aproximações aos respectivos 
multiplicadores de KKT do problema (P). 
Passo Principal: Resolver o problema ),,( kkk vuxPQ dado por (29), com ),,(
2
kkkx vuxL∇ 
substituído por kB . Seja kd a solução desse problema e ),( 11 ++ kk vu os multiplicadores de 
 39 
KKT associados. Se 0=kd , Parar! ),,( 11 ++ kkk vux é um ponto de KKT para o problema (P). 
Caso contrário, fazer kkkk dxx λ+=+ :1 , onde kλ minimize )( kkE dxF λ+ , para 0≥λ . 
Atualizar kB para uma matriz definida positiva 1+kB (a qual pode ser mesmo kB ou 
),,( 111
2
+++∇ kkkx vuxL . Fazer 1: += kk e repetir o Passo Principal. 
 
Pode-se provar que, sob condições simples, o algoritmo anterior termina encontrando um 
ponto de KKT para o problema (P).