Upload
dangcong
View
221
Download
0
Embed Size (px)
Citation preview
Programação
Não Linear Irrestrita
EA 044 Planejamento e Análise
de Sistemas de Produção
DCA-FEEC-Unicamp
2
Tópicos
1-Introdução
2-Busca unidimensional
3-Condições de otimalidade
4-Convexidade e otimalidade global
5-Algoritmos
DCA-FEEC-Unicamp
3
1-Introdução
� Modelos de programação não linear (PNL)
max (min) f (x)sa x∈D ⊂ Rn
max (min) f (x)sa x∈D = Rn
restrito
irrestrito
DCA-FEEC-Unicamp
4
DCA-FEEC-Unicamp
Exemplo: regressão não linear
número custo número custo número custo
i p i q i i p i q i i p i q i
1 19 7.9 5 5 19.5 9 14 9.2
2 2 25 6 6 13 10 17 6.3
3 9 13.1 7 3 17.8 11 1 42.0
4 4 17.4 8 11 8.0 12 20 6.6
Número de unidades x Custo unitário
0
10
20
30
40
50
0 5 10 15 20
número
cust
o u
nit
ári
o
5
DCA-FEEC-Unicamp
Número de Unidades x Custo Unitário
0
10
20
30
40
50
0 5 10 15 20
número
cu
sto
un
itá
rio
2
1121 ])([),(min 2∑
=−=
m
i
xii pxqxxf
2)()( 1xpxprq ==
6024.069.40)( −== pprq
6024.0;69.40 21 −== ∗∗ xx
12=m
Hipótese:
Modelo PNL:
6
DCA-FEEC-Unicamp
Funções suaves e derivadas
f (x)
x
f (x)
x
f (x)
xsuave não contínua não diferenciável
7
� f (x) suave = contínua e diferenciável no domímio D ⊆ Rn
� Modelos PNL com funções suaves são mais tratáveis
� Funções suaves: possuem derivadas → busca mais eficiente
� Derivada: forma analítica pode ser difícil/impossível de ser
obtida
DCA-FEEC-Unicamp
8
2-Busca unidimensional
f (x)
x
xlo
xhixlo x1 x2
x2 xhix1
f (x)
xxlo
xlo
xhi
xhi
x2
x2
x1
x1
618.0
)(
)(2
1
=α−α+=
−α−=lohilo
lohihi
xxxx
xxxx
DCA-FEEC-Unicamp
f (x) unimodal
[xhi, xlo] contém x*
número de ouro
9
DCA-FEEC-Unicamp
Passo 0 Inicialização: escolher xlo , xhi e tolerância ε > 0; α = 0.618; determinar
x1 ← xhi – α (xhi – xlo )
x2 ← xhi + α (xhi – xlo )
calcular valor da função f (x) para os quatro pontos; t ← 0;
Passo 1 Parada: se (xhi– xlo ) ≤ ε,parar: solução ótima aproximada x* = 1/2(xhi– xlo);
senão ir para Passo 2, se f (x1) é superior a f (x2); caso contrário ir
para o Passo 3;
Passo 2 Esquerdo: estreitar lado esquerdo do intervalo;
xhi ← x2; x2 ← x1
x1 ← xhi – α (xhi– xlo )
avaliar f (x1); t ← t + 1; ir para Passo 1;
Passo 3 Direito: estreitar lado direito do intervalo;
xlo ← x1 ; x1 ← x2
x2 ← xlo + α (xhi – xlo )
avaliar f (x2); t ← t + 1; ir para Passo 1;
Busca unidimensional com número de ouro
10
DCA-FEEC-Unicamp
Intervalo inicial para busca unidimensional
� Intervalo inicial deve ser tal que x* ∈ [ xlo, xhi ] → padrão 3 pontos
� Padrão 3 pontos: { xlo, xmid , xhi }, xlo < xmid < xhi, f (xmid) melhor que f(xhi) e f(xlo)
{ xlo, xmid , xhi } → x* ∈ [ xhi , xlo ]
f (x)
xxhixlo x*
f(xhi)
f(xlo)
f(xmid)
xmid
11
Passo 0 Inicializa: escolher limitante inferior xlo para x* e passo δ > 0;
Passo 1 Esquerda ou Direita: se f (xlo + δ ) é superior à f (xlo) então xmid ← xlo + δ;
ir para o Passo 2 para busca à direita; caso contrário ótimo está à
esquerda; fazer xhi ← xlo + δ; ir para Passo 3;
Passo 2 Expande: amentar δ ← 2 δ; se f (xmid) é superior à f (xmid + δ) então
xhi ← xmid + δ e parar; { xlo, xmid , xhi} fornece padrão 3 pontos;
senão xlo ← xmid ; xmid ← xmid + δ; repetir Passo 2;
Passo 3 Reduz: diminuir δ ← δ/2; se f (xlo + δ ) é superior à f (xlo ) então
xmid ← xlo + δ e parar; { xlo, xmid , xhi} fornece padrão
3 pontos; senão xhi ← xlo + δ; repetir Passo 3;
Algoritmo padrão três pontos
DCA-FEEC-Unicamp
12
DCA-FEEC-Unicamp
3-Condições de otimalidade
� Vetor gradiente
)((x) 1 nj xf/...xf/...xf/f ∂∂∂∂∂∂=∇
� Matriz Hessiana
∂∂
∂∂∂
∂∂∂
∂∂
=
2
2
1
2
1
2
21
2
(x)
nn
n
x
f
xx
f
xx
f
x
f
H
L
MOM
L
f: Rn → R diferenciável em x
x = (x1, x2,...,xn)
13
DCA-FEEC-Unicamp
)ln()(2
)(2
])([),(
),(
111
2
11
1
2
1121
21
22
22
2
i
m
i
xi
xii
m
i
xi
xii
m
i
xii
ppxpxqx
f
ppxqx
f
pxqxxf
xxx
∑
∑
∑
=
=
=
−−=∂∂
−−=∂∂
−=
=
Exemplo: regressão não linear
14
)]ln())(()ln())([(2
])())()[((ln2
2
2222
222
2
11
112
2
21
2
21
111
222
2
1
221
2
ixi
xii
m
i
xi
xii
xi
m
i
xi
xiii
m
i
xi
ppxppppxqxx
f
xx
f
pxpxpxqpx
f
px
f
−−−=∂∂
∂=∂∂
∂
−−−=∂∂
=∂∂
∑
∑
∑
=
=
=
DCA-FEEC-Unicamp
15
DCA-FEEC-Unicamp
=
∂∂
∂∂∂
∂∂∂
∂∂
=
−−=∂∂∂∂=∇
−==
12.1100365.179
65.17977.50.5)-(33,
)23.174,07.23(),(0.5)- (33,
)5.0,33(),(x̂
x̂22
2
12
221
2
21
2
x̂21
21
x
f
xx
f
xx
f
x
f
H
xf/xf/f
xx
16
DCA-FEEC-Unicamp
Aproximação via série de Taylor
j
n
j j
tt
ttt
xx
fff
fff
∆
∂∂λ+=λ+
∆∇λ+=λ+
∑=1
1
1
)(xx)∆(x
x)(x)(x∆x)(x
ji
n
i
n
j jij
n
j j
tt
tttt
xxxx
fx
x
fff
Hfff
∆∆
∂∂∂λ+∆
∂∂λ+=λ+
∆∆λ+∆∇λ+=λ+
∑ ∑∑= == 1 1
2
12
2
2
2)(xx)∆(x
x)(xx2
x)(x)(xx)∆(x
1a ordem
2a ordem
17
DCA-FEEC-Unicamp
Gradientes e ótimos locais
� Ponto estacionário de f em xt: ∇f (xt) = 0
� Ponto estacionário: ótimo local de uma função objetivo suave
� Condição necessária de 1a ordem
)(x)(x)(xx)∆(x
]minmax,[)(xx
x)(x)(xx)∆(x
tttt
t
ttt
ffff
f
fff
∇∇λ±=λ+
−+±∇=∆
∆∇λ+=λ+
função objetivo melhora (a não ser que ∇f (xt) = 0)
↓
18
Hessianas e ótimos locais
DCA-FEEC-Unicamp
x)(xx2
0)(x
x)(xx2
x)(x)(xx)∆(x
t2
t2
∆∆λ++≈
∆∆λ+∆∇λ+≈λ+
Hf
Hfff
t
ttt
se xt é um ponto estacionário de f então ∇ f (xt) = 0; logo
� Condição necessária
xt mínimo local de f → H(xt) semi-positiva definida
xt máximo local de f → H(xt) semi-negativa definida
∆x direção que
melhora em xt
� Condição suficiente
xt ponto estacionário de f e H(xt) positiva definida → xt mínimo local de f
xt ponto estacionário de f e H(xt) negativa definida → xt máximo local de f
� Condições de 2a ordem
19
Exemplos de pontos estacionáriosmáximo
mínimo
sela
DCA-FEEC-Unicamp
20
DCA-FEEC-Unicamp
4-Convexidade e otimalidade global
f(x1)
f(x2)
f(x)
xx1 x2
f (x)
x
]1,0[D;x,x)];(x)(x[)(x))x(x(x 21121121 ∈∈−+≤−+ λλλ ffff
� Funções convexas
21
DCA-FEEC-Unicamp
f(x1)
f(x2)
f(x)
xx1 x2
]1,0[D;x,x)];(x)(x[)(x))x(x(x 21121121 ∈∈−+≥−+ λλλ ffff
x
f(x)
� Funções côncavas
22
DCA-FEEC-Unicamp
Funções convexas e côncavas
1- Se f(x) é convexa então – f(x) é côncava
2- f(x) com segundas derivadas continuas é convexa se e somente se
a matriz Hessiana H(x) é semi-positiva definida em um domínio convexo
(aberto); f(x) é côncava se e somente se H(x) é semi-negativa definida.
3- Funções lineares são convexas e côncavas
4- Se f(x) é côncava, g(x) = 1/ f(x) é convexa ∀ x | f(x) > 0
se f(x) é convexa, g(x) = 1/ f(x) é côncava ∀ x | f(x) < 0
5- Se g (y) é uma função convexa não decrescente e h (x) é convexa, então
f(x) = g(h(x)) é convexa; se g(y) é uma função côncava não decrescente
e h(x) é côncava, então f(x) = g(h(x)) é côncava
23
DCA-FEEC-Unicamp
6- f(x) é convexa se, para αi ≥ 0 e gi(x) convexa, i = 1, .., k
∑=
α=k
iii gf
1(x)(x)
7- f(x) formada a partir de máximos de funções convexas é convexa
f(x) formada a partir do mínimo de funções côncavas é côncava
},,1(x);{max(x) x kigf i L==
},,1(x);{min(x) x kigf i L==
8- Funções convexas (côncavas) são unimodais (o contrário não)
24
DCA-FEEC-Unicamp
Otimalidade global: condições suficientes
� Se f(x) é uma função convexa, então todo mínimo local é mínimo global
� Se f(x) é uma função côncava, então todo máximo local é máximo global
Considerando o caso de mínimo: seja x* mínimo global e x1 ≠ x*
0;0)](x*)(x[)(x*)(x 11 >λ∀<−λ⇒< ffff
]1,0[;)(x)](x*)(x[)(x)]x(x*[x 11111 ∈λ<−λ+≤−λ+ fffff
∆x = (x1 – x*) direção que melhora em x1,∀x1 ∈ D
x* ótimo global
↓
25
DCA-FEEC-Unicamp
� Todo ponto estacionário de uma função convexa suave é um mínimo global
� Todo ponto estacionário de uma função côncava suave é um máximo global
x0)(x(x)0)(x
)x)(x(x)(x(x)
)x(x)(x)(x)]x(x[x
]1,0()](x(x)[)(x)]x(x[x
**
***
****
****
∀≥−⇒=∇
−∇≥−
−∇λ+≈−λ+
∈λ−λ+≤−λ+
fff
fff
fff
ffff
Por exemplo, se f (x) é convexa, então:
x* é mínimo global
definição convexidade
Taylor
↓
26
DCA-FEEC-Unicamp
Passo 0 Inicialização: com solução inicial x0; tolerância ε > 0; t ← 0;
Passo 1 Gradiente: calcular ∇f (xt) em xt;
Passo 2 Ponto Estacionário: se ||∇f (xt)|| ≤ ε então parar; xt é
ótimo;
Passo 3 Direção: ∆ xt +1 ← ±∇f (xt) [+ para max, – para min];
Passo 4 Busca Unidimensional: determinar λt +1 resolvendo
maxλ (min) f(xt + λ ∆ xt +1);
Passo 5 Atualiza: xt +1 = xt + λ∆ xt +1 ;
Passo 6 Incrementa: t = t + 1; ir para Passo 1;
Algoritmo do gradiente
5-Algoritmos
27
Algoritmo do gradiente
x1
x2
x*
f(x)
xo
x1
x2 x3
∇f(xo)
DCA-FEEC-Unicamp
28
DCA-FEEC-Unicamp
29DCA-FEEC-Unicamp
30
Algoritmo de Newton
� Utiliza informação de segunda ordem
ji
n
i
n
j jij
n
j j
tt
ttt
xxxx
fx
x
fff
Hfff
∆∆
∂∂∂λ+∆
∂∂λ+=λ+
∆∆λ+∆∇λ+=λ+
∑ ∑∑= == 1 1
22
12
t2
2
2)(xx)∆(x
x)(xx2
x)(x)(xx)∆(x
fazendo λ = 1 e derivando com relação à ∆xi
x)x()(xx)(
,,1,
2
1
22
∆+∇=∆∇
=∆∂∂
∂+∂∂=
∆∂∂
∑=
tt
j
n
j jiii
Hff
nixxx
f
x
f
x
fL
)(xx)(x0x)(2tt fHf −∇=∆→=∆∇
DCA-FEEC-Unicamp
31
Newton
xo
x1
f(x)
DCA-FEEC-Unicamp
32
xo
x1 x2
x3x4
f(x)
Gradiente
DCA-FEEC-Unicamp
33
� Algoritmo Newtoniano converge para ótimo local se inicialização é
suficientemente próxima do ótimo local
� Não há garantia de que a matriz Hessiana seja não singular em
todo domínio de interesse
� Ideia: combinar gradiente + Newton
� Métodos quase Newtonianos: ∆xt +1 = – Dt∇f (xt)
� Matriz D aproxima da inversa da Hessiana H –1 durante a busca
� Hessiana: relacionada com a variação do gradiente:
])[()()( 1)1 ttttt xxxHxfxf −≈∇−∇ ++
↓
DCA-FEEC-Unicamp
34
Broyden, Fletcher, Goldfarb, Shanno: BFGS
max)min,(
)(x)(xgxxd
gd
dggd
gd
dd
gd
gg1
011
1
+−
±=∇−∇=−=
+−
++←
++
+
IDff
DDDDD
tttt
Tt
TTt
T
T
Tt
T
tt
11
1
1
xxx
)(xx
++
+
+
∆λ+←
∇−←∆
tt
tt
tt
t fD
DCA-FEEC-Unicamp
35
xo
x1
x2
BFGS
DCA-FEEC-Unicamp
36
Algoritmo de Nelder-Mead
� Não utiliza derivadas
� Mantém (n +1) soluções candidatas
� Baseia-se nos conceitos de:
– reflexão
– expansão
– contração
– encolhimento
1,,2)yy(2
1y
y1
x
yyxx
1
1
11
+=−=
≡
−≡∆
∑=
++
ni
n
ii
n
i
it
nnt
K
pior solução entre as (n + 1) candidatas
centróide dos n melhores
encolhimento
DCA-FEEC-Unicamp
37
xoy1
y2
y3
reflexão λ = 1 contração λ = 1/2 ou −1/2
expansão λ = 2
yn + 1 ← xt + λ∆x
DCA-FEEC-Unicamp
38
y2
y3
y1
encolhimento
novo y2
novo y3
1,,2)yy(2
1y 1 +=−= niii
K
DCA-FEEC-Unicamp
39
DCA-FEEC-UnicampProfFernandoGomide
Este material refere-se às notas de aula do curso EA 044 Planejamento e
Análise de Sistemas de Produção da Faculdade de Engenharia Elétrica e de
Computação da Unicamp. Não substitui o livro texto, as referências
recomendadas e nem as aulas expositivas. Este material não pode ser
reproduzido sem autorização prévia dos autores. Quando autorizado, seu
uso é exclusivo para atividades de ensino e pesquisa em instituições sem
fins lucrativos.
Observação