Otimiza

UNIVERSIDADE FEDERAL DO RIO DE JANEIRO

COPPE

PROGRAMA DE ENGENHARIA QUMICA

COQ-897 - OOttiimmiizzaaoo ddee PPrroocceessssooss

Profs. Argimiro R. Secchi e Evaristo C. Biscaia Jr.

2012

COQ-897 Otimizao de Processos - Profs. Argimiro e Evaristo - PEQ/COPPE/UFRJ

2

CCoonntteeddoo

1. FORMULAO DE PROBLEMAS .............................................................................................................. 5

1.1 APLICAES ................................................................................................................................................. 5

1.2 NOMENCLATURA .......................................................................................................................................... 7

1.3 PROCEDIMENTO GERAL ................................................................................................................................. 9

1.4 DIFICULDADES ENCONTRADAS ................................................................................................................... 10

2. CONCEITOS BSICOS ................................................................................................................................ 10

2.1 MNIMOS E MXIMOS .................................................................................................................................. 10

2.2 CONDIES PARA A OTIMALIDADE .............................................................................................................. 11

2.2.1 Otimizao sem restrio .................................................................................................................. 11

2.2.2 Otimizao com restries ................................................................................................................ 15

2.3 CONVEXIDADE ............................................................................................................................................ 23

2.4.1 Generalizao de funes convexas .................................................................................................. 25

2.4 FORMAS FUNCIONAIS .................................................................................................................................. 27

2.5 LGEBRA VETORIAL ................................................................................................................................... 30

EXERCCIOS DE FIXAO .................................................................................................................................. 31

3. OTIMIZAO SEM RESTRIO ............................................................................................................. 32

3.1 MTODOS DE BUSCA MONOVARIVEL E MULTIVARIVEL ........................................................................... 32

3.1.1 Mtodo da seo urea...................................................................................................................... 33

3.1.2 Mtodo da aproximao polinomial .................................................................................................. 34

3.1.3 Mtodo de busca seccionada ............................................................................................................. 36

3.1.4 Mtodo de Hooke & Jeeves ............................................................................................................... 37

3.1.5 Mtodo de Rosenbrock ...................................................................................................................... 38

3.1.6 Mtodo de Powell .............................................................................................................................. 39

3.1.7 Mtodo de busca de limites ............................................................................................................... 42

3.1.8 Mtodo dos poliedros flexveis .......................................................................................................... 42

3.1.9 Mtodos de busca aleatria ............................................................................................................... 44

3.2 MTODOS ANALTICOS (MTRICA VARIVEL) ............................................................................................. 51


3

3.2.1 Mtodos gradientes ............................................................................................................................ 52

3.2.2 Mtodo de Newton ............................................................................................................................. 54

3.2.3 Mtodo do gradiente conjugado ........................................................................................................ 55

3.2.4 Mtodos da mtrica varivel ............................................................................................................. 56

4. TEORIA DA DUALIDADE ........................................................................................................................... 63

4.1 PROBLEMA PRIMAL ..................................................................................................................................... 63

4.2 PROBLEMA DUAL ........................................................................................................................................ 64

4.3 INTERPRETAO GEOMTRICA DO DUAL ..................................................................................................... 65

4.4 DUALIDADE FRACA E FORTE ....................................................................................................................... 68

5. PROGRAMAO LINEAR (LP) ................................................................................................................ 71

5.1 FUNDAMENTOS ........................................................................................................................................... 72

5.2 MTODO SIMPLEX ....................................................................................................................................... 74

5.2.1 Primeira soluo vivel ..................................................................................................................... 77

5.2.2 Forma padro .................................................................................................................................... 78

5.3 MTODO DO PONTO INTERIOR (KARMARKAR) ............................................................................................ 79

6. PROGRAMAO NO LINEAR (NLP) .................................................................................................... 83

6.1 PROGRAMAO QUADRTICA (QP) ........................................................................................................... 83

6.2 RELAXAO LAGRANGEANA ...................................................................................................................... 87

6.3 FUNES PENALIDADE ................................................................................................................................ 90

6.4 PROGRAMAO LINEAR SEQENCIAL (SLP) ............................................................................................... 93

6.5 GRADIENTES REDUZIDOS GENERALIZADOS (GRG) ..................................................................................... 95

6.6 PROGRAMAO QUADRTICA SEQENCIAL (SQP) ................................................................................... 100

Exerccios de fixao ................................................................................................................................ 104

6.7 OTIMIZAO MULTI-OBJETIVO .................................................................................................................. 105

7. PROGRAMAO INTEIRA MISTA ........................................................................................................ 113

7.1 PROGRAMAO DINMICA ....................................................................................................................... 116

7.2 PROGRAMAO LINEAR INTEIRA MISTA (MILP) ....................................................................................... 118

7.2.1 Princpio dos mtodos dos planos de corte ..................................................................................... 120


4

7.2.2 Mtodo de branch and bound .......................................................................................................... 121

7.3 PROGRAMAO NO LINEAR INTEIRA MISTA (MINLP) ............................................................................ 127

7.3.1 Decomposio Generalizada de Benders (GBD) ............................................................................ 127

7.3.2 Aproximaes Externas (OA) .......................................................................................................... 129

7.3.3 Aproximaes Externas com Relaxamento de Igualdade (OA/ER) ................................................. 130

7.3.4 Aproximaes Externas com Relaxamento de Igualdade e Penalidade Aumentada (OA/ER/AP) .. 131

7.3.5 Aproximao Externa Generalizada (GOA).................................................................................... 132

7.3.6 Decomposio Cruzada Generalizada (GCD) ................................................................................ 133

7.3.7 Branch and Bound Espacial (SBB).................................................................................................. 134

8. OTIMIZAO DE PROCESSOS DINMICOS ...................................................................................... 142

8.1 FORMULAO DA FUNO OBJETIVO E RESTRIES ................................................................................. 143

8.2 PRINCPIO DO MNIMO DE PONTRYAGIN .................................................................................................... 144

8.3 CONTROLE TIMO ..................................................................................................................................... 151

8.4 CONTROLE PREDITIVO .............................................................................................................................. 154

EXERCCIOS ................................................................................................................................................... 155

BIBLIOGRAFIA BSICA .............................................................................................................................. 158


5

11.. FFoorrmmuullaaoo ddee PPrroobblleemmaass

Os componentes chaves da formulao de um problema de otimizao so:

1) A funo objetivo

2) O modelo do processo

3) As restries

A funo objetivo representa lucro, custo, energia, produo, distncia, etc., em termos das variveis de deciso do processo ou sistema em anlise. O modelo do processo e as restries descrevem as inter-relaes entre estas variveis.

11..11 AApplliiccaaeess As tcnicas de otimizao, que buscam a melhor soluo para um problema (mximos ou mnimos de grandezas mensurveis em seus domnios de definio), fazem-se necessrias em muitas reas da engenharia, tais como:

pesquisa operacional: otimizao de sistemas tcnico-econmicos, controle de estoques, planejamento de produo, etc.;

engenharia de processos: dimensionamento e otimizao de processos, integrao mssica e energtica de processos, estimao de parmetros, reconciliao de dados, anlise de flexibilidade, etc.;

controle de processos: identificao de sistemas, controle timo, controle adaptativo, controle preditivo, estimadores de estados, etc.;

anlise numrica: aproximaes, regresso, soluo de sistemas lineares e no-lineares, etc.

A otimizao pode ser efetuada em diferentes nveis dentro de uma empresa, desde uma combinao complexa de plantas e unidades de suprimentos, passando por plantas individuais, combinaes de unidades, equipamentos, peas de equipamentos, at entidades menores. Portanto, o escopo de um problema de otimizao pode ser toda a empresa, uma planta, um processo, uma equipamento, uma pea de um equipamento, ou qualquer sistema intermedirio entre estes. Em uma indstria tpica existem trs nveis que podem ser otimizados: nvel gerencial, nvel de projeto de processo e especificao de equipamento e nvel de operao de plantas.


6

Existe uma srie de atributos de processos que afetam os custos ou lucros, tornando-os atrativos para aplicao de otimizao, tais como:

- vendas limitadas pela produo aumento de capacidade produtiva

- vendas limitadas pelo mercado aumento de eficincia ou produtividade

- grandes unidades de processamento reduo dos custos de produo

- elevados consumos de matria-prima ou energia reduo do consumo

- qualidade do produto superior s especificaes operar perto das restries

- perda de componentes valiosos para os efluentes ajustes e re-aproveitamentos

- alto custo de mo-de-obra automao e replanejamento das unidades.

Exemplo 1.1: No projeto de um sistema de resfriamento representado abaixo:

deseja-se dimensionar os trocadores de calor de modo a resfriar a corrente a temperatura to para t3 com o menor custo possvel. Uma anlise econmica levou a seguinte expresso do custo do sistema:

custo por unidade: c a A b Wi i i i i

custo total: c cT ii

1

3

onde o coeficiente ai funo do tipo de trocador de calor e do fluido refrigerante e bi o custo unitrio do refrigerante. Uma anlise tcnica (balano de energia) gerou as seguintes relaes restritivas:

AF CpU

t Tt Ti ii i

i i

ln 1 e W F Cp t tii

i i O ( )1

onde Cp o calor especfico da corrente, Ui o coeficiente global de troca trmica e Oi o calor de vaporizao do refrigerante. Portanto, dados os tipos de trocadores de calor e fluidos refrigerantes, e conhecidas as temperaturas Ti e as propriedades Cp, Oi e Ui, o problema de levar a corrente (F, to) para a condio (F, t3) da maneira mais econmica possvel, consiste em minimizar cT no projeto dos trocadores de calor.

A1, U1

W1, T1

W1, T1

F, to A2, U2

W2, T2

W2, T2

F, t1 A3, U3

W3, T3

W3, T3

F, t2 F, t3


7

11..22 NNoommeennccllaattuurraa No contexto de otimizao os problemas so tratados dentro da seguintes definies:

funo objetivo: a funo matemtica cujo mximo ou mnimo deseja-se determinar. No exemplo acima a funo objetivo o custo total.

variveis de deciso: so as variveis independentes que aparecem na funo objetivo. Correspondem, em nmero, ao excesso de variveis em relao ao nmero de equaes (restries de igualdade), isto , o grau de liberdade do sistema. No exemplo acima tem-se 6 equaes (3 para Ai e 3 para Wi) e 8 variveis (t1, t2, Ai e Wi), portanto 2 variveis de deciso ou grau de liberdade igual a 2.

restries: so os limites impostos ao sistema ou estabelecidos pelas leis naturais que governam o comportamento do sistema, a que esto sujeitas as variveis de deciso. As restries podem ser de igualdade (equaes) ou de desigualdade (inequaes). No exemplo acima tem-se 6 restries de igualdade e 3 restries de desigualdade: t3 d t2 d t1 d to.

