o MrTODO DE DIREÇOES VIÃVEIS EM DUAS ETAPAS PARA

PROGRAMAÇÃO NÃO-LINEAR E APLICAÇÕES Ã

PROGRAMAÇÃO QUADRÃTICA

Lu{s Alfredo Vidal de Carvalho

TESE SUBMETIDA AO CORPO DOCENTE DA COORDENAÇÃO DOS PROGRAMAS DE PÕS-GRADUAÇÃO DE ENGENHARIA DA UNIVERSIDADE FEDERAL DO RIO DE JANEIRO COMO PARTE DOS REQUISITOS NECESSÃRIOS PARA A OBTENÇÃO DO GRAU DE MESTRE EM CIENCIAS (M. Se.) EM ENGENHARIA MECÃNICA

Aprovada por:

os~ Herskovits Norman (Presidente)

João Lauro D. Facõ

RIO DE JANEIRO, RJ - BRASIL DEZEMBRO DE 1984

i i

CARVALHO DE, LUiS ALFREDO VIDAL O Metodo de Direções Viãveis em Duas Etapas para Programação

Não-Linear e Aplicações ã Programação Quadrãtica (Rio de Janei­ro) 1984.

xi., .. 119 p. 29,7 cm (COPPE/UFRJ, M. Se., Engenharia Mecâni ca, 1984)

Tese - Universidade Federal do Rio de Janeiro. COPPE l.

I. COPPE/UFRJ II. Titulo (Serie)

i i i

AGRADECIMENTOS

Agradeço ao Professor Jose Herskovits Norman pela amiza

de e orientação const<1nte.

Ao Professor Jules Slama por seu apoio e incentivo.

Ao Programa de Engenharia Mecânica, na pessoa de seu

Coordenador Luis Carlos Martins, pelo auxilio nunca negado.

i V

A meus pais.

V

RESUMO DA TESE APRESENTADA A COPPE/UFRJ COMO PARTE DOS REQUISI-TOS NECESSÃRIOS PARA A OBTENÇÃO DO GRAU DE MESTRE EM {M. Se.)

o MrTODO DE DIREÇÕES VIÃVEIS EM DUAS ETAPAS PARA

PROGRAMAÇÃO NÃO-LINEAR E APLICAÇÕES A

PROGRAMAÇÃO QUADRÃTICA

Lu{s Alfredo Vidal de Carvalho

DEZEMBRO DE 1984

ORIENTADOR: José Herskovits Norman PROGRAMA: Engenharia Mecãnica

CIÊNCIAS

Este trabalho apresenta um estudo e implementação com­

putacional do algoritmo de direções viãveis em duas etapas para

programação não-linear restrita. Também propoe um .. novo proc!

dimento de programação quadrãtica, de convergencia assintõt±ca,

baseado nas mesmas ideias. Como consequéncia da implementação do

algoritmo não-linear e desenvolvido um método de busca-linear

com restrições. Técnicas para acelerar a convergéncia, bem corno

aumentar a estabilidade do algoritmo quadrãtico são desenvolvi­

das, e testadas através de problemas da literatura. Para ambos

os métodos diversas versoes com velocidades de conver,,-

gençia, diferentes sao apresentadas. Em particular, a exten­

são dos ffiitodos quasi-Newton a problemas restritos permite· a

obtenção de convergéncia superlinear.

vi

ABSTRACT UF THESIS PRESENTED TO COPPE/UFRJ AS PARTIAL FULFILL-MENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER O~ (M. Se.)

SCIENCE

THE TWO-STAGES FEASIBLE DIRECTIONS METHOD FOR NONLINEAR

PROGRAHMING ANO APPLICATIONS TO QUADRATlC PROGRAMMING

CHAIRMAN:

Luls Alfredo Vidal de Carvalho

DEZEMB~O DE 1984

Jos~ Herskovits Norman DEPARTMENT: Mechanical Engineering

This work presents the computational implementation of

the two-steps feasible directions algorithm for non-linear cons

trained optimization. It' s stated an assimptotic convergence me­

thod for quadratic programming, based on the sarne ideas. As a

consequence of the computational implementation, a constrained

line-search·procedure is developed. To avoid ili-conditionning and

accelerate the convergence rate, new techniques are

and tested by means of classical problems. For both

developed

methods,

many versions that have different convergence rates are pre­

sented. Versions w~ich use quasi-Newton techniques have super­

linear convergence rate.

Vi i

LISTA DE S1M80LOS

l) f(x) Função objetivo

2) gi (x) - Restrição i-êsima

3) L(X, A) Lagrangeano do problema

4) V Gradiente de uma função

5) A Vetor de multiplicadores de Lagrange

6) d Vetor direção

7) íl Conjunto de soluções viãveis

8) d(x) Campo vetorial de direçõe.s viãveis

9) t passo da busca-linear

10) T(x) Sub-espaço tangente as restrições

11) H(X, A) Matriz h.essiana do Lagrangeano

l 2 ) BK Sequência de matrizes simétricas positivas-definidas

l 3 ) K r Sequência de -~etores,,., l .. ~- , ...

l 4 ) K y Sequência de escalares no intervalo (O, l)

15) p Escalar sempre positivo

16) a Escalar no intervalo (O, 1)

l 7 ) do Direção de descida inicial

18 )_ À o vetor de multiplicadores de Lagrange inicial

Vi i i

l 9) A Matriz contendo os gradientes das restrições

20) R Matriz diagonal contendo o vetor rK

21 ) G Matriz diagonal contendo as restrições

22) ec Função objetivo do problema auxiliar

23) e. l

Escalar positivo

24) Í', Conjunto de soluções viãveis extendido

25) h (t l Função objetivo na direção de descida

26) Gi ( t) Restrição na direção de descida

27) m Escalar auxiliar ao teste de função

28) m' Escalar auxiliar ao teste de derivada

29) 13 Escalar auxiliar ao teste de banda

30) to Passo inicial do procedimento de busca-linear

31 )_ TL Ponto base para interpolação

32) TH Ponto base para interpolação

33) TA Ponto base para interpolação

34) TG Resultado da interpola~ão das restrições

35) TF Resultado da interpolação da função-objetivo

36) N Dimensão do problema

37) NF Numero de restrições do problema

i X

38) NG Numero de avaliaçõe.s das restrições

39) NDF - Numero de avaliações do gradiente da função objetivo

40) NDG - Numero de avaliações do gradiente das restrições

41 ) FV Valor da função objetivo

42) Q Hesstana da função objetivo quadritica

43) e Vetor de coeficientes da função quadritica

44) L(t) Lagrangeano na direção de descida

45) tl Passo para minimizar o Lagrangeano

46) t. l

Passo miximo para nao violar uma restrição

47) HK Matriz que aproxima a hessiana inversa

48) ge Vetor contendo as restrições de igualdade

49) W (x) Indtce auxiliar na atualização de parâmetros

X

ÍNDICE

CAPTTULO I - O ALGORITMO DE DIKEÇUES VIÃVEIS EM DUAS ETA­

PAS PARA PROGRAMAÇÃO 'NÃO~LINEAR COM RESTRI-

~ ....................................... .

I.1 - Introdução ........................................ .

I.2 - Definições e Nomenclatura.......................... 5

I.3 - Estudo do Algoritmo de Direções Viãveis em Duas Et~

pas para Otimização Não-Linear com Restrições...... 7

I.4 - Anãlise do Algoritmo............................... 13

I.5 - Versões do Algoritmo............................... 16

I,6 - Extensão do Algoritmo para Restrições de Igualdade. 19

CAPTTULO II - DESENVOLVIMENTO DE UM ALGORITMO DE BUSCA-

LINEAR COM RESTRIÇOES...................... 24

II.1 - Introdução........................................ 23

II.2 - Características de um Algoritmo de Busca-Linear... 25

II.3 - Criterio de Aceitação............................. 28

II.4 - FÕrmula Iterativa Convergente..................... 31

II.5 - Desenvolvimento LÕgico do Algoritmo de Busca-Li-

near.............................................. 34

II.6 - Procedimento para Cãlculo do Passo Inicial........ 37

Il.7 - Implementação do Algoritmo de Direções Viãveis

Versão I ..... ·.· •........ , ............ , .•....... ,... 38

xi

II.8 - Implementação do Algoritmo de Direções Viãveis

Versão II......................................... 44 II. 9 - Resulta dos Numeri cos.............................. 45

II.10-·Conclusões ........................................ 48

CAPITULO III - DESENVOLVIMENTO DE UM ALGORITMO DE DIRE-

ÇÕES VIÃVEIS PARA PROGRAMAÇAO QUADRÃTICA... 67

III. l - Introduçao........................................ 67

III.2 - Desenvolvimento de um Algoritmo de Direções Viã-

veis para Programação Quadrãtica................. 69

III.3 - Estabelecimento do Algoritmo Bãsico.............. 77

III.4 - Extensão do Algoritmo para Restrições de Igualda-

d e • . • . . . . . . . . . . . . . • . . • • • • . . . . • • • • • • • • • . . . . . . . . • • . 7 g

CAPITULO IV - ESTUDO NUMtRICO DO ALGORITMO DE !,: DI REÇõES

VIAVEIS, PARA PROGRAMAÇAO QUADRÃTICA....... 86

IV.l - Introduçao........................................ 86

IV.2 - Atualização do Parâmetro Gama (yJ................. 91

IV.3 - Atualização dos Parâmetros r.. ... ......... .•...... 101 . . l

IV.4 - Estudo Comparativo Entre as Versões............... 106

IV.5 - Redução do Esforço Computacional.................. 110

IV.6 - Conclusão......................................... 113

APÊNDICE . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .. . . . . . . . . . . . . . 114

REFERÊNCIAS BI.BLIOGR/\FICAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

CAPITULO I

O ALGORITMO DE DIREÇOES VIAVEIS EM DUAS ETAPAS

PARA PROGRAMAÇAO NAO-LINEAR COM RESTRIÇÕES

I.l - INTRODUÇAO

Podemos, de modo geral, dizer que engenharia e a ativi

dade atravês da qual projetos de produtos óu soluções sao gera­

dos. Em muitas questões, a engenharia se limita a determinar so

luções que satisfaçam ãs exigências do projeto. As novas neces­

sidades tecnolÕgicas e humanas, assim como considerações de ar-

dem econômica mostram que este tipo de soluções não são sufi-

cientes. Torna-se necessãrio não sõ determinar uma solução que

satisfaça ao projeto mas tambêm detectar a melhor delas segundo

algum critêrio, a chamada solução Õtima.

A busca da solução Õtima, ou otimização, ê feita atra­

ves de mêtodos especificas tratados em uma ciência, chamada Pro

gramação Matemãtica, que ainda não evoluiu a ponto de apresen­

tar uma metodologia para resolução eficiente de todos os probl!

mas passiveis. Desta forma, existem um sem numero de algoritmos

de otimização que são útilizados em função de sua maior adapta­

ção ao problema tratado.

De maneira geral, os problemas de otimização, sejam

eles econômicos, estatisticos ou de engenharia, podem ser repr!

sentados atravês de funções matemãticas que ditam as exigências

2

do modelo ou projeto, chamadas restrições, e uma função que de­

termina o critério segundo o qual a melhor solução serã avalia­

da, chamada função objetivo. De acordo com as restrições e fun-

çao objetivo, podemos classificar os problemas como lineares,

quadrãticos ou não-lineares existindo

mêtodos especif·1,:os a cada caso.

naturalmente classes de

Neste trabalho nos propomos a desenvolver idéias no

campo da otimização não-linear restrita. Definimos o

geral de programação não-linear, como:

minimizar f (X) ; X E lR n

sujeito a g i (X) < o. '

i l ... ' m

g i (X) = o.; i = m+l ... ' m+p

onde a função objetivo f(x) e as restrições gi(x) sao

problema

( L 1)

funções

não-lineares com dominio no lRn ~ chamamos x de vetor das variã­

veis de projeto.

Em se tratando de projeto Õtimo de uma estrutura metã-

lica, por exemplo, o objetivo poderã ser minimizar o peso da

mesma enquanto as restrições serão limitações nas tensões e

d~formações, sendo o problema não-linear.

Em projeto de componentes mecânicos podemos ter como

objetivo a minimização da concentração de tensões, sendo a for··

ma a variãvel de projeto que deverã obedecer ã r~strições geom!

tricas.

3

Em projeto de mecanismos articulados podemos minimizar

o comprimento dos componentes, respeitando o curso e o ângulo

mãximo dos atuadores, sendo também um problema não linear. En­

fim, a programação não-linear apresenta uma infinidade de apli­

caçoes prãticas que dependem, apenas, do conhecimento do proje­

tista nesta ârea da matemãtica.

Considerãvel esforço tem sido empreendido por pesquis!

dores no desenvolvimento de algoritmos que possam resolver, de

forma eficiente, o problema (I.l}. A maioria dos processos se

utiliza de principios de otimização sem restrições, como gra-

diente conjugado, método de Newton, método do gradiente e técni

cas de métrica variãvel. Algoritmos que usam funções de penali­

dades transformam o problema restrito em uma sequência de mini­

mizãções sem restrições que, porem, pode ser mal condicionada

119 1. Em se tratando de restrições de igualdade, a ideia dos me

todos do gradiente projetado e gradiente reduzido ê projetar a

direção de descida sobre o plano tangente as restrições, neces­

sitando todavia de recursos de manutenção da viabilidade. Se as

restrições ativas no Õtimo fossem conhecidas a priori, teriamas

transformado um problema de desigualdades em igualdade. Os me­

todos de estratégia de conjunto ativo realizam hipõteses com o

objetivo de identificar o referido conjunto. Em problemas cóm

um grande numero de restrições estes métodos são de dificil con

vergência.

Uma importante familia de métodos sao os de direções

viãveis.que, partindo de um ponto inicial viãvel, geram uma se-

4

quência de configurações, tambêm viãveis, que converge ao ponto

Õtimo [ 20]. Esta caracterlstica ê interessante em engenharia

pois a qualquer ponto do processo de otimização tem-se um proj~

to tecnicamente posslvel. O mêtodo dos centros de HUARD, em ca­

da iteração, define como ponto seguinte o ''centro'' da região

determinada pelas restrições e fechada pela curva de ntvel da

função objetivo. Foi desenvolvida uma linearização deste mêtodo

que requer, a cada iteração, a resolução de um problema de pro­

gramação linear. Outros metadas como ZOUTENDIJK e POLAK [ 2 º]

podem ser considerados como aperfeiçoamento do métodd

HAURD.

A presente tese baseia-se no mêtodo de direções viã-

veis em duas etapas 116

1 que determina a direção de descida

atravês da resolução de dois sistemas lineares e, devido ã sua

simplicidade, tem-se demonstrado bastante eficiente em proble­

mas de engenharia. Sua convergência global foi demonstrada, ten

do-se desenvolvido duas versões que apresentam convergência as­

sintõtica linear e superlinear.

No primeiro capltulo faremos a apresentação de concei­

tos bãsicos e do algoritmo de direções viãveis em duas etapas.

No segundo capltulo serã desenvolvido um processo de busca-li-

near restrita que trabalharã em conjunto com o algoritmo nao-

5

linear na implementação computacional do mesmo. No terceiro e

quarto capitulas apresentaremos o algoritmo quadrãtico e reali­

zaremos testes numericos respectivamente.

I.2 - DEFINIÇÕES E NOMENCLATURA

Definição I.1: O Lagrangeano do problema I.l e definido por:

m+p L(x, \) = f(x) + l: Ài gi (x)

i = 1

onde À E mm+p e o vetor de multiplicadores de Lagrange.

Definição I.2: Seja I(x) = {i lgi(x) = O} o conjunto de indices

das restrições atjvas no ponto x, definimos x E mn como ponto

regular se:

'v'gi(x); i E I(x) sao linearmente independentes.

'v' e usado na representação do gradiente.

Definição I.3: x E ffin e um ponto estacionário do problema

linear se existe À E mm+p tal que as condições abaixo são

tisfeitas:

a ) g i (X) < o; i = l , ... , m

