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).