25
Programação Não-Linear 1 Programação Não Linear

Program a Cao Nao Linear

Embed Size (px)

Citation preview

Page 1: Program a Cao Nao Linear

Programação Não-Linear 1

Programação

Não Linear

Page 2: Program a Cao Nao Linear

Programação Não-Linear 2

Os modelos empregados em Programação Linear são, como o próprio nome diz, lineares (tanto a função-objetivo quanto as restrições). Este fato é, sem dúvida, “a maior das restrições” impostas sobre um modelo de Programação.Em grande parte das aplicações, modelos lineares refletem apenas aproximações dos modelos reais. Fenômenos físicos ou econômicos são geralmente melhor representados por modelos não-lineares.A maioria das não-linearidades englobadas em um modelo de programação está dentro de 2 principais categorias:1)Relações observadas empiricamente, tais como variações não-proporcionais em custos, resultados de processos e características de qualidade.2)Relações deduzidas estruturalmente, que englobam fenômenos físicos, deduzidos matematicamente e regras administrativas.Em geral, os modelos empregados em Programação Não-Linear são do tipo:

( )

( )

( )( ) ( ) linearesnãofunções.ge.f

x,...,x,xXcom

0Xm,...,2,1iparabXg

asujeitoXf)Minou(Max

i

n21

ii

−=

⎩⎨⎧

≥=≤

Page 3: Program a Cao Nao Linear

Programação Não-Linear 3

Os métodos para resolução de problemas de Programação Não-Linear podem ser divididos em 2 grupos: 1) Modelos sem restrições e 2) Modelos com restrições

O principal conceito envolvido em Programação Não-Linear é o de taxa de variação⇒ derivadas e gradientes.

O grande problema que dificulta a obtenção da solução ótima nos problemas de Programação Não-Linear são os mínimos e máximos (extremos) locais da função-objetivo.

f(x)

x

a b c

Page 4: Program a Cao Nao Linear

Programação Não-Linear 4

Métodos de Otimização Sem Restrições

Método de Minimização de funções muito simplesConsiste nos seguintes passos:1)“chutar” 3 pontos (a,b,c).2)Escolher um ponto x entre a e b ou entre b e c.supondo que escolhemos entre b e c:3)Se f(b) < f(x) ⇒ 3 novos pontos são (a,b,x).4)Senão ⇒ 3 novos pontos são (b,x,c).5)Repetir processo até precisão desejada.

f(x)

xa b

f(a)

f(b) f(c)

c

Problema deste Método:

Extremamente dependente da inicialização (problema comum aos Métodos determinísticos).

Função precisa ser avaliada em muitos pontos ⇒ alto custo computacional.

Informação da derivada da função permite alcançar o extremo com menor número de avaliações da função ⇒ melhor eficiência computacional.

Page 5: Program a Cao Nao Linear

Programação Não-Linear 5

Método do Gradiente (ou Método de Cauchy ou Método do Passo Mais Descendente (Steepest Descent Method)).

Derivada fornece a informação da taxa de variação da função (1-D).

Para o caso n-D, o vetor gradiente fornece a direção da maior taxa de variação da função.Vetor Gradiente

Método consiste em:

Procurar o máximo (ou mínimo) na direção de maior taxa de crescimento (decrescimento) da Função Objetivo a partir de uma solução (ponto) inicial X(0).

maximização

minimização

t é o “tamanho do passo”

i é o número da iteração

⎥⎦

⎤⎢⎣

⎡∂∂

∂∂

∂∂

∂∂

=∇n321 x

f,...,xf,

xf,

xff

( ) ( ) ( )( )iXf.tiX1iX ∇+=+

( ) ( ) ( )( )iXf.tiX1iX ∇−=+

( )n21 x,...,x,xX =

Page 6: Program a Cao Nao Linear

Programação Não-Linear 6

Exemplo

De uma longa folha de metal de 30 cm de largura deve-se fazer uma calha dobrando as bordas perpendicularmente à folha. Quantos centímetros devem ser dobrados de cada lado de modo que a calha tenha capacidade máxima ?