b) g i (X) = o; i = m+ 1 , ... , m+p

c) À· g i (X) = o; i = 1 , ... , m+p l

nao-

sa-

m+p d) llf(x) + I "i 17gi (x) = O

i = l

6

onde "i, i = l ... m+p sao os multiplicadores de Lagrange.

Definição I.4: x E Rn e um ponto de Kuhn-Tucker do problema não

linear se:

a) x E Rn e estacionãrio

b) "· > O; i = l •.• m 1

Definição I.5: O vetor d ERn e dito direção de descida da fun­

ção ~(x): Rn ~ R se:

Definição I. 6: Se íl = {x E Rn Jgi (x) 2 O; i = l ... r.1} ê o con­

junto de pontos viãveis do problema não-linear, d(x) ê um campo

vetorial de direções viáveis se existe T > O tal que:

Para todo x E íl, x + td{x)Eíl

onde t E [O, T]

Definição I. 7: Sendo NE(x) - {y E Rn Jj jy-xj j < E; E > O} uma

vizinhança do ponto x E Rn e S E Rn um conjunto qualquer, defi­

nimos o fechamento~ e o interior S do conjunto S, como:

7

S _{x E IRnlN (x) C S; para algum E> O} E

Notamos T(x) = {y E IRn l(y-x)T 17gi(x) = O; i E I(x)} como o sub­

espaço tangente ãs restrições ativas no ponto x E !Rn.

I.3 - ESTUDO DO ALGORITMO DE DIREÇÕES VIÃVEIS EM DUAS

PARA OTIMIZAÇÃO NÃO-LINEAR COM RESTRIÇ0ES

Nesta seçao faremos um estudo do algoritmo

ETAPAS

proposto

por HERSKOVITS [ 16] e que foi posteriornenti; extendido pelo n€smo

autor em [ 17]. Apôs o estudo passaremos ã implementação.comput~

cional e a testes numericos do referido algoritmo.

Consideraremos o problema não-linear restrito

por desigualdades:

minimizar

sujeito a:

f(x); x E !Rn

gi(x) < O; i = 1 .... m.

apenas

Não incluiremos as restrições de igualdade com o intuito de fa­

cilitar a exposição, não havendo porem nenhuma limitação do al­

goritmo quanto a isto. Os resultados aqui obtidos poderão ser

axtendidos facilmente ao problema geral de programação não-li­

near, o que serã mostrado mais adiante.

8

Iniciaremos a apresentação do algoritmo pela exposição

das hipóteses que foram feitas no seu desenvolvimento, com o

objetivo de garantir a coerência e convergência do mesmo. O es­

tudo destas hipóteses nos darã uma ideia precisa das flexibili

dades e limitações do algoritmo.

1. Estudo das Hipóteses:

a) O conjunto íl tem interior íl e o fechamento do interior íl e

igual a íl.

Esta suposição visa evitar que o conjunto de soluções

viãveis íl contenha pontos isolados ou ''rabos". Por ser um algo­

ritmo de direções viãveis torna-se impossivel atingir pontos

isolados, pois não existe um campo viãvel atraves do qual se

possa definir uma direção capaz de alcançã-los. Alem disto, o

algoritmo trabalha na região estritamente viãvel, como sera vis

to posteriormente, não podendo então atingir pontos em "rabos''

do conjunto íl. Esta hipótese ê necessãria apenas para a formali

zaçao matemãtica do algoritmo, sendo dificilmente desrespeita­

da em problemas reais .

. bL Todo x E íl verifica gi(x) < O; i = 1 •.. m.

Com esta hipótese enfatiza-se o fato de que no inte­

rior do conjunto de soluções viãveis, todas as restrições devem

ser estritamente satisfeitas. r importante que isto se verifi­

que para que haja garantia da veracidade de algumas demonstra-

g

çoes.

c) Existe um escalar "a'' tal que o conjunto de nTvel íla defini­

do por:

íla - {x E íllf(x) < a}

e compacto e tem interior.

O algoritmo gera uma sequência {xk} convergente a um

ponto de Kuhn-Tucker X contido em um conjunto compacto de solu­

ções viáveis. íla ê o conjunto de soluções viáveis onde efetiva­

mente o algoritmo procura a solução do problema não-linear.

d) A função objetivo f(x) e as restrições gi(x); i = l ... m per

tencem ã classe C2•

O respeito a esta hipõtese ê importante na demonstra­

çao de convergência e coerência do algoritmo. Mais tarde vere­

mos que em certos casos pode-se utilizar uma hipõtese mais fra­

ca.

e) Todo ponto x E íla e o ponto regular do problema não-linear.

A hipõtese de regularidade ê fundamental em todos os

algoritmos que se firmam na condição de otimálidade de Kuhn­

Tucker. A mesma e importante na demonstração de convergência do

algoritmo e torna-se muito forte quando tratamos de problemas

l ü

linearmente restritos onde o fenómeno de degeneração e comum~

f) Seja x* um ponto de Kuhn-Tucker do problema não-linear e

À* E ~mo correspondente vetor de multiplicadores de Lagran­

ge. Assumimos que:

m H{x*, À*) = v 2 f(x*) + I

i=l À- v2 g.(x*)

l l

ê definida positiva sobre o subespaço tangente T{x*). Ou se­

ja: (y-x*)T H(x*, À*) (y-x*) > O; V y E T(x*), y f x*.

Esta hipótese é simplesmente uma condição de minimo de

segunda ordem sendo necessária para demonstrações de convergên­

cia do algoritmo. Certa variação do algoritmo não requer .:esta

hipótese, como veremos adiante.

2. ~presentação do Algoritmo Básico:

O algoritmo de direções viáveis em duas etapas consis­

te em, ,partindo-se de um ponto inicial interior ao conjunto de

soluções viáveis, determinar uma direção viável de descida eQ

relação a uma função pré-determinada. Na primeira etapa uma di-

reção de descida inicial é calculada através da resolução de

um sistema linear. Em uma segunda etapa, a direção inicial e

defletida de forma a obter-SE uma direção de descida viável.

Um processo de busca-linear determina o passo a ser

percorrido na direção calculada de modo a garantir a viabilida

l l

de estrita e a convergência global do algoritmo.

No processo nao ê utilizada a estratêgia de conjunto

ativo e nem funções de penalidades, sendo a busca-linear desen­

volvida considerando-se as restrições.

O algoritmo básico e:

Seja:

Bk uma sequência de matrizes simêtricas e definidas positivas no

]Rmxn 'fº d , veri 1can o:

para todo y e: lRn e B2 > B1

> O

- rk uma sequência de vetores no lRm verificando:

yk e: (O, l} tal que lim yk = O k+oo

- p > o o

-ac:(0,1)

l 2

PASSO O: Selecionar ponto inicial x0

s íla e valores admissiveis

para r5, y0 , p0

e a. Faça p = p0

.

PASSO l: Calcular "o E lRm e d0

E lRn resolvendo o sistema linear:

- r. l

m I

i = l

l . . . m

Se d0

= O, parar, x e ponto de Kuhn-Tucker.

( I. l )

( I. 2)

PASSO 2: Calcular p conforme serã .indicado, d E lRn e À E lRm re

solvendo o sistema linear:

m

I ( I. 3) i = l

PASSO 3: Para cada restrição fazer:

yi = y se "i > O

Realizar busca-linear com as restrições:

l 3

onde te o passo da busca-linear.

PASSO 4: Atualizar as variãveis: xk+l = xk + td. Retornar ao

Passo l.

Nota-se a simplicidade do algoritmo que se resume, pr~

ticamente, na resolução de dois sistemas lineares e uma busca­

linear a cada iteração. Faz-se importante mostrar· os conceitos

existentes implicitamente no processo, o que faremos na

seguinte.

I.4 - ANKLISE DO ALGORITMO

seçao

Nesta seçao faremos uma série de observações visando a

explicação resumida do funcionamento do algoritmo proposto.Mai~

res detalhes podem ser encontrados nos trabalhos de HERSKOVITS

[1s] e [11].

a) Vãrios parâmetros necessãrios para o funcionamento do algo­

ritmo são definidos, tendo cada um deles uma função especlf!

ca. A se~uência de matrizes Bk pode ser qualquer desde que

respeitadas as condições de sua definição. t, obviamente, im

portante definir-se meios de gerar a sequência Bk de modo a

estabelecer o algoritmo em sua melhor forma. A sequência de

vetores

produto

k -r exerce funçao de

escalar d1 Vgi(x) e

estabilização e amplificação do

pode ser tal que aumente a con-

vergência do algoritmo, como serã visto mais tarde. O para-

k - -metro y e fundamental na manutençao da viabilidade estrita

l 4

na busca-linear sendo essencial, por motivos de velocidade

de convergência, que se reduza a zero ao final do processo

iterativo. Meios de atualização de yk serão vistos no Capit~

lo Ili. Finalmente a E (O, l) ê importante no cálculo do

raio de curvatura p que serã usado na deflexão da direção

inicial.

b) No Passo 1, calculamos o vetor de multiplicadores de Lagran­

ge 1c0

E lRm e a direção de descida inicial d0

E lRn. Se defini­

mos:

Anxm como uma matriz contendo em suas colunas os gradien­

tes das m restrições.

Rmxm uma matriz diagonal contendo os parâmetros ri; i =

=l ... m.

Gmxm uma matriz diagonal contendo as restri.ções gi(x); i =

= 1 • • • m.

As expressoes (1.1) e (1.2) ficam:

( r . 5)

( 1. 6)

Resolvendo o sistema chegamos a:

( 1. 7)

l 5

( I. 8)

A expressao (I.6) e dita atualização dos multiplicadores de

Lagrange e quando estes são positivos a direção d0

aponta p~

ra as respectivas restrições, afastando-se delas em caso con

trãrio. Através desta mesma expressãd pode-se notar que se

todas as restrições são ativas, a direção d 0 estã contida no

sub-espaço tangente.

Da expressao (I.5) percebemos que se promove uma convergen­

cia a um ponto estacionãrio do problema não-linear e que,

neste, a direção d0

e nula, pois o gradiente do Lagrangeano

e zero.

c) No Passo 2 uma nova direção e calculada de forma semelhante

ã direção d0

e com auxTlio do cãlculo anterior. Devido a Pº!

sibilidade da direção d0

não ser viãvel, se faz necessãrio

defletT-la de modo que a nova direção seja de descida e viã­

vel. Para isto subtrai-se o termo pld0

12 , na tentativa de

compensar a curvatura das restrições ativas. Para que a dire

ção defletida seja de descida e preciso estabelecer um limi­

te mãximo para p, o que serã feito na prõxima seção.

Utilizando a mesma notação definida anteriormente

reescrever as equações (I.3) e (I.4) e resolver o

podemos

sistema

para cãlculo da direção de descida e dos multiplicadores de

Lagrange:

onde e

l G

n = (1, l, l, l, ... ); e E:!R.

( I. 9)

(I.10)

d) No Passo 3 vemos a influência do parâmetro yk na manutenção

da viabilidade estrita do algoritmo. Para restrições com mul

l k -tip icadores de Lagrange positivos, y esta entre zero e

um, o que implica em c~locar uma barreira de segurança fictT

eia que impede a saturação destas restrições. Caso os multi­

plicadores de Lagrange sejam negativos yk e unitârio, evitan

do assim uma aproximação destas restrições.

I.5 - VERSUES DO ALGORITMO

Vimos, na apresentação do algoritmo de direções viã-

veis em duas etapas, que se faz necessârio gerar uma sequência

de matrizes Bk que seja simétrica e definida positiva. vãrias

sequências podem ser utilizadas, alterando-se assim a converge~

eia do algoritmo bãsico. Duas delas foram estudadas formalmente

por Herskovits nas referências jã mencionadas. No trabalho de

HERSKOVITS [ 16] assumiu-se Bk constante igual ã identidade, foi

chamada de "versão sem quasi-Newton'' ou ''versão I" tendo conver

gência linear demonstrada.

Posteriormente, na referência [1 7], a matriz Bk foi

aproximada pela hessiana do Lagrangeano do problema, sendo esta

l 7

versao chamada de '!quasi-Newton'' ou ''versão II'', demonstrou-se

convergência superlinear. Procedemos, agora, ao estudo dos dois

casos separadamente:

a) Versão I:

Neste caso Bk = I; Vk sendo Ia matriz identidade, is­

to implica em simplificação na implementação computacional do

algoritmo, como pode ser visto nos sistemas lineares para cãlc~

lo das direções. A direçio de descida d passa a ser o negativo

do gradiente do Lagrangeano e o mêtodo pode ser considerado uma

extensão do mêtodo do gradiente. Nos Lemas 3.3 e 3.4 do traba­

lho de HERSKOVITS [ 16] vemos demonstrado que d

0 e d são dire­

ções de descida da função objetivo. Com a finalidade de garan­

tir que d seja tambêm direção de descida, condicionamos:

(1.11)

substituindo (1.10) em (I.11),temos:

(1.12)

substituindo (I.7) em (1.12):

donde:

l ll

T P = (a-1) Vf (x)do

À~ e l[d0

]1 2 (1.13)

A expressão (I.13) nos di o valor miximo que o raio de

curvatura pode assumir para que a taxa de descida seja

porcento menor que a .. taxa de descida inicial.

Como regra de atualização de p, calcula-se pmix

expressão (I.13) e faz-se:

l se Pmãx < P + P =

( l -a)

pela

garantindo-se, então, que sempre haja uma boa taxa de descida.

Ainda na versao sem quasi-Newton, notamos que o proce!

so de busca-linear deve ser efetuado com base na função objeti­

vo, e que a hip6tese ''f'' ~ dispensivel para sua demonstração de

convergência. Como consequência, a hip6tese ''d'' torna-se

fraca, aceitando que a função objetivo seja de classe C1 •

b) Versão II:

mais

Quando se utiliza uma sequência de matrizes Bk tenden-

do a aproximar a hessiana do Lagrangeano do problema, estamos

aplicando um m~todo quasi-Newton ã resolução do sistema de

Kuhn-Tucker e, consequentemente, aumentando a convergência do

processo. De manéira aniloga ã anterior, no artigo de HERSKOVITS

l 17 1 encontramos, no Lema 3.1, que d

0 e d são direções de desci

da do Lagrangeano do problema e relacionadas por:

19

(I.14)

Semelhantemente, substituindo (1.10) e (1.7} em (1.14),

chegamos ao limite miximo para o raio de curvatura~ que e dado

por:

(l-a}d! VL{x, À0

) p =~~~~..--~~......-~.--~~-.-~

l[d0

]1 2 À~ RG(ATB-lA-RG}-I e (I.15)

Uma vez que a direção d e de descida em relação ao La­

grangeano do problema, a busca-linear deveri ser feita em rela

çao ao mesmo.

1.6 - EXTENS~O DO ALGORITMO PARA RESTRIÇUES DE IGUALDADE

Nas seçoes precedentes foi visto o algoritmo de dire-

çoes viivets em duas etapas aplicado ao caso de restriç5es de

desigualdade apenas. Nesta seção veremos, resumidamente, as