regio de busca: ou regio vivel, a regio do espao definido pelas variveis de deciso, delimitada pelas restries, em cujo interior ou em cuja fronteira se localiza o timo da funo objetivo. No exemplo acima, tomando t1 e t2 como variveis de deciso, a regio de busca aquela delimitada pelas restries de desigualdade.

No exemplo acima, o problema de otimizao foi gerado pela busca de um projeto timo do processo. Outra aplicao tpica de tcnicas de otimizao aparece na melhoria das condies de operao de um processo em produo.

t2

t1 t3

to

t1 t t2


8

Exemplo 1.2: No processo de extrao por solvente puro, ilustrado abaixo, deseja-se encontrar a condio de operao com a maior lucratividade possvel.

onde Wi e Wi so vazes mssicas de solvente, F a vazo mssica de gua, xi a massa de soluto por unidade de massa de gua e yi a massa de soluto por unidade de massa de solvente. Uma anlise econmica levou a seguinte expresso do lucro do sistema: lucro: L = R C receita: R = Ps (W1 y1 + W2 y2) custo: C = Px (W1 + W2) restrio: R > C

onde Ps o preo do soluto no extrato, Px o preo do solvente puro. Uma anlise tcnica gerou as seguintes relaes restritivas:

balanos de massa para o soluto: F xo W1 y1 F x1 = 0

F x1 W2 y 2 F x2 = 0

balanos de massa para o solvente: W1 W1 s F = 0

W2 + s F W2 s F = 0

relaes de equilbrio: y1 = m x1

y2 = m x2

onde s a solubilidade do solvente em gua (massa de solvente / massa de gua) e m a constante de equilbrio entre as fases. Portanto, dados F, xo, s, m, Ps e Px, o problema de extrair o soluto da gua da maneira mais lucrativa possvel, consiste em maximizar L em funo das condies de operao. Este exemplo possui tambm 6 equaes (4 equaes de balano de massa e 2 equaes de equilbrio) e 8 variveis (Wi, Wi, yi, x1 e x2), tendo portanto 2 variveis de deciso, ou dois graus de liberdade. Tomando x1 e x2 como variveis de deciso, a regio de busca para o problema de otimizao est delimitada pelas seguintes restries de desigualdade:

xo > x1 > x2 > 0

L(x1, x2) > 0

1

W1

W1, y1

F, xo 2

W2

W2, y2

F, x1 F, x2


9

A figura abaixo ilustra a regio de busca para F = 1,0 x 104 kg-gua / h, xo = 0,02 kg-soluto / kg-gua, s = 7,0 x 10-4 kg-solvente / kg-gua, m = 4,0 kg-gua / kg-solvente, Ps = 0,4 R$ / kg-soluto e Px = 0,01 R$ / kg-solvente.

0.005 0.01 0.015 0.02 0.025 0.03

0.005

0.01

0.015

0.02

X1

X2

0

5

10 15

18

Outra aplicao muito comum, que utiliza as tcnicas de otimizao, o ajuste de modelos matemticos a dados experimentais (ajuste de curvas), onde a funo objetivo utilizada, S(x), formada pelos quadrados dos desvios do modelo em relao aos dados experimentais (mnimos quadrados):

S x y x yj jj

N( ) [ ( ) ]exp

2

1

onde y(x) o modelo proposto (ou tipo de curva) para ser ajustado aos N dados experimentais yexp, e x so os parmetros de ajuste do modelo. Ou, se for utilizado o mtodo da mxima verossimilhana:

S x y x yj

j jj

N( ) [ ( ) ]exp

12 2

1V

onde V j2 so as varincias dos dados experimentais.

11..33 PPrroocceeddiimmeennttoo ggeerraall No existe um nico mtodo que pode ser aplicado eficientemente para todos os problemas. O mtodo escolhido para um caso particular depende das caractersticas da funo objetivo, da natureza das restries e do nmero de variveis do problema. Contudo, os seguintes passos devem ser observados na formulao e soluo de um problema de otimizao:

invivel economicamente


10

1) Anlise do processo e suas variveis;

2) Determinao do critrio para otimizao e especificao da funo objetivo em termos das variveis do processo;

3) Desenvolvimento do modelo para o processo, relacionando as suas variveis atravs de restries de igualdade e desigualdade. Clculo do grau de liberdade do sistema;

4) Se a formulao do problema de dimenso elevada, ento procurar particionar o problema em partes menores ou simplificar a funo objetivo e/ou o modelo;

5) Aplicao de tcnicas apropriadas de otimizao;

6) Analisar a soluo obtida e a sua sensibilidade frente a variaes em parmetros do modelo e suas consideraes (hipteses).

11..44 DDiiffiiccuullddaaddeess eennccoonnttrraaddaass Problemas de otimizao que apresentam funes objetivo e/ou restries complicadas podem apresentar grandes dificuldades para obter a soluo pelo uso de algumas tcnicas de otimizao. Algumas destas complicaes esto listadas abaixo:

- funo objetivo e/ou restries podem apresentar descontinuidades;

- funo objetivo e/ou restries no lineares;

- funo objetivo e/ou restries podem estar definidas em termos de complicadas interaes entre as variveis, podendo ocorrer valores no nicos destas variveis para o valor timo da funo objetivo;

- funo objetivo e/ou restries podem exibir patamares (pouca sensibilidade variao das variveis) para alguns intervalos das variveis e comportamento exponencial (muita sensibilidade) para outros intervalos;

- funo objetivo pode apresentar timos locais.

22.. CCoonncceeiittooss BBssiiccooss

22..11 MMnniimmooss ee mmxxiimmooss Seja uma funo S: X n o . Diz-se que x* um mnimo global (ou absoluto) de S se S(x*) d S(x) x X, e que x* um mnimo local (ou relativo) de S se existe H > 0, tal que S(x*) d S(x) x tal que ||x x*|| < H. Se as desigualdades forem estritas, isto , S(x*) < S(x) tem-se mnimos globais e locais estritos.


11

Se existe um nmero E tal que S(x) t E x X e, para um H suficientemente pequeno, S(x) < E + H para algum x X, ento E o nfimo (ou valor inferior) de S(x). Considerando os pontos rf, ento toda funo S(x) tem um nfimo e um supremo (ou valor superior) em X. Nem toda funo tem mnimo (mximo), mas se ele existir deve ser finito e obtido no nfimo (supremo), isto ,

S(x*) = )(inf)(min xSxSXxXx

[S(x*) = )(sup)(max xSxSXxXx

]

Por exemplo, as funes S(x) = ex e S(x) = e-x no tem mximo nem mnimo em X = . Contudo, o supremo destas funes E = +f, ocorrendo em x* = +f para ex e em x* = f para e-x, e o nfimo E = 0, de ex ocorrendo em x* = f para ex e em x* = +f para e-x.

22..22 CCoonnddiieess ppaarraa aa oottiimmaalliiddaaddee

22..22..11 OOttiimmiizzaaoo sseemm rreessttrriioo

No caso da otimizao sem restries, onde deseja-se encontrar os pontos extremos da funo objetivo, tem-se as seguintes condies de otimalidade.

Condio necessria de primeira ordem:

Para que x* seja um mnimo (mximo) local da funo S(x), diferencivel em x*, necessrio que:

S(x*) = 0

Condio necessria de segunda ordem:

Para que x* seja um mnimo (mximo) local da funo S(x), duas vezes diferencivel em x*, necessrio que:

S(x*) = 0 e que H(x*) { 2S(x*) seja positiva (negativa) semidefinida

onde H(x*) chamada de matriz Hessiana.

x

S(x) mnimos locais

mnimo global


12

Observa-se que estas condies so apenas necessrias porque os termos de primeira e segunda ordem podem estar nulos, deixando ainda dvida sobre a natureza de x*.

Condio suficiente:

Seja S(x) duas vezes diferencivel em x* tal que:

S(x*) = 0 e H(x*) seja positiva (negativa) definida

ento x* um mnimo (mximo) local estrito de S.

Pode-se analisar a condio da matriz Hessiana, H(x*), pelas seguintes formas:

1) Pela sua contribuio no termo de segunda ordem da expanso em srie de Taylor em torno do ponto timo.

*)(*)(*)(21*)()( xxxHxxxSxS T

2) Pelos sinais dos valores caractersticos de H(x*).

Decompondo a matriz Hessiana em seus valores e vetores caractersticos:

H(x*) = V / V-1 onde V a matriz dos vetores caractersticos (nas colunas) e / a matriz dos valores caractersticos (na diagonal). Definindo z(x) = V-1 (x - x*) e lembrando que sendo a matriz Hessiana simtrica ento V-1 = VT (matriz ortogonal) e (x - x*)T V = zT. Desta forma a expanso em srie de Taylor pode ser escrita como:

O /

n

iii

T zzzxSxS1

221

21*)()(

3) Pelos sinais dos determinantes das primeiras menores principais de H(x*) (critrio de Sylvester).

A menor Mij de uma matriz H definida como a matriz obtida pela remoo da i-sima linha e da j-sima coluna de H. Uma menor principal de ordem k uma matriz obtida pela remoo de quaisquer n k colunas e suas linhas correspondentes de uma matriz de ordem n. A primeira menor principal de ordem k de uma matriz H, denotada por Mk(H), obtida pela remoo das ltimas n k colunas e linhas da matriz H. Observa-se que os determinantes das primeiras menores principais de ordem 1,2,...,n da matriz / so, respectivamente: O1, O1O2, ..., O1O2O3On.


13

Na tabela a seguir apresenta-se as relaes entre a matriz Hessiana e as trs formas de analisar a sua condio.

H(x*) Taylor O 'k = det (Mk) positiva semidefinida xT H x t 0 t 0 t 0 positiva definida xT H x > 0 > 0 > 0

negativa semidefinida xT H x d 0 d 0 (-1)k 'k t 0 negativa definida xT H x < 0 < 0 (-1)k 'k > 0 no definida xT H x

! 0 ! 0 z dos acima

Desta forma, pode-se afirmar que x* :

ponto de mnimo local se H(x*) for positiva definida, S(x) > S(x*)

ponto de mximo local se H(x*) for negativa definida, S(x) < S(x*)

ponto de sela se H(x*) for no definida, ora S(x) > S(x*) e ora S(x) < S(x*)

Nas situaes onde H(x*) semidefinida deve-se ainda investigar os termos de ordem superior da expanso em srie de Taylor.

Exemplo 2.1: S(x) = (x2 1)3

S(x) = 6 x (x2 1)2 o S(x) = 0 xxx

1

2

3

01

1

, satisfazem a condio necessria de

primeira ordem;

H(x) = (x2 1) (30 x2 6) o H(x1) = 6; H(x2) = 0; H(x3) = 0 satisfazem a condio necessria de segunda ordem; contudo somente x1 satisfaz a condio suficiente. Neste caso (univarivel) x2 e x3 so pontos de inflexo, como pode ser visto no grfico abaixo, ou avaliando o valor da derivada terceira de S(x) nestes pontos:

3S(x) = 24 x (5 x2 3) o 3S(x2) = 48 z 0 e 3S(x3) = 48 z 0.


14

S(x)

-1.5

-1.0

-0.5

0.0

0.5

1.0

1.5

2.0

-1.5 -1.0 -0.5 0.0 0.5 1.0 1.5x

Exemplo 2.2: S x x x x x( , )1 2 12

1 22

S x x xx x

( ) 22

1 22

1 2

ento, x1* = x2* = 0, e:

12

2

2222

)(xxx

xH o H x( *)

2 00 0

isto , uma matriz positiva semidefinida. O grfico abaixo ilustra a funo S(x), onde se observa que x* = 0 no um ponto de mnimo. Fazendo a mesma anlise com a mudana de varivel 22xy , verifica-se que a origem um ponto sela.

11

1

2( , )

x yS x y

x

12 1

( , )1 0

H x y o 1 2 2,4142

0,41421 2

O

-5

0

5

-5

0

5-100

-50

0

50

100

150

x1x2

S(x

)


15

22..22..22 OOttiimmiizzaaoo ccoomm rreessttrriieess

Seja o problema de otimizao sujeito a restries de igualdade, h(x), e desigualdade, g(x): min S(x)

sujeito a: hj(x) = 0 , j = 1, 2, ..., m

gj(x) d 0 , j = 1, 2, ..., p x X n onde S(x), g(x), e h(x) C2. O conjunto de todos os pontos viveis definido por:

K = {x X n / h(x) = 0, g(x) d 0}

Uma restrio de desigualdade gj(x) chamada de ativa em um ponto vivel x se gj( x ) = 0, caso contrrio ela uma restrio inativa. As restries ativas restringem a regio de viabilidade, enquanto que as inativas no impem restrio alguma na vizinhana do ponto x , definida pela hiperesfera de raio H em torno deste ponto, denotada por BH( x ).

Um vetor d chamado de vetor de direo vivel a partir do ponto x se existe uma hiperesfera de raio H tal que:

( x +O d) {BH( x ) K} para todo 0 d O d dH .

O conjunto de vetores de direes viveis a partir de x chamado de cone de direes viveis de K no ponto x . A figura abaixo ilustra estas definies.

Se d z 0, ento x deve satisfazer as seguintes condies:

dT h( x ) = 0


16

dT g( x ) d 0 para as g( x ) ativas, pois ( ) ( )g x g x| 0 ( ) 0T g x d O d

e se dT S( x ) < 0, ento d uma direo vivel e promissora, isto ,

S( x + O d) < S( x ) para todo 0 d O d dH , pois ( ) ( ) ( ) 0TS x S x S x d | O .

Se x = x* um ponto de mnimo local do problema, ento para um O suficientemente pequeno, tem-se:

S(x*) d S(x* + O d). A idia chave para desenvolver as condies necessrias e suficientes para um problema de otimizao com restries transform-lo em um problema de otimizao sem restries e aplicar as condies para este caso. Uma forma de fazer esta transformao atravs da introduo de uma funo auxiliar, chamada de funo de Lagrange, L(x, O, P), definida como:

L(x, O, P) = S(x) + OT h(x) + PT g(x) , P t 0 onde O e P so os multiplicadores de Lagrange associados com as restries de igualdade e desigualdade, respectivamente (P so tambm conhecidos como multiplicadores de Kuhn-Tucker). Deste modo, o problema transformado torna-se:

xminmax

0, tPOL(x, O, P)

onde os multiplicadores O associados com as restries de igualdade, h(x) = 0, assumem sinais positivos quando h(x) t 0 e negativos quando h(x) d 0. No ponto timo tem-se:

L(x*, O*, P*) = S(x*)

Cada multiplicador de Lagrange indica o quo sensvel a funo objetivo em relao restrio associada. Por exemplo, se as restries de igualdade so perturbadas por um vetor b, isto , hb(x) = b, ento:

bS(x*) = O*. Note que neste caso a funo de Lagrange tem a forma:

L(x, O) = S(x) + OT [hb(x) b] e sua sensibilidade em relao ao parmetro b dada por:

bL = Tb x [xS(x) + Tx hb(x) O] + Tb O [hb(x) b] O

Como os termos entre colchetes da expresso acima devem ser nulos no ponto timo (condio necessria de primeira ordem), ento:


17

bL(x*, O*) = O* e bS(x*) = O* pois bL(x*, O*) = bS(x*) + Tb O [hb(x*) b] + Tb hb(x*) O* O* ,

hb(x) = b e bhb(x) = I Portanto, o valor de S(x) aumenta ou diminui a partir de S(x*) com um aumento ou diminuio em b, dependendo do sinal de O*. Por isso, os multiplicadores de Lagrange so tambm conhecidos como shadow prices ou custos marginais das restries, porque a mudana no valor timo da funo objetivo por unidade de acrscimo no lado direito da restrio de igualdade dado por O*.

Exemplo 2.3: Seja o seguinte problema de otimizao com restrio

min S(x) = (x1 5)2 + (x2 5)2 sujeito a: h(x) = x1 x2 = 0 Introduzindo uma perturbao na restrio de igualdade do tipo: x1 x2 = b, ento a funo de Lagrange toma a forma:

L(x, O) = (x1 5)2 + (x2 5)2 + O (x1 x2 b) cujo gradiente nulo com relao a x1, x2 e O leva ao seguinte sistema de equaes:

2 (x1 5) + O = 0 2 (x2 5) O = 0 x1 x2 b = 0

resultando na soluo tima: x1* = 5 + b / 2, x2* = 5 b / 2 e O* = b. Deste modo S(x*) = b2 / 2 e bS(x*) = b = O*.

Para entender a origem da funo de Lagrange, o timo do exemplo acima deve satisfazer as seguintes condies:

GS = 1x

Sww Gx1 +

2xS

ww Gx2 = 0

Gh = 1xh

ww Gx1 +

2xh

ww Gx2 = 0

Se S(x) fosse uma funo sem restrio, ento as suas duas derivadas parciais seriam nulas no ponto timo e GS(x*) seria nulo para quaisquer valores das variaes Gx1 e Gx2. Entretanto, como as variveis x1 e x2 esto restritas (Gx1 e Gx2 no so independentes), as duas derivadas parciais de S(x) no precisam ser igualadas a zero.


18

Contudo, S(x) deve ser um ponto estacionrio no ponto timo e, portanto, GS(x*) = 0. A segunda condio, Gh(x*) = 0, existe porque h(x) = 0. Para se obter uma soluo (Gx1 e Gx2) no-trivial do sistema de equaes acima, a matriz dos coeficientes do sistema:

ww

ww

ww

ww

21

21

xh

xh

xS

xS

deve ter determinante nulo, ou seja, as linhas da matriz so linearmente dependentes:

1xS

ww + O

1xh

ww = 0 e

2xS

ww + O

2xh

ww = 0

Ento, definindo uma funo auxiliar: L(x, O) = S(x) + OT h(x) as condies acima so satisfeitas se: xL(x, O) = 0. Para que a restrio de igualdade, h(x) = 0, seja tambm satisfeita necessrio que OL(x, O) = 0. Portanto, no ponto timo necessrio que L(x*, O*) = 0. A existncia dos multiplicadores de Lagrange depende da forma das restries, e estar garantida se e somente se os gradientes das restries de desigualdade ativas, gj(x*), e das restries de igualdade, h(x*), forem linearmente independentes. Por exemplo, no caso de um problema somente com restries de igualdade, a condio necessria de primeira ordem para L(x, O) fica:

xS(x) + [xh(x)]T O = 0 cuja soluo para O existir somente se a matriz xh(x) possuir posto completo, m, isto , estar composta por m vetores linearmente independentes.

Condio necessria de primeira ordem de Karush-Kuhn-Tucker (KKT):

Para que x* seja um timo local do problema com restries, com S(x), g(x), e h(x) diferenciveis em x*, necessrio que:

os gradientes das restries de desigualdade ativas, gj(x*), e das restries de igualdade, h(x*), sejam linearmente independentes (qualificao de segunda ordem das restries), e que as seguintes condies sejam satisfeitas:

xL(x*, O*, P*) = S(x*) + (O*)T h(x*) + (P*)T g(x*) = 0 h(x*) = 0

g(x*) d 0 Pj* gj(x*) = 0 , j = 1, 2, ..., p (condies de complementaridade) P* t 0


19

A condio de independncia linear pode ser relaxada por outras qualificaes de primeira e segunda ordem das restries (Floudas, 1995, pg. 59 e 64).

A condio do gradiente nulo, xL(x*, O*, P*) = 0, implica em: (O*)T h(x*) + (P*)T g(x*) = S(x*)

que interpretada graficamente, figura abaixo, mostra que o vetor S(x*) pertence ao cone das direes viveis, formado pelo negativo dos gradientes das restries de igualdade e desigualdade ativas (uma vez que *jP = 0 para as restries inativas).

Supondo que S(x*) caia fora do cone das direes viveis, ento haveria uma direo d tal que dT S(x*) < 0, dT g(x*) d 0 e dT h(x*) = 0, isto , existiria um ponto melhor que x*, como ilustra a figura abaixo.


20

Condio necessria de segunda ordem de KKT:

Para que x* seja um mnimo local do problema com restries, com S(x), g(x), e h(x) duas vezes diferenciveis em x*, necessrio que:

a condio de primeira ordem de KKT seja satisfeita e, que a matriz Hessiana da funo de Lagrange, 2x L(x*, O*, P*), seja positiva semidefinida para todo vetor no nulo d tal que:

dT hi(x*) = 0 , i = 1, 2, ..., m dT gj(x*) = 0 para as gj(x*) ativas

isto , dT 2x L(x*, O*, P*) d t 0.

Condio suficiente de KKT:

Para que x* seja um mnimo local do problema com restries, com S(x), g(x), e h(x) duas vezes diferenciveis em x*, suficiente que:

a condio de primeira ordem de KKT seja satisfeita e, que a matriz Hessiana da funo de Lagrange, 2x L(x*, O*, P*), seja positiva definida para todo vetor no nulo d tal que:

dT hi(x*) = 0 , i = 1, 2, ..., m dT gj(x*) = 0 para as gj(x*) ativas {gj(x*) = 0 e Pj* > 0}


21

dT gj(x*) d 0 para as gj(x*) inativas {gj(x*) < 0 e Pj* = 0}

isto , dT 2x L(x*, O*, P*) d > 0.

A positividade da matriz Hessiana com restrio, isto :

dT 2x L(x*, O*, P*) d > 0 d {d / dT hi(x*) = 0, dT gj(x*) = 0, d z 0}

garantida se todas as razes do polinmio caracterstico

00

)(2

O O Tx

MMLIp

forem positivas, onde M a matriz formada pelos gradientes de h(x*) e g(x*) ativas, isto , a matriz tal que MT d = 0, com m+pa < n e com posto completo (pa o nmero de restries g ativas). O mesmo critrio se aplica para semipositividade, negatividade e seminegatividade, com os respectivos sinais das razes.

Uma maneira de resolver o problema de valor caracterstico acima usando a decomposio QR (ou decomposio ortogonal-triangular, ou decomposio de Householder) da matriz M (= Q R) para obter a matriz de projeo, ZT, do vetor d no sub-espao nulo de MT, isto , MT d = 0, ou ento a decomposio em valores singulares da matriz MT (= U S VH). A matriz Z formada pelas ltimas w colunas de Q, ou ainda pelas ltimas w colunas de V, onde w a dimenso do espao nulo (nmero de valores singulares nulos, ou nmero de linhas nulas da matriz R):

Zi,j = Qi,j = Vi,j i = 1,2,..., n , j = m+paw+1,...,m+pa

onde QH M =

0R

(Q uma matriz unitria e Q1 = QH a transposta conjugada)

Uma vez encontrada a matriz Z, obtm-se os valores caractersticos da matriz Hessiana projetada neste sub-espao: ZT 2x L Z.

Exemplo 2.4: Verificar as condies necessrias e suficientes para o seguinte problema (Edgar & Himmelblau, 1988 , pg. 314):

min S(x) = (x1 1)2 + 22x

sujeito a: g1(x) = x1 22x / 4 d 0

Exemplo 2.5: Verificar as condies necessrias e suficientes para o problema com a mesma funo objetivo do exemplo 2.4, mas usando a seguinte restrio:

g2(x) = x1 22x d 0


22

Exemplo 2.6: Verificar se o ponto x* = [1 4,9]T um mnimo local para o seguinte problema (Edgar & Himmelblau, 1988 , pg. 316):

min S(x) = 4 x1 22x 12

sujeito a: h1(x) = 25 21x 22x = 0

g1(x) = 21x 10 x1 + 22x 10 x2 + 34 d 0

g2(x) = (x1 3)2 (x2 1)2 d 0 g3(x) = x1 d 0 g4(x) = x2 d 0


23

22..33 CCoonnvveexxiiddaaddee Um subconjunto K de um espao vetorial X dito convexo se x1, x2 K e 0 d D d 1:

D x1 + (1 D) x2 K

e apresenta as seguintes propriedades:

a) E K = {x K e x = E y, y K } convexo para E ; b) K + L e K L so convexos para subconjunto convexo L de X. Seja K um convexo no vazio do n. A funo S: K o dita convexa se x1, x2 K e 0 d D d 1:

S[D x1 + (1 D) x2] d D S(x1) + (1 D) S(x2) A funo S(x) estritamente convexa se a desigualdade for estrita. Uma funo T(x) cncava se a funo S(x) = T(x) for convexa.

Sejam S(x), Si(x), i=1,2,...,m, funes convexas em um convexo no vazio K do n, ento as seguintes propriedades so apresentadas: a) S(x) contnua em qualquer ponto do interior de K;

b) as sees KH = {x K e S(x) d H} so conjuntos convexos;

c) S(x) = 1

( )m

ii

S x uma funo convexa. Se no mnimo uma Si(x) estritamente

convexa, ento S(x) estritamente convexa;


24

d) E S(x) convexa para E > 0 . e) se todas Si(x) < f x K, ento S(x) = max{S1(x), S2(x), ..., Sm(x)} convexa. Quando S(x) convexa, as condies de otimalidade simplificam-se, porque as condies de segunda ordem so equivalentes convexidade local da funo. Alm disso, um mnimo local ser tambm global e se a funo for estritamente convexa o mnimo global nico.

Para ilustrar, define-se y = D x1 + (1 D) x2 e w = D S(x1) + (1 D) S(x2)

Seja X um conjunto aberto no vazio do n e S(x) uma funo diferencivel em xo X. Se S(x) convexa em xo, ento

S(x) S(xo) t TS(xo)(x xo) Para uma funo S(x) diferencivel em X,

S(x) convexa S(x2) S(x1) t TS(x1)(x2 x1) x1, x2 X. Seja X um conjunto aberto no vazio do n e S(x) uma funo duas vezes diferencivel em xo X. Se S(x) convexa em xo, ento 2S(xo) positiva semidefinida. Para uma funo S(x) duas vezes diferencivel em X,

S(x) convexa 2S(x) positiva semidefinida x X. Seja K um conjunto convexo no vazio do n, xo K e d um vetor no nulo tal que (xo + D d) K para um D > 0 suficientemente pequeno. Ento, a derivada direcional de S(x) no ponto xo, ao longo da direo d, denotada por S(xo,d), definida pelo seguinte limite (incluindo rf):

20 0

( ) ( )( , ) lim lim ( ) ( )o o

o T o T oS x d S xS x d S x d d S x d Do Do

D c | D D

Portanto, a derivada direcional no ponto xo dada por S( xo,d) = TS(xo) d. Seja K um conjunto convexo no vazio do n e S(x) uma funo convexa. Ento, o sub-gradiente de S(x) no ponto xo K, denotado por d, definido como:

y x1

funo convexa S(x)

x2 x

S(y) w

y x1

funo cncava S(x)

x2 x

S(y)

w


25

S(x) t S(xo) + dT (x xo) , x K Isto , a aproximao linear com o uso do vetor d sempre resulta em uma sub-estimativa de S(x).

22..44..11 GGeenneerraalliizzaaoo ddee ffuunneess ccoonnvveexxaass

Para generalizar a definio de funes convexas necessrio definir a continuidade de funes escalares multivariveis.

Sejam X n, xo X e S(x): X o . S(x) contnua em xo se:

para cada H > 0 existir G(H) tal que ||x xo|| < G |S(x) S(xo)| < H, ou para cada sequncia x1, x2, ..., xm em X convergindo para xo:

)(lim)(lim omm

mm

xSxSxS

fofo.

S(x) contnua em X se ela for contnua x X. S(x) semicontnua inferior em xo se:

para cada H > 0 existir G(H) tal que ||x xo|| < G H < S(x) S(xo), ou para cada sequncia x1, x2, ..., xm em X convergindo para xo:

)(lim)(inflim omm

mm

xSxSxS

fofo,

onde )}(),...,(),(min{lim)(inflim 21 mm

mm

xSxSxSxSfofo

.

S(x) semicontnua inferior em X se ela for semicontnua inferior x X.

funo semicontnua inferior funo semicontnua superior


26

S(x) semicontnua superior em xo se:

para cada H > 0 existir G(H) tal que ||x xo|| < G S(x) S(xo) < H, ou para cada seqncia x1, x2, ..., xm em X convergindo para xo:

)(lim)(suplim omm

mm

xSxSxS

fofo,

onde )}(),...,(),(max{lim)(suplim 21 mm

mm

xSxSxSxSfofo

.

S(x) semicontnua superior em X se ela for semicontnua superior x X.

Seja K um convexo no vazio do n. A funo S: K o dita quasi-convexa se x1, x2 K e 0 d D d 1:

S[D x1 + (1 D) x2] d max{S(x1), S(x2)} A funo S(x) estritamente quasi-convexa se a desigualdade for estrita quando S(x1) z S(x2). Uma funo T(x) (estritamente) quasi-cncava se a funo S(x) = T(x) for (estritamente) quasi-convexa. Um mnimo local de uma funo estritamente quasi-convexa ser tambm global.

Funo quasi-convexa Funo estritamente quasi-convexa (pseudo-convexa)

Definindo as sees KH = {x K e S(x) d H}, ento: S(x) quasi-convexa KH convexo H .

Seja S(x) uma funo semicontnua inferior no convexo K n. Se S(x) estritamente quasi-convexa em K, ento S(x) quasi-convexa, mas o converso no verdadeiro.

A soma de funes quasi-convexas no necessariamente uma funo quasi-convexa, propriedade vlida para funes convexas. Por outro lado, o recproco de


27

uma funo quasi-convexa, 1/S(x), uma funo quasi-cncava, mas o recproco de uma funo convexa no necessariamente uma funo cncava (j o recproco de uma funo cncava positiva uma funo convexa). Por exemplo, S(x) = ex convexa e 1/S(x) convexa tambm.

Seja S(x) uma funo diferencivel em um conjunto convexo aberto no vazio K n, ento:

S(x) quasi-convexa S(x2) d S(x1) o TS(x1)(x2 x1) d 0 x1, x2 K. Seja S(x) uma funo quasi-cncava duas vezes diferencivel em um conjunto convexo aberto no vazio K n, ento uma direo, d, ortogonal ao S(x) exibe as seguintes propriedades:

a) se xo K, d n e dT S(xo) = 0, ento dT 2S(xo) d d 0; b) a matriz Hessiana de S(x) tem no mximo um valor caracterstico positivo x K. Isto , a generalizao da concavidade de funes (para quasi-cncavidade) equivalente existncia de no mximo um valor caracterstico positivo da Hessiana.

Seja S(x) uma funo diferencivel em um conjunto aberto no vazio X n. S(x) pseudo-convexa se S(x2) < S(x1) o TS(x1)(x2 x1) < 0 x1, x2 X. Uma funo T(x) pseudo-cncava se a funo S(x) = T(x) for pseudo-

convexa. O recproco de uma funo pseudo-cncava, 1/S(x), uma funo pseudo-convexa. As seguintes relaes so vlidas:

a) uma funo convexa diferencivel pseudo-convexa;

b) uma funo convexa estritamente quasi-convexa;

c) uma funo convexa quasi-convexa;

d) uma funo pseudo-convexa estritamente quasi-convexa;

e) uma funo estritamente quasi-convexa e semicontnua inferior quasi-convexa.

22..44 FFoorrmmaass ffuunncciioonnaaiiss O mtodo empregado para solucionar um problema de otimizao depende, fundamentalmente, da forma da funo objetivo e de suas restries. Com relao a funo objetivo tem-se:

funo linear: S x a c x a c xT ii

n

i( )

1

como neste caso S(x) = c z 0 x, a funo S(x) no apresenta pontos de mximo ou mnimo. Para este tipo de funo objetivo, s faz sentido a existncia de um problema


28

de otimizao com restrio, cuja soluo, se existir, estar localizada em algum ponto da fronteira da regio de busca.

funo quadrtica: S x a c x x A x a c x a x xT T ii

n

i ij i jj

n

i

n( )

12

121 11

como xT A x um escalar xT A x = [xT A x]T = xT AT x,

tem-se que: x A x x A x x A x x A A xT T T T T T

12

12

( ) ( ) ,

ento definindo Q A AT 12

( ) , que uma matriz simtrica: Q = QT,

resulta em: xT A x = xT Q x, isto :