30 cm 30 - 2xx x

30 - 2x

x

x

Quanto deve medir x para que a calha tenha capacidade máxima ?

Page 7: Program a Cao Nao Linear

Programação Não-Linear 7

A capacidade de escoamento de água da calha é, formalmente, a vazão!( ) v.Av,AQ = Q(A,v) é a vazão (cm3/s);

A é a área da seção (cm2); ev é a velocidade do fluído (cm/s).

Supondo v constante, a vazão torna-se diretamente proporcional à área da seção!

Portanto, maximizando A implica em maximizar Q(A,v).

30 - 2x

x

xÁrea da seção

30- 2x

x

2x2x30)x230.(x)x(f −=−=

0 2 .5 5 7 .5 1 0 1 2 .5 1 50

2 0

4 0

6 0

8 0

1 0 0

1 2 0ár e a m áx im a

Page 8: Program a Cao Nao Linear

Programação Não-Linear 8

30 - 2x

7.5cm

Área daseção

7.5cm

Solução do problema da calha pelo Método do Gradiente2x2x30)x230.(x)x(f −=−= ( ) x430)x(fxf −=′=∇ ( ) ( ) ( )( )ix430tix1ix −+=+

Por inspeção do gráfico anterior verifica-se que a função alcança o máximo (ótimo) em x = 7.5

19o iteração

x(18) = 7.4982

x(19) = 7.4982+0.1(30 – 4(7.4982)) = 7.4989

resíduo=0.0007

3o iteração

x(2) = 3.72

x(3) = 3.72 + 0.1(30 - 4(3.72)) = 5.232

resíduo=1.512

2o iteração

x(1) = 1.2

x(2) = 1.2 + 0.1(30 - 4(1.2)) = 3.72

resíduo=2.52

1o iteração

x(0) = -3

x(1) = -3 + 0.1(30 - 4(-3)) = 1.2

resíduo=4.2

resíduo = |x(i+1)-x(i)| ⇒ Processo iterativo cessa quando resíduo é menor que “precisão desejada” ⇒ critério de parada. Para t=0.1.

Page 9: Program a Cao Nao Linear

Programação Não-Linear 9

O gráfico da esquerda mostra o “caminho de busca (trajetória)” da solução ótima realizada pelo algoritmo para t = 0.1 e o da direita para t = 0.4.

-3 -1.5 0 1.5 3 4.5 6 7.5 9-150

-100

-50

0

50

100

150Função Objetivo e Processo de Busca do Máximo

solução

área

solução ótima

solução inicial

Caminhode Busca

FunçãoObjetivo

-3 -1.5 0 1.5 3 4.5 6 7.5 9 10.5 12 13.5 15-150

-100

-50

0

50

100

150Função Objetivo e Processo de Busca do Máximo

solução

área

Caminho de Busca

FunçãoObjetivo

Solução ótima

trajetória é função do tamanho do passo ⇒ Deve existir um tamanho de passo ótimo ?!

A solução ótima será alcançada mais rapidamente quanto menos a Função Objetivo for avaliada! Para isso, vamos fazer, sem perda de generalidade, algumas alterações no Método do Gradiente substituindo x(i+1) por Z(t), ou seja, uma expressão que é função do tamanho do passo t e x(i) por simplesmente x. O Método então fica:

)x(f.tx)x(f.tx)t(Z ′+=∇+=

Page 10: Program a Cao Nao Linear

Programação Não-Linear 10

Substituindo Z(t) em f(x), temos:

Igualando a derivada de g(t) (em relação a t) a zero (g'(t)=0) e então resolvendo para t, encontra-se uma função que descreve os valores ótimos de t para cada solução x.

No exemplo, Z(t) fica:

Substituindo Z(t) em f, fica:

Resolvendo para t:

( ) ( ))t(Zftg =

)x430(tx)t(Z −+=

222222 tx32t1800xt480tx16x2xt240t900x30)t(g −−++−−+=

tx64t3600xt960x16x240900)t(g 22 −−++−=′

⎩⎨⎧

=∉≠ℜ∈∀

=−−−+−

=5.7xparat5.7x25.0

x643600x960900x240x16t 2

2

1o iteração

x(0) = -3

x(1) = -3 + 0.25(30 - 4(-3)) = 7.5-3 -1.5 0 1.5 3 4.5 6 7.5 9 10.5 12 13.5 15

-150

-100

-50

0

50

100

150Função Objetivo e Processo de Busca do Máximo

solução

área

Caminho de Busca

FunçãoObjetivo

Solução ótima

Page 11: Program a Cao Nao Linear

Programação Não-Linear 11

Outro exemplo (caso 2-D)

( ) 22

21 x3xXfMin += ( )

⎥⎥⎥⎥

⎢⎢⎢⎢

∂∂∂∂

=∇

2

1

xfxf

Xf ( ) ⎥⎦

⎤⎢⎣

⎡=∇

2

1

x6x2

Xf

50

100

150

200

250

300

350

-10 -9 -8 -7 -6 -5 -4 -3 -2 -1-1

0

1

2

3

4

5

6

7

8

função objetivo representada por curvas de nível + vetores gradientes

x1

x2

Page 12: Program a Cao Nao Linear

Programação Não-Linear 12

A próxima figura mostra o "caminho de busca" no plano x1x2 dada a solução inicial em (-10,10).

50

100

150

200

250

300

350

-10 -8 -6 -4 -2 0 2 4 6 8 10-10

-8

-6

-4

-2

0

2

4

6

8

10

x1

função objetivo representada por curvas de nível + vetores gradientes

x2

Page 13: Program a Cao Nao Linear

Programação Não-Linear 13

O tamanho do passo ótimo t é calculado como:

Fazendo

e

Resolvendo para t

( )( )

( )( )

( )( )⎥⎦⎤

⎢⎣

⎡−⎥

⎤⎢⎣

⎡=⎥

⎤⎢⎣

⎡++

ix6ix2

.tixix

1ix1ix

2

1

2

1

2

1

( ) ( )( )⎥⎦

⎤⎢⎣

⎡++

=1ix1ix

tz2

1 ( ) ( )( )tzftg =

( ) ( )( ) ( ) ( ) 22

221

2 xt613xt21tzftg −+−==

( ) ( ) ( ) ( ) ( ) 06xt6162xt212tg 22

21 =−−+−−=′

22

21

22

21

x54x2x9xt

++

=

( ) ( )( ) ( ) ( )( )2222

11 ix1ixix1ixresíduo −++−+=

x1 x2 tamanho passo

iteração

-10.0000 10.0000 - 0

-6.4286 -0.7143 0.1786 1

-1.0714 1.0714 0.4167 2

-0.6888 -0.0765 0.1786 3

-0.1148 0.1148 0.4167 4

-0.0738 -0.0082 0.1786 5

-0.0123 0.0123 0.4167 6

-0.0079 -0.0009 0.1786 7

-0.0013 0.0013 0.4167 8

-0.0008 -0.0001 0.1786 9

-0.0001 0.0001 0.4167 10

Page 14: Program a Cao Nao Linear

Programação Não-Linear 14

Uma outra maneira de encontrar extremos de uma função não-linear é simplesmente igualar as derivadas parciais a zero e resolver o sistema de equações não-lineares.

Exemplo

O sistema não-linear fica:

Resolvendo este sistema, na região , tem-se: x1 = 2 e x2 = 1.

Para confirmar que temos um ponto de mínimo, podemos substituí-lo, nas derivadas parciais de 2o ordem:

( ) 121221

21 x10xx10x20xx

80x,xfMin +++=

⎪⎪⎩

⎪⎪⎨

=++−=∂∂

=++−=∂∂

020x10xx

80xf

010x10xx

80xf

12212

22

211

0x,x 21 ≥

80xx

160x

f

20xx

160x

f

1x,2x321

22

2

1x,2x231

21

2

21

21

==∂∂

==∂∂

==

==que por sua vez, são positivos, confirmando portanto, que o ponto é de mínimo.

Page 15: Program a Cao Nao Linear

Programação Não-Linear 15

Resumo( ) ( )( ) ( )

localMáximofffe0f

localMínimofffe0f

Strangsegundo

localMáximo0Xfe0XflocalMínimo0Xfe0Xf

2xyyyxxxx

2xyyyxxxx

⇒><

⇒>>

⇒<′′=′⇒>′′=′

Um grande problema desta abordagem estáem resolver sistemas de equações não-lineares, os quais geralmente, são resolvidos através de métodos numéricos.

( )( )( )

( )( ) ( )

( )

( ){ ( ) )1r(nciacircunferê1xxx,xgasujeito

x2xx,xfMax2ne1m

Exemplox,...,x,xX

linearesnãoXgeXfbXg

.bXgbXg

equaçõesassatisfaçaXXfMaxouMin

22

21211

22121

n21

i

mm

22

11

=⇒=+=

+=

==

=−

⎪⎪⎩

⎪⎪⎨

=

==

Otimização com Restrições e Função-Objetivo Não-Linear

Page 16: Program a Cao Nao Linear

Programação Não-Linear 16

Método dos Multiplicadores de Lagrange

Função Lagrangiana

onde: λ = (λ1, λ2,..., λm) são os multiplicadores de Lagrange.

Nota-se que para valores viáveis de X:

assim:

Portanto, se (X, λ) = (X*, λ*) é um extremo local ou global para a função sem restrição h(X, λ), então X* é um extremo para o problema original.

Assim, h(X, λ) é analisado normalmente como um modelo sem restrições. Com isso, n + m derivadas devem ser igualadas a zero.

( ) ( ) ( )[ ]∑ −λ−=λ=

m

1iiii bXgXf,Xh

( ) i,0bXg ii ∀=−

( ) ( )Xf,Xh =λ

( )⎪⎪⎩

⎪⎪⎨

==+−=λ∂∂

==∑∂∂

λ−∂∂

=∂∂

=

m,...,2,1i,0bXgh

n,...,2,1j,0xg

xf

xh

iii

m

1i j

ii

jj

Este sistema deverá fornecer os extremos locais (ou globais). No entanto, para problemas reais, tais sistemas tornam-se praticamente impossíveis de soluciona-los.

Page 17: Program a Cao Nao Linear

Programação Não-Linear 17

( )( )( ) ( )

( )

( )

( ) ( )⎪⎪⎪⎪

⎪⎪⎪⎪

=−+−=λ∂∂

=λ−=∂∂

=λ−=∂∂

−+λ−+=λ

=+=

+=

01xxh3

0x22xh2

0x2x2xh1

então1xxx2x,x,xh

1xxx,xg

x2xx,xf

Exemplo

22

21

1

22

111

22

2112

21121

22

2121

22121

( )

( )

( )

( )

( )

0x011x

31x0x1

20x221

2

1ou

0x01x

0xx1

1

21

22

2

1

1

1

11

111

==+−−

=⇒=−÷=−

⎪⎩

⎪⎨

=⇒=λ−

=λ− ( )

( ) ( )

( ) ( )1,0x,xe

1,0x,x1x1x

01xx

30xSe

21

21

222

22

21

1

−=

=∴±=⇒=

=+−−

=

Estes pontos são máximo e mínimo locais. Neste caso, estes pontos são máximo e mínimo globais. Como estamos querendo maximizar, a solução ótima é (x1,x2)=(0,1).

f(0,1)=02+2.1=2.

Page 18: Program a Cao Nao Linear

Programação Não-Linear 18

No exemplo anterior, os extremos locais são também globais. Porém, este fato foi observado apenas por inspeção dos resultados. Uma maneira mais elegante de verificar isto consiste em analisar a questão de convexidade de uma função, uma vez que esta propriedade pode garantir a existência de mínimos ou máximos globais.

Funções Convexas e Côncavas Unidimensionais

Uma função de uma única variável f(x) é uma função convexa se, para cada par de valores de x, por exemplo, x´ e x´´ com x´<x´´ tem-se:

Se pode ser recolocado por <, f é uma função estritamente convexa.

Se pode ser recolocado por por , f é uma função côncova.

Se pode ser recolocado por por >, f é uma função estritamente côncova.

A interpretação geométrica destas propriedades é a seguinte: se para cada par de pontos sobre o gráfico de f(x), um segmento de reta conectando estes 2 pontos estiver inteiramente acima ou sobre o gráfico de f(x), f(x) é dita convexa.

( )[ ] ( ) ( ) ( ) 10´xf1´´xf´x1´´xf <λ<λ∀λ−+λ≤λ−+λ

≤ ≥

Page 19: Program a Cao Nao Linear

Programação Não-Linear 19

Concâva

Estritamente Concâva

Convexa

Estritamente Convexa

Convexa e Côncava

Não Convexa e Não Côncava

Page 20: Program a Cao Nao Linear

Programação Não-Linear 20

O raciocínio é análogo para funções côncavas.

De maneira mais formal, o teste de convexidade (ou concavidade) pode ser realizado através da derivada segunda.f(x) é:

-Convexa se e somente se

-Estritamente convexa se e somente se

-Côncava se e somente se

-Estritamente côncava se e somente se

Esta propriedade pode ser generalizada para o caso de 2 variáveis. A seguinte tabela resume as condições.

( ) x0dx

xfd2

2∀≥

( ) x0dx

xfd2

2∀>

( ) x0dx

xfd2

2∀≤

( ) x0dx

xfd2

2∀>

Page 21: Program a Cao Nao Linear

Programação Não-Linear 21

As propriedades acima originam da análise da matriz Hessiana. De modo formal, uma função com n variáveis é dita convexa se a sua respectiva matriz Hessiana é Semi-Definida Positiva. Com isso, o conceito de convexidade pode ser generalizado para n dimensões.

Apenas como recordação, a matriz Hessiana de uma função f de n variáveis é:

Uma matriz é Semi-Definida Positiva se qualquer uma das seguintes propriedades ésatisfeita.

[ ][ ] ( ) n,...,2,1j,ixx

x,...,x,xfjiHji

n212

=∂∂

∂=

0épivôtodo)40antesminerdetpossuemprincipaisssubmatrizetodas)3

sautovetorexcomxHx0éHdeautovalortodo)2xvetor0Hxx)1 t