ideias que estendem o processo tambem ao caso restrito por

igualdades.

Talvez, a ideia mais simples seria utilizar uma função

de penalidades das restriç5es de igualdade e minimizi-la sujei­

ta apenas ãs desigualdades.

Na presente abordagem torna-se melhor a criação de um

problema auxiliar apenas restrito i desigualdades e cuja :sólu­

ção, atraves do algoritmo proposto, leva ã solução do problema

original.

ou

20

Para isto define-se uma função auxiliar, como:

e = f(x) -c

m+p I

i =m+ l

m+p ec = L(x, ,;) - I

i =m+ l Ci gi (x), na versa o quasi-Newton

onde: Ci > O; i = m+l ... , m+p e L(x, À) o Lagrangeano do pro­

blema.

O problema auxiliar e:

minimizar ec(x)

sujeito a: gi(x) < O; i = 1, .•. m+p

chamamos ao conjunto extendido de pontos viãveis ~. como:

n 6 _ {x s R ; gi(x) < O; i = 1, •.• m+p}

O algoritmo extendido fica:

PASSO O: Selecionar ponto inicial x 0 s 6 e valores admissiveis

para r O, y O

, p O

, a e C i .::_ O ; i = m+ l . . . m+p.

p = Po·

Fazer

PASSO 1: Calcular Ào s Rm+p e d0

s Rn resolvendo o sistema li­

near:

PASSO 2:

m+p l

i = l

21

À o. l

ri Ào. gi(x); i = l ... m l

g i ( x) ; i = m+ l . . . m+ p

Se d0

= O, parar, x e ponto de Kuhn-Tucker.

Se e. < - l. 2 À faça e. = - 2 À . i = m+l ... m+p l o. l o . ,

l l

m+p m+p (l-a) Se u = ( l Ào. + l e . ) > o ache Pmãx = qua.!! i = l i=m+l l u l

do Pmãx < p fazer p = Pmãx 2

Calcule À E Rm+p e d E Rn resolvendo o sistema linear:

d = - B-l [vf(x) + m+p l

i = l

dTVgi(x) = [ri ;\. g i (X) + p[dºJ2J; i = l ... , m l

dTVgi(x) ['.' + Ci

PI d0 1 2] ; = g i (X) + i = m+ l ... m+p

+ e. ºi l

PASSO 3: Para cada restrição de desigualdade fazer:

yi = y0

se Ài > O

y. = l se À·< O l l

22

Para cada restrição de igualdade fazer:

Y· = O 1

Realizar a busca-linear em ec(x) com as restrições:

gi(x + td) ·e yi gi(x); i = l .•• m+p

PASSO 4: Atualizar as variãveis: xk+l = xk + td. Voltar ao PAS­

SO l.

23

CAPITULO II

DESENVOLVIMENTO DE UM ALGORITMO DE

BUSCA-LINEAR COM RESTRIÇÕES

II. l - INTRODUCJ\O

Nos algoritmos modernos de minimização sem restrições,

ê gerada uma sequência de pontos {xk} de forma que f(xk+l) <

f(xk), sendo esta condição fundamental para a obtenção da con­

vergência 1lobal. Neste processo, uma direção de descida ê acha

da e o prõximo ponto da sequência ê encontrado sobre a mesma. A

determinação do passo t que se'vai ca~inhar sobre a referida di

reçao requer, muitas vezes, um algoritmo especifico chamado de

busca-linear. Desta maneira se transforma um problema multi-di­

mensional em uma sequência de sub-problemas uni-dimensionais.

Uma vez que a direção dk ê obtida atraves de informa­

çoes pontuais, sua caracteristica de descida -sõ ê garantida em:uma

determinada vizinhança do ponto xk.A partir de certos valores do

passo,a ,função objetivo não sofrerã decrêscimo,sendo necessãrio

determinã-lo de forma a manter,pelo menos qual itativamente,as c~

racteristicas pontuais. Seguindo este raciocinio, uma ideia in~

cial seria reduzir ao mãximo a função objetivo, ou seja, achar

o passo que a minimize sobre a direção dk. No caso em que nao

haja restrições este processo ê relativamente simples, reduzin­

do-se a uma minimização exata em uma dimensão. Em problemas re!

tritos pode ser necessãrio um acrêscimo· no valor da função obj!

24

tivo para obter-se a verificação das restrições. A busca linear

e, então, feita em relação a uma função auxiliar convenientemen

te definida que inclua as restriçõesº

Nos algoritmos de direções viãveis, uma vez que todos

os pontos satisfazem as restrições, a busca-linear e realizada

sobre o objetivo do problema, não sendo necessãrio definir fun­

ções auxiliares. Porem esta busca deve ser realizada respeitan­

do-se as restrições.

Em trabalhos recentes diversos autores destacaram que

a minimização exata uni-dimensional consome muito esforço de

cãlculo, sem ganhos compensadores na função objetivo. Foram, en

tão, propostos criterios de minimização inexata para problemas

sem restrições, que garantem uma descida suficiente da função.

Estes criterios mostraram-se muito eficientes tanto em estudos

teõricos como em aplicações numericas. Nesta tese propomos um

criterio de descida suficiente para a busca-linear restrita e

desenvolvemos um algoritmo para sua implementação computacio-

nalº Desta forma estamos interessados no problema de achar um

passo t capaz de provocar uma diminuição aceitãvel no valor da

função objetivo e mantendo a viabilidade, ou seja:

achar t tal que: h(t) < h(O)

e

onde:

< y. 1

h(t) = f(x + td)

G.(t) = g (x + td). 1 1

') r: L :J

II.2 - CARACTERISTICAS DE UM ALGORITMO DE BUSCA-LINEAR

Uma vez que nos propomos a desenvolver um algoritmo de

busca-linear, e importante conhecermos as características neces

sãrias a este processo. Ressaltamos algumas delas abaixo:

a) Rãpida convergencia: Uma vez que o algoritmo de busca-linear

deverã ser executado a cada iteração do algoritmo de dire-

ções viãveis, e preciso uma convergência rãpida para que o

esforço computacional do primeiro não seja co~parãvel ao do

segundo. Os processos que se utilizam dos chamados ··~ritê­

rios de descida suficiente'' são os que apresentam uma maior

convergencia e serão mostrados posteriormente.

b) Segurança: Como a solução do problema não-linear multi-dimen

sional depende de sucessivas solu~ões de problemas uni-dime~

sionais, a busca-linear deve ser a prova de falhas.

c) Economia: Na resolução de problemas de otimização faz-se ne­

cessãrio a avaliação das funções e derivadas do modelo adota

26

do, um numero considerãvel de vezes. Dizemos que um processo

e mais econômico que outro quando o numero de avaliações do

modelo e menor. Em problemas de pequena dimensão, ou de fã­

cil avaliação, a economia e fator de pouca importância. Este

nao e o caso dos problemas estruturais, de sorte que a cada

avaliação e preciso analisar toda uma estrutura, geralmente

através do metodo dos elementos finitos.

d) Generalidade: Uma característica bastante desejãvel em um al

goritmo de busca-linear e a capacidade de ser o mais geral

possível. Entendendo-se por generalidade a independencia re­

lativa ao algoritmo global, a busca-linear deve füncionar

bem, seja qual for o metodo de cãlculo da direção de descidL

Entretanto, devem ser levadas em consideração algumas pro-

priedades intrínsecas ao algoritmo global e ao problema,tais

como diferenciabilidade e dificuldade de avaliação do mode-

1 o •

e) Exatidão: No processo de busca-linear a exatidão com que se

calcula o passo e função das necessidades do algoritmo glo­

bal. Um processo ''exato'' e aquele que determina um passo pr!

ciso, enquanto um ''inexato'' se satisfaz em delimitar um in­

tervalo admissível para o mesmo. Desta forma os processos in!

xatos são mais econômicos e rãpidos que os exatos,

ser usados quando possível.

devendo

Em muitos casos, e tambem no nosso, a demonstração da

convergencia global do algoritmo depende fundamentalmente do

27

processo de büsca-linear, que é geralmente suposto exato. No

trabalho de COHEN [ 5] vemos que estas demonstrações, müitas ve­

zes, também sao validas para processos inexatos, o que e o caso

do algoritmo de direções viãveis em duas etapas.

Em certos processos, como por exemplo no método do gr~

diente, a utilização de um algoritmo inexato de busca-linear 1!

va ã geração de direções não-ortogonais na vizinhança do Õtimo,

reduzindo o prejudicial fenõmeno do "Zigzagging''.

No método do gradiente conjugado, e suas varia~Ões fo­

ram feitas âlgumas experiéncias numéricas por SHANNO [ 22] favo­

recendo também o uso de busca-linear inexata. Apenas em alguns

algoritmos, como direções conjugadas, torna-se imprescindfvel a

determinação exata do passo para garantir a geração de direções

consecutivas conjugadas.

Com vista no que foi dito e nas propriedades do algo­

ritmo proposto decidimos desenvolver um processo de otimização

uni-dimensional restrito, do tipo ''inexato'' e para isto é precf

so definir um critério de aceitação para o passo e uma fÕrmula

iterativa convergente ao passo aceitãvel. Estes dois itens nao

sao totalmente independentes mas, por motivos didãticos, fare­

mos as exposições separadamente.

28

II.3 - CRITtRIO DE ACEITAC~O

Como jã foi dito, em um processo de busca-linear é pr~

ciso determinar um intervalo dentro do qual qualquer passo e

aceitãvel. A delimitação do mesmo e feita segundo a definição

de ''critérios de aceitação" ou ''critérios de descida suficien­

te'' uma vez que implicam na redução do valor de alguma fun~ão

pré-determinada. Basicamente, o objetivo é achar um passo que

não seja tão pequeno a ponto de evitar que o algoritmo caminhe

e nem tão grande que não provoque diminuição do valor da função

pré-definida.

Através de informações pontuais tais como valor da fun

çao, restrições e seus respectivos gradientes defini~os os cri­

térios a começar pelo limitante superior do passo:

h{t) ~-h{O) + mth'{O) (II.l)

onde m E {O, l)

Desta forma o maior passo admissivel é aquele que re­

duz ''m" vezes o valor da função h{t) caso ela fosse linear. O

critério, que pode ser visto na Figura (II.l), a.lém de limitar

d passo garante automaticamente uma descida suficiente da fun­

ção h{t). Ao processo de verificação da satisfação ou não deste

critério chamaremos de ''teste de função''.

29

De modo a evitar um passo muito pequeno definimos um

criterio para seu limite inferior, da forma:

h'{t) > m'h' (O) ( I I . 2 )

onde m' s {m, l)

Podemos dizer que o menor passo admissivel e aquele que

provoca, no minimo, um aumento de m' vezes na derivada direcio­

nal, como estã esquematizado na Figura {II.2). Da mesma forma,

ao processo de verificação da satisfação deste critério chama­

mos de ''teste de derivada''.

A união dos dois criterios definidos acima chama-se Cri

teria de Wolfe [ 24 ] e através do mesmo limitamos o passo tanto

inferiormente como superiormente, como pode ser visualizado na

Figura {II.3), sendo suficiente para determinação do passo em

problemas irrestritos ou quando a restrição mais prõxima estã ã

direita do passo mãximo admissivel.

Quando introduzimos restrições no processo de busca-l!

near, o criterio de Wolf deixa de ser suficiente, sendo preciso

definir novos criterios de aceitação, o que faremos a segui·r.

Para efeito de exposição definiremos regi5es no plano h{t) x t

da seguinte maneira:

- Região I: Parte do plano h{t) x t que não satisfaz ao teste

de derivada, limitada inferiormente pelo passo nu

30

1 o •

- Região II: Parte do plano h(t) x t que obedece aos testes de

função e derivada simultaneamente.

- Região III: Parte do plano h(t) x t que não satisfaz ao teste

de função.

As três regiões estão esquematizadas na Figura (II.4).

Uma vez que o algoritmo de direções viãveis impõe a

manutenção da viabilidade estrita, torna-se imprescindivel a de­

finição de um critêrio para a satisfação desta exigência. Desta

forma um passo s6 poderã ser aceito se:

< y. 1

onde Gi(t)=gi(x+td)

(II.3)

denominamos "teste de restri.ções" ao processo de verificação da

obediência a este critêrio.

O critêrio de aceitação ainda nao estã totalmente defi

nido, de sorte que o minimo da função h(t) restrita poderã es­

tar em uma fronteira, ou melhor em uma barreira imposta pelo

parãmetro yi. Neste caso, para aumentar a flexibilidade do cri­

têrio, define-se uma banda ã esquerda da barreira limitante e

aceita-se o passo que estiver contido na mesma:

onde:

31

3 i [G.(t) E [G· , G. J 1 l . l -m1n max

G . l . m1n

G. l -max

yS < l

==BG. ;B>l 1 mãx

= Y· G.(O) 1 l

(II.4)

Ao procedimento de verificação da obediência a este

critêrio chamaremos de ''teste de banda'' e um esquema pode ser

visto na Figura (II.5).

Os critêrios definidos anteriormente são suficientes p~

ra o estabelecimento de um algoritmo de busca-linear, antes po­

rem ê preciso definir-se um meio de convergência aos mesmos, o

que faremos a seguir.

II.4 - FÕRMULA ITERATIVA CONVERGENTE

Na seçao anterior resolvemos uma parte da nossa propo­

sição em desenvolver um processo de busca-linear restrito. En­

tretanto, definir-se um critêrio de aceitação, implica, poste­

riormente, em se estabelecer um procedimento para achar um pas­

so que o verifique. Comumente, nos algoritmos de busca-linear,

usa-se um processo de tentativas onde se inicia com um passo

3?

unitãrio e reduz-se o mesmo, a cada iteração, através de uma

sequência decrescente como:

1 -:-:f=T} ; V > 1 V

Este procedimento converge ao critério de

apresentado, porém apresenta ~lgumas desvantagens.

(II.5)

àteitação

a) Não hã razao lÕgica para justificar o passo unitãrio inicial

b) A taxa de redução do passo ê pré-determinada,

do comportamento do algoritmo.

independendo

c) Por ser um processo de tentativa e erro, torna-se caro póis

exige um nümero considerãvel de anãlises do modelo.

Consideramos este procedimento muito primãrio e pouco

satisfatório, e, devido a isto, desenvolveremos um processo con

vergente mais robusto.

Nossa ideia ê utilizar informações das iterações ante-

riores para, através de interpolações, prever o comportamento

do processo na iteração atual. O procedimento pode ser resumido

em:

a) Através de interpolações aproximadas, baseadas em informa-

ções da iteração,anterior, determina-se o passo inicial do

processo de busca-linear t0

•

33

b) A partir do passo inicial t0

, realiza-se interpolações com

base nas informações da iteração atual de mddo a encontrar

um passo aceitãvel.

c) Utilizaremos parãbolas de segundo grau para as interpolações

uma vez que os polinômios cúbicos apresentam dificuldade lÕg~

cana implementação computacional das rotinas. Alem do que,

FLETCHER 1''1 em seus experimentos não notou melhoras compe!

sãveis da interpolação cÜbica em relação ã quadrãtica.

d) Com vista a aumentar a eficiencia do processo, serã interes­

sante interpolarmos, tomando como base pontos na região I e

na região III.Uma vez que estas regiões são vizinhas, ã es­

querda e ã direita, da região II estaremos cercando esta ul­

tima que, geralmente, contem o passo aceitãvel. Se chamamos

de TL o ponto base para interpolação que estã contido na re­

gião I e TH o que estã na região III, serã necessãrio um pr~

cesso de atualização de forma a aproximar, cada vez mais, e!