S x a c x x Q x a c x q x xT T ii

n

i ij i jj

n

i

n( )

12

121 11

e portanto:

S x Sx c qxx

x xxxk

k iji

kj i

j

kj

n

i

n( ) ww

ww

ww

12 11

,

mas como ww G

xx

i k

i ki

kik

z

0

1

,

, , tem-se:

S x c q x q xk kj j ik ij

n

i

n( ) ( )1

2 11

e sabendo que a matriz Q simtrica:

S x c q x c Q xk ik ii

n( )

1

e H(x) = 2S(x) = Q

com isto, a condio necessria de primeira ordem, S(x*) = 0, para este tipo de funo resulta em:

Q x* = c ou de forma similar (x*)T Q = cT e

S x a c x x Q x a c xT T T( *) * ( *) * * 12

12

Subtraindo S(x*) da funo S(x) tem-se:


29

> @S x S x c x x x Q x x Q xT T T( ) ( *) ( *) ( *) * 12 como cT = (x*)T Q,

> @S x S x x Q x x Q x x Q x x x Q x xT T T T( ) ( *) ( *) * ( *) ( *) ( *) ( *) 12 > @S x S x x Q x x Q x x Q x xT T T( ) ( *) ( *) ( *) ( *) 12 > @S x S x x x Q x x Q x xT T( ) ( *) ( *) ( *) ( *) 12

S x S x x x Q x xT( ) ( *) ( *) ( *) 12

funo no linear: S(x): n o a expanso em srie de Taylor de S(x) em torno de um ponto xo dada por:

S x S x S x x x x x S x x xT T( ) ( ) ( ) ( ) ( ) ( ) ( ) 0 0 0 0 2 0 012

No caso particular de xo = x*, tem-se S(x*) = 0 e:

S x S x x x H x x xT( ) ( *) ( *) ( *) ( *)| 12

Se S(x) for duas vezes diferencivel em x*, ento H x Sx xi j x

( *)*

ww w

2 simtrica.

Portanto, tanto no caso de funo quadrtica, onde H(x*) = Q, quanto no caso geral de funo no-linear, a matriz Hessiana fornece as caractersticas do(s) ponto(s) timo(s) de S(x).

Algumas observaes adicionais:

1) no caso de S(x) ser uma funo quadrtica, o ponto timo global;

2) se H(x*) positiva definida, ento S(x) estritamente convexa na vizinhana de x* (ou x no caso da funo quadrtica);

3) se H(x*) positiva semidefinida, ento S(x) convexa na vizinhana de x* (ou x no caso da funo quadrtica);


30

4) se H(x*) negativa definida, ento S(x) estritamente cncava na vizinhana de x* (ou x no caso da funo quadrtica);

5) se H(x*) negativa semidefinida, ento S(x) cncava na vizinhana de x* (ou x no caso da funo quadrtica);

funo mista linear e inteira: S(x, y) = cT x + dT y , x X n e y Y onde y um vetor de variveis inteiras de dimenso q, Y q, ou um vetor de variveis binrias de dimenso q, Y = {0, 1}q. Como a funo linear, s faz sentido a existncia de um problema de otimizao com restrio.

funo mista no-linear e inteira: S(x, y): X u Y o Problemas de otimizao mista no-linear e inteira apresentam grandes desafios e dificuldades associados com o carter combinatorial do domnio discreto (inteiro) junto com as comumente encontradas no-convexidades e no-linearidades do domnio contnuo.

funo unimodal: a funo que apresenta apenas um extremo.

funo multimodal: a funo que apresenta mais de um extremo.

NOTA: toda funo cncava ou convexa unimodal, mas nem toda funo unimodal necessariamente cncava ou convexa. Veja exemplo S(x) = (x2 1)3.

22..55 llggeebbrraa vveettoorriiaall Sejam x e y X n, A e B nun, S(x): X o , g(x) e h(x): X o X. Ento as seguintes regras de diferenciao se aplicam:

[g(x)T h(x)] = Tg(x) h(x) + Th(x) g(x) [S(x) g(x)] = g(x) TS(x) + S(x) g(x) (A x) = A (xT A) = A (xT A x) = (A + AT) x S[g(x)] = Tg(x) gS(g) S{g[h(x)]} = Th(x) hTg(h) gS(g) g[h(x)] = hg(h) h(x)


31

yxyxdt

yxd TTT )(

xAxAdt

xAd )(

BABAdt

BAd )(

xAxxAxxAxdt

xAxd TTTT )(

EExxeerrcccciiooss ddee ffiixxaaoo 1. Teste as condies necessrias e suficientes do problema abaixo.

min S(x) = x1 x2

sujeito a: g x x x1 12

22 25 0( ) d

2. Determine se as funes abaixo so cncavas, convexas, estritas ou no, ou nenhum destes casos ?

a) S(x) = 2 x1 + 3 x2 + 6

b) S(x) = 222121 232 xxxx

c) S(x) = 283 212231 xxxx

3. Verifique se as restries abaixo, definindo uma regio fechada, formam uma regio convexa.

g1(x) = 21x + x2 t 1 e g2(x) = x2 x1 d 2

NOTA: se todas as restries colocadas na forma gi(x) d 0 so funes convexas (ou na forma gi(x) t 0 so funes cncavas), ento elas formam uma regio convexa. Funes lineares so tanto convexas quanto cncavas.

4. Mostre que a funo S(x) = x1 x2 com x1 t 0 e x2 t 0 quasi-convexa. Ela tambm convexa ? Por qu ?

5. Mostre que a funo S(x) = 222121 35 xxxx com x1 > 0 e x2 > 0 pseudo-convexa. Ela tambm convexa ? Por qu ?


32

33.. OOttiimmiizzaaoo SSeemm RReessttrriioo

Na otimizao sem restrio o problema que est sendo resolvido :

min S xx n

( ) ou max S xx n

( )

como max S xx n

( ) equivalente a min S xx n

( ) , os mtodos descritos a seguir so para

problemas de minimizao. Os mtodos existentes para a soluo deste problema podem ser agrupados em duas categorias:

1) mtodos que no usam derivadas (mtodos de busca, mtodos diretos);

2) mtodos que usam derivadas (mtodos analticos, mtodos da mtrica varivel, mtodos indiretos).

Como regra geral, na soluo de problemas sem restrio, os mtodos que usam derivadas convergem mais rapidamente que os mtodos de busca. Por outro lado, os mtodos de busca no requerem regularidade e continuidade da funo objetivo e, principalmente o clculo de derivadas primeira ou segunda de S(x).

33..11 MMttooddooss ddee bbuussccaa mmoonnoovvaarriivveell ee mmuullttiivvaarriivveell Uma forma de avaliar os diferentes algoritmos de busca utilizando os seguintes critrios:

1) Nmero de problemas resolvidos

2) Nmero de clculos da funo objetivo em cada exemplo

3) Tempo computacional para a soluo de cada exemplo

4) Qualidade da soluo

Pode-se ento definir uma tabela de classificao, com ndices de 0 (pior) a 100 (melhor) usando os seguintes ndices:

N

j ji

ji T

TN 1 ,

*100T

N

j ji

ji S

SN 1 ,

*100F NNi

i 100 K *

1 ,

( )100( )

Nj

ij i j

dN d

H[ H

onde, para o i-simo algoritmo, Ti a sua eficcia, Fi a sua eficincia, Ki a sua robustez para resolver problemas, [i a qualidade da soluo obtida, Ti,j o seu tempo computacional para resolver o problema j, *jT o menor tempo entre os algoritmos

para resolver o problema j, Si,j o seu nmero de avaliaes da funo objetivo para


33

resolver o problema j, *jS o menor nmero de avaliaes entre os algoritmos para resolver o problema j, *jd a melhor qualidade da soluo para o problema j, di,j a

qualidade da soluo para o problema j definida como * *

, ,,

|| || | ( ) ( ) |i j j i j ji j

x S

x x S x S xd H H

, H a preciso da mquina, Hx a tolerncia na

varivel independente, HS a tolerncia na funo objetivo, *jx a soluo exata do problema j, Ni o seu nmero de problemas resolvidos e N o nmero total de problemas. Quando o i-simo algoritmo no consegue resolver o j-simo problema, ento Ti,j = f e Si,j = f.

33..11..11 MMttooddoo ddaa sseeoo uurreeaa

um mtodo de busca monovarivel, onde a cada iterao o intervalo de busca reduzido por um fator D, chamado de razo urea, obtido pela relao geomtrica abaixo (retngulo ureo) :

a bb

ba

ba

ba

2

1 0

D ba

1 52

0 618,

Outras escolhas do fator D levariam a mtodos similares, como por exemplo o mtodo da bisseo para D = 0,5. Contudo, a vantagem da razo urea est na reduo do nmero de clculos da funo objetivo, em funo da propriedade deste mtodo de conservar o retngulo ureo a cada iterao. Outro mtodo com caractersticas similares a seo urea a busca de Fibonacci.

algoritmo

1) Determinar o intervalo de busca [Lo, Uo] que contm o ponto de mnimo

2) Fazer k = 0 e calcular 'o = Uo Lo, x L S S xL L L

o o o o o D' , ( ) ,

x U S S xU U Uo o o o o D' , ( ) ,

3) Se S x S xUk

Lk( ) ( )! , ento L xk Uk+1 , x xUk Lk 1 , S SUk Lk 1

seno U xk Lk+1 , x xLk Uk 1 , S SLk Uk 1

b

a

a-b

b


34

4) Fazer (k m k + 1) e calcular 'k = Uk Lk, x L S S xL L L

k k k k k D' , ( ) se S x S xUk Lk( ) ( ) !1 1

ou x U S S xU U Uk k k k k D' , ( ) se S x S xUk Lk( ) ( ) 1 1

5) Se 'k > H (tolerncia), ento (ir para 3) seno FIM.

33..11..22 MMttooddoo ddaa aapprrooxxiimmaaoo ppoolliinnoommiiaall

Na verdade uma classe de mtodos de busca monovarivel, que aproxima a funo S(x) por uma interpolao polinomial, Pn-1(x):

11

( ) ( ) ( )n

n j jj

P x x S x

"

onde z

n

jkk kj

kj xx