≥≥

λ=≥λ∀≥

Page 22: Program a Cao Nao Linear

Programação Não-Linear 22

Condições para Otimização com Restrições de Karush-Kuhn-Tucker (KKT)

Se f(X), g1(X), g2(X),..., gm(X) são diferenciáveis, então:

X* = (x1*, x2

*, ..., xn*) pode ser uma solução ótima para um problema de Programação

Não-Linear somente se existe m números λ1, λ2, ..., λm tais que todas as condições KKT são satisfeitas:

Nas condições 2 e 4 existem o produto de 2 quantidades, portanto, no mínimo umas dessas 2 quantidades deve ser zero para satisfazer a igualdade.

( )( )[ ]

n,...,2,1i0.6

n,...,2,1j0X.5

n,...,2,1ipara0bXg.4

0bXg.3

n,...,2,1jeXXem0

xg

xfx.2

0xg

xf.1

i

*j

i*

ii

i*

i

*

m

1i j

ii

j

*j

m

1i j

ii

j

=≥λ

=≥

=⎪⎭

⎪⎬⎫

=−λ

≤−

==

⎪⎪

⎪⎪

=⎟⎟⎠

⎞⎜⎜⎝

⎛∑

∂∂

λ−∂∂

∑ ≤∂∂

λ−∂∂