tes pontos da região II. Com este objetivo, a cada vez que

se obtém um ponto na região I mais prÕximo da reglão II que

o ponto TL, este e atualizado. Da mesma forma, a obtenção de

um ponto na região III mais prÕxima da região II que TH,obr!

ga a uma atualização deste ultimo. Sendo assim, TL pertence

ã região I tendendo ã região II pela esquerda, enquanto TH

tende ã mesl'.la pela direita.

Fazendo uso das ideias anteriormente expostas podemos

desenvolver o algoritmo de busca-linear com restrições.

34

II,5 - DESENVOLVIMENTO LÕGICO DO ALGORITMO DE BUSCA-LINEAR

Definido um criterio de descida suficiente e uma fÕrmu

la iterativa convergente ao mesmo, jã dispomos das ferramentas

necessárias para o estabelecimento lÕgico do processo de busca­

linear. Faremos uma exposição progressiva, partindo do racioci­

nio básico e evoluindo ate sua forma mais completa.

O processo mais simples que podemos conceber e o apli­

cado ao caso em que nao existam restrições limitando o passo,o~

de o criterio de Wolfe e suficiente. Desta forma:

Achado o passo inicial t0

, por um meio que sera exposto mais

tarde, verifica-se o teste de função. Se este não e satisfei­

to, interpola-se o passo, tendendo a reduzi-lo.

- Se o teste de função e verificado, porem o de derivada nao o

e, e preciso extrapolar o passo afim de aumentã-lo.

Entenda-se, aqui, por ''extrapolação'' a qualquer proce!

soque tenha por objetivo aumentar o passo e por ''interpolação''

aquele que tenda a diminui-lo. O fluxo de lÕgica deste procedi­

mento pode ser visto na Figura (II.6),

Ao introduzirmos restrições torna-se necessãrio deter

minar em que região do plano h{t) x t se encontra a restrição l~

mitante do passo e, desta forma, tomar a decisão correta. O pr~

cedimento para o caso restrito seria:

35

- Se os testes de restrições, função, derivada ou banda sao sa­

tisfeitas, a busca-linear estã terminada.

- Se nao hã satisfação, apenas do teste de função, basta inter­

polar o passo com base na função objetivo.

- Se nao se satisfazem os testes de função e restrição, e pre­

ciso interpolar o passo tomando como base a função objetivo e

as restrições, assumindo o menor passo obtido. Neste caso a

restrição limitante do passo se encontra na região III e o es

quema pode ser visto na Figura (II.7).

- Interpolamos o passo com base apenas nas restrições quando er

tas são violadas e o teste de função e satisfeito. A restri­

çao limitante do passo se encontra na região II, conforme re

gistrado na Figura (II.8).

- Finalmente; extrapola-se o passo quando o teste de derivada

ou banda não e obedecido como vemos na Figura (II.5).

A Figura (II.9) nos mostra o fluxo de lÕgica para a

busca-linear restrita, utilizando o criterio de Wolfe extendido,

enquanto na Figura (II.10) vemos detalhes acerca das interpola­

ções e extrapolações com derivadas.

No procedimento de busca-linear desenvolvido ate aqui,

as interpolações e extrapolações quadrãticas são feitas utili­

zando-se derivadas uma vez que sõ dispomos de dois pontos-base.

36

Em problemas de otimização estrutural o cãlculo de derivadas r~

quer a resolução de sistemas lineares, geralmente de grande Pº!

te, o que representa um esforço computacional +mportante que

deve ser evitado. Se realizarmos as interpolações e extrapola­

çoes com base em três pontos ao invês de derivadas, estaremos

não sõ aumentando a velocidade de convergência como tambêm au­

mentando a economia. Definimos, por isto, o passo auxiliar TA

que e simplesmente um ponto-base para a interpolação e extrapo­

lação por pontos, e que pode pertencer a qualquer uma das re­

giões. Notamos que na primeira iteração da busca-linear dispo­

mos da derivada·no passo t = O, pois o algoritmo de direções

viãveis jã a avaliou. Desta forma podemos, na primeira itera-

çao, interpolar utilizando derivadas e, a partir dai, apenas po~

tos. Modificando-se o fluxograma da Figura (II.9) chegamos a um

processo de busca-linear que não se utiliza de derivadas e este

se encontra na Figura (11.11).

Devido ãs caracteristicas do algoritmo de direções viã

veis com atualização quasi-Newton, neste as interpolações sao

feitas sempre com derivadas, o que não ocorre na outra versão.

Para finalizarmos o nosso desenvolvimento de um algo-

ritmo de busca-linear, resta a definição acerca do passo ini-

cial t0

, que serã feito a seguir.

37·

II,6 - PROCEDIMENTO PARA C~LCULO DO PASSO INICIAL

Como já dissemos, pretendemos es.tabelecer uma rotina de

cálculo de passo inicial baseada em interpolações aproximadas,

uma vez que são feitas com informações da iteração anterior.

Como no ponto de partida da busca-linear sõ dispomos de duas

informações, não podemos realizar uma interpolação quadrãtica.

Para obtermos o dado que falta, ·podemos supor que as concavida­

des da função objetivo e das restrições nao variem de uma itera

çao para outra. Se o coeficiente quadrãtico da parábola inter­

polante ªk-l e guardado, podemos fazer:

y = ªk-l t 2 + bt + c

como em t = O, y = h' (O) e y' = h' (O)

temos b = h' (Q) e C = h(O)

onde y(t) e a parãbola interpolante da função objetivo.

Pelo mesmo processo podemos gerar as parãbolas interp~

lantes das restrições não-lineares. Quando o problema possui re~

trições lineares, não realizamos interpolações mas calculamos

de forma exata o passo mãximo Tmãx que se pode assumir sem vio­

lar as mesmas. Impedindo que no processo de busca-linear os pa~

sos extrapolados ultrapassem Tmãx• podemos desprezar as restri­

ções lineares aumentando a economia do processo.

38

O procedimento para o cãlculo do passo inicial

ser expresso da forma:

pode

a) Interpolam-se as restrições não-lineares e toma-se o .,1 menor

passo encontrado, TG.

b) Interpola-se a função objetivo achando o passo TF.

c) Se existem restrições lineares, determina-se T - e despre­max zam-se as mesmas.

d) Tomar o passo inicial como o m]nimo entre Tmãx' TG e TF.

Com este procedimento que estã representado na Figura

(II.12) determinamos um passo inicial capaz de acelerar o pro­

cesso de busca-linear pois o mesmo jã se encontra prÕximo da re

gião aceitãvel. Resultados numericos serão mostrados mais tar­

de.

II.7 - IMPLEMENTAÇ~O DO ALGORITMO DE DIRECÕES VI~VEIS - VERS~O

I

No Capitulo I foi apresentado o algoritmo de direções

viãveis em suas duas versões, utilizando-se ou não, recursos de

métrica variãvel. Nosso objetivo não e, simplesmente, gerar um

cõdigo FORTRAN capaz de executar o algoritmo, mas aproveitar

suas características para atingir certos objetivos, tais como:

39

a) Estabilidade numérica

b} Minimo esforço computacional

c) Minimo gasto de memõria

d} Precisão

e) Menor numero de anilises do problema

Uma vez que o algoritmo lida com resolução de sistemas

lineares, poderi surgir instabilidade numêrica reduzindo ou im­

pedindo a convergência do mesmo. Com vistas a aumentar a velo­

cidade do mêtodo alem de, reduzindo o nümero de operações, me­

lhorar a precisão, devemos diminui'r o esforço computacional. O~

tra preocupaçao ê a utilização de um m1nimo de memõria, uma vez

que o algoritmo deveri ser usado em otimização estrutural que

geralmente exige um cõdigo de elementos finitos para a anilise

da estrutura.

Basicamente, devido ã simplicidade do algoritmo, div_i_­

diremos as etapas em blocos distintos, visando facilitar o en­

tendimento, a depuração de erros e a introdução de modificações

futuras. As fases do processo são estanques do ponto de vista

lÕgico e em conjunto forn,am um fluxo bastante linear, como pode

ser visto na Figura (II. 13). Notamos a simplicidade do algorit­

mo em relação a processos que se utilizam da estratêgia de con­

junto ativo o que pode ser concluido dos trabdl.hos de ESCUDERO

[ 7 J , [ª J , [ 9 J •

40

Com o intuito de minimizar o gasto de memõria, utili­

za-se um artificio de alocação dinâmica de memõria que e o arma

zenamento de todas as informações em um Ünico vetor. Desta for-

ma, todas as matrizes que são simétricas serão alocadas veto-

rialmente e a posição relativa a cada informação no vetor de me

mõria serã dada por um ponteiro definido inicialmente obedecen-

do a um tamanho exato para o dado. São definidos onze

ros, a saber:

pontei-

Ponteiro 1: Indica o inicio do vetor de variãveis, X com a di­

mensão do problema.

Ponteiro 2: Indica o inicio do vetor de valores minimos das va­

riãveis, X . com a dimensão do problema. m1n

Ponteiro 3: Aponta o inicio do vetor X - de valores mãximos das max va~iãveis, tendo a dimensão do problema.

Ponteiro 4: Sendo NF o numero de restrições do problema, ·;este

ponteiro indica o inicio do armazenamento do valor das restri­

ções e função objetivo que ocupa NF + 1 posições.

Ponteiro 5: Sendo Na dimensão do problema, este ponteiro apon­

ta o inicio do vetor gradiente das restrições e função objeti­

vo, tendo dimensão (NF + 1) x N.

Ponteiro 6: Aponta o vetor direção de dimensão N.

41

Ponteiro 7: Aponta o vetor de coeficientes da interpolação,ak-l'

de dimensão (NF + l} e que auxilia no cilculo do passo inicial.

Ponteiro 8: Indica o vetor de multiplicadores de Lagrange com

dimensão NF.

Ponteiro 9: Aponta para o inicio do armazenamento da matriz do

sistema linear dos multiplicadores de Lagrange, ocupando

(NF + l) x NF/2 posições de memõria. Este ponteiro, apõs o cãl­

culo da direção de descida, passa a apontar o vetor de deriva­

das direcionais das restrições e função objetivo com dimensão

N F + l.

Ponteiro 10: Indica, inicialmente, o vetor <j) de "status" da sa­

turação (</l = l) ou não (</l = O) das restrições, tendo dimensão

NF. Apõs o cãlculo da direção de descida, este ponteiro passa

a apontar o vetor das barreiras, Fmãx para a busca-linear, com

dimensão idêntica ã anterior.

Pontetro 11: Aponta o vetor S que contem os termos independen­

tes do sistema linear dos multiplicadores de Lagrange.

Este esquema, que estã representado na Figura (II.14),

evita o dimensionamento de vetores e matrizes que poderiam ser

sub-utilizados dependendo do tipo de problema analisado, otimi­

zando assim a memõria.

42

Como um dos nossos objetivos e a generalidade da impl~

mentação, e preciso definir um meio simples e exato para a ob­

tenção das informações acerca do problema. Desta forma a anãli­

se do problema deverã ser feita por meias totalmente independe~

tes do algotitmo, não interessando ao mesmo se o problema e es­

trutural, académico ou econômico. A passagem do resultado da

anãlise do problema para o algoritmo deverã obedecer certas re­

gras a saber:

1) Fornecer apenas as informações requisitadas pelo fndice !.:

a) I = l: Apenas os gradientes das restrições

b) I = 2: Valor da função objetivo, seu gradiente, valor das

restrições e gradientes das restrições de igualdade, se

existirem.

c) I = 3: Todos os valores de função objetivo, restrições e

seus respectivos gradientes.

2) Fornecer o vetor de contadores K devidamente atualizado:

a) K ( 1 ) : Numero de avaHações da função objetivo.

b) K ( 2) : Numero de avaliações das restrições.

c) K ( 3) : Numero de avaliações do gradiente da função objeti-

vo

d) K ( 4) : Numero de avaliações do gradiente das restrições de

desigualdade.

43

e) K(5): Numero de avaliações do gradiente das restrições de

igualdade.

3) Os valores das restrições, função e seus gradientes deverão

ser devolvidos em vetores, seguindo uma ordem interna a sa­

ber:

a) Vetor de funções:

19 - restrições de igualdade lineares

29 - restrições de igualdade não-lineares

39 - restrições de desigualdade lineares

49 - restrições de desigualdade não-lineares

59 - função objetivo.

b) Vetor de gradientes:

l 9 - gradiente das restrições de igualdade lineares

29 - gradiente das restrições de igualdade não-lineares

39 - gradiente das restrições de desigualdade lineares

49 - gradiente das restrições de desigualdade não-lineares

59 - gradiente da função objetivo.

Como a direção de descida e de crucial importância pa­

ra o algoritmo, e natural que o seu procedimento de cãlculo se-

ja impecãvel, preciso e iãpido. Na realidade, e neste ponto

que encontramos os maiores volumes de cãlculo e a possTvel ins­

tabilidade numerica. Torna-se necessãria uma rotina de cãlculo

44

estãvel e capaz de avaliar a direção de descida para problemas

com ou sem restrições de igualdade de forma eficiente. Na tent!

tiva de estabilizar a solução do sistema dos multiplicadores de

Lagrange, fatora-se a matriz de coeficientes pelo mêtodo de

Choleski. Para aumentarmos a eficiência do procedimento, ao in­

ves de defletirmos a direção d0

sempre, soa defletimos se hou­

ver ao menos uma restrição ativa, o que ê verificado pelo vetor

~ pré-definido. Como o parãmetro p depende de a, ê Ütil verifi­

car-se este ultimo e evitar, em certos casos, a deflexão da di­

reção d0

• Finalmente,· para melhoria da precisão, todos os cãlcu

los de produtos de matrizes e vetores são feitos em precisão du

p 1 a.

O melhor fluxo de 16gica encontrado para o cãlculo da

direção d0

estã apresentado na Figura (II.15).

II.8 - It1PLEMENTAÇ~O DO ALGORITMO DE DIREÇÕES VI~VEIS - VERS~O

II

Nesta seçao mostraremos a implementação computacional

do algoritmo de direções viãveis que se utiliza de mêtrica va­

riãvel. Basicamente, todos os recursos e procedimentos da im­

plementação da versão I serao repetidos, sõ havendo necessidade

de mostrarmos, aqui, as diferenças. A primeira delas reside na

existência de uma matriz aproximada da inversa da hessiana que tem importante

participação no algoritmo e deve ser atualizada a cada itera-

ção. Com isto, o fluxograma recebe mais um procedimento que e

chamado de ''atuallzação'', como pode ser visto na Figura

45

(II.16).

Em se tratando do vetor de memõria foram introduzidas

duas modificações:

a) Inclt1iu-se um novo ponteiro para o vetor de (N+l) x N/2 pos!

ções que armazena a matriz hessiana inversa do problemay

b) Inclui-se outro ponteiro para um vetor de trabalho de N pos!

çoes.

O mapeamento de memõria ficou ampliado, totalizando ag~

ra treze ponteiros, cujas posições são vistas na• Figura

(II.17).

A grande diferença entre as duas versoes estã no fato

de que na segunda a busca-linear e féita sobre o Lagrangeano do

problema e não sobre a função objetivo. Consequentemente, e pr~

ciso avaliar o gradiente das restrições a cada iteração, o que

nos obriga a utilizar uma busca-linear com derivadas jã desen­

volvida . anteriormente. Neste caso, a economia esperada em nao

avaliar o gradiente das restrições e perdida mas, intuitivamen­

te, os resultados devem melhorar devido a estas informações.

II.9 - RESULTADOS NUMERICOS