xxx1 )(

)()(" so os interpoladores de Lagrange. Quando a derivada de

S(x) est disponvel, ento ela tambm usada na aproximao polinomial:

> @

n

jjjn xSxhxSxhxP

12112 )()()()()(

onde > @)()(21)()( 21 jjjj xxxxxh "" e )()()( 22 jj xxxxh " so os interpoladores de Hermite.

IInntteerrppoollaaoo qquuaaddrrttiiccaa oouu mmttooddoo ddee CCooggggiinnss ((oouu DDSSCC--PPoowweellll))

O mtodo de G.F. Coggins (1964) ou de Davies-Swann-Campey-Powell (1964) aproxima a funo S(x) por uma interpolao quadrtica, P2(x):

L U

S(xU)

S(xL)

S(x)

x xU xL

D' D'

L U

S(xL)

S(xU)

S(x)

x xL xU

D' D'


35

)())((

))(()(

))(())((

)())((

))(()( 3

2313

212

3212

311

3121

322 xSxxxx

xxxxxS

xxxxxxxx

xSxxxx

xxxxxP

calculando o mnimo desta funo quadrtica, isto , 02 dx

dP , tem-se:

)()()()()()()()()()()()(

21

321213132

322

212

21

231

23

22#

xSxxxSxxxSxxxSxxxSxxxSxx

x

algoritmo

1) Determinar o intervalo de busca [x1, x3]

2) Calcular S1 = S(x1) e S3 = S(x3)

3) Calcular x2 = 0,5 (x1 + x3) e S2 = S(x2)

4) Calcular 321213132

322

212

21

231

23

22#

)()()()()()(

21

SxxSxxSxxSxxSxxSxx

x e S# = S(x#)

5) Se |x# xi| < H para algum i = 1, 2, 3, ento FIM. 6) Se (x3 x#) (x# x2) > 0, ento k = 1 seno k = 3

7) Se S# < S2, ento xk m x2, Sk m S2 e k = 2 8) x4-k m x#, S4-k m S# e (ir para 4).

IInntteerrppoollaaoo ccbbiiccaa

Para a aproximao cbica so necessrias quatro informaes sobre a funo objetivo, ou seja, quatro valores da funo ou dois valores da funo e de sua derivada:

P2(x)S(x)

S(x#)

x2 x

x3 x#x1


36

4

13 )()()(

jjj xSxxP " ou > @

2

1213 )()()()()(

jjj xSxhxSxhxP

Escrevendo o polinmio na forma: P3(x) = a3 x3 + a2 x2 + a1 x1 + a0 , a condio necessria de primeira ordem para o mnimo:

dxxdP )(3 = 3 a3 x2 + 2 a2 x + a1 = 0

resulta no ponto 3

31222#

33

aaaaa

xr cujo sinal usado aquele que fornece um

valor positivo para a derivada segunda de P3(x), isto , 6 a3 x# + 2 a2 > 0. No caso de usar dois pontos tem-se as expresses:

)(2)()(

)(12

12

22

# xxwxSxS

zwxSxx

onde z = S(x1) + S(x2) 3 [S(x1) S(x2)] / (x1 x2) e w = [z2 S(x1) S(x2)]1/2

algoritmo

1) Determinar o intervalo de busca [x1, x2]

2) Calcular S1 = S(x1), S1 = S(x1) e S2 = S(x2), S2 = S(x2) 3) Calcular x#, S# = S(x#) e S# = S(x#) 4) Se |x# xi| < H para algum i = 1, 2, ento FIM. 5) Se S# S1 > 0, ento k = 1 seno k = 2

6) xk m x#, Sk m S# , Sk m S# e (ir para 3).

33..11..33 MMttooddoo ddee bbuussccaa sseecccciioonnaaddaa

um mtodo de busca multivarivel, mas em uma nica direo por vez, que utiliza os mtodos de busca univarivel em cada direo. As figuras abaixo ilustram a idia do mtodo na busca de um ponto de mnimo.


37

33..11..44 MMttooddoo ddee HHooookkee && JJeeeevveess

um mtodo de busca multivarivel dividido em duas fases (R. Hooke e T.A. Jeeves, 1962):

fase de explorao: estimar a direo provvel do extremo, a partir de um ponto inicial (ponto base).

fase de progresso: progredir na direo provvel do extremo enquanto o valor da funo objetivo for diminuindo.

algoritmo

Partida:

1) Determinar a regio de busca [Li, Ui], (i = 1,2,...,n)

2) Selecionar o ponto base inicial xio (i = 1,2,...,n)

3) Calcular o valor So = S(xo) da funo objetivo em xo

4) Selecionar os incrementos iniciais Gi e as respectivas tolerncias Hi (i = 1,2,...,n)

5) Tomar a primeira direo de busca (k = 1)

S(x)

S(x*)

x1 = dx1 = a

x1 = c x1 = b

x2 x2*

x2

9

10

12

15 17 x20

x1

G G2 G1 G1 G2

x10

x21 +

x21

x11 x11 +

explorao

x2 4

9

10

12

15 17 x20

x1

G

G

x10

x21+

x21

x11 x11 +

progresso


38

Fase de Explorao:

6) Calcular x xk k ko o G (sentido negativo)

7) Se xko estiver fora da regio de busca, ento insucesso em k- (ir para 10)

8) Calcular o valor de S S xo o ( )

9) Se S So o ! ento insucesso em k-

seno sucesso em k- e fazer x xk ko om e S So om (ir para 14) 10) Calcular x xk k ko o

G (sentido positivo) 11) Se xko

estiver fora da regio de busca, ento insucesso em k+ (ir para 14) 12) Calcular o valor de S S xo

+o ( )

13) Se S So o ! ento insucesso em k+

seno sucesso em k+ e fazer x xk ko om e S So om 14) Se j foram exploradas todas as direes (k = n) ento (ir para 15) seno tomar a direo seguinte (k m k + 1) e (ir para 6) 15) Se houve sucesso em alguma direo ento (ir para 17)

16) Se G Hi id i ento FIM. seno G Gi im / 2 i tal que G Hi i! (ir para 5)

Fase de Progresso: 17) Tomar x xi io i1 r G (e, opcionalmente, G Gi im 2 ) para todas as direes que

houve sucesso 18) Se x1 estiver fora da regio de busca, ento insucesso na progresso (ir para 16)

19) Calcular o valor de S S x1 1 ( ) 20) Se S S1 ! o ento insucesso na progresso (ir para 5) seno sucesso na progresso e fazer x xo m 1 e S So m 1 (ir para 17)

33..11..55 MMttooddoo ddee RRoosseennbbrroocckk

um mtodo de busca multivarivel parecido com a fase de explorao do mtodo de Hooke & Jeeves (H.H. Rosembrock, 1960). Entretanto, ao invs de continuamente explorar nas direes dos eixos coordenados, so construdas novas direes ortogonais, usando o procedimento de Gram-Schmidt, baseadas nos tamanhos dos passos das direes bem sucedidas.

Sejam kid n , i = 1,2, ..., n, vetores direo unitrios do k-simo estgio de busca e G ' iki a soma de todos os passos bem sucedidos (distncia percorrida) na i-sima direo durante o k-simo estgio de busca. Ordenando os valores das


39

distncias em ordem decrescente: knkk '!!'!' 21 , onde as ltimas m direes (se

existirem) possuem 0 'ki , i = (n m) + 1, ..., n, ento os novos vetores direo para o estgio de busca k + 1 so obtidos pelo seguinte processo de ortogonalizao:

'

n

ij

kj

kj

ki dA , 1 d i d n

k

kk

A

Ad1

111

ki

kik

iB

Bd 1 , > @

1

1

11)(i

j

kj

kj

Tki

ki

ki ddAAB 1 < i d (n m)

ki

ki dd 1 (n m) < i d n

algoritmo

1) Selecionar o ponto base inicial xo, fazer k = 0, e ii ed 0 (direo dos eixos)

2) Selecionar os incrementos iniciais Gi e as respectivas tolerncias Hi (i = 1,2,...,n)

3) Calcular S0 = S(xo) , escolher a direo m =1 e fazer 00 ' i (i = 1,2,...,n)

4) Fazer x1 = xo + Gm kmd e calcular S1 = S(x1)

5) Se S1 > S0 ento insucesso e fazer Gm m Gm / 2 seno sucesso e fazer xo m x1, S0 m S1 , mkmkm G'm' , Gm m 3 Gm

7) Se alguma direo ainda no teve insucesso, fazer m m (m < n ? m+1 : 1) (ir para 4)

7) Se G Hi id i ento FIM.

8) Calcular a nova direo ortogonal e fazer k m k + 1 (ir para 4).

33..11..66 MMttooddoo ddee PPoowweellll

um mtodo de busca multivarivel ao longo de direes conjugadas (C.S. Smith, 1962 e M.J.D. Powell, 1964). Duas direes d1 e d2 n so ditas conjugadas entre si, com respeito a uma matriz H, se:

Td1 H d2 = 0

A ortogonalidade um caso particular de conjugncia, onde H = I. Em geral, um conjunto de n direes linearmente independentes di n , i = 1,2,...,n, so conjugados com respeito a uma matriz positiva definida H nun se:


40

Tid H dj = 0 1 d i z j d n

Se H a matriz Hessiana de uma funo quadrtica, S(x), ento o mnimo alcanado aps n estgios de buscas unidirecionais exatas. Se os eixos coordenados so transladados e rotacionados por transformaes adequadas de modo que os eixos estejam nas direes dos vetores caractersticos de H e centralizados no ponto estacionrio de S(x), ento a conjugncia pode ser interpretada como ortogonalidade no espao transformado.

Para construir uma direo conjugada sem o uso das derivadas de S(x), pode-se partir de um ponto xo e obter o ponto xa que minimiza S(x) ao longo de uma direo d, como ilustra a figura abaixo. Ento, partindo de outro ponto x1 z xo e obtendo o ponto xb que minimiza S(x) ao longo da mesma direo d, o vetor (xb xa) conjugado ao vetor d, com respeito a matriz Hessiana, H, se S(x) uma funo quadrtica (para funes no lineares em geral, este conceito uma aproximao).

Para verificar esta conjugncia, basta representar S(x) em srie de Taylor em torno do ponto xo:

)()(21)()()()( oToooTo xxHxxxxxSxSxS

e minimiz-la ao longo da direo d: x = xo + D d, isto , obter D tal que:

dHdxSddHddxSd

dxdS ToTToTo D D DD )()(0)(

resultando em: dHd

dxST

oT )( D

Rescrevendo a funo S(x) na forma: S(x) = a + bT x + xT H x, tem-se:

S(x) = b + H x e S(xo) = b + H xo


41

que substitudo na equao dS/dD = 0, sabendo que D d = xa xo, resulta em: dT (b + H xo) + dT H (xa xo) = 0 o dT (b + H xa) = 0

e portanto: dT S(xa) = 0, isto , o gradiente da funo objetivo no mnimo da direo de busca ortogonal a esta direo. Fazendo a mesma anlise para o ponto x1, tem-se: dT S(xb) = dT (b + H xb) = 0. Subtraindo estes dois resultados chega-se a:

dT H (xb xa) = 0 que mostra que d conjugado a direo (xb xa) com respeito a matriz H. O mtodo de Powell uma implementao da busca em direes conjugadas, que pode ser sumarizado nos seguintes passos:

algoritmo

1) Selecionar um ponto inicial 00x , fazer estgio k = 0 e ii ed 0 (direo dos eixos)