=

=

Page 23: Program a Cao Nao Linear

Programação Não-Linear 23

Assim, as condições 3 e 4 podem ser combinadas para uma forma equivalente:

Da mesma maneira, pode-se combinar as condições 1e 2:

Os multiplicadores de Lagrange λi correspondem para “variáveis duais”.

As condições KKT não garantem solução ótima ainda, faz-se necessário verificar as condições de convexidade-concavidade.

Se f(X) é côncava e g1(X), g2(X), ...., gm(X) são convexas (Programação Não-Linear Convexa) e condições KKT satisfeitas, X* = (x1

*, x2*, ..., xn

*) é ótima.

( )( )⎪⎩

⎪⎨⎧

=λ≤−

≠λ=−

0se0bXg

0se0bXg.4,3

ii*

i

ii*

i

⎪⎪⎩

⎪⎪⎨

=∑ ≤∂∂

λ−∂∂

∑ ≠=∂∂

λ−∂∂

=

=

0xse0xg

xf

0xse0xg

xf

.2,1*m

1i j

ii

j

m

1i

*

j

ii

j

j

j

Page 24: Program a Cao Nao Linear

Programação Não-Linear 24

( ) ( )

⎪⎩

⎪⎨

≥≥

≤+

++=

0x0x

3xx2asujeito