As versoes implementadas foram aplicadas a vãrios pro­

blemas não-lineares e mostraremos aqui alguns resultados. Em to

46

dos os problemas analisados o ponto inicial era viãvel e o cri­

terio de parada utilizado foi o numero de casas decimais corre­

tas no valor da função objetivo no ponto 6timo. Os testes foram

executados no microcomputador SCOPUS-ClO com microprocessador

Z80 e em precisão simple;,

Os problemas foram retirados do livro de

[ 21 } e são apresentados no Apendice:

Problema 22: Objetivo não-linear e duas restrições

res. Dimensão dois.

SCHITTOWSKI

não-linea-

Problema 35: Não-linear com dimensão tres. Quatro restrições nao

lineares.

Problema 43: Objetivo não-linear de dimensão quatro e tres res­

trições não-lineares.

Problema 44: Objetivo não-linear com dimensão quatro e dez res­

trições lineares.

Utilizamos nas tabelas com os resultados, a

nomenclatura:

NF:: numero de avaliação da função objetivo

NG numero de avaliações das restrições

seguinte

NDF: numero de avaliações do gradiente da função objetivo

47

NDG: Niimero de avaliações do gradiente das restrições

FV : Valor da função objetivo

Problema 22

ti F NG tlDF NDG

Versão I 8 l 6 8 l 2

Versão I I 7 l 4 7 l 4

Problema 35

tff NG NDF fWG

Versão I 8 32 8 28

Versão II 6 24 6 24

Problema 43

tff IJG IIDF NDG

Versão I 18 54 30 30

Versão I I l 5 45 l 5 45

FV

l. 000

l . O 00

FV

O • 111

O. 111

FV

-43.999

-43.999

48

Problema 44

NF NG rrnF rrnG FV

Versão I 20 200 20 100 -14.999

Versão I I l 6 160 l 6 160 -14.999

II. 10 - CONCLUS~O

A implementação computacional se apresentou de forma

eficiente como era esperado. O procedimento de busca-linear, a~

sim como o de avaliação do passo inicial, se comportaram de for

ma muito eficiente nos exemplos considerados, tendo sido, em to­

dos os casos, pequeno o numero de avaliações de funções e deri­

vadas. Podemos di.zer que o algoritmo de busca unidimensional e

robústo e cónfiãvel, nao tendo apresentado problemas de diver­

gência ou geração de configurações inviãveis.

Porem ainda hã necessidade de um trabalho numérico mais

apurado, nao sono que tange ao numero de problemas testados

mas tambêm ã qualidade dos mesmos na demonstração de caracterís

ticas específicas como estabilidade. Não conseguimos reproduzir

os resultados obtidos nos trabalhos de HERSKOVITS [ 16], l 171

talvez devido ã falhas de programação ou ao tamanho da palavra

de micro-computador utilizado, sendo portanto necessãrio execu­

tar os mesmos testes, posteriormente, em um computador de gran­

de porte:·

49

Uma vez que o algoritmo necessita de um ponto inicial

viãvel, e preciso um procedimento de pre-otimização com o intui

to de viabilizar o processo. Existem metodos com esta função,

como por exemplo GARCIA-P1'\LOMARES [ 23], e sugerimos que pesqui-

sas futuras sejam feitas no sentido de obter uma

viãvel ã medida que se minimiza a função objetivo.

configuração

h (t)

REGIÃO ADMISSÍVEL .1 t

Fi~. II.l

h ( t )

h1

{o)

1. REGIÃO AOMISSÍVEL t

Fig. 1I.2

h ( t )

TESTE DE

DERIVADA

REGIÃO ADMISSIVEL

Fin,. 11.3

•

1 1. 1

t

~ ( t )

h ( t )

II m

1~ RI .1. RlI R IlI t

Fig. !1.4

h ( t l

I

, .

RESTRIÇÃO LIMITANTE

TESTE OE FUNÇÃO

TESTE OE

DERIVADA

11

Fin,. II.5

•

]l

t

h ( t)

TESTE CE

CUl~AI •

I

FLUXOGRAMA BÁSICO

INICIO

CALCULAR

T~

..._ CALCULAR h

0

(t) .........

h'0

1t) ~-1 . --.....:::::.,.,.---

! !~ ' ' ·:-,....,