2) A partir do ponto kx0 determine D1 via busca unidimensional na direo de kd1 e kx1 = kx0 + D1 kd1 . A partir do ponto kx1 , determinar D2 via busca unidimensional

na direo de kd2 e fazer kx2 = kx1 + D2 kd2 , e assim sucessivamente at determinar todos os Di, i = 1, 2, ..., n. A transio do ponto kx0 para o ponto kmx equivalente a:

D

m

i

kii

kkm dxx

10 , m = 1, 2, ..., n

3) Calcular knx 1 = 2 knx kx0 , isto , fazer um passo adicional de tamanho ( knx kx0 ) na direo resultante das n buscas unidimensionais. Este passo procura

garantir que duas direes de busca no se tornem colineares quando algum Di = 0.

4) Calcular )]()([max 1,...,1

ki

ki

nik xSxS ' . A direo de busca relativa a esta variao

mxima ser designada por kmd . Definindo S1 = S( kx0 ), S2 = S( knx ) e S3 = S( knx 1 ), Se S3 t S1 e/ou (S1 2 S2 + S3) (S1 S2 'k)2 t 'k (S1 S3)2, ento usar as mesmas direes do estgio k, isto , kiki dd 1 , i = 1, 2, ..., n e iniciar o prximo estgio a partir do ponto knk xx 10 (ou knx 1 se S2 > S3).

5) Seno usar as direes [ 11 kd 12 kd ... 1knd ] = [ kd1 kd2 ... kmd 1 kmd 1 ... knd kd ], onde a direo kmd (de mxima variao) eliminada e a nova direo resultante,

kd , (de kx0 para knx ) includa em ltimo lugar, com o correspondente valor de D obtido via minimizao nesta direo e 10kx = knx + D kd .


42

6) Se Hd kkn xx 0 ento FIM

7) Fazer k m k + 1(ir para 2).

33..11..77 MMttooddoo ddee bbuussccaa ddee lliimmiitteess

A maioria dos mtodos de busca necessitam da definio do intervalo de busca, que contm o ponto extremo, para garantirem a determinao do timo. Segue abaixo um algoritmo de busca para a determinao de um intervalo [xo, x1] que contm um ponto de mnimo.

algoritmo

1) Escolher um ponto inicial, xo, e um passo inicial, D 2) Calcular So = S(xo), k = 0

3) Calcular x1 = xo + D e S1 = S(x1) 4) Se So d S1, ento D m D, k m k + 1 e (ir para 7) 5) So m S1, D m 2 D, x1 = xo + D e S1 = S(x1) 6) Se So > S1, ento (ir para 5)

seno k = 1 (ir para 8)

7) Se k < 2, ento (ir para 3)

8) xo m xo + D (k - 1), I = [xo, x1], FIM.

33..11..88 MMttooddoo ddooss ppoolliieeddrrooss fflleexxvveeiiss

um mtodo de busca multivarivel (J.A. Nelder e R. Mead, 1964), onde o pior vrtice de um poliedro com n + 1 vrtices substitudo por um novo vrtice colinear com o vrtice antigo e o centride, como ilustra a figura abaixo.

6

78

9 1011

12

1 4

5

X2

X1

23

13


43

As coordenadas do centride so dadas por:

xn

x x j nj i j h ji

n

01

11 1 2, , , , ,

onde xh,j o pior vrtice.

O algoritmo envolve quatro operaes de busca, que para o caso da minimizao da funo objetivo tm as seguintes formas:

1) Reflexo: ^ `x x x x

onde S x max S x S xRk k k

hk

hk k

nk

!

0 0

1 1

0D D( ) ,( ) ( ), , ( )

2) Expanso:

^ `1 10 0

1

1

( ) ( ) min ( ), , ( ) ,

( ) , 1

( ) ( ),

sen1 ( 1)

d J J !

" k k k kR n

k k k kE R

k k k kE R h E

k kh R

Se S x S x S x S x

ento x x x xSe S x S x ento x x

o x xk k ir para

onde x k" o melhor vrtice.

3) Contrao: 0 0

1

( ) ( ) , ( )

, 0 11 ( 1)

! z E E

k k k k k kR i C h

k kh C

Se S x S x i h ento x x x xx xk k ir para

4) Reduo:

Se S x S x ento x x x x

i nk k ir para

Rk

hk

ik k

ik k( ) ( ), ( )

, , ,( )

!

1 12

1 2 11 1

" "

O critrio usado por Nelder e Mead para terminar a busca o seguinte:

> @1 1 02

1

112

nS x S xi

k k

i

n

d

( ) ( ) H .


44

33..11..99 MMttooddooss ddee bbuussccaa aalleeaattrriiaa

So os mtodos de busca menos elegantes e eficientes (menores valores para F) de todas as tcnicas de busca, mas so mais robustos para problemas multimodais e atrativos para computao paralela (multiprocessamento).

MMttooddoo ccoommpplleexx

similar ao mtodo dos poliedros flexveis, sem a restrio de usar somente n+1 vrtices (M. J. Box, 1965). A partir de um ponto inicial, x1, outros p1 pontos so obtidos aleatoriamente:

xi = L + \i [U - L] , i = 2, 3, ..., p onde L e U so vetores que limitam a regio de busca e \i uma matriz diagonal de nmeros aleatrios, distribudos uniformemente no intervalo [0,1]. A busca procede de forma anloga ao mtodo dos poliedros flexveis. Recomenda-se, em geral, usar p = 2 n.

BBuussccaa aalleeaattrriiaa rreeppeettiittiivvaa

uma busca completamente aleatria (R.J. Kelly e R.F. Wheeling, 1962), onde um caminho aleatrio construdo na seqncia dos passos em busca do timo, atravs da seguinte relao:

EED k

k

k

kkk r

ddxx )1(1 , k = 1,2,...

onde Dk o passo, que ampliado aps uma direo bem sucedida e reduzido caso contrrio, E um coeficiente ajustvel durante a busca (grau de aleatoriedade das direes), rk n um vetor unitrio gerado aleatoriamente, dk n um vetor da histria da busca (uma direo mdia dos passos anteriores), obtido por:

dk+1 = J dk + (1 J) (xk+1 xk) /k onde J [0, 1] o fator de esquecimento das direes e /k n+n uma matriz diagonal de fatores de escala para as variveis x. A figura abaixo ilustra um caminho tpico de uma busca aleatria.


45

DDiirreeeess aalleeaattrriiaass

uma tcnica onde as direes de busca so aleatrias, geradas a partir de um raio de busca uniforme, isto , os pontos aleatrios em cada estgio esto localizados sobre a superfcie de uma hiperesfera com centro no ponto xk. Uma busca em linha realizada na direo que passa pelo ponto xk e pelo melhor ponto da hiperesfera. A figura abaixo mostra que quanto maior o raio da hiperesfera (limitado pela posio do ponto timo), maior a probabilidade do melhor ponto cair dentro do cone de direes melhores que a direo do gradiente no ponto xk. Para atender os critrios de convergncia, o raio de busca deve ser periodicamente reduzido. A busca pode ser acelerada se os pontos aleatrios forem restritos a um ngulo mnimo entre eles e a direo do estgio anterior.


46

BBuussccaa aalleeaattrriiaa aaddaappttaattiivvaa

mtodo de otimizao global, baseado em uma busca aleatria memorizada, com distribuio assimtrica e reduo sistemtica da hiperelipse de amostragem (A.R. Secchi e C.A. Perlingeiro, 1989), onde os pontos so selecionados da seguinte forma:

> @G \G )1(1

iiiik

iki AB

Rxx , i = 1, 2, ..., n , k = 1, 2, ...

onde xk n o melhor ponto da ltima amostragem, \ um vetor de nmeros aleatrios (0, 1), R o vetor dos eixos da hiperelipse, G o parmetro de forma da distribuio das amostras (G = 1, 3, 5, ..., sendo que para G = 1 tem-se uma distribuio uniforme), A o vetor de assimetria da distribuio (Ai = 2 distribuio simtrica), B o vetor de direo da assimetria (Bi = 1 assimetria positiva, no sentido de aumento de xi, e Bi = 1 assimetria negativa). Aps a amostragem, se estiver na etapa de explorao, um nmero determinado de pontos so armazenados para uso posterior, quando a busca na direo do melhor ponto for encerrada. As etapas principais do algoritmo de busca so as seguintes:

1) Amostragem de pontos aleatrios em torno de xk, usando a equao acima;

2) Ordenao das amostras baseado no valor da funo objetivo;

3) Memorizao das amostras, isto , armazenar os melhores pontos, exceto o melhor de todos, durante a fase de explorao (G = 1);

4) Anlise do melhor ponto: verificar os critrios de convergncia;

5) Checar validade de um novo ponto timo encontrado: anlise de redundncia de pontos, baseado em uma mtrica;

6) Resgate de um ponto da memria;

7) Eliminao pelos timos: verificar a tendncia da busca;

8) Ajustar direo e critrios de amostragem: alterao dos parmetros de busca (A, B, G);

9) Anlise dos critrios de parada: nmero mximo de avaliaes e timos;

10) Ordenao dos timos.

A figura abaixo ilustra a caracterstica de memorizao de pontos amostrados, que so utilizados como novos pontos de partida quando a busca em uma determinada direo terminada. O encerramento da busca em uma direo pode ocorrer devido a localizao de um ponto timo local ou pela anlise de redundncia dos pontos.


47

-5 -4 -3 -2 -1 0 1 2 3 4 5-5

-4

-3

-2

-1

0

1

2

3

4

5s tart pointoptim um

AAllggoorriittmmoo ggeennttiiccoo

A idia dos algoritmos genticos (GA), J. Holland (1975), est baseada no processo evolutivo dos organismos biolgicos da natureza (princpios da seleo natural e da sobrevivncia do mais adaptado). Os indivduos que tm mais sucesso para se adaptar ao meio ambiente tero mais chance de sobreviver e reproduzir, enquanto que os menos ajustados sero eliminados. Isto significa que os genes dos indivduos mais adaptados sero disseminados em um nmero crescente de indivduos nas prximas geraes. A combinao de caractersticas de ancestrais bem ajustados pode produzir indivduos que so bem mais adaptados que os pais. Os GAs procuram simular este processo natural pela aplicao de operadores genticos sobre uma populao inicial e suas prximas geraes. Cada indivduo da populao codificado em um cromossomo (string), que representa uma soluo possvel para o problema. A adaptao de um indivduo avaliada pelo valor da funo objetivo. Indivduos altamente ajustado so permitidos a se reproduzirem pela troca de parte de sua informao gentica (em um procedimento de cruzamento) com outro indivduo altamente ajustado, produzindo filhos (offsprings) com caractersticas de ambos os pais. Mutaes so freqentemente permitidas pela alterao de alguns genes dos cromossomos. Os filhos podem substituir toda a gerao anterior (tcnica das geraes), ou substituir apenas os indivduos menos ajustados (tcnica do estado estacionrio). Os passos bsicos de um algoritmo gentico so os seguintes:


48

1) Gerar aleatoriamente uma populao inicial e avaliar a adaptao de cada indivduo;

2) Selecionar os pais de uma populao, cruz-los para produzirem os filhos e avaliar a adaptao dos filhos;

3) Substituir alguns ou todos os indivduos da populao pelos filhos;

4) Se o critrio de convergncia no foi satisfeito ir para o passo (2);

5) FIM.

O procedimento de cruzamento (operao gentica) consiste em gerar aleatoriamente um ou mais pontos de cruzamento e, ento trocar os segmentos dos cromossomos dos dois pais para produzir dois filhos.

A mutao aplicada a um filho aps um certo nmero de cruzamentos, pela substituio de um gene do cromossomo por um valor aleatrio (ou inverso de bit no caso de cromossomos binrios). A mutao ajuda resguardar a possvel perda de informao gentica valiosa devido a uma convergncia prematura, expandindo o espao de busca.

SSiimmuullaatteedd aannnneeaalliinngg

uma tcnica de busca direta com relaxao estocstica (S. Kirkpatrick, C. Gelatt Jr. e M. Vecchi, 1983), baseada no processo de recozimento de slidos (onde um slido aquecido a altas temperaturas e gradualmente resfriado para permitir a sua cristalizao). Como o processo de aquecimento permite que os tomos se movimentem aleatoriamente, se o resfriamento no realizado muito rapidamente, ento os tomos tero tempo suficiente para se alinharem de modo a atingir um estado de mnima energia. Usando esta analogia, o estado do slido corresponde a uma soluo vivel e a energia de cada estado corresponde ao valor da funo objetivo. Neste procedimento, a busca permitida a prosseguir mesmo se o movimento causar um aumento na funo objetivo, atravs do uso de um parmetro chamado temperatura (T), onde o movimento aceito com uma probabilidade de exp('/T), com ' = S(xk+1) S(xk). O valor de T (0,f) controlado pelo processo de resfriamento, sendo que valores baixos resultam em um algoritmo de busca local, ao passo que valores altos reduzem a velocidade de convergncia. Os passos bsicos de um algoritmo simulated annealing (SA) so os seguintes:

1) Escolher um ponto inicial, xo n, e os parmetros D e E 2) Calcular So = S(xo), T = To, Tf = D To, N = E n O, r = 0, c = 0, k = 0


49

3) Fazer N vezes:

Mudar de direo O componentes de xk e gerar aleatoriamente um vizinho, x Calcular ' = S(x) S(xk) Se ' < 0 ou exp('/Tk) > Y, ento xk m x e c = 0, seno r m r + 1

4) Se r = N, ento c m c + 1 5) Atualizar Tk, r = 0, k m k + 1 6) Se o processo no estiver congelado (T > Tf ou c d Cmax), ento ir para (3) 7) FIM.

onde D um parmetro que define o nvel de temperatura (Tf) que o algoritmo deve terminar, E um parmetro utilizado para definir o nmero de iteraes (N) em cada nvel de temperatura, To a temperatura inicial, r o nmero de rejeies, O nmero de mudanas de direo, Y [0,1] uma varivel aleatria uniforme e Cmax o nmero de mximo de nveis consecutivos de temperatura sem progresso (isto , rejeio total). O clculo de To e a atualizao de Tk podem ser feitos de diversas maneiras, tal como (Aarts et al., 1988):

1

12

2)1(

ln

KK'

mmmTo e

k

k

kk T

TT

VG

3

)1ln(1

1

onde aps um nmero m de tentativas iniciais, m1 e m2 so os nmeros de movimentos com ' d 0 e ' > 0, respectivamente, ' o valor mdio dos ' > 0, K (0, 1) a taxa de aceitao inicial (| 0,95), Vk o desvio padro da funo objetivo durante a busca em Tk e G a mxima mudana relativa permitida para a probabilidade de aceitao dos estados (| 0,1).

PPSSOO

O Particle Swarm Optimization (PSO) um algoritmo que tem como fundamento o comportamento de organismos sociais tais como uma revoada de pssaros ou um cardumes de peixes, onde cada indivduo da populao (partcula) modifica sua posio com o tempo (gerao). A posio modificada de acordo com a experincia do indivduo e a dos demais componentes da populao, valendo-se de sua melhor posio e a melhor posio do conjunto.


50

SSiisstteemmaass FFrrmmiiccooss

Um Sistema Frmico (ou Ant System) um algoritmo baseado em agentes que emulam o comportamento natural de formigas e desenvolvem mecanismos de cooperao e aprendizado. O Ant System foi proposto como uma nova heurstica para otimizao combinatorial. Ele composto de um conjunto de formigas artificiais que cooperam entre si para resolver um problema atravs de troca de informaes via feromnio que depositado nas arestas de um grafo. As formigas passeiam pelo grafo construindo uma soluo para o problema. Aps cada soluo ser gerada, as formigas atualizam a intensidade de feromnio na arestas que fazem parte de sua soluo como uma funo da qualidade da soluo encontrada por aquelas formigas. Alm disso, parte do feromnio evapora a cada passo, diminuindo a intensidade de trilhas que no so seguidas. O feromnio depositado nas arestas desempenha o papel de memria distribuda atravs da qual as formigas reforam as solues progressivamente melhores. Ao mesmo tempo, a escolha probabilstica de cada passo da soluo evita a converso prematura para um timo local.

BBuussccaa ttaabbuu

um procedimento para levar mtodos de busca local para fora da regio de atrao de um timo local (meta-estratgia ou meta-heursticas), pela incorporao de funes de memria flexvel para proibir movimentos que levam a caractersticas (ou atributos, ou estado das variveis) de solues passadas (F. Glover, 1986). Os atributos que no so permitidos a serem retomados so chamados de tabu e so mantidos em uma memria de curta durao (lista de tabus).

Para maiores detalhes deste procedimento e dos dois mtodos anteriores, sugere-se a leitura de Hasan et al. (2000) e suas referncias.


51

33..22 MMttooddooss aannaallttiiccooss ((mmttrriiccaa vvaarriivveell)) Apesar da literatura referenciar somente os mtodos quasi-Newton, que utilizam aproximaes para o clculo da matriz Hessiana (tambm conhecidos como mtodos da secante), como mtodos da mtrica varivel, nestas notas o termo mtrica varivel engloba todos os mtodos que utilizam a primeira e/ou a segunda derivada da funo objetivo. Estes mtodos tm como equao bsica para o processo iterativo: xk+1 = xk Dk W(xk) S(xk) (3.1)

onde Dk o tamanho do passo, dk = W(xk) S(xk) o vetor direo e W(xk) a matriz direo (inversa da matriz Hessiana ou aproximao desta)

Em qualquer mtodo de otimizao, uma boa direo de busca deve reduzir (para o caso da minimizao) o valor da funo objetivo, isto , S(xk+1) < S(xk). Tal direo, dk, satisfaz o seguinte critrio em cada ponto:

TS(xk) dk < 0 ou em outras palavras, o ngulo (T) formado entre os vetores S(xk) e dk deve ser sempre maior que 90, ou seja:

TS(xk) dk = |TS(xk)| |dk| cos T < 0 T > 90

Como a otimizao sem restries equivalente a encontrar a soluo do sistema de equaes no-lineares F(x) = S(x) = 0, pode-se utilizar todos os mtodos disponveis para a soluo de F(x) = 0. Por exemplo, na utilizao do mtodo de Newton-Raphson, a matriz Jacobiana a prpria matriz Hessiana.


52

A seguir sero descritos os mtodos mais conhecidos desta classe, seguidos de uma generalizao dos mtodos da mtrica varivel.

33..22..11 MMttooddooss ggrraaddiieenntteess

Utilizam somente a primeira derivada da funo objetivo, caso em que W(xk) = I:

xk+1 = xk Dk S(xk)

Quando Dk escolhido de modo a minimizar: gk(D) = S(xk D S(xk)) , D > 0 (3.2) tem-se o mtodo da maior descida (steepest descent), cujo algoritmo bsico pode ser escrito da seguinte forma.

algoritmo

1) Escolher um ponto inicial xo, k = 0

2) Calcular dk = S(xk) 3) Encontrar Dk tal que S(xk + Dk dk) = minD ! 0 gk(D) = S(x

k + D dk)

4) Calcular xk+1 = xk + Dk dk 5) Se o critrio de convergncia no foi satisfeito, ento k m k + 1 (ir para 2) 6) FIM.


53

0.005 0.01 0.015 0.02 0.025 0.03

0.005

0.01

0.015

0.02

X1

X2

A minimizao de gk(D), conhecida como funo de mrito, tambm chamada de busca em linha (linesearch), pode ser realizada com o uso de qualquer mtodo de minimizao univarivel. Para ilustrar esta funo, a figura abaixo mostra a funo g2(D) do problema acima:

Aproximando S(x) por uma funo quadrtica:

S x S x S x x x x x H x x xk k T k k k k k T k k k( ) ( ) ( ) ( ) ( ) ( ) ( ) | 1 1 1 112

ou de forma similar:

kkTkkkTkkkk dxHddxSxSdxSg )()(2

1)()()()( 2DD|D D

que minimizando em relao a D, dgd

k

D 0 , resulta:

kkTkkTk

kkTk

kkT

kdxHd

dddxHd

dxS)()(

)()()(

)(* D D (3.3)

xo

g1(D)

g2(D)

g2(D)

D D2

L(x1,x2)


54

Contudo, a equao (3.3) no utilizada para o clculo de D nos mtodos gradientes, pois exigiria o clculo da segunda derivada da funo objetivo. Neste caso, utiliza-se, em geral, mtodos de busca para a sua seleo.

33..22..22 MMttooddoo ddee NNeewwttoonn

Faz uso da segunda derivada da funo objetivo, caso em que W(xk) = [H(xk)]-1:

xk+1 = xk Dk [H(xk)]-1 S(xk)

que resultado da minimizao da aproximao de S(x) por uma funo quadrtica:

S x S x S x x x H x xk T k k k T k k( ) ( ) ( ) ( ) ( )| ' ' '12

(3.4)

onde 'xk = x - xk, na direo 'xk, isto : ww'

Sxi

k 0

'xk = [H(xk)]-1 S(xk)

Neste caso Dk ou um parmetro de relaxao do processo iterativo 0 < Dk d 1, ou um fator de correo da inversa da matriz Hessiana, caso esta no seja atualizada em todas as iteraes. A positividade da matriz Hessiana deve estar sempre garantida para evitar a migrao para um ponto sela. E, para assegurar a convergncia do mtodo de Newton, a correo 'xk deve ser tal que S(xk+1) < S(xk). Uma maneira de assegurar a positividade da m

Documents

Otimiza