x1xlnXfMax

2

1

21

21

Exemplo

( )( ) ( ) ( )

( ) ( ) ( )

( ) ( )( )

( )( ) ( )

( ) ( ) ( )

ótimaéKKTatendaquesoluçãoqualquer

0xxXf

xXf.

xXf

0xxXf0

xXf0

1x1

xXf

:pois,acovcônx1xlnXf

0xxXg

xXg.

xXg

0xxXg0

xXg0

xXg

:pois,convexaxx2Xg1m

21

2

22

2

21

2

21

2

22

2

21

21

221

21

12

22

12

21

12

21

12

22

12

21

12

211

=⎥⎦

⎤⎢⎣

⎡∂∂

∂−

∂∂

∂∂

=∂∂

∂=

∂∂

<+

−=∂

⇒++=

=⎥⎦

⎤⎢⎣

⎡∂∂

∂−

∂∂

∂∂

=∂∂

∂=

∂∂

=∂

⇒+==

( ) 01x2j

021x

1x

1j

0xg

xfx

2condição01

2j

021x

11j

0xg

xf

1condiçãoKKT

12

11

1

j

11

j

*j

1

11

j

11

j

=λ−=

=⎟⎟⎠

⎞⎜⎜⎝

⎛λ−

+

=

=⎟⎟