FcUNÇÃO ? o{RIVADA ?

RESTRIÇÍ.0 LIIIIT(

h (t l

FIM 1 •

f ::~~F~: r':r..;;S_-< ;:;~s/6h 51<

Ll----''--1~,_--J-----\......ba._..-1--+---0------!C-,

N N t INTERPOLAR EXTRAPOLAR

o o PASSO Fig. ; l. 7PASSO

Fi~. II.G

h ( t )

TESTE DE

DERIVADA

I ][

5G -·

Fig. II.7

RESTRIÇÂ9, LIMITE

h ( t }

m

h ( t)

TESTE DE

DERIVADA

I ]I

RESTRIÇÃO LIMITANTE

Fig. !1.8

o

h ( t )

][

t

FLUXOGRAMA COM RESTRIÇÕES

INICIO

CALCULAR

T~

t -t~

CALCULAR h ( t 1 h' ( t l

SATISFAZ TESTE DE

RESTRIÇÕES ?

N

SATISFAZ TESTE DE FUNÇÃO?

N

INTERPOLAR FUNÇÃO TF-T

INTERPOLAR RESTRIÇÃO

TG-T

T, MIN (T,G,TF)

s

s

SATISFAZ s TESTE DE FUNÇÃO ?

N

INTERPOLAR FUNÇÃO

T F *'::' + co

Fig. Il.'l

SATISFAZ TESTE DE

DERIVADA ?

SATISFAZ TESTE DE BANDA?

N

EXTRAPOLAR FUNÇÃO TF-T

EXTRAPOLAR RESTRIÇÃO

TG-T

T, MIN (TF,TG)

s FIM

CALCULAR

T~

T-T~

CALCULAR

h ( ti h

0

( t)

SATISFAZ TESTE OE

RESTRIÇÃO?

N

TH-T

SATISFAZ TESTE DE

FUNÇÃO?

N

INTERPOLAR FUNÇÃO TF-T

INTERPOLAR FUNÇÃO "

TG-T

T• MIN (TF,TG)

FLUXOGRAMA COM DERIVADAS

SATISFAZ , s TESTE OE

FUNÇÃO?

N

TF-T

INTERPOLAR FUNÇÃO

s

J:"in II 10 . ',_,. .

SATISFAZ

TESTE OE

DERIVADA?

N

SATISFAZ TESTE DE

BANDA?

N

TH , O

N

T > TH

N

TL-T

EXTRAPOLAR FUNÇÃO TG-T

EXTRAPOLAR RESTRIÇÃO TG-T

T• IIIN (TF, TG)

s

s

s

s

FIM

TH-T

TL,-TH TH-T

t

INICIO

CALCULAR

T~

TL-o TH-o r-o TA-o T- rfl

CALCULAR h ( t) h' ( t )

'SATISFAZ• TESTE DE

RESTRIÇÃO ?

TA-TH

TH-T

N

SATISFAZ TESTE DE

FUNÇÃO?

N •

INTERPOLAR FUNÇÃO TF-T

I, 1

N

r-1

INTERPOLAR RESTRIÇÃO

COM DERIVADAS TG-T

T,MIN (TF,TG)

G,Q., ,,;.,, , ',5,' .

FLUXOGRAMA SEM DERIVA DAS

SATISFAZ s SATISFAZ s TESTE TESTE OE

OE FUNÇÃO J , OÉRlVAOA?

N N

TA-TH SATISFAZ s TH-T TESTE OE

r-1 SANDA?

N

INTERPOLAR s FUNÇÃO

TH, O

N

T> JH s

N

TA- TL

TL -T

s EXTRAPOLAR TF - + CI) FUNÇÃO

TF-T

I , 1 s

N INTERPOLAR

s RESTRIÇÃO r-1 POR PONTOS

TG -T

N EXTRAPOLAR RESTRIÇÃO

COM DERIVADAS TG-T

T' MIN (TF,TG)

Fi9. TI.11

FIM

TH-T

TA-TL TL-TH TH-T

EXTRAPOLAR RESTRIÇÃO

POR PONTOS TG-T

FLUXOGRAMA - VERSAO SEM QUASI- NEWTON

INi°CIO FLUXOGRAMA PAR-At?JfS O INICIAL

INICIO

INTERPOLAR RESTRIÇÕES

NÁO • LINEARES • ~ TG, min {tiJ

IN!ERPPLAR FUNÇAO OBJETIVO

ACHAfl TF

. '

INICIALIZAÇÃO E ESCOLHA

DE PARÂMETROS

ANÁLISE 00

PROBLEMA

CÁLCULO l>A DIREÇÃO DE DESCIDA

• 1 1 NUMERO 5 TMAX , O< TG

DE RESTRIÇÕES 1---,---1~..,, 0<:-"->-,-I --, LINEARE~, O ? CAl;ilO

• IN PASSO INICIAL

' ACHAR jT~AX A TRAVES

DAS RESTRIÇÕES . LINEAllES

"

FIM

BUSCA llNUR

SATISFAZ 'T!STE CE PARADA 1

$

Fii g. 1(1. l 2FII.I

1'. Fig. -!I.13

62

FLUXOGRAMA -VERSÃO SEM QUASI· NEWTON

( INICIO

INICIALIZAÇÃO E ESCOLHA

OE PARÂMETROS

ANÁLISE 00

PROBLEMA .

CÁLCULO DA DIREÇÃO DE DESCIDA

CÁLCULO DO

. PASSO INICIAL

BUSCA LINEAR

x •• , ' x. + ,.d.

N SATISFAZ TESTE DE PARADA ?

s

( FIM

Fig. II.13

X X MIN

X1 X2 . . . XN XMIN XMIN . . . . . .

1 2

' '

N1 N2

d 0 K-1

d(!) d(2) . . . . . . d(N) K-1

( 1) OK-1

(2) OK-1

. . .. . ..

N6 N7

,

MAPEAMENTO DE MEMORIA

X MAX g L e f (X)

XMIN XMAX XMAX . . . . . . XMAX 91 92 . .. . .. f 17(1) v<21 v'3,

N ' 2 N g, 91 g,

N3 N4 N5

/.. -

(NF) OK-1, Á1 Á2" Á3 . . . ÁNF An A12 A22 . - . A "' 02 03

FNFN

1 1

NB N9 N10

d' F. F. ••• NF+I MAX MAX

1 2

V (

. . .

. . .

...

0NF

FMAX NF

. . .

{!> 1

1 l

Ntt

v~', vl21 v\51

~2 {!>3 ...

(!>NF e,

ATUALIZAÇÃO OOS PARÂMETROS

ri e~

SO HÁ RESTRIÇÕES

OE IGUALDADE ?

s

DECOMPOR A POR CHOLE S K 1

ACHAR TERMO INDEPENDENTE

(3 : - A'tif

HÁ RESTRIÇÕES

DE IGUALDADE ?

s

(!> = f-,+g'

FLUXOGRAMA PARA CÁLCULO DA DIREÇAO

=

s

ACHAR

VETOR~ OE SATURAÇÃO

~ é NULO ?

s

Fig. Il.15

N

CALCULAR

Áo

CALCULAR

do

CALCULAR

f

f .. NULO ?

s

CALCULAR

Á

CALCULAR

d

FIM

(j 5

FLUXOGRAMA - VERSAO QUASJ - NEWTON

N

1N(c10

INICIALIZAÇÃO E ESCOLHA

DE PARÂMETROS

ANÁLISE DO

PROBLEMA

CÁLCULO DA DIREÇÃO DE DESCIDA

CÁLCULO DO

- PASSO INICIAL

BUSCA LINEAR

COM DERIVADAS

ATUALIZAÇÃO OUASI • NEWTON

SATISFAZ

TESTE DE PARADA

s

FIM

Fig. ll.lG

X X MIN

X, X2 X3 ... XN X, X2 X3 . .. XN MIN ,1N MIN MIN

NI N2

0 K-1

OK-1 0 K-1 . . . OK-1 ,< 1 ..<2 ,(3 .. . . ÁNF

' NS N9

~

MAPEAMENTO DE MEMORIA

X MAX g· e f l (X) "

x, X2 X3 x. f (K) v'' v(2l v1,1 v, . . . g, 92 g, . .. g, 91 i.1 ... MAK MAX .. , N3 N4 N5

AUXILIAR -

A11 A,2 . . . ... A 0, 02 0, . .. 0NF NFNF

1 1

N10 Nl1 Nt2

d' d' d~ · · · d'N Fu., FMAx · • · · · • FMAX . 1 2 ~ 1 2 NF

Ntt N12

1 1

1 1 1

Hn

N6

r;,

N13

H

H12 .. . . ..

~2 (!>, . ..

d

HNN d, d2 d, . .. d.

N7

-~NF -

67

CAP1TULO III

DESENVOLVIMENTO DE UM ALGORITMO DE DIREÇUES

VIÃVEIS PARA PROGRAMAÇÃO QUADRÃTICA

III.l - INTRODUÇÃO

Nos capitulas anteriores estudamos o algoritmo de dire

çoes viãveis para programação não-linear e vimos que uma de

suas vantagens e a viabilidade permanente. Em qualquer ponto do

processo de otimização, a solução, mesmo não sendo ôttma, e tec

nicamente viãvel, sendo esta caracteristica especialmente impo~

tante em problemas de engenharia.

Uma das classes dos problemas de programaçao matemãti­

ca e o problema quadrãtico que definimos como:

Minimizar l xTQ T IR n - X + C X, X E

2 a~x Sujeito a: b. < o; i = 1 , ... ' m (III.l)

1 1 T b. o. i m+l aix = = ... m+p

1 ,

Alguns fenômenos econômicos, estatisti cose de engenha­

ria podem ser modelados da forma acima; como por exemplo a mini

mização do funcional de energia de uma estrutura restrita ã de­

formaç3es p~e-determinadas.

Obviamente, os problemas quadrãticos representam uma

pequena parcela, apenas dos objetos de estudo da programação ma

Gb

temãtica, parecendo, ã primeira vista, ser de pouco interesse o

desenvolvimento de mitodos especfficos e soffsticados para sua

solução. Pori~ atravis de uma ticnica chamada ''Programação Qua-

dritica Sucessiva'', problemas não-lineares podem ser tràtados

resolvendo-se uma sequincia de sub-problemas quadrãticos, just!

ficando,,assim o estabelecimento de mitodos mais eficientes.

Vãrios sao os algoritmos existentes para solução de

problemas quadriticos entre os quais GOLFARB e IDNANI [ 15] que,

partindo do ponto Õtimo irrestrito, engloba uma a uma as restri

çoes violadas e calcula uma direção tal que a viabilidade dual

seja mantida e a primal seja obtida passo a passo. A viabilida-

de primal 50 e obtida ao se atingir o.ponto Õtimo, o que e f e i ··

to de forma exata, ou seja, em um numero finito de iterações

GI11 e MURRAY [ 14] nos mostram um processo que utiliza estrati­

gia de conjunto ativo, no qual partindo de um ponto inicial es-

tacionãrio avalia-se, atravis do gradiente projetado sobre o

plano tangente ãs restrições ativas, a direção de descida da

função objetivo. Com base nos multiplicadores de Lagrange deter

mina-se as restrições que serão retiradas e inclufdas no conjun

to ativo chegando-se ã solução tambim em um numero finito de

iterações.

Nossa proposta i desenvolver um algoritmo para progr~

maçao ~uadrãtica baseado ~os moldes do processo não-linear apr!

sentado nos capftulos anteri~res.

69

Desta forma, pretendemos um algoritmo de direções viã

veis que tenha convergência assintõtica e independência da velo

cidade de convergência em rela~ão ao niimero de restrições do

proble~a. Isto implica em dizer que o algoritmo apresentarã uma

eficiência crescente quando comparado a mêtodos de convergência

finita a medida que aumenta o niimero de restrições do problema.

No Capitulo III serao apresentadas as três versoes do

algoritmo que podem ser consideradas extensões dos mêtodos do

gradiente, quasi-Newton e Newton. ~o Capitulo IV, testes numêr!

cos acerca da estabilidade e convergência serão realizados com

as três versões.

III.2 - DESENVOLVIMENTO DE UM ALGORITMO DE DIREÇÕES VIKVEIS PA­

RA PROGRAMAÇ~O QUADRKTICA

Nesta seçao propomo-nos a estabelecer um algoritmo se-

gundo os moldes definidos na introdução deste capitulo. Para

. simplificação da exposição, restringimo~nos ao problema quadrãt!

cosem restrições de igualdade mas o processo pode, e serã, ex­

tendido a este caso facilmente. Trataremos então, do problema:

min f(x) 1 = - xTQx + CTx

2

sujeito a: g i (X) T

bi o. i 1 = a.x - < = ... m l

,

Se definimos de maneira anã.loga ao Capitulo Ias matri

zes:

70

- A como contendo em suas colunas os vetores a. nxm 1

- b como um vetor de Rm, contendo os termos independentes bi.

O problema fica:

min f{x) = 1 T - X QX + CTx 2

(III.2) sujei to a: T A .. x- b < o

- . k Precisamos gerar uma sequencia {x} de for~a que

f{xk+l) < f{xk) e alem disso ê necessãrio que esta sequências~

ja sempre viãvel e que a cada iteração o ponto xk esteja mais

pr6ximo de satisfazer a condição de Kuhn-Tucker segundo a defi­

nição (I.4). Definindo uma iteração do tipo:

m I (III.3)

i = 1

onde Bk ê uma matriz simêtrica e positiva definida que influen­

cia a convergência do mêtodo e chamando dk = xk+l - xk de dire­

çao de descida,. temos:

- 1 [ dk = - Bk Vf(x) + m I

i = 1 (III.4)

Uma vez que a direção de descida ê baseada no sistema

de Kuhn-Tucker torna-se necessãrio fazer a hip6tese de regular!

dade pontual, segundo a definição (I.2). Não podemos, atravês da

Equação {III.4), calcular a direção dk se~ avaliar os multipli-

71

cadores de Lagrange, o que so pode ser feito si definirmos m

equaç5es alem das n definidas anteriormente (Equaçio III.4}.Ch!

maremos a estas equaç5es de ''regra de atualizaçio dos multipli­

cadores de Lagrange", que devem ter as caracterTsticas abaixo:

a) Como no ponto de Kuhn-Tucker os multiplicadores de Lagrange

devem ser positivos para as restriç5es ativas, e preciso que

nos aproximemos das restrições com esta caracterTstica. Des

ta forma:

Ài <O+ dk se afasta da restrição i

Ài >O+ dk se aproxima da restriçio t.

b} A direção dk deve ser sempre viãvel. Então quando uma restri

çao for ativa, ela deverã formar um ângulo de, no

90° com o gradiente da restrição.

mTnimo,

Uma das possTveis regras para a atualizaçio dos multi­

plicadores de Lagrange pode ser dada pela expressão:

dr. Vg;(x) = Ài 9;(x); i = 1, ... , m (III.5)

O produto dr . Vg;(x) permite-nos verificar o afasta­

mento ou aproximação em rela~ão as restrições, e como xk e viã­

vel e gi(x) e negativo, o produto escalar tem sempre o sinal de

À; da forma:

72

T - se Ài >O+ dk . Vgi(x) > O, dk se aproxima da restrição i

- se Ài <O+ dr . Vgi(x) < 0, dk se afasta da restrição i

Desta maneira a equaçao (III.5) respeita a condição a.

Por outro lado, se uma restrição for ativa, gi(x) = O,

o produto escalar, se anula, obrigando dk a ser paralela ã res­

trição. É, portanto, respeitada a condição b e a equação(Ill.5)

se presta bem para o cãlculo dos multiplicadores de Lagrange.

Neste ponto introduzimos o parâmetro ri na equação (111.5) e

veremos posteriormente sua influência na velocidade de conver­

gência e estabilidade do algoritmo. Desta forma:

- r. 1

1 • • • m (Ill.6)

= l . . . m

No Capitulo IV sera feito um estudo do parâmetro r 1 e

sera dada a regra de atualização do mesmo, para acelerar a con­

vergência do processo a um ponto de Kuhn-Tucker.

Com o objetivo de tornar a notação mais compacta, defi

nimos as matrizes:

Rmxm como diagonal contendo os parâmetros r. ' 1 i ~ 1 • • • m

Gmxm como diagonal contendo as restrições gi (x); i = 1 ... m

73

Assim a equaçao {III.6) pode ser escrita da forma:

{III.?)

sendo À o vetor de multiplicadores de Lagrange. Do sistema li­

near formado por {III.4) e (III.7) podemos achar a direção de

descida dk e o vetor Às Rm.

(III.8)

(III.9)

r interessante notar que a direção de descida d~ estâ

contida no espaço tangente ãs restrições ativas, devido ao câl­

culo dos multiplicadores de Lagrange. Defiriindo P = - ·sk 1 [I

- A(ATBk 1A - RG)-l ATBk 1] então:

dk = + P Vf(x)

Pê o operador que projeta o gradiente sobre o plano tangente

desde que Bk seja igual ã identidade e as restrições sejam ati­

vas. Neste caso o operador Pê idêntico ao do mêtodo do gradie~

te projetado como pode ser visto em LUENBE RGER[ 19].

Atravês da expressao (III.4) podemos ver que a direção

dk e o oposto do gradiente do Lagrangeano rodado pela matriz

Bk e, desta forma, ao atingirmos um ponto de Kuhn-Tucker a dire

ção se anula interrompendo o processo.

74 •

Obtida a direção dk pode-se caminhar sobre esta uma de

terminada distância ou passo tk e encontrar o próximo ponto da

sequência:

(III.10)

Para determinar o passo tk minimizamos o Lagrangeano sobre a di

reção de descida, mantendo a viabilidade estrita.

Definindo a função objetivo na direção dk' como:

h ( t) -

O processo de busca-linear seria:

m minimizar L(t) = h(t) + l ),. G i ( t)

t i = l l

Sujeito a: G i ( t) < o. i = l ... m ,

onde G i ( t) - gi(xk + tdk)

Se permitirmos que o passo tk seja tal que sature uma

restrição, teremos alguns prejufzos ~o algoritmo, tais como:

a) a direção dk+l serã paralela ã restrição ativa e a vantagem

do processo em caminhar pelo interior do conjunto de pontos

viãveis e perdida.

75

b) Se a restrição saturada for ativa no ponto Õtimo, convergir~

mos para este, porem do contrãrio chegaremos a um ponto esta

cionãrio que não e de Kuhn-Tucker.

Para impedir que as condições acima ocorram e preciso

evitar que haja uma saturação precoce das restrições, ou melhor

dizendo, manter a viabilidade estrita. Com este objetivo, intro

duzimos o parãmetro y E (O, l) que colocarã barreiras no inte­

rior do conjunto de soluções viãveis impedindo a saturação pre­

coce das restrições.

Então a busca-linear fica:

minimizar L(t) t

sujeito a: Gi(t) < y Gi(D); i = l .•. m

Desta maneira o maior passo permitido é aquele que au­

menta o valor da restrição de no mãximo (l-y) porcento,

mos:

donde:

Achando o passo tL para minimizar o Lagrangeano, te-

dL(t)=O= dt

m E

i = l

7G .

então:

t =

T T dk(Qxk + e + AÀ)

dk Q dk

mas

Qxk + CT + AÀ = VL(xk, À)

dT VL(xk, À) k t = dkQdk

como dk - l VL(xk, À ) , temos = - E\

dT Bk dk tL

k = df Q dk k

(III.11)

Este passo nao e o adotado na busca-linear pois pode

violar alguma restrição, sendo preciso determinar o passo mãxi­

mo permitido pelas barreiras impostas por y.

Gi(t) = y Gi(O); i = l ..• m

T +tidk) b. T b . ) ai ( X k - = y(a. xk -

l l l

T dk (y l ) T

b i ) t. a. = = ( a . xk -l l l

t. T dk (y - . l ) gi (xk) a . =

l l

mas por (III.6), temos:

77

t = ( 1 -y l · À > O· 1·. = l m i - , i ' ••• r. À -.l l

(III.12)

o passo efetivo a ser actotado~e o mínimo entre os passos calcula

dos anteriormente:

Estamos agora prontos para estabelecer o algoritmo, o

que sera feito na seçao seguinte;

IlI.J - ESTABELECIMENTO DO ALGORITMO B~SICO

Anteriormente, mostramos o raciocínio usado no desenvol

vimento do algoritmo de direções viãveis para programação quadri

tica. Nesta seção estabeleceremos o processo de forma resumida,

a começar pelas hipóteses assumidas.

l) Hipóteses:

a) O ponto inicial x0

deve ser viãvel e interior a n: x0

s n

b) Todo ponto do conjunto viãvel n deve ser regular segundo a

definição (I.2).

c) A Hessiana

yTQy > O V

da função objetivo n y#O,yslR

deve ser definida positiva:

78

2) O algoritmo:

PASSO O: Escolher um ponto inicial x0

E n, Bk ri > O; i = l ... m

e y E (O, l)

PASSO l: Calcular a direção dk:

e os multiplicadores de Lagrange,

Se ªk = O, parar o processo.

PASSO 2: Calcular o passo tk:

PASSO 3: Calcular o próximo ponto da sequência {xk}

X = Xk + tk dk k+I

Voltar ao passo l.

O algoritmo bãsico poderã dar lugar a vãrias versões,

dependendo da escolha da matriz Bk' tendo taxas de convergência

certamente diferentes. Consideraremos aqui três casos distintos,

79

a saber:

a) Bk = I, chamaremos esta forma de "versão I"

-1 b) Bk = Hk , onde Hk ê uma atualizaçao quasi-Newton que aproxima

a inversa da hessiana da função objetivo a cada itêraçáo. Cha

maremos a esta forma de "versão II''.

c) Bk = Q, que sera chamada "versão III''.

Notamos que as três versoes definidas podem ser consid~

radas como extensões dos métodos do gradiente, quasi-Newton e

Newton, respectivamente, quando aplicados a problemas irrestri­

tos.

III.4 - EXTENS~O DO ALGORITMO PARA RESTRIÇÕES DE IGUALDADE

Como jã foi dito na seçao III.2, os resultados do alg~

ritmo jã desenvo·lvido para restrições de desigualdade poderão

ser extendidas ao problema geral de programação quadrática:

minimizar f{x) l = - xTQx + CTx

2

sujeito a : g i (X) T b. o; i 1 (III.13) = a.x - < = ... m l l

g i (X) = aTx bi = o. i = m+l . .. m+p l •

Seguindo o mesmo raciocfnio a tlireção de descida e:

80

m+p I

i = l À- Vg.(x)]

1 1 (III.14)

A regra de atualização dos multiplicadores de Lagrange

permanece a mesma para as restrições de desiguald~de, mas em re­

lação ãs restrições de igualdade é preciso estabelecer uma condi

ção que determine sua saturação. Aplicaremos a regra abaixo, si­

milar ao método de Newtón, para resolução de sistemas lineares:

dT . Vgi(x) = - r. "i gi(k); r- > o. i = l . .. m k 1 1 ' (III.15)

aT . 17gi(x) = - gi(x); i = m+l . .. m+p (III.16) k

Porém, neste caso a direção dk conforme definida ante­

riormente, em geral, nao e mais de descida em relação a função

objetivo do problema quadrãtico. Isto se deve ao fato de que pa­

ra conseguir a saturação de uma restrição de igualdade pode ser

necessãrio aumentar o valor da função objetivo. Poder-se-ia con-

tornar esta questão utilizando os resultados de MAYNE e POLAK

[2 º 1 que definem uma função auxiliar que engloba as restrições

de igualdade e o problema original passa a ser restrito apenas

por desigualdades. Preferimos, ao invés disto, realizar a busca­

linear com base no Lagrangeano do problema uma vez que dk e dire

ção de descida em relação ao mesmo.

Somando as equaçoes (III. 15) e (III. 16) e escrevendo de

forma compacta, obtemos:

(III.17)

81

onde ge _ (O, O, O, ... g(x), g(x) •••• g (X) )

m+p m+I m+Z

Resolvendo o sistema linear formado por (III.14) e

(III.17) chegamos ãs expressões que permitem calcular a direção

de descida e o vetor de multiplicadores de Lagrange:

dk = - Bk 1 [vf(xJ-A(ATBk 1A-RG)-l(-ATBk 1vf(x)+ge)}

(III.18)

Para acharmos o passo tk efetivo da busca-linear utili

zamos novamente as funções h(t) e Gi(t) definidas anteriormente,

da forma:

por:

minimizar m+p

L(t) = h(t) + I Ài Gi(t) · i = 1

sujeito a: Gi(t) .::_YGi(OJ; i = 1 ... m+p

O passo para minimizar o Lagrangeano pode ser calculado

dL{ t) =

dt (III.20)

que e a mesma expressao para o problema restrito apenas por de­

sigualdades.

82

E preciso achar o passo mãximo permitido sem violar as

restrições, desta forma:

t. = 1

(y-1) gi(x)

ai . d k (III.21)

Para as restrições de desi~ualdade podemos ver pela

equaçao {III. 15) que:

dã:

- r. 1

l . . . m

Substituindo em {III.21), temos:

t. = (l-yJ; i = 1 1 ••• m, Ài > O

Para as restrições de igualdade a equaçao {I1I.l6J nos

T ªi . dk = - gi(x); i = m+l ... m+p

donde substituindo em (III.21), temos:

ti = {l-y) = constante; i = m+l •.. m+p

83

Poderfamos tomar y = O para as restrições de igualdade

e aumentar o passo para a saturação destas restrições, porem is­

to retardaria o processo uma vez que o algoritmo não se comporta

bem quando prõximo das fronteiras do conjunto de soluções viã­

veis.

Da mesma maneira, o passo efetivo da busca-linear sera

o mínimo dos passos calculados anteriormente:

Podemos, então estabelecer o algoritmo:

1) Hi põteses:

a) O ponto inicial x0

deve ser viãvel e interior ao conjunto de

soluções viãveis extendido b

x0 E b, onde b ={x/gi(x) < O; i = 1 ... m+p}

bJ Todo ponto x E b e regular segundo a definição (I.2).

c) A hessiana da função objetivo deve ser positiva definida:

yT Q y > O; V y I O, y E Rn

84

2) O algoritmo extendido:

. PASSO O: Escolher um ponto x

0 E 6, Bk E Psym'

r. > O; i = 1 •.. m l

yE(O,l)

PASSO 1: Achar a direção de descida dk'

e o vetor de multiplicadores de Lagrange À,

PASSO 2: Achar o passo tk:

tk = inf{tl-y); i = l. .. m; Ài > O, (1-y), ri \

PASSO 3: Calcular o pr5ximo ponto da sequincia {xk}:

Voltar ao Passo 1.

85

O algoritmo quadrático desenvolvido serã implementado e

testado no prõximo capitulo, onde tambêm serão feitas algumas m~­

dificações com o objetivo de acelerar a convergência do mesmo.

86

CAPITULO IV

ESTUDO NUMERICO DO ALGORITMO DE DIREÇÕES

VIAVEIS, PARA PROGRAMAÇAO QUADRATICA

IV.l - INTRODUÇAO

No capítulo anterior mostramos as ideias e definimos o

algoritmo de direções viãveis para programaçao quadrãtica. Vimos

que para garantir sua convergencia foi preciso definir parame-

tros alheios ao problema quadrãtico como ri e y e seria interes­

sante derivar uma regra de atualização para os mesmos de forma a

acelerar o processo. A redução do esforço de cãlculo e a verifi­

cação do comportamento do algoritmo em problemas instãveis tam­

bem são importantes do ponto de vista de implementação computa­

cional e serão desenvolvidos neste capítulo.

Nos estudos que realizaremos aqui, proporemos vãrias

formulações diferentes para determinação der. e y e faremos tes 1 -

tes numericos que possam nos dar uma ideia, pelo menos media, da

eficiência de cada uma delas. Nestes testes utilizaremos a ver­

são III do algoritmo por ser a que apresenta a melhor convergên­

cia. Isto não altera qualitativamente, os resultados pois as re­

gras de atualização não dependem da iteração mas sim da distân­

cia ao ponto õtimo. Em todos os testes usaremos o mesmo criterio

de parada, definido abaixo:

87

m J !Vf(x) + I Ài Vgi (x) 11

E< o.05 onde E= ~~~~~~~1~=~1~~~~~~ m

[[vf(xJII + Jli~l \ Vgi(x)]I

Para a realização dos testes definiremos os

problemas quadrãticos:

PROBLEMA IV. l:

7 restrições e 2 variãveis

f (X) =

y < 2.5

y - X < 'e.

X + y < 4

X < 1 • 5

y - X > Ü

X + y > l

y - 4x <

seguintes

88

PROBLEMA .TV.2:

l 5 restrições 5 .-e var1aveis

5 4 f(x) = 5 I x? - I X; . xi+l

i = l l i = l

- l 6 X l + 2x 2 + X4 + 40 > o

- 3.5x 1 + 2x 3 + 0.25 > o

zx 1 - 4x::i + l > o

- xl - Xz - X3 - X4 - X5 + 40 > o

- xl - 2Xz - 3x 3 - zx 4 - X5 + 60 > o

xl + 2x 2 + 3x 3 + 4x 4 + 5x 5 - 5 > o

xl + Xz + X3 + X4 + X5 - l > o

x 1 > O

x 2 > Ü

X~> Ü

PROBLEMA IV,3:

13 restrições e 8 variiveis

8 f(xl = I

i = l

8 í.

i = l

8

l i = l

X. < 30 1 -

X. > 2 1

8

í. i = l

89

+ X > ., • 4 X 3 4 ~

PROBLEMA IV.4:

13 restrições e 10 variãveis

f (X) = 2

y. i = j

onde: H = -1, ji-jj = 1

8

}: xi < 30 i = l

O, caso contrãric

9 ()

91

X3 < 22

8

I xi > 2 i = l

Este problema foi introduzido aqui devido ãs suas carac

ter1sticas de instabilidade, pois de acordo com o valor de y o

numero de condiçâo pode atingir valores muito altos. A origem

deste problema e o trabalho de ARRIOU [ 1] e o nümero de condi­

çao e dado por:

"max = y + 2cos(rr/ll) À y-- 2cos(rr/11) min

Escolhemos y = l.Y6 e o numero de condição de 94.7.

IV.2 - ATUALIZAÇ~O DO PARÃMETRO GAMA (y)

Vimos no cap1tulo anterior que, devido ã regra de atua­

lização dos multiplicadores de Lagrange, não e util que uma res­

trição se sature pois, de acordo com a equação (III.6) a direção

de descida torna-se paralela ã restrição. Notamds, tam6em, que

todos os pontos gerados pelo algoritmo devem pertencer ao inte­

rior do conjunto de soluçóes viãveis e o parãmetro gama tem fun­

ção primordial neste sentido, Percebemos que gama e um limitante

92

do passo e quando tende ã unidade prejudica a velocidade de co~

vergencia do processo. Este deve manter a viabilidade estrita e

tender a zero ã medida que se aproxima de um ponto de

Tucker.

Kuhn-

Para determinarmos uma regra de atualização para este

par~metro procederemos a uma sirie de testes numêricos, como

abaixo:

a) Teste IV.l:

Neste teste estamos interessados em analisar a conver­

gência do algoritmo para alguns valores fixos de gama. Medire­

mos o numero de iterações necessãrios para gerar um ponto na vi

zinhança do ponto õtimo, e para isto escolhemos tres valores do

parâmetro ri e utilizamos três problemas definidos anteriormen­

te. Os resultados podem ser vistos abaixo:

Tabela IV. l - Problema IV. l

Yo r.

l 50 100 200

O. 7 . 18 . 20 23

O. 5 lo 11 l 3

o. 3 . 6 7 8

o. l 4 . . 4 . 5

o. o l 7 . 7 7 ' .

93

Tabela IV.2 - Problema IV.2

Yo r.

.... l 50 100 200

O. 7 27 57 -0.5 1 6 35 72

O. 3 1 2 25 51

O. 1 9 19 40

o.o, 9 1 8 36

Tabela IV.3 - Problema IV.3

Yo ri 50 100 200

O .7 1 6 18 20

O. 5 9 1 O 1 1

0.3 6 6 7

O. 1 4 4 4

0.01 3 3 3

Podemos ver que em todos os problemas os piores valo­

res de convergincia ocorreram para y = 0.7, independentemente de

ri, pois valores grandes do parâmetro nos levam a passos peque­

nos. A adoção de valores pequenos acelera a convergincia -ate

certo ponto, porem valores próximos de zero permitem a satura­

çao precoce de restriç6~s. retardando o processo. Nesta situa­

çao passa-se a caminhar pela fronteira do conjunto de soluç6es

viáveis e perde-se a principal característica do algoritmo que

94

ê caminhar pelo interior. t, portanto, preciso evitar valores p~

quenos de gama, a nao ser na vizinhança do ponto Õtimo.

Concluímos do teste IV.l que gama deve assumir, de

início, um valor razoável que evite a saturação precoce deres-

trições mas seja tal que não diminua muito o passo da busca-

linear.e, ã medida que se aproxime do ponto de Kuhn-Tucker, te~

da a zero. Nosso problema reside agora na taxa de diminuição de

gama de forma a atingir valor nulo no ponto otimo. Poder-se-ia

uti.lizar qualquer recursiva do tipo:

Yk+l =yk. aonde a E (O, 1)

desta maneira: l im yk = O k-,.oo

Entretanto, ao invés de resolvermos o problema dopa­

râmetro gama, estamos criando uma nova variável. Alem disto, s~

ria interessante que a atualização dependesse, de alguma forma,

da convergência do algoritmo, o que não ê o caso da formulação

acima.

Sabemos que no ponto de Kuhn-Tucker do problema a

igualdade abaixo se satisfaz:

m Vf(x) + I

i = l À· \lg.

1 1 = o

Se achamos o modulo deste vetor e aplicamos a desi-

gualdade triangular de Schwartz para sua normalização, podemos

95

defi.nir o Tndice W(x):

m ] jvf(x) + I À· Vg.(x)II

1 1. . . . i = l

W (X) = ---------'--m-'-------[ [ Vf ( x) ! f +li l "i Vgi(x)]!

i = l

notar que: lim W(xk) = O k-+O,

e

(IV.l)

O indice W(xk) e uma medida da "distância" entre o po~

to xk e o ponto Õtimo do problema e uma vez que decresce conti­

nuamente em função da convergência podemos usa-lo para atuali­

zar gama. Sugerimos uma taxa de decréscimo linear ou quadrática

como:

onde y0

e o valor inicial de gama.

Como nao hã maneira teõrica de avaliarmos a melhor for

mulação, procederemos então a testes numéricos acreditando ser

muito pequena a diferença entre as duas.

96

b) Teste IV.2:

Nesta seçao faremos, de maneira anãloga a

testes com variação linear de gama da forma:

Os resultados sao:

Tabela IV.4 - Problema IV. 1

Yo r-

1 50 100

O. 7 11 1 3

0.5 8 9

0.3 6 6

O. 1 4 4

0.01 3 3

Tabela rv.5 - Problema IV.2

r. 50 100 Ya ·1

0.7 16 29 ..

O. 5 13 24

0.3 10 21

O.l 9 18

O.Ol 9 18 ' .

anterior,

200

1 4

10

7

5

3

200

55

47

42

38

36

97

Tabel.a IV.6 - Problema IV.3

Yo r. .. l . 50 100 200

O. 7 10 ll 13

D. 5 7 8 9

0.3 5 6 6

o. l 4 4 4

0.01 3 3 3

Podemos notar que a atualização linear do parãmetro g~

ma jã acelera em muito a convergência do algoritmo. Em certos

casos houve uma redução de 50% no numero de iterações em rela­

ção ao teste não atualizado de gama, como no problema IV.2 onde

para ri = 100, tivemos uma diminuição de 57 para 29 iterações.

Para compararmos a atualização linear com a quadrãtica procede­

mos ao teste IV.3.

c) Teste IV.3

Analisaremos a convergencia do algoritmo para uma atua

lização do tipo:

Os resultados estão nas tabelas abaixo:

98

Tabe·la TV.7· - Probl,ema IV. 1

r. . . 50 . · .. · .. 100 . 200 Yo . ,. .

. . .

O. 7 1 O 1 l l 3

0.5 7 8 9

0.3 5 6 7

o. l 4 4 5

0.01 3 3 3

Tabela IV.8 - Problema IV.2

Yo r.

l 50 100 200

O. 7 14 25 46

0.5 1 1 22 42

0.3 10 20 39

o. l 9 18 37

0,01 9 1 8 36

Tabela IV.9 - Problema IV.3

Yo r. . l. 50 . 100 200

O. 7 . 9 . .10 l 1

O. 5 7 7 8

0.3 5 .6 6

O,l 4 4 4

0.01 3 .. . . 3 3

99

Comparando-se o teste IV.2 e teste IV.3 podemos notar

que a atualização quadrãtica de gama nos leva a resultados lgv!

mente melhores que a linear. Para qualquer valor de ri e y0

re­

lativamente grande, obtemos uma reduçao util do número de itera

ções tornando justificãvel sua utilização.

Nos testes realizados anteriormente, notamos que o

fndice W(x) se presta bem para a atualização do parãmetro gama

de forma quadrãtica. Porem, analisando a função de gama de for­

ma detalhada podemos gerar uma atualização mais efetiva:

- Gama tem função primordial de evitar ~ue se perca a viabilid~

de estrita do algoritmo, pois se esta e perdida, pode-se sat~

rar uma restrição que não e ativa no ponto Õtimo, levando o

processo a um ponto estacionãrio.

Se tivermos certeza acerca das restrições ativas no

ponto õtimo, podemos permitir a saturação de uma delas, sem con

tudo prejudicar o processo. Desta forma, gama sõ cteverã exis-

tir, e ser atualizado, ate o momento em que estamos na vizinhan

ça do ponto de Kuhn-Tucker do problema, e isto serã

com base no fndice W(x).

detectado

Sugerimos, então, uma nova formulação para a atualiza-

çao:

100

d) Teste IV.4:

Atualizaremos gama da forma:

= o W(xk)

se < 0.05 W(x 0 J

Nas tabelas abaixo vemos os resultados:

Tabela IV. 10: Problema IV.l

Yo r; 50 100 200

0.7 10 l l l 3

O. 5 7 8 9

O. 3 5 6 7

o. l 4 4 5 .

0.01 3 3 3 .

Tabela IV.11:- Problema IV.2

r. 50 100 200 Yo .l ! • . .

0.7 . 13 23 42

0.5 . ll 20 39

0.3 10 19 38

o. l .9 .18 36

·º. o l 9 18 36

lo l

Tabela IV.12: Problema IV.3

r. 50 .100 200 Yo . l

O. 7 9 .. lO l l

0.5 6 7 8

0.3 5 6 6

o. l 4 4 4

0.01 3 3 3

Comparando com os resultados anteriores vemos que esta

formulação e bastante satisfatõria em acelerar a convergência do

algoritmo. Obviamente as conclusões aqui chegadas são uma me-

dia, uma vez que nos limitamos a alguns testes numericos ape-

nas, mas acreditamos que seja suficientemente boa para qualquer

problema quadrãtico. Desta forma, daqui por diante, serã sempre

utilizada a atualizaçao do teste IV.4.

IV.3 - ATUALIZAÇ~O DOS PARÃMETROS ri

Na seçao anterior desenvolvemos uma forma para a atua-

lização do parâmetro mantenedor da viabilidade estrita, gama. ',

Da mesma forma, tentaremos agora chegar a uma maneira razoãvel

de se atualizar os parâmetros ri, i = l •.. m que fazem parte

da equaçao para o cãlculo dos multiplicadores de Lagrange.

Na equaçao (III.6) definida no capftulo III nota-se

que ri, i = l •.. m existem no sentido de amplificar o produto

102

escalar dT~g 1 , tornando a direção de descida cada vez mais co­

linear com o gradiente da restrição. Sendo assim temos a idiia

intuitiva de que quanto maior ri, melhor seria a convergência do

algoritmo, uma vez que a direção dk se dirigiria mais diretamen

te ãs restrições com multiplicadores de Lagrange positivos. Ut~

lizar-nos-emos dos resultados do teste IV.4 para tirarmos algu­

mas conclusões e realizaremos ainda outros testes:

a) Teste IV.5

Assumindo y0

= 0.3 e reunindo os resultados do

IV.4 em uma única tabela, temos:

Tabela IV.13

r. f'I{ u l:l tMA I V . l IV. 2 IV.3 1

50 5 10 5

100 6 l 9 6

200 . 7 38 . 6

teste

Pode-se perceber que o aumento de ri, em qualquer pro­

blema, aumenta o numero de iterações pi orando a cconvergênci a do

algoritmo. Isto se deve ao fato de que um valor muito grande de

ri gera uma direção onde a influencia das restrições e pequena,

como explicado abaixo:

Pela equaçao (III.9) notamos que os multiplicadores de Lagta~

ge tornam-se pequenos ã medida tjue R aumenta, fazendo com que

103

a direção de descida se aproxime do gradiente da função obje-

tivo. Ao utilizarmos esta direção, minimizamos a quãdrica e

nao o Lagrangeano do problema, reduzindo a convergencia do

processo.

Na tentativa de buscar uma formulação para atualizar R

sentimos que, durante o andamento do algoritmo, duas situações

ocorrem:

1) O passo efetivo da busca-linear ê igual ao passo que minimi-

za o Lagrangeano. Neste caso não se caminha na direção dk

tanto quanto se poderia em relação ã viabilidade.

2) O passo efetivo da busca-linear ê igual ao passo mãximo per-

mitido pela manutenção da viabilidade estrita do processo.

Neste caso, caminha-se na direção dk o mãximo permitido mas

não se minimiza o Lagrangeano do problema.

Parace, então, ser o ideal que os dois passos se igua­

lem e isto depende do valor de R adotado, desta forma se usamos

a versão III do algoritmo, temos:

ti = (l-y) r. À • . 1 1

= 1

Se "e'' ê o fndice da restrição limitante do passo na

iteração "k'', igualando os dois passds, temos:

l = (1-y) r. · À

1 e

+ r. .]

104

= ( 1-y) ' = 1 • . • m

Podemos avaliar o desempenho desta atualização através

do teste IV.6:

b) Teste IV.6

Atualizamos r. da forma abaixo: l

r. = l

çao limitante

(l-y), i

À e do passo

= l ••• monde e e o índice

na iteração anterior.

da res tri -

Se Àe e muito pequeno precisamos limitar o valor de ri

adotando um valor mãximo Rmãx·

Ser. > R - + r = R -1 max 1 max

Consideramos y0

= 0.3 em todos os testes mostrados abai

xo:

Tabela IV.14

R - PROBLl:.MA IV.l IV. 2 IV.3 .. max -

50 4 8 .. 5

100 4 1

8 5

200 4 . 8 6

105

Sentimos uma grande melhora, através desta atualiza-

çao, principalmente no problema IV.2. Entretanto, analisando a

equação (III. 6) e fazendo ri Ài = 1, temos a equação do método

de Newton aplicado ã resolução da equação gi(x) = O.

Aproveitando-nos disto, podemos fazer ri yi = 1 para

multiplicadores de Lagrange positivos e estaremos obrigando o

algoritmo a se aproximar destas restrições. Igualmente, para

evitar valores muito grandes de ri' i = l ... m adotamos Rmãx

como seu valor mãximo,

r. = 1/;\. se À· > 1/R -1 1 1 max

O teste IV.7 nos mostra a convergencia do algoritmo p~

ra esta atualização.

c) Teste IV. 7

Da mesma forma que anteriormente, y0

= 0.3, procedemos

a seguinte atualização:

Se;\. < 1/R - então r. = Rma-x 1 max .1

Na tabela abaixo estão os resultados:

106

Tabela IV.15

R - PJ<UllU:.MA IV. l .. IV. 2 IV .3 max -50 4 4 3

l 00 5 4 3

200 5 4 3

comparando os testes IV.6 e IV.7 notamos melhora neste

último e passamos adotar esta formulação para a atualização de

R:

IV.4 - ESTUDO COMPARATIVO ENTRE AS VERSOES

No capítulo anterior foram definidas três versoes do

algoritmo quadrático e em duas delas havia a presença de matri­

zes importantes do ponto-de-vista de estabilidade numêrica, a

hessiana inversa e uma aproximação quasi-Newton da mesma. Quan­

do tratamos de problemas instãveis, a inversão da matriz hessi~

na pode ser fatal para o processo de otimizaçao, sendo necessã­

rio avaliar o comportamento do algoritmo e suas versões, nestes

casos.

Na versão·r, devido ã nao utilização da hessiana do

problema, espera-se que o algoritmo se comporte como o mêtodo

do gradiente projetad6, pois se assemelha muito a este quando

todas as restriç~es são ativas. Neste caso uma vez que Bk = I o

passo da busca-linear toma a forma:

107

Realizando testes com esta versao, chegamos a:

Tabela IV. 16

PROBLEMA ITERAÇÕES

I V. l lo

IV.2 l 5

IV. 3 9

: rv .4 l 4

Quando utilizamos a versao III o passo da busca-linear

passa a ser igual ã unidade e os testes nos dão os resultados

abaixo:

Tabela IV.17

PROBLEMA lTERAÇ/10

IV. l 5

IV. 2 . 6

IV.3 .. . 6

IV.4 *

* Este problema, devido as suas caracter1sticas de instabilida­

de, não pôde ser resolvido por esta versão.

103

Notamos que devido a nao utilização da hessiana inver­

sa na versão I o nümero de iterações cresce consideravelmente ,

mas em compensaçao o problema IV.4 foi resolvido, apesar de sua

instabilidade.

Como solução intermediãria entre estas duas versoes en

contra-se a utilização de uma aproximação da inversa da matriz

hessi ana, utilizada na versao II.

vãrias sao as formulações quasi-Newton conhecidas e,

em todas, a matriz que aproxima a hessiana inversa e simétrica

e definida positiva. BROYDEN ["J mostrou que todas as formula­

ções de posto dois podem ser agrupadas em uma fãm1lia, a partir

da variaç~o de 8 E R, da forma:

Hk-l + 8 • B

onde:

s = ( ( y ! Hk-1 Yk) vk VT k

vk pk Hk-l yk

= yk pk yk Hk-l yk

yk = Vf(xk) - Vf(xk-l)

109

Em particular se e= o temos a formulaçao conhecida como D.F.P.

e se e= 1, a chamada B.F.G.S.

Segundo FL~TCHER [ 12] a formulação BFGS e mais estãvel

e, por isto, nõs a utilizaremos:

Para todas as formulações quasi-Newton da família apre­

sentada acima, a matriz Hk+l sã i definida positiva ss Hk tambim

oi, e a condição abaixo se verifica:

Como, pela hipbtese feita na definição do algoritmo, a

matriz Q i definida positiia, então a condiçao se verifica -sem­

prepara qualquer passo da busca-linear. Sendo assim, a formula­

çao BFGS pode ser usada mesmo que o passo seja truncado por al­

guma restrição e os testes estão na tabela abaixo:

l l ()

Tabela IV.18

PROBLEMA .. .I.TERAÇ/10

IV. l .. 6

IV. 2 ll .

IV. 3 8 .

IV.4 9

Pode-se notar que os resultados sao melhores que a ver­

sao I porem piores que a versão III. A grande vantagem desta vei

sao e que nâo hã inversão da matriz hessiana, reduzindo o esfor­

ço e a instabilidade computacional, e alem disto, problemas ins­

tãveis podem ser resolvidos satisfatoriamente. Concluimos, en­

tão, ser esta versão a mais justificãvel de todas as definidas.

IV.5 - REDUÇ/10 DO ESFORÇO COMPUTACIONAL

Independentemente da versao do algoritmo utilizada, o

sistema linear dos multiplicadores de Lagrange, precisa ser re­

solvido a cada iteração.

Obviamente o esforço computacional e grande mesmo se

utilizando de metodos estãveis e eficientes como por exemplo a

decomposição de Choleski. Aproveitando-nos de uma característica

do algoritmo podemos reduzir o esforço computacional para ares~

lução do sistema. Sabemos que os multiplicadores de Lagrange são

função das variãveis do problema e que a cada iteração

seus valores tendendo ao õtimo. Se assumimos que estes

muclam

sofrem

uma pequena modificação a cada iteração, podemos nos utilizar de

111

valores da iteraçao anterior para uma estimativa inicial nesta

iteração e usar um mitodo iterativo para a solução do sistema de

multiplicadores de Lagrange. Dos metodos iterativos · eficientes,

o de mais simples implementação e menor nümero de operaçoes e o

metodo de Gauss-Seidel, sendo visto na referência [ 2J que sua

convergência e garantida para qualquer sistema cuja matriz de

coeficiente e positiva definida. Desta forma, o sistema de multi

plicadores de Lagrange e, então, passivel de resolução por Gauss

-Sei dei, sendo no entanto necessãrio que haja vantagem computa­

cional.

O numero de operaçoes de multiplicação e divisão no me­

todo de Gauss-Seidel e dado por:

S = q n2 onde: q e o numero de iterações e

n e a dimensão do problema.

enquanto que no metodo de Choleski e:

ou

e= 1 (n' + 9n 2 + 2N) + n 6

sõ haverã vantagem computacional se:

s < e

l q n2 < (n 3 + 9n 2 + 2n} + n 6

donde: 6

4

3n

11 2

Se resolvermos os problemas e medimos o numero mêdio de

iterações do mêtodo de Gauss-Seidel podemos verificar se hã dimi

nutção do esforço computacional, o que pode ser visto na tabela

IV.19, abaixo:

Tabela IV. 19

PROBLEMA ITERAÇUlS II tKAÇAU GAUSS-SEIDEL MÃXIMA

IV. l l. 4 2.86

IV.2 2.8 4.08

IV.3 3.3 3. 7 7

IV.4 3.4 3. 7 7

A iteraçao mãxima dada acima e o numero de iterações necessãrias

para que o esforço computacional dos dois mêtodos seja igual.

Com base nestes resultados, verificamos que a utiliza­

çao de Gauss-Seidel para a solução do sistema-linear de multipll

cadores de Lagrange e vantajosa em relação i decomposição de

Choliski e, portanto, esta não deverã ser utilizada.

Notamos que na primeira iteração do algoritmo, por nao

haver valores dos multiplicadores de Lagrange para uma aproxima­

ção inicial, estes são calculados de forma exata atravês da de­

composição de Choleski. Obviamente no cãlculo dos valores mêdios

l l 3

esta i teraçao foi descontada.

IV.6 - CONCLUS)(O

O algoritmo de direções viáveis para programaçao quadri

ticas mostrou-se simples e eficiente e, com base no trabalho de

H~RSKOVITS [ 16], podemos afirmar que a versão I tem convergência

linear e a versão II superlinear.

Os testes numéricos, que deixaram a desejar quanto ao

tamanho dos problemas analisados, mostraram que uma atualização

racional dos parâmetros definidos nos levam a uma maior velocida

de de convergênéia, e que determinadas versoes se apresentam mais

estãveis. Um estudo numérico incluindo problemas de grande porte

e comparando tempos de processamento entre as vãrias versões e

outros métodos, seria desejável. Apesar disto, os resultados ob­

tidos são bastante alentadores e incentivam a um aprimoramento.

Por se tratar de um algoritmo de direções viáveis que

nao utiliza estratégia de conjunto ativo, hã uma relativa inde-

pendência no tocante ao numero de restrições do problema, alem

de permitir o truncamento do processo a qualquer instante sem

prejudicar a viabilidade da solução.

Uma vez que necessita de um ponto iniciàl viável, o

algoritmo deverã ser ampliado incluindo-~e, talvez, uma primeira

fase com o intuito de viabilizar o processo.

11 4

APtNDICE

PROBLEMA 22

Min f(_x)_ = (x 1 - 2) + (x 2 - l)

Sujeito a:

PROBLEMA 35

Sujeito a:

=l,2,3

PROBLEMA 43

Sujeito a:

8 - X 2 - X 2

- X 2 - X 2

- X - X + X - X + X4

> O l 2 2 3 41 2 3 ,

11 5

PROBLEMA 44

Sujeito a:

8 - Xl - 2X 2 ~ o

l 2 - 4X 1 - x2 ~ o

l 2 - 3X 1 - 4X 2 > o ,

8 - 2X 3 - X4 > , o

8 - X3 - 2X 4 > o ,

5 - X3 - X4 ~ o

xl ~ o i=l ... ,4

l l 6

REFERfNCIAS BfBLI"OGRAFfCAS

[ 'J ARRIOU, M.; LARATTA, A. e M~NCHI, O - "Numeri cal Study of

Some Feasible Directions Methods in Mathematical Program­

ming", Joc.ur.nal oó Op.timiza:U.on The.oh..y and Applic.a.tion.6 ,

Vol. 40, nQ 1, maio 1983.

[ 2

] EÍ'.EREZIN e ZHIDKOV - "Compu.ting Me..thod.6 11, Pergamon Press, Vol.

2, pp. 56-60, Great-Bretain, 1965.

[ 3

] BIGGS, BARTHOLOMEW - ''A Matrix Modification Method for Cal­

culating Approximate Solutions to Systems of Linear Equ~

ti ons", T: In.6.t. Ma.th..6. Appl-<-c..6., 1979.

[ 4

] BROYDEN, C. G. - "Quasi-Newton Methods and thei r Applica-

tion to Function Minimization", Ma.th.e.ma.t-<.c..6 oó Compu.ta­

.t1on, nQ 21, 1967.

[ 5

] COHEN, A. I. - ''Stepsize Analysis for Descent

JOTA, Vol. 33, nQ Z, Fev. 1981.

Methods",

[ 6

] ESCUDERO, L. F. - ''On Hessian Matrices in Unconstrained Op-

timization", Palo Al.to IBM Sc.ie.n.t-<-ó-<-c. Ce.n.te.'1..,

1980.

[ '] ESCUDERO, L. F. - "An Algorithm for Large-Scale

junho

Quadra ti e

Programming Problemas and its Extensions to the Linear.ly

Constrained Nonlinear Case", IBM Madh..-<.d Sc.1e.n.tió1c. Ce.n­

.te.11., abril 1981.

l l 7

[ ª] ESCUDERO, L. F. - "On Diagonal ly Preconditioning the Trunc2_

ted Newton Methods for Super-Scale Linearly Constrained

Nonlinear Programming'', IBM Madhid Seienti6ie Centeh,

Setembro, 198c.

[ 9

] ESCUDERO, L, F. - "A Projected Lagrangi an Method for Non-

linear Programmi ng", Palo Alto IBM Sieenti6ie

Abri 1 1980.

['ºJ FLETCHER, R. - "A General Quadratic Algorithm", J,

Ma;th~. Applie~., 1171.

[11

] FLETCHER, R. - ''A New Approach to Variable-Metric

rithms'', Computeh Jouhnal, n9 13, 1970.

Centeh,

In~t.

Algo-

[12

] FLETCHER, R. - "P,'Lae;tieal Me;thod~ oó Op;t,i.m,i.za;t,i.on", John

Wiley and Sons., 1980.

[13

] GEOFERION, A. M. - "Elements of Large-Scale Mathematical Pro

gramming'', University of California.

['"] G!LL, P. E. e MURNAY, W. - "Linearly-Constrained Problems

Including Linear and Quadratic Programming", The State

06 the aht in Numeh,i.eal Analy~i~-- Academic Press,1977.

[15

] GOLDFARB e IDNANI - "A Numerical ly Stable Dual Method for

Solving Strictly Convex Quadratic Programs", Ma;themaüeal

Phoghamm,i.ng, Hl83.

11 8

[ 16 ] HERSKOVITS, J. N. - "A Two-Stage Feasible Directions Algo­

ritlím for Nonl inearly Constrained Optimization", Rapp. de

Reclí., n9 103, INRIA, BP 105, 78153, Le Chesnay, France.

[ 17 ] HERSKOVITS, J. N. - "A Two-Stage Feasible Directions Algo­

rithm In~luding Variable Metric Techniques for Nonlinear

Optimization", Rapp. de Rech., n9 118, INRIA, ibid.

[18

] LEMARECHAL, C. - "A View of Line Searches, in!': Optimization

and Optimal Control, Editors Auslender, Oettli . and J.

Stoer, Lectures Notes in Control and Information Sciences,

30, Springer Verlag, pp.-59-78, 1981.

[ 1 ~] LUENBERGER, D. G. - ''Intnoductlon to Llnean and Nonllnean

Pnognammlng'', Addison-Wesley Publishing Company, 1973.

[ 20 ] MAYNE e POLAK - "Feasible Directions Algorithms for Optimi­

zation Problems with Equality and Inequality Constraints",

Mathematlcal Pnognammlng, n9 11, 1976.

[ 21 ) SCHlTTOWSKI e HOCK - "Test Examples for Nonlinear Program­

ming Codes'', Lectune Notea ln Economlca and MathematlcaL

Syatema, Springer-Verlag, 1981.

[22

] SHANNO, D. F. - "Numerical Comparison of Several Variable-

Metric Algorithms'', Journal of Optimization Theory and

Applications, Vol. 25, n9 4, 1978.

1 1 9

[23

] U. GARCI.A-PALOMARES. e A. RESTUCLA - "A Global Quadratic Al­

goritbm for Solving a System of Mixed Equalities and Ine

qualities'', Mathematleal P~ag~ammlng, nQ 21, 1981.

[z•J WOLFE, P. - "Convergence Conditions for Ascent Methods",SIAM

Revlew, nQ 11, 1969 ..