⎜⎜

∂∂

λ−⎟⎟⎠

⎞⎜⎜⎝

∂∂

≤λ−=

≤λ−+

=

≤∂∂

λ−∂∂

( )

( )[ ][ ]

00

6condição0x,0x

0x

5condição03xx2

0bXg

4condição03xx2

0bXg

3condição

1

*i

21

*j

211

1*

11

21

1*

1

≥λ≥λ

≥≥

=−+λ=−λ

≤−+≤−

Page 25: Program a Cao Nao Linear

Programação Não-Linear 25

( ) ótimaé3,0X

KKTcondiçõesdosatisfazen1,3x,0x11,3x,0x

:porvioladacondiçãonenhuma)7)2j(2condição10x)6

3x03xx2)5

4condição03xx20)4)1j(2condição0x)3

021x

1)2

5condição0x)2j(1condição1)1

soluçãoRe

*

1211

121

12

2

21

211

1

11

1

1

=∴

=λ===λ∃∴

=λ==

=⇒=λ⇒≠=

=−+⇒=−+⇒≠λ=⇒=∴

<λ−+

⇒≥=⇒≥λ Outros tipos de problemas de

Programação Não-Linear:

-Programação Separável

-Programação Quadrática

-Programação Geométrica

-Programação Fracional

-Programação Não-Convexa