Untitled

UM NOVO ALGORÍTMO DE PENALIZAÇÃO HIPERBÓLICA PARA
RESOLUÇÃO DO PROBLEh4A DE PROGRAMAÇÃO NÃO-LINEAR COM
RESTRIÇÕES DE IGUALDADES
Turíbio José Gomes dos Santos
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 OBTENÇÃO DO GRAU DE DOUTOR EM CIÊNCIAS EM
ENGENHARIA DE SISTEMAS E COMPUTAÇÃO .
Aprovada por :
I
Prof Nelson Mac Filho ,D. Habil.
/'4,
*>' ,
-'
/ /<;37>
k/
Prof Luis f i e d o v. de Carvalho ,D. Sc.
, .
-, w
Prof. Roberto Quirino do Kascimento ,D. Sc.
l-
'prof. Luiz Satoru Ochi ,D. Sc.
RIO DE JANEIRO - RJ - BRASIL

ABRIL DE 1998 .
SANTOS, TURÍBIO JOSÉ GOMES DOS
Um novo algorítmo de penalização hi-
perbólica para resolver o problema de progra-
mação não-linear sujeito a restrições de igual-
dades . [ Rio de Janeiro ] 1998
XIII , p. 29,7 cm (COPPE 1 UFRJ,
D.Sc. ,Engenharia de Sistemas e Computação
1998 )
Tese - Universidade Federal do Rio de
Janeiro ,COPPE
1. Otimização , 2 . Programação Não-Linear
3 . Método de Penalidade , 4 . Lagrangeano.

I. COPPE / UFRJ 11. Título ( série )
A minha esposa
Ana Elvira e a
meus filhos ,
Cristhiano
Andréa e
Raíssa
AGRADECIMENTOS
Ao Programa de Engenharia de Sistemas e Computação da COPPE 1 UFRJ pelo
apoio na realização deste doutorado .
Aos professores Paulo Roberto , Susana Scheimberg , Clovis Gonzaga , Adilson

Xavier, pelos cursos teóricos básicos que deram sustentação à elaboração deste
trabalho.
Ao professor Adilson Xavier , a quem muito admiro pelo espírito de pesquisa,
agradeço profundamente a sua confiança , solidariedade , amizade , e pela riqueza e

abrangência de sua orientação.
Ao professor Roberto Quirino , pelo incentivo , apoio , compreensão e amizade ,

demonstrados em todos os momentos.
A minha esposa Ana Elvira , aos meus filhos Cristhiano ,Andréa e Raíssa ,pelo
incentivo , colaboração , compreensão e amizade . O apoio de todos foi muito
importante para o término deste trabalho.
Aos meus pais Avelino e Lôide ,muito presentes e solidários me incentivando e
dando forças para a elaboração deste trabalho .
Aos meus irmãos e minhas irmãs Ana Clara e Lélia , pelo incentivo , força,
compreensão e amizade, desde o início deste trabalho .
Aos meus colegas da UFPb e em particular aos professores do Departamento de
Matemática da UFPb-JP, pela contiança, incentivo e apoio em todos os momentos.
Aos meus colegas da COPPE / UFRJ , por estarem sempre presentes e prontos a
ajudar em qualquer problema, agradeço por suas amizades.
A CAPES / PICD , pelo apoio financeiro durante todo o período de estudos e

realização desta Tese.
Resumo da Tese apresentada à COPPE 1 UFRJ como parte dos requisitos necessários
para a obtenção do grau de Doutor em Ciências (D. Sc. ).
UM NOVO ALGORÍTMO DE PENALIZAÇÃO HIPERBÓLICA
PARA RESOLVER O PROBLEMA DE PROGRAMAÇÃO NÃO-
LINEAR SUJEITO A RESTRIÇÕES DE IGUALDADES
Abril de 1998 .
Orientador : Adilson Elias Xavier
Programa : Engenharia de Sistemas e Computação
O presente trabalho mostra um novo algorítmo para resolução do problema de
programação não-linear com restrições de igualdades. Para isso , se utiliza do método
de penalização hiperbólica , originalmente desenvolvido para resolução de problemas de
programação não-linear com restrições de desigualdades.
Através da consolidação de resultados previamente estabelecidos , apresentamos
ademais, um outro algorítmo que contempla a resolução dos problemas de programação
não-linear simultaneamente com restrições de igualdades e desigualdades.
O desempenho computacional desses algorítmos é ilustrado através da resolução
de um conjunto de problemas -teste da bibliografia.

Abstract of Thesis presented to COPPE 1 UFRJ as partia1 fuIfiument of the requirments
for the degree of Doctor of Science.(D. Sc. ).
A NEW ALGORITHM OF HIPERBOLIC PENALIZATION TO
TO SOLVE THE NONLINEAR PROGRAMMNIG PROBLEMS
SUBJECT TO EQUALITY CONSTRAINTS
Abril de 1998.
Chaimian: Adilson Elias Xavier
Department : Systems Engineering and Computer Sciences
This work presents a new algorithm in order to solve the nonlinear programming
problems with equality constraints . To achieve this proposal , it is used the hyperbolic
penalty method , which was originally developed to solve the nonlinear programming
problems with inequality constraints.
By the consolidation of previously established results , it is presented additionally
another algorithm which considers the solution of the nonlinear prograqrnming problems
with equality and inequality constraints simultaneously.
The computational performance of these algorithm is exhibited through the
solution of a set of test-problerns extracted fiom the literature.

ÍNDICE DAS FIGURAS ................................................................................. x
ÍNDICE DAS TABELAS ............................................................................... xi
NOTAÇÕES ...................................................................................................... xii
MÉTODOS UTILIZADOS PARA RESOLUÇÃO DE PROBLEMAS
DE PROGRAMAÇÃO NÃO-LINEAR COM RESTRIÇÕES ........................ 18
MÉTODO DE D ~ E Ç Õ E SVIÁVEIS .............................................................. 18
MÉTODO DE GRADIENTE PROJETADO ................................................... 20
&TODO DE GRADIENTE REDUZIDO ....................................................... 21
METODO DE GRADIENTE REDUZIDO GENERALIZADO ........................ 23
MINIMIZAÇÃO RESTRITA VIA KKT ........................................................ 24
PROGRAMAÇÃO QUADRÁTICA SEQUENCIAL ........................................ 26
vii
METODOS DE PENALIDADES ...................................................................... 30
METODO DE PENALIDADE EXTERIOR ................................................... 30
METODO DE PENALIDADE INTERIOR ..................................................... 33
PENALIDADE MISTA ................................................................................... 36
PENALIDADE EXATA .................................................................................... 37
PENALIDADE EXATA DIFERENCIAVEL ..................................................... 39

METODO DOS MULTIPLICADORES ............................................................ 41
VANTAGEM DOS MÉTODOS DOS MULTIPLICADORES ........................ 46
PENALIDADE HIPERBOLICA ......................................................................... 47
RESOLUÇÃO DO PROBLEMA DE PROGRAMAÇÃO NÃO-
LINEAR COM RESTRIÇÕES DE IGUALDADES ......................................... 57
KGORITMO I DE PENALIZAÇÃO HIPERB~LICA ................................... 65
I ..................................................
~ r s c u s s Ã oINICIAL DO ALGORÍTMO 68
CONDIÇÕES DO PROBLEMA ..................................................................... 69
FUNCIONAMENTO DO ALGORÍTMO I ...................................................... 75
CONVERGÊNCIA DO ALGORIIMOI ........................................................ 81
RESULTADOS DOS PROBLEMAS RESTRITOS A IGUALDADES ............ 87
DESCRIÇÃO DAS TABELAS ....................................................................... 89
.
TABELAS 1 2 e 3 .......................................................................................... 91
PROBLEMAS TESTES COM RESTRIÇÕES DE IGUALDADES ................ 94
viii
PROBLEMAS DEGENERADOS ....................................................................... 97
..
TABELAS 4 5 6 e 7 ...................................................................................... 98
RESOLUÇÃO DO PROBLEMA GERAL DE PROGRAMAÇÃO
VIA PENALIZAÇÃO HIPERBÓLICA ...........................................................103

11 DE PENALIZAÇÃO HIPERBÓLICA ................................. 106
ALGORÍTMO
ESCOLHA DOS PARÂMETROS INICIAIS .................................................. 109

RESULTADOS COMPUTACIONAIS DE UM PROBLEMA
RESTRITO A IGUALDADES E DESIGUALDADES ................................... 111
TABELAS 8 . 9 . 10 e 11 ........................................................................... 112
PROBLEMAS TESTES COM RESTRIÇÕES DE IGUALDADES
E DESIGUALDADES ...................................................................................... 116
ESCOLHA DOS PARÂMETROS INICIAIS .................................................. 119
CONCLUS~ES.............................................................................................. 126
COMBINAÇÃO DA PENALIZAÇÃO HIPERBÓLICA COM
OUTROS MÉTODOS ...................................................................................... 128
BIBLIOGRAFIA ....................................................................................... 130

ÍNDICE DAS FIGURAS
FIGURA 1 : Penalização exterior ......................................................................30

FIGURA 2 : Penalização interior .................................................................... 34
FIGURA 3 : Função penalidade hiperbólica ..................................................... 49
FIGURA 4 : Aumento do parâmetro a da função de
penalização hiperbólica ................................................................ 50
FIGURA 5 : Diminuição do parâmetro .z: da função de
penalização hiperbólica .............................................................. 51
FIGURA 6 : Relaxação das restrições de igualdades ....................................... 59
FIGURA 7 : Redução do intervalo entre as folgas .......................................... 68

FIGURA 8 : Acréscimo da inclinação da função penalidade ............................ 84
ÍNDICE DAS TABELAS
.
TABELA 1. Resultados computacionais do problema teste 1 Parte 113.................. 91
.
TABELA 2 . Resultados computacionais do problema teste 1 Parte 213................. 92
TABELA 3 . Resultados computacionais do problema teste 1.Parte 313.................. 93
TABELA 4 . Resultados computacionais do problema teste 46.Parte 114................ 98
TABELA 5. Resultados computacionais do problema teste 46.Parte 214................. 99
TABELA 6. Resultados computacionais do problema teste 46.Parte 314.................. 100
TABELA 8 . Resultados computacionais do problema teste 2.Parte 114.................. 112
TABELA 9. Resultados computacionais do problema teste 2.Parte 214 .................... 113
TABELA 12. Valores de aij para o problema 119 .................................................... 124

TABELA 13. Valores de bij e cj para o problema 119 ............................................. 125
Função objetivo
Função objetivo aumentada ou modificada
Funções restrições de desigualdades
Funções restrições de igualdades
Índice especificando restrição de desigualdade
Índice especificando restrição de igualdade
Número da iteração
Função Lagrangeana
Função Lagrangeana aumentada ou modificada
Função Lagrangeana hiperbólica
Número de restrições de desigualdades
Dimensão do espaço Euclidiano
Número de restrições de igualdades
Função de penalidade hiperbólica
Espaço Euclidiano n - dimensional
Conjunto solução do problema com restrições
Conjunto solução do problema relaxado
Variável no espaço R"
Ponto ótimo da função objetivo modzcada na iteração k
Ponto inicial
Ponto ótimo ou solução do problema original
Parâmetro ângulo da penalização hiperbólica
Relaxação ou folga superior
Relaxação ou folga inferior
Multiplicador de Lagrange relativo as restrições de desigualdades
Multiplicador de Lagrange relativo às restrições de igualdades
Parâmetro distância da penalização hiperbólica

Consideraremos neste trabalho a resolução do problema geral de programação
não-linear sujeito a restrições de igualdades e desigualdades da forma:
minimizar f(x)
sujeito à : gi(x) 2 O , i = 1 , ..., m
hj(x) = O ,j = 1 , ...,p
onde f : R" - + R , g : R " + R" e h : R" + RP.

Em particular ,consideraremos a resolução do problema de programação não-linear
sujeito a restrições de igualdades da forma :
minimizar f ( x )
sujeito à : hj(x) = O ,j = 1 , ...,p
onde f : R" + R e h : Rn+RP.
Primeiramente apresentaremos um novo método para sua resolução . Esse método
se fundamenta na utilização da penalização hiperbólica , que na sua abordagem inicial
trata da resolução de problemas unicamente com restrições de desigualdades e com
ademais ,a hipótese de possuir região viável com interior não-vazio.
O novo método basicamente se constitui na relaxação das retrições de igualdades,
transformadas em desigualdades , através de folgas superiores E + e inferiores E - ,

criando assim interior não-vazio ,e permitindo desse modo , a utilização da penalização
hiperbólica .
Basicamente , seguindo essas idéias e incorporando a imprescindível manipulação
conveniente das folgas ,apresentamos o algorítmo I para resolução do problema ( 2 ).
Para estabelecermos o estudo teórico de convergência do método , relacionamos
primeiramente um conjunto de resultados subsidiários a esse estudo . Além disso ,
especificamos um conjunto de condições que o problema ( 2 ) necessita satisfazer. A
seguir são desenvolvidos resultados que mostram a convergência do algorítmo I.
Com o objetivo de validar o desempenho do algorítmo I , efetuamos um conjunto
de experimentos computacionais se utilizando da referência de Hock e Schittkowiski
[ 34 ] , seguindo as recomendações de JACKSON et al. [ 36 ] e consentâneo a outros
trabalhos publicados na literatura.
Os resultados obtidos se comportaram conforme a teoria previamente desenvolvida ,
demonstrando robustez e eficiência fiente à totalidade dos problemas testes efetuados
em nossos experimentos.
Através da consolidação dos resultados previamente estabelecidos e daqueles
descritos em Xavier [ 62 ] ,estendemos nossos estudos à resolução do problema ( 1 ).
Nesse sentido, apresentamos o algorítmo I1 para avaliação de seu desempenho e o
submetemos a um conjunto de problemas testes relacionados em Hock e Schittkowiski
[ 34 1. Registramos igualmente robustez e eficiência fiente a esse conjunto de problemas
testados.
A apresentação do presente trabalho é feita com mais detalhes em descrição dos
capítulos ,visto logo a seguir.

Este trabalho de tese consta de cinco capítulos assim distribuídos :
No Capítulo 1 , apresentamos algumas definições e condições de otimalidade para
problemas de programação não-linear irrestritos como também para problemas restritos.
No Capítulo 2 , apresentamos urna revisão bibliográfica envolvendo basicamente
alguns métodos de resolução dos problemas de programação não-linear com restrições
tais como : método de direções viáveis , método de gradiente projetado, método de
gradiente reduzido , método de gradiente reduzido generalizado ,método de penalidades
tais como : pontos exteriores , pontos interiores , mista , exata , método dos
multiplicadores ,método de programação quadrática sequencial e finalmente o método de
penalização hiperbólica .
Do método de penalização hiperbólica , nos emulamos para chegarmos ao objetivo
do trabalho de tese, que trata de resolver o problema de programação não-linear com
restrições de igualdades ,que será apresentado no capítulo seguinte .
No Capítulo 3 , apresentamos o problema de programação não-linear com
restrições de igualdades , a ser resolvido , utilizando a penalização hiperbólica , o
algorítmo I e seu funcionamento . Fundamentado sob um conjunto de condições que o
problema deve satisfazer , são desenvolvidos os resultados teóricos que nos levam até a
convergência .
Com o objetivo de mostrarmos o fiincionamento do algorítmo e a validade do
método , apresentamos os resultados computacionais , obtidos a partir de um exemplo
simples de programação não-linear restrito , contendo duas variáveis e somente uma
restrição de igualdade ,
Apresentamos ainda, uma relação de alguns problemas testes do livro de Hock e
Schittkowski [ 34 ] , envolvendo somente restrições de igualdades , inclusive alguns
problemas considerados degenerados , face a presença de multiplicadores de Lagrange
iguais a zero , contrariando a condição de hjk # O ,j = 1 , ... ,p estabelecidos
anteriormente.
No capítulo 4 , desenvolve-se um novo algorítmo I1 para o problema geral de
programação não-linear com restrições simultaneamente de igualdades e desigualdades .
Com o objetivo de mostrarmos o funcionamento do algorítmo e a validade do
método , apresentamos os resultados computacionais , obtidos a partir de um exemplo
simples de programação não-linear contendo duas variáveis , uma restrição de
igualdade e três restrições de desigualdades ,
Apresentamos ainda, uma relação de alguns problemas testes do livro de Hock e
Schittkowski [ 34 ] , envolvendo restrições de igualdades e desigualdades , onde todos
foram resolvidos com sucesso utilizando-se o algorítmo I1 .
No capítulo 5 , apresentamos as conclusões e propostas para estudos futuros.

CLASSIFICAÇÃO DOS PROBLEMAS
Nosso objetivo é mostrar uma introdução no campo da programação não-linear ,
cam a perspectiva de abordar em síntese. mas com a máxima amplitude, os resultados-
padrão mais importantes atualmente disponíveis nessa área, tais como algumas definições
e condições de otimalidade para os problemas de programação nãa-linear .

Basicamente abordaremos dois tipos de problemas : os denominados irrestritos,
e as denominadas restritos ,Os problemas restritos consistem em otimizar ( minimizar
ou maximjzar ) uma função , denominada função objetivo, respeitando um conjunto de
restrigões.
Estas restriçães determinam um canjunto de sohçtles viáveis, e a solução viável que
otirniza a função objetivo, que é a melhor solução encontrada, denomina-se solução
átima do problema.
O objetivo ideal da otirnização s& encontrar o ótima global ,Lnfelizmente ,os
ótimos globais podem ser caracterizados somente em alguns casos particulares, como
.
nas problemas de programação convexa . Portanta quando falarmos em otimalidade
estamos nos referindo aos ótimos locais .
Arepresentação de um problema de minimizaç-ão restrito ( PR) é dado por :
rninimizar f(x )
sujeito a : x E S ,
onde x = ( x~ . ..,. . x,,) designa as variáveis , S o conjunt~de restciçães ou
conjunto solução ,e f ( . ) : S c R" + R é uma função objetivo qualquer .
.
Por outro lado quando S = R",temos os problemas ditas irrestritos ( PL ) ,que
consistem em minimizar uma função objetivo sem restrições , e cuja representação é
dada por :
DEFINIÇÃO ( ~).:í( ~íniílioLocal )
Um ponto x* E S é dito uma solução local ou relativa do problema ( PR ) , se
existe uma vizinhança Q( x* Q ) . = { z/ I z - x* 1 < 6 ; â > O ) tal que
f ( x * ) 5 f ( x ) , para todo X E Q(x*,â)nS.
DEFINIÇÃO ( 1.2 ) : ( global )
Um ponto x* E S é dito um mínimo global ou absoluto do problema ( P R ) se
f(x*) < f ( x ) , para qualquer X E S .
Usualmente, os métodos de programação não-iinear são iterativos ,no sentido de
que ,partindo-se de um ponto inicial xO,uma sequência de pontos { xk ) é obtida
através de repetidas aplicações de uma regra algorítmica . Essa sequêmia deve
convergir para uma solução x* do problema.

DEFINIÇÃO ( 1.3 ) : ( Convergência Local )
Um algorítmo é localmente convergente , se existe um escalar o positivo, tal
que para qualquer ponto inicial x0E R" ( ou x0 E S ) , verificando 1 xO- x* 1 5 <r ,o
algorítmo gera uma sequência de pontos convergindo para a solução x* do problema
original .
DEFINIÇÃO ( 1.4 ) : ( Convergência Global )
Um algorítmo iterativo é dito globalmente convergente, se para qualquer ponto
inicial xOE Rn ( ou x0 E S ), O algorítmo gera uma sequência de pontos convergindo
para uma solução do problema original.
A convergência é dita assintótica ,quando a solução não é encontrada após um
número finito de iterações . Exceto em alguns casos particulares , como problemas de
programação linear e também de programação quadrática , um caso de programação
não-linear ,posteriormente descrito ,podendo ter convergência f i t a .
Em geral, os algorítmos globalmente convergentes defhem a cada ponto uma
direção de busca à procura de um novo ponto. Daí teremos :
DEFINIÇÃO ( 1.5 ) : ( Direção de Descida )
Um vetor d E R" é uma direção de descida de uma função real f em x E R",
se existe 6 >O, tal que f ( x + t d ) < f ( x ) para qualquer t ~ ( 0 , 61.

DEFINIÇÃO ( 1.6 ) : ( Direção Viável )
Um vetor d E Rn é urna direção viável para o problema geral em x E S, se
para algum 8 > O temos x + td E S para todo t E [ O ,e ]
Os resultados mais importantes na programação não-linear são as condições de
otimalidade ,porque elas devem ser satisfeitas em qualquer ponto ótimo restrito, local
ou global, de qualquer problema de programação linear, e na maioria dos problemas
de programação não-linear . De outro lado ,essas condições formam a base para o
desenvolvimento de muitos algorítmos . Além disso , os critérios de parada de muitos
algorítmos , isto é , de reconhecer quando um ponto ótimo local restrito é atingido ,
são diretamente derivados dessas condições, as quais apresentaremos a seguir.
CONDIÇÕES DE OTIMALIDADE PARA PROBLEMAS DE
OTIMIZAÇÃO IRRESTRITO
Considere o problema de programação não-linear irrestrito dado por :
minimizar f (x ) ( 1.2)
x E Rn
CONDIÇÃO NECESSÁRIA DE PRIMEIRA ORDEM :
Se a função f ( . ) é de classe C' ,então uma condição necessária para x* E R" ser
uma solução do problema ( 1.2 ), é que :
Vf(x")=O
CONDIÇÃO NECESSÁRTA DE SEGUNDA ORDEM :
Se a função f ( . ) for de classe c2,então uma condição necessária parax* E R"
ser uma solução do problema ( 1.2 ) é que v2 f (x* ) ,a Hessiana de f em x* , seja
semidefinida positiva, isto é ,para toda direção d E R" ,
dt v 2 f ( x * ) d 2 0 . ( 1.4
CONDIÇ~ESDE SUFICIÊNCIA :
As condições de suficiência para x* E Rn ser uma solução local para o
problema irrestrito ( 1.2 ) são :
Vf(x*) = O ( 1.5
zV2f(x*)z > O , ( 1.6)
para todos os vetores não-nulos z E R" .
DEFINIÇÃO DOS PROBLEMAS DE OTIMIZAÇÃO COM RESTRIÇÕES
Primeiramente dizemos que , se o conjunto viável S for definido por um

conjunto de restrições de igualdades e desigualdades , então o problema ( 1.1 ) será
chamado de problema geral de programação não-linear restrito ( PGR ) , e sua

representação é dada por :
minimizar f ( x ) ( 1.7
sujeitoà: g i ( x ) 2 0 , i = l ¶... ?m
hj(x) = O , j = 1 , ...,p
onde f ( . ) : R" +R , gi(.):Rn + R" e h j ( . ) : R" + RP são funções
não-lineares e diferenciáveis .
Como um caso especial do problema ( 1.3 ) , podemos pensar em minimixar uma
função f ( . ) sobre uma superficie S , defMda somente pelas equações hj ( x ) = O
para j = 1, ... , p < n . Como estamos tratando unicamente com restrições de
igualdades , então , nos referimos a este problema como um problema de otimização

restrito a igualdades ( PRI ) ,e pode ser escrito na f o m :
rninimizar f ( x ) ( 1.8 1
sujeito à : h j ( x ) = O ; j = 1 ,...,p
Por outro lado , nos referimos a problemas em que somente as restições de

desigualdades são envolvidas , nos proporcionando os chamados problemas de otimização
restrito a desigualdades ,que podem ser expressos na forma :
minimizar f (x ) ( 1.9 1
sujeito à : gi(x) 2 O ; i = 1 ,..., m
C O ~ I Ç Õ E SDE OTIMALIDADE PARA PROBLEMAS DE
OTIMIZAÇÃO COM RESTRIÇÕES DE IGUALDADE
Primeiramente introduzimos as variáveis auxiliares p E RP e h E Rm,
chamadas de Variáveis Duais ou de Multiplicadores de Lagrange para definirmos as
seguintes funções Lagrangeanas .

DEFINIÇÃO ( 1.7 ) :
A função Lagrangeana 1( . ) : R" x RP -+ R associada ao problema restrito a
igualdades ( 1.8 ) é definida como :
l(x,p) = f(x) + pth(x) ( 1.10)
onde p E RP é O vetor multiplicador de Lagrange .
Restrições não-lineares podem ser extremamente complicadas , de maneira que
as condições de otimalidade serão defúiidas fazendo-se hipóteses favoráveis a respeito
dessas restrições , que são conhecidas na literatura como condições de qualificação
das restrições .
Uma condição normalmente usada, conhecida como hipótese de regularidade, é
apresentada a seguir :
DEFINIÇÃO ( 1.8 ) : ( Regularidade )
Um ponto x E S é um ponto regular das restrições se os vetores Vhj ( x* ) ,
para j = 1, ... ,p são linearmente independentes .
CONDIÇOES NECESSÁRIAS DE PRIMEIRA ORDEM :
As condições necessárias de primeira ordem para que x* seja um ponto de
mínimo local para o problema ( 1.8 ) , ou condições de Kamsh - Kuhn - Tucker

( KKT ) , são que x* seja um ponto viável , h ( x* ) = O , e que exista um
multiplicador de Lagrange p* E RP tal que :
Fazendo uso da função Lagrangeana, esta equação é equivalente a :
CONDIÇÕES NECESSÁFUAS DE SEGUNDA ORDEM :
A condição necessária de segunda ordem para que x* seja um ponto de mínimo
local para o problema ( 1.8 ) é que exista y* E RP tal que sejam satisfeitas as
condições de primeira ordem ( 1.11 ) ,e que a Hessiana da função Lagrangeana seja
semidefínida positiva para todos os vetores sobre o espaço nulo associado aos
vetores gradientes Vh ( x* )t, isto é , para todo vetor v que satisfaz
V~(X*)~V=O,
deve ser observado
CONDIÇÕES DE SUFICIÊNCIA :
As condições suficientes para x* ser um rninimizador local isolado do problema
restrito ( 1.8 ) são que x* seja um ponto KKT , isto é, x* e y* satisfaçam as
condições necessárias de primeira ordem, e que
V ~ V ~ ~ ~ ( X *> , O~ *, ) V ( 1.14)
para todo vetor v ;t O que satisfaça
Vh(x* )'.v= O .
Considerando o problema de programação não-linear com restriqões de
desigualdade dado em ( 1.9 ) ,definimos sua função Lagrangeana como :
DEFINIÇÃO ( 1.9 ) :
A função Lagrangeana 1 ( . ) : RnxRm -+ R associada ao problema restrito a
desigualdades ( 1.9 ) é definida como :
l(x,h) = f(x) - htg(x) , ( 1.15 )
onde h E Rm , h 2 O ,é o vetor multiplicador de Lagrange .
DEFINIÇAO ( 1.10 ) :( Regularidade ) .
Um ponto x E S é um ponto regular das restrições , se os vetores Vgi (x )
para i E I ( x ) , são linearmente independentes , onde I ( x ) = ( i / gi ( x ) = O } é o
conjunto de restrições ativas em x .
Suponhamos agora que x* , um ponto regular , seja um mínimo local para o
problema ( 1.9 ) . É claro que x* é também um mínimo local de f ( x ) , sujeito à
gi (x) = O ,para i E I ( X* ). Então ,segue das condicões necessárias de primeira ordem
que existe um vetor h* E Rm tal que :

onde h;*= O para i P I ( x* ) .
A condição Ai* = O para i e I ( x* ) é chamada de Condição de
Complementaridade, e pode ser representada por meio de as seguintes igualdades :
Ademais , se x* é um ponto de mínimo , devemos ter necessariamente Ai* 2 0,
i E I ( X* ) , pois em caso contrário ,haveria uma direção de decréscimo de f ( x ),
que seria viável .
CONDIÇOES NECESSÁRIAS DE PRIMEIRA ORDEM :
As condições necessárias de primeira ordem para que x* ,um ponto regular em
relação às restrições , seja um ponto de mínimo do problema ( 1.9 ) , é que exista
um vetor h* E Rm tal que :

CONDIÇÕES DE OTIMALIDADE PARA O PROBLEMA
GERAL DE OTIMIZAÇÃO
Considerando o problema geral de programação não-linear ( 1.7 ) ,temos :
D E J ~ I Ç Ã O ( 1.11 ) :
A função Lagrangeana 1( . ) : R" x R" x RP + R associada ao problema geral
de programação ( 1.7 ) é definida como :
l(x,p,h) = f(x) + pth(x) - htg(x) ( 1.19)
DEFINIÇÃO ( 1.12 ) : ( Regularidade ) .
Um ponto x E S é um ponto regular em relaçao as restrições, se os vetores
Vhj ( x ) , para j = 1 ,. ,p e Vgi ( x ) , para i E I ( x ) são linearmente
independentes, onde I ( x ) = ( i / g i ( x ) = O ) .
CONDIÇÕES NECESSÁRIAS DE PRIMEIRA ORDEM OU KKT :
As condições necessárias de primeira ordem ou condições KKT para umponto
x* E S ser um ponto de mínimo local para o problema ( 1.7 ) . Supondo que x* seja
um ponto regular para as restrições dadas na definição de S , é que exista um
vetor multiplicador p* E RP e um vetor multiplicador h* E R" ,h* 2 O tais que :
V f ( x * ) + ~ * ~ . ~ h ( x- *h*'Vg(x*)
) = O
h*'g(x*) = O ( 1.20)
h(x*) = O
g(x*) 2 o
CONDIÇ~ESNECESSÁRIAS DE SEGUNDA ORDEM :
Nas condições necessárias de segunda ordem supomos que as funções f ( . ) ,
g ( . ) , e h( . ) sejam de classe c2,e que x* seja um ponto regular em relação às
restrições h ( x* ) = O e g ( x* ) 2 O . Se x* é um ponto de mínimo local para o
problema ( 1.7), então existe um vetor p* E RP e um vetor h* E Rm , h* 2 O tais
que as condições de primeira ordem sejam obedecidas, e que a matriz
seja semi-definida positiva sobre o espaço tangente associado às restrições ativas em x* .

Denotamos v21 ( x*, p*, h* ) como sendo a Hessiana da função Lagrangeana relativa ao
problema ( 1.6 ) , e v2f ( X* ) ,v2h ( X* ) e v2g ( X* ) como sendo as Hessianas das
funções f , h e g respectivamente.
CONDIÇOES DE SUFICIÊNCIA:
Agora, nas condições de suficiência de segunda ordem, sendo as funções f , g
e h de classe c2,e um ponto x* satisfazendo as restrições h ( x* ) = O
e g ( x* ) 2 O para ser um ponto de mínimo local para o problema ( 1.7 ) é que
exista um vetor p* E RP e um vetor h* E Rm tais que :
Vf(x*) + p*'Vh(x*) - h*'Vg(x*) = O
h*tg(x*) = O
h * 2 0 ,
e a matriz Hessiana
seja definida positiva sobre o espaço tangente M , onde
M = { y / Vh(x*).y = O ; Vg(x*).y = O para todo ~ E ) I
com I = { i / g i ( x * ) = O ; Ai > O )
&TODOS UTILIZADOS PARA RESOLUÇÃO DE
PROBLEMAS DE PROGRAMAÇÃO NÃO-LINEAR COM
RESTRIÇ~ES
O objetivo fundamental do presente trabalho, como já referido na introdução, é
o desenvolvimento de um algorítmo para a resolução do problema de programação
não-linear com restrições de igualdade, e como uma extensão ,o problema geral . Face
a essa proposta, julgamos de suma importância efetuar uma apresentação sintética de
alguns dos principais métodos destinados à resolução dos problemas de otimização
com restrições .
A idéia central desse método é adaptar os princípios dos métodos de
rninimização irrestrita ,levando em consideração as limitações impostas pela presença
de restrições .
Considere o problema :
minimizar f ( x )
sujeito a : x E X C Rn,
onde X é um subconjunto fechado do R" e f (. ) uma função continuamente
diferenciável ,que tem conjunto de nível limitado .
Um algorítmo para resolver o problema ( 2.1 ) segundo o enfoque de direções
viáveis segue basicamente os seguintes passos :
1- Para k = 0 , 1 , ... , e dado um ponto xk E X , encontrar um vetor
direção dk+' que seja de decréscimo, ou seja :
e também que seja uma direção viável ,o u seja , que exista um 8 k+l > O
-
satisfazendo x! + A, dk'" E X para todo O < 8k+lIí3 k+l . Em &tese ,&*' é
simultaneamente uma direção de descida e uma direção viável.
2 - Determinar um passo &+I* por algum critério de forma que :
=
xk+l
xk + &+I* dktl E X
eque f(xh1)<f(xk).
3 - Continue dessa forma até uma condição de parada ser atendida, e a
convergência será atingida.
A despeito da convergência desse método ser aparentemente segura, ela não
pode ser garantida para um problema geral , conforme descrito detalhadamente em
Bazaraa [ 6 ] e Minoux [ 48 ] .
Um dos métodos mais conhecidos da classe dos métodos de direções viáveis é
o método de Rosen [ 59 ] , que essencialmente é uma adaptação do método do
gradiente , que leva em consideração as restrições do problema . Essa adaptação se
constitue basicamente na projeção ortogonal do gradiente, na variedade linear das
restrições ativas. O método de Rosen [ 58 ] é melhor aplicável nos problemas onde as
restrições são lineares da forma :
minimizar f ( x )
sujeito à : ai x Ibi ; i E 11
aix=bi ; i€I2
Para o caso mais geral , onde as restrições são não-lineares , segue um
esquema semelhante ,isto é , em um ponto viável xk ,determina-se as restrições ativas ,
e projeta-se o gradiente naquele subespaço ,que é tangente à variedade gerada pelas
restrições . Esse vetor , se for diferente de zero , determinará a direção para a
obtenção do próximo ponto . Face a não-linearidade das restrições , geralmente esse
vetor não é uma direção viável, devido a curvatura das superficies. Neste caso ,ao se
mover ao longo do gradiente projetado , afasta-se da região viável . Face a esse
fenômeno ,o método deve incorporar uma estratégia de retorno a região viável .

MÉTODO DE GRADIENTE REDUZIDO
O método de gradiente reduzido ,devido a Wolfe [ 61 1, é uma extensão direta
do método simplex, da programação linear, aplicado ao caso da função objetivo não-
linear .
Para elucidar sua conexão com o método simplex .considere o problema:
minimizar f ( x )
sujeito à : Ax = b
x 2 0
O vetor das variáveis define-se como x = ( XB ,XN ) ,a matriz A escreve-se na

forma A = [ B ,N ] ,onde B é uma base , isto é ,uma submatriz quadrada de ordem
m ,não-singular extraída da matriz A .
As restrições de igualdade podem ser escritas como :
o que nos permite escrever :
XB = B-' b - B-' NxN
com B" =h e B-'N = E , tal como se fm no mktodo simplex .

,d x )~ seja
Assim sendo ,para que um deslocamento Mtesitnal dx = ( d x ~
compatível com as equações lineares, devemos ter :
A idéia básica dos métodos de gradiente reduzido , consiste em eliminar XB
( como uma furição de XN) através de ( i i ) , e considerar o problema de otimização
em termos de XN apenas .Essa idéia tem sido usada em outros algorítmos de
programação não-linear ,como por exemplo ,no método simplex convexo de Zangwill
[W.
A variação da função objetivo f para um pequeno deslocamento dx compatível
com as restrições é dada por :
onde ,pode-se escrever :
df = ,
u,f d x ~
com
( vii)
que por definição ,é o gradiente reduzido da h q ã o f em relação à base B .

Wolfe ,para a caso de restrições não-lineares , simplesmente toma como a matriz
A do problema ( 2.3 ) , a matriz jacobiana do sistema h ( xk ) = O , do problema
( 1.8 ) , ou seja, é efetuada a linearização dessas restrições .
MÉTODO DE GRADIENTE REDUZIDO GENERALIZADO
O método de gradiente reduzido foi generalizado por Abadie e Carpentier [ 1 ] em
1969 ,para o caso de restrições não-lineares de igualdades , e variáveis limitadas
inferiormente ,ou seja, para o problema :
minirnizar f ( x )
sujeito a : h ( x ) = O
x 2 0
O método combina as idéias de gradiente reduzido de WoKe , com as

estratégias do método de linearização ,e tem sido considerado um dos mais eficientes
para tratar o caso mais geral em que as restrições, assim como a função objetivo ,
são não-lineares . Veja Colviile [ 19 ] , Abadie & Gulgou [ 2 ] e Schittkowski [ 34 1 .
O método tem total analogia com o método de gradiente de Wolfe ,e

portanto, com o simplex ,logo a idéia básica é que um conjunto de restrições de
igualdades não-lineares é um sistema de equações , onde , de maneira ímplícita é
possível colocar algumas variáveis em função das outras .

Assim , minitnizar com esse conjunto de restrições passa a ser um problema
irrestrito ,cujas variáveis são exatamente as variáveis escolhidas como independentes .
Esta fundamentação se dá pelo teorema da função implícita.
MINIMIZAÇÃO RESTRITA VIA RESOLUÇÃO DAS EQUAÇÕES KARUSH-
KUHN -TUCKER
As técnicas para otimização irrestrita podem ser estendidas para o problema
minimizar f ( x )
sujeitoa: h ( x ) = O
O par ( x* , p* ) , satisfazendo as condições de otimalidade de primeira ordem
K m s h - Kuhn - Tucker ( 1.11) ,é solução do sistema de equações não-lineares :
Vf(x) + p t ~ h ( x )= O ( 2.6
h(x) = O ,
onde as variáveis x e p sao chamadas de variáveis primais e duais , respectivamente.
Para termos uma solução p única em ( 2.6 ) num ponto ótimo x*, este deve ser
um ponto regular do problema ( 2.5 ) , que corresponde ao Jacobiano do segundo
conjunto de igualdades do sistema ( 2.6 ) ,ser não-singular no ponto x* .
Devido a esse fato , os algorítmos que resolvem as condições de otimalidade de
primeira ordem, requerem a hipótese de que os iterados xk sejam pontos regulares
dos problemas .
Fazendo-se :
temos :
onde :
é a Hessiana da função Lagrangeana definida em ( 1.10 ) .

Os métodos baseados na resolução das equações Karush- Kuhn - Tucker ,
basicamente se utilizam do método de Newton para resolução do sistema de
equações não-lineares ( 2.6 ).
A iteração de Newton que começa em ( xk , pk ) ,tem como próximo ponto
( Xk"' , pk+l ) ,a solução do sistema linearizado :
Sob condições especiais, a sequência de pares gerada converge para um par ótimo
(x* & * I .
PROGRAMAÇÃO QUADRÁTICA SEQUENCIAL
A programação quadrática sequencial é um método bastante empregado em
problemas d e otimiza@b aão-linear com restriçóes . É wui técniea Quasi-Newton
baseada na primeira idéia proposta por Wilson [ 60 1, e interpretada por Beale [ 7 1.
Pesquisadores tais como Bard e Greenstadt 5 ] ,Biggs [ 13 ] e outros mais, também
desenvolveram esse método .
Um programa quadrático é uma classe de problemas de otimização com
restrições, tais que a função objetivo é uma função quadrática , e as restrições são
necessariamente lineares . Existem técnicas eficientes para resolver estes problemas,
mesmo quando restrições de desigualdades são incluídas . A solução exata é obtida
após um número f i t o de iterações.
Para explicar a idéia de Wilson ,consideremos o seguinte problema :
minimizar f ( x )
sujeitoa : h ( x ) = 0,
onde temos a função objetivo e um conjunto de restrições, geralmente não-lineares
todas diferenciáveis .
Conforme exposto em Martinez [ 43 ] , o método de Wilson consiste em
substituir, em cada passo , a função objetivo por urna aproximação quadrática , e as
restrições por equações ou inequações lineares .

Dessa maneira .o subproblema a ser considerado em cada iteração é
consideravelmente mais simples em comparação ao problema original , ou seja , o
subproblerna se constitui em um problema de programação quadrática ( PQ ) da
forma :
onde d é a direção de deslocamento ,e B é urna matriz defùida positiva ,

basicamente tomada como uma aproximação Quasi-Newton da Hessiana.
Se adota B como uma matriz defluida positiva com o objetivo de garantir a
existência de ponto de mínimo global do problema ( 2.12 ) ( o que não
necessariamente acontece, quando se toma B como a própria matriz Hessiana do
Lagrangeano ) .
Como o problema ( 2-12 ) é convexo ,o mínimo global satisfaz as condições
de otimalidade de KKT ,isto é :
onde p é O vetor multiplicador de Lagrange . Então , ( d ,p ) pode ser obtido ,
resolvendo-se o problema ( 2.12 ).

Baseado nessa idéia, para resolver o problema geral de programação não-linear
simultaneamente com retrições de igualdades e desigualdades , Wilson na sua
proposta definiu a direção de busca d , e novas estimativas dos multiplicadores de
Lagrange y e h para a resolução em cada iteração do subproblema :
O algorítmo de Wilson de programação quadrática sequencial é assim , uma
generalização dos métodos de Newton aplicado ao sistema de condições KKT. De
uma maneira genérica ,nos algorítmos de programação quadrática sequencial , a matriz
B é definida como uma aproximação Quasi-Newton da Hessiana da Lagrangeana .
Ademais a função de mérito utilizada na busca linear é normalmente uma função de
penalidade exata que contempla simultaneamente a função objetivo e a observância
das restrições do problema ,como por exemplo :

MÉTODOS DE PENALJDADES
Dado o problema de programação não-linear com restrições da forma :
minirnizar f (x)
sujeito à : x E S
A idéia comum aos métodos de penalidades é a de resolver o problema acima,
transformando-os na resolução de problemas irrestritos sob a seguinte forma:
minimizar f ( x ) + P (x ) (2.17 )
x E Rn
A função P ( x ) ,denominada função penalidade, deve incorporar de urna forma
conveniente o espaço viável S .
Os métodos de penalidades podem ser basicamente classificados em métodos de
penalização exterior e penalização interior.
Esses métodos transformam o problema restrito em um problema irrestrito,
introduzindo as restrições na função objetivo, penalizando qualquer violação das
mesmas . Nessa família de métodos , a função de penalidade gera uma penalidade
positiva para pontos inviáveis ,e em contrapartida não penaliza os pontos viáveis.

Esses métodos obtém a solução do problema original através de uma sequência
de rninimizações irrestritas . A sequência de pontos de ótimos gerada nesse processo
tem como limite um ponto, que para esse caso ,a função de penalidade P ( x ) deve
satisfazer :
i) P ( x ) é contínua
íi) P ( x ) 2 o
iii) P ( x ) = O # XES
O efeito da função de penalidade exterior é visto na figura 1 :
Figura 1 : Penalização Exterior
O uso das funções de penalidades exterior em problemas restritos foi proposto
originalmente por Courant [ 20 ] . Subsequentemente Camp [ 15 ] discutiu esse
procedimento para resolver problemas não-lineares . No entanto , o estudo detalhado
de tais métodos para resolver problemas práticos foi apresentado por Fiacco &
McCorrnick primeiramente em [ 24 ] ,e mais detalhadamente em [ 25 1. Outros autores
como : Avriel [ 4 ] ,Polak [ 51 ] , Luemberger [ 42 ] ,Zangwill [ 67 , 68 ] , Himrnelblau
[ 33 ] ,Lootsma [ 40 ] e Osborne e Ryan [ 49 ] também estudaram esses métodos.

A primeira função de penalidade para o problema restrito , com restrições de
igualdades :
minllnizar f(x) ( 2.18 )
sujeito&: h(x) = O ,
sugerida por Courant [ 20 ] em 1943 ,foi definida de tal forma a produzir o problema:
minimizar f ( x ) + y [ h ( x ) ] 2 ; y 2 0
x E Rn
Assim, nesta proposta ,a resolução de problemas com restrições de igualdades , é
obtida através de uma seqüência de minimizações da forma :
onde ( ck ) é uma seqüência de escalares positivos com ck < ck+~ para todo k ,
e ck ++ , as funções f ( . ) : Rn + R , h ( . ) : Rn + RP são contínuas , e

I.I é a norma Euclideana, conforme apresentado com detalhes em Fiacco &
McCormick [ 25 1.
Considerando o problema de programação restrito a desigualdades :
minimizar f (x)
sujeitoa: gi(x)<O ; i = l , ..., m ,

Zangwill [ 67 , 68 ] usa duas alternativas de funções de penalidades que
produzem problemas irrestritos :
Agora, considerando o problema geral de programação ,onde as funções f , g e
h são contínuas em Rn e S = ( x / g i ( x ) 2 0 , i = l,...,m , h j ( x ) = O , j = l , ...,p ) é o
conjunto viável . Zangwiii em [ 68 ] , generaliza as penalidades definidas anteriormente
através das fbnções cp e 4 de variáveis 5ER por :
onde oc 2 O e p 2 O são constantes dadas usualmente iguais a 1e 2
respectivamente, e toma :
ou seja :
Analogamente a ( 2.19 ),o problema original é resolvido através da resolução da
seqüência de problemas :
minimizar f ( x ) + l l y k ~ ( x ) ; k=0,1 ,........ ( 2.28 )
x E R"
Uma outra classe de técnicas de minimização sequencial bastante utilizada para
resolver problemas de programação não-hear sujeito a restrições de desigualdades
são conhecidas como :
Estes métodos , tais como os métodos de penalidade exterior , substituem a
resolução de um problema restrito pela resolução de uma sequência de problemas
irrestritos, em que a função objetivo é igual à função objetivo original, adicionada do
termo de penalidade ,no qual são consideradas as restrições .
Essa família de métodos trabalha unicamente com pontos viáveis, ou seja, com
pontos interiores à região viável.
Assim , nesses métodos obtém-se novos pontos , também viáveis que
gradativamente vão se aproximando da eonteira da região viável a medida que se
diminue o termo de penalidade.
O termo de penalidade tem o papel de desestimular a aproximação da Konteira
da região viável . Esse desestímulo é efetuado por uma " barreira " resultante da
contribuição do termo penalidade na função objetivo .. Entre as vantagens ,está o fato

de trabalharmos na região viável, obtendo-se pelo menos uma solução viável , caso
ocorra uma parada prematura .
Prova-se que, se tivermos uma sequência { xk ) convergente , então o limite é
uma solução ótima para o problema original . Ademais é provado que f ( xk) -+ f * ,
onde { xk ) é a seqüência de pontos gerados pelo algoritmo , e f * é solução
ótima do problema original .
Para esse caso , a função de penalidade P ( x ) deve satisfazer :
i) P ( x ) é contínua
ii) P ( x ) 2 o
iii) P ( x ) -+ oo quando x se aproxima da fronteira de S .
O efeito da função de penalidade interior é visto na figura 2 :
Figura 2 : Penalização Interior

O uso da função barreira foi inicialmente proposto por Frish [ 29 ] em 1955, e
mais tarde por Carro1 [ 16 ] em 1959 , com o nome de CRST - Created Response
Surface Technique . O procedimento foi usado para resolver problemas com restrições
de desigualdades por Box ,Davies e Swann [ 14 ] e Kowalik [ 38 ] .
O problema numérico de como mudar os parâmetros da penalidade exterior e
da penalidade interior têm sido investigado por vários autores , em particular por
Fiaccco & McCormick , que estabeleceram os resultados teóricos fundamentais desses
métodos em seu premiado livro [25 ] para uma discussão mais detalhada.
Várias extensões para os conceitos das funções de penalidade exterior e
interior tem sido feitas . Primeiro a fim de evitar as dificuldades associadas com o
mal-condicionamento quando os parâmetros da penalidade exterior vai para infinito , e
os parâmetros da penalidade interior vai para zero ,por conseguinte ,vários métodos
de parâmetro livre têm sido propostos. Para maiores detalhes, veja igualmente em
Fiacco & McCormíck [ 25 ] ,o método dos centros de Huard [ 35 1 e Lootsma [ 40 1.
Uma descrição integrada desses métodos pode também ser vista em Lootsma [ 41 ] .
Considere o problema de programação restrito a desigualdades :
onde f ( . ) e gi ( . ) são funções contínuas no R".

O conjunto SO = ( x ; g i ( x ) > O ; i = 1 , ... ,m ) deve ter interiornão-
vazio ,isto porque , o método trabalha no interior da região .

O problema irrestrito tem a forma básica :
minimÍzar f ( x ) + pP(x) , ( 2.30 )
X E S0
A função de penalidade P ( x ) pode assumir diferentes formas ;por exemplo
que é a função barreira inversa de Carro1 [ 17 ] , ou
que é a função barreira logarítrnica de Frisch [29 ] .
Para resolver um problema geral de programação não-linear da forma :
minimizar f.( x )
sujeitoà: gi(x) 2 0 ; i = 1 ,...,m
hj(x)=O ; j=l,...,p
pode-se usar um método de penalidade mista, obtida pelo uso simultâneo da
penalização exterior e penalização interior . Para ilustração , a função objetivo

aumentada do problema irrestrito associada ao problema ( 2.41 ),por exemplo ,assume
a forma :
Sob certas condições ,a seqüência { F ( xk*, pk ,qk ) ) converge para f ( x* ) ,o
valor ótimo do problema original, e uma subsequência de { X* ) converge para x* .
Veja Fiacco & McCorrnick [ 24 , 2 5 ] e Lootsma [ 41 ] .
Observa-se que em todos estes métodos algumas preocupações devem ser
ressaltadas. A primeira delas é saber quão bem os problemas irrestritos aproximamo
restrito e , se as soluções destes problemas convergem a solução ótima do problema
original . Outra preocupação é quanto a dificuldades impostas ao problema irrestrito
com o acréscimo da função de penalidade ,e como consequência destas dificuldades , a
escolha do método de minimização irrestrita deve ser pesquisada.
MÉTODO DE PENALIZAÇÃO EXATA
A idéia central no método de penalização exata é construir funções de pena-
lidade que são exatas , no sentido de que , a solução dos problemas de penalidade,
produzem a solução exata para o problema original, para um valor nnito do
parâmetro de penalidade.
Com estas funções não é necessário resolver uma sequência infinita de
problemas de penalidade para obter a solução correta.
Um dos primeiros desses métodos é devido a Zangwill [ 67 ] usando uma
função de penalidade exterior linear . Posteriormente Evans , Gould e Tolle [ 22 1,

conforme exposto em Avriel [ 4 1, desenvolvem uma teoria geral sobre a penalização
exata para uma classe de funções de penalidades diferenciáveis por partes.
Por exemplo ,para o problema geral de programação da forma :
minimizar f ( x )
sujeitoà: g i ( x ) 2 0 ; i = 1 , ..., m
hj(x) = O ;j = 1 , ...,p
a função de penalidade valor-absoluto proposta em Zangwill [ 66 ] é :
onde o problema penalizado se escreve como :
rninimizar f ( x ) + c.P(x),
x E R"
para alguma constante positiva c .
Zangwill[ 67 ] , em 1967 prova a existência de um valor tal que para todo
c >2 ,a solução do problema ( 2.37 ) é solução do problema origina1 ( 2.3 5 ) .

Todavia , essa aparentemente extraordinária vantagem desse método desaparece
face à presença das não-diferenciabilidades . Resulta por essa razão , que essa
abordagem tem quase unicamente um interesse de natureza teórica.
Seguindo as linhas apresentadas em Bertsekas 1 12 f , mostraremos que é
possivel construir um problema de minimização irrestrita diferenciável envolvendo
minimização em x e p , e tendo soluções ótimas que são chamadas de par KKT
para o problema :
minimizar f ( x ) ( 2.38 )
sujeitoa: h ( x ) = O
onde as ftinções f , h E c2 n0 R" . Para tal , precisamos considerar a função
Lagrangeana
~(x,P=
) f W + 1 l ~ U x 1,
as condições necessárias para o t W d a d e
V,l(x,p) = O , V,l(x,p) = h(x) = O,
e o problema de minimização irrestrito :
minimizar \ ~ ?4 1 V , I ( x , p ) j2
l / z l I ~ ( x )+
( x , p ) €RnxRP
Observa-se que ( x* , y* ) é um par KKT para o problema original se , e
somente se , ( x* , y* ) é um mínimo global do problema irrestrito . Logo é possível
encontrar urna solução para o problema restrito a igualdades , resolvendo-se o
problema irrestrito dado acima.
Uma dificuldade dessa abordagem , é que a distitiqão entre mínimo local e
máximo local do problema ( 2.38 ) é completamente perdida , quando da passagem
para o problema irrestrito ( 2.39 ) .
Como uma alternativa para o problema ( 2.39 ) ,podemos considerar o problema:
onde r e s são parhetras positivos .
Como motivação para isso , mencionamos o fato de que, para todo r > O e
s >O .
se ( x* , y* ) é qualquer par KKT para o problema ( 2.38 ) então o par
( x * , p* ) é um ponto crítico da função objetivo do problema (2.40).
Nossa esperança, no entanto ,é que introduzindo na h g ã o objetivo a função
Lagrangeana 1( x , p ) , e escolhendo-se apropriadamente r e s ,podemos construir no
problema irrestrito ( 2-40 ) uma preferência para mínimo local em vez de máximo
local .
A relação entre os pontos críticos da função objetivo do problema ( 2.40 ) com
os pares KKT do problema (2.38 ) é dado no teorema seguinte :
TEOREMA 1 :
Seja X x A um subconjunto compacto de R" x RP. Suponha que Vh ( x )
tenha posto p , para todo x E X . Existe um escalar a > O , e para cada

- - -
a E ( O, a ] um escalar c > O tal que, para todo c e a com a E ( O, a ] e

-
c 2 c ( a ) ,todo ponto crítico da função objetivo de ( 2.40 ) pertencendo ao sub-
conjunto X x A é um par KKT para o problema ( 2.38 ) .
Se v2, 1( x ,p ) é semidefinida positiva para todo par ( x , p ) pertencente à

-
X x A ,então a pode ser tomado como qualquer escalar positivo .

Demostração : Ver Bertsekas [ 12 ] .
Essa abordagem apresentada por Bertsekas é um dos caminhos que nos leva
aos métodos Lagrangeanos aumentados .
LAGRANGEANO AUMENTADO OU DOS MULTIPLICADORES
Os métodos Lagrangeanos Aumentados também conhecidos como métodos dos
multiplicadores , podem ser vistos como uma extensão da idéia da função de
penalidade, com a perspectiva de evitar a necessidade do parâmetro p de penalidade

definido abaixo na equação ( 2.42 ) se tornar muito grande . Consideremos o
problema de programação não-linear com restrições de igualdades:
minimizar f ( x )
sujeitoa: h j ( x ) = O ; j = 1 , ...,p
Para este problema a função objetivo modificada do problema irrestrito
correspondente à penalização exterior de Courant [ 20 ] se apresenta na forma :
cuja solução x ( p ) -+ x* quando p + a.
Por outro lado, as condições de primeira ordem estabelecem :
em qualquer ponto ótimo x* . Segue-se que, o gradiente da função
é zero no par ( x* , p* ) ,para todos os valores de p . Portanto ,parece ser melhor
substituir a função ( 2.42 ) pela função :

onde p > O é o parâmetro de penalidade, e p é o multiplicador de Lagrange .
A função ( 2.44 ) definida acima , é a função Lagrangeana Aumentada proposta
por Hestenes [ 32 1.
O método de penalidade quadrática à função Lagrangeana proposto por
Hestenes ,consiste em resolver uma seqüência de problemas da forma :
onde ( pk } é urna sequência limitada do R", e ( pk } é uma seqüência de
parâmetros satisfazendo 0 < pk < pk'" b' k , pk + m.
Observa-se na versão original dos métodos de penalidades, os multiplicadores pk
são tomados iguais a zero, isto é , pk = O b' k = 0 , 1 , ...
O resultado que p* é a escolha ótima do vetor parâmetro de controle na
função proposta por Hestenes é expresso no seguinte :

TEOREMA 2 :
Se as condições de suficiência de segunda ordem valem num par ótimo
( x* , p* ) , então existe p' 2 O tal que ,para qualquer p 2 p' , x* é um
minimizador local da função L ( x , p* , p ) , isto é ,x* = x ( p* ) .
Deonstração : Fletcher [ 27 ] .
Já Powell [ 51 ] ,de uma forma independente , propôs a seguinte função :
onde ej é uma tolerância a violação a cada restrição e T é o parâmetro de penalidade ,
que é absolutamente equivalente a formulação de Hestenes ( eq . 2.8 ) . Da mesma
forma ,Haarhoff e Buys [ 3 1 ] propuseram uma outra equação equivalente .
O método Lagrangeano Aumentado pode ser também aplicado a problemas restritos a
desigualdades . Por exemplo : Rockafellar [ 55 , 56 ] sugeriu a seguinte função :
Em outro trabalho , Rockafellar [ 54 ] , para o caso do problema de
programação convexa com restrições de desigualdades mostra que, um ponto de sela
irrestrito da função ( 2.11 ) corresponde a uma solugão do problema de programação
convexo original .
Como vimos, o Método dos Multiplicadores ou do Lagrangeano Aumentado
para problemas de programação não-linear restrito a igualdades, foi independentemente
introduzido por Hestenes [ 32 ] , Powell [ 52 ] e Haarhoff & Buys [ 31 ] .Eles
propuseram um método dual de solução no qual quadrados das funções restrições são
adicionados a função Lagrangeana.
A característica associada a esse método é a minimização irrestrita de urna
função objetivo L ( . ) contínua, que envolve multiplicadores de Lagrange e um termo
de penalidade . O temo de penalidade tem por finalidade fazer x* um ponto de
mínimo irrestrito .
A expressão da função Lagrangeana Aumentada é dada por :
onde 1 ( . ) é a função Lagrangeana simples e P ( . ) é a função de Penalidade .
Uma série de minllnizações irrestritas sobre a função Lagrangeana aumentada ou
penalizada é seguida de uma atualização do vetor de multiplicadores de acordo com
uma regra simples. Powell [ 52 ] mostra que , se as condições de suficiência de segunda
ordem para otimalidade são satisfeitas, o algorítmo converge localmente numa taxa linear.
A vantagem do algorítmo é que ele produz uma estabilidade numérica que não
é encontrada nos métodos de penalidades usuais . Por outro lado, Miele et a1 [ 44 ,45 ,
46 , 4 7 ] modificou e melhorou os métodos de Hestenes e Powell e ,tem obtido resultados
computacionais muito bons para o caso restrito a igualdades .
Fletcher [ 27 , 28 ] desenvolveu uma outra técnica relativa às de Hestenes e
Powell , que em vez de atualizar o vetor dos multiplicadores após uma sequência de
minimizações ,o vetor dos multiplicadores é ajustado simultaneamente ao processo de
minimizações sobre as Lagrangeanas penalizadas .
Já, Kort & Bertsekas [ 37 ] consideraram o caso mais geral em que o problema
apresenta simultaneamente restrições de igualdades e desigualdades em seus métodos
de multiplicadores para programação convexa .
Arrow , Gould & Howe [ 3 ] estudaram a função Lagrangeana aumentada de
Rockafellar , e a incluiu numa classe geral para problemas de programação não-convexa,
onde estabeleceram propriedades locais de ponto de sela . Já Pierre & Lowe [ 50 ]
sugeriram algorítmos de multiplicadores, considerando restrições de igualdades e
desigualdades , utilizando função Lagrangeana aumentada , e mostra propriedades de
convergência local .
VANTAGENS DO MÉTODO DOS MULTIPLICADORES COM RELAÇÃO
AOS MÉTODOS DE PENALIDADES
Uma vantagem do método dos multiplicadores é que não é necessário fazer os
parâmetros de penalidades pk ir para o infinito a fim de obtermos convergência, assim
evitando ou moderando a conhecida dificuldade do mal-condicionamento do problema
penalizado .
Uma segunda vantagem do método dos multiplicadores é que sua taxa de
convergência é consideravelmente melhor do que a dos métodos de penalidades, isto
é , nos métodos dos multiplicadores , a taxa de convergência é linear ou superlinear ,

enquanto que ,nos métodos de penalidades sua taxa de convergência é muito inferior e
depende essencialmente da taxa que o parâmetro de penalidade é aumentado.
Esta vantagem em velocidade de convergência tem sido verificada em muitos
estudos computacionais ,onde uma redução consistente em tempo de computação passou
de 80% para 30% em certos problemas de programação envolvendo restrições de
igualdades ,quando são atualizados via
Li = hk f $.h@)
com relação ao método de penalidade, onde h k é mantido constante em todas as
iterações .Por outro lado , uma desvantagem do método Lagrangeano é que ele
requer um bom ponto inicial a fim de obtermos a convergência para uma solução
ótima . Para aumentarmos a região de convergência é necessário fazermos combinações
com outros métodos , basicamente do tipo de região de confiança , para assim
obtermos propriedade de convergência global .
Na medida que este trabalho se fundamenta numa extensão da Penalização
Hiperbólica , apresentaremos como preâmbulo este método com um particular
detalhamento.
O método de penalização hiperbólica apresentado por Xavier [ 62 ] trata de resolver
o problema de programação não-linear com restrições de desigualdades da forma :
minimizar f ( x )
( 2.49 )
sujeito à : gi ( x ) 2 O ; i = 1 ,..., m
Sua solução é obtida através da resolução de uma sequência de problemas de
minimizações irrestrito da função objetivo f ( x ) acrescida de um termo de penalidade
P ( x ,a ,z ) para cada restrição, isto é:
onde a função de penalidade P ( . ) é definida por :
com
Figura 3 : Função Penalidade Hiperbólica
Aumentando-se o ângulo a da assíntota da função penalidade ,provoca-se um
significativo aumento da penalização fora da região viável, enquanto que, simultaneamente,
reduz-se a penalização para pontos dentro da região viável . O processo continua até que se
consiga um ponto viável. Veja figura 4 .

Figura 4 : Aumento do parâmetro a
A partir daí ,mantém-se o ângulo a constante e diminue-se sequencialrnente o
valor da distância z . Dessa maneira consegue-se que a penalização interior torne-se
cada vez mais irrelevante , mantendo-se o mesmo nível de proibitividade fora da
região viável. Este fato pode ser visto na figura 5 .

Figura 5 : Diminuição do parâmetro .r:
Algumas características fundamentais deste método , por exemplo , mostram que

quando se manipula o parâmetro a ,a penalização hiperbólica se comporta
sirnultaneamenta aos métodos de penalização exterior , e quando se manipula o
parâmetro z o seu comportamento torna-se similar aos métodos de penalização
interior .
Uma outra forma para a função de penalidade P (. ) se dá quando definimos :
hi=%tgai , ( 2.52 )
obtendo-se a expressão :
com
De maneira simplificada apresentamos o algorítmo O de penalização hiperbólica
proposto por Xavier [ 6 4 ] ,para resolver o problema de programação não-linear com
restrições de desigualdades .
1 ) Faça k =O . Tome valores iniciais xO, h' > O e z1 > O
2) Faça k : = k + l .
Resolva o problema de minimização irrestrito
a partir do ponto inicial xk-' obtendo um ponto ótimo intermediário xk.
3 ) Atualizar os multiplicadores de Lagrange :

4 ) Atualizar os parâmetros de penalidades z
k+l
Ti =qz;" ; O < q 5 1
Vá para o passo 2 .
Pode-se observar que existe uma ligação deste método com a função Lagrangeana, e
por consequência, com as condições de otitnalidade. Temos a função Lagrangeana relativa
ao problema ( 2.49 ) defínida como :
e com alguns cálculos chega-se à forma :
onde LH( . ) é a função Lagrangeana Hiperbólica .
Dessa forma podemos obsevar que a função objetivo modificada corresponde a
um função Lagrangeana aumentada ou função Lagrangeana modificada , como
preferem outros autores .

Vejamos agora uma propriedade da função de penalização hiperbólica que
relaciona avariação de sua inclinação com a variação do parâmetro h desta função.
Para valores y < O , o aumento do parâmetro h sempre corresponde a um
decréscimo da derivada da função de penalização P( y, h ,.r: ) em relaçào a y , ( ou
equivalentemente ,um aumento da inclinação da penalidade .

-
Enquanto para um certo valor y > O fixo , e dado t > O , existe um valor h
tal que , para h 2 2 ,a derivada da função penalidade P ( y , h ,t ) em relação a
y é urna função crescente com h .

Demonstração :
Primeiramente façamos um estudo do comportamento da inclinação da função
penalidade em relação a modificação em seu parâmetro h . Para facilitar a notação,
vamos escolher a função penalidade dada por:
Calculando-se a derivada da função penalidade em relação a y ,teremos :

Pelo simples exame da expressão ( 2.57 ) acima podemos observar que esta derivada
varia no intervalo ( - 2 h ,O ) . Agora, vamos estudar o comportamento dessa derivada com
relação ao parâmetro h . Calculando-se a derivada da expressão ( 2.57 ) em relação a h
teremos :
Pela análise da expressão ( 2.58 ) acima, e considerando que h 2 O , podemos

ver que , para valores de y < O , ou seja , para pontos inviáveis , a expressão
( 2.5 8 ) é negativa . Vale dizer : a derivada da função penalização em relação a y diminui
crescentemente com h para pontos inviáveis , ou seja , a inclinação da curva se torna

crescentemente mais escarpada com o aumento de h .
Por outro lado , para valores de y > O , que correspondem a pontos viáveis ,
temos numa faixa inicial de y , a expressão ( 2.58 ) negativa ,o que corresponde a um
comportamento da penalização análogo ao descrito anteriormente. Todavia , para

valores maiores que y será observada que a expressão ( 2.58 ) é positiva, e o
comportamento será exatamente o contrário ,ou seja , a inclinação se reduz com o
aumento de h .
Calculamos agora ,para um ponto y > O fixo , qual é exatamente o valor de
h em que ocorre a transição entre esses dois comportamentos acima descritos .

Devemos assim, achar as raízes da equação :
Da expressão ( 2.58 ) obtém-se a equação :
que tem uma única solução com significado ( h 2 O ) , a raiz :
onde
RESOLUÇÃO DO PROBLEMA DE PROGRAMAÇÃO NÃO-
LINEAR COM RESTRIÇÕES DE IGUALDADES VIA
PENALIZAÇÃO HIPERBÓLICA
O objetivo deste trabalho é resolver o problema de programação não-linear com
restrições de igualdades da forma :
minimizar f ( x )
sujeitoa: h j ( x ) = O ; j = 1 , ...,p
onde as funções f ( . ) : R" +R e hj ( . ) : R" +R são contínuas.
A estratégia a ser utilizada para resolver o problema acima é baseada em um
novo método derivado do algorítmo de Penalização Hiperbólica ,Xavier [ 62 ] .
Este algorítmo se destina a resolução de problemas de programação não -linear
restrito somente a desigualdades, cuja solução é obtida através da resolução de uma
seqüência de problemas de minimizações irrestritas da forma ( 2.50 ) como descrito
anteriormente.
Sendo assim , a primeira providência é transformar cada restrição de igualdade do
problema ( 3.1 ) em duas restrições de desigualdades produzindo um problema equivalente
da forma :
rninimizar f(x)
sujeitoà: h j ( x ) % O ; j = l , ...,p
hj(x) 2 0 ; j = 1 , ...,p
Supondo-se por hipótese que todos os multiplicadores são positivos, então o
problema definido abaixo por :
minimizar f ( x )
sujeitoa: h j ( x ) IO ;j = 1, ...,p
é equivalente ao problema anterior ( 3.2 ). Nesta hipótese , equivalentemente , estamos
supondo que as restrições ( 3.2.b ) são redundantes , isto é , os multiplicadores

correspondentes são nulos . Dessa maneira , podemos acrescentar ao problema ( 3.3 )
restrições relaxadas não-ativas obtendo-se assim o problema equivalente :
minimizar f ( x )
sujeito à : hj ( x ) r O ; j = 1 , ...,p
hj(x) 2 ~ j - ; j = 1 , ...,p ,
sendo - 5 O , j = 1 , ... ,p .
Como o algorítmo de penalização hiperbólica assume a hipótese de que a
região viável tenha interior não-vazio , para a sua utilização , no problema ( 3.2 )
devemos relaxar as restrições colocando folgas superiores ~j' e inferiores . Assim

~ j -
obtemos o problema :
com E; 2 O e Ej- IO , que nos dá condições necessárias para utilizmos o

algorítmo da penalidade hiperbólica.
A figura abaixo mostra o efeito provocado pela relaxação quando se trata do
problema ( 3.5 )
Figura 6 : Relaxação das restrições de igualdades
ou seja, provoca uma região viável com interior não-vazio ,associada a cada restrição
de igualdade .
Assim fazendo , vamos resolver uma sequência de problemas irrestritos da
forma :
onde :
com m = 2p . A k ç ã o de penalidade P( . ) definida de acordo com a expressão
( 2.5 1 ) acima citada ,tem a forma :
( 3.7
Alternativamente a função objetivo do problema irrestrito pode ser escrita como :
onde o gradiente da hnção F( x , a , .c ) é dado por :

VxF(x,a,z) = V f ( x )- %
1
,
tga (h,( x ) - E J)
j=i [ t ,(hjx - E + r,
2
No algorítmo de penalização hiperbólica , como descrito em Xavier [ 64 ] , na
resolução da sequência de problemas irrestritos simultaneamente a correspondente
sequência de pontos de mínimos ( 2 também é gerada uma sequência de
estimativas dos multiplicadores de Lagrange .
Assim , denominando respectivamente e OS multiplicadores associados
às restrições ( 3.6a ) e ( 3.6b ) .
Na iteração k teremos :
1 k k
i tga, (h, (x ) - E:-)
- ,
Pela análise das expressões ( 3.9a ) e ( 3.9b ) podemos ver que sempre serão
observadas as relações :y > O e q: > 0.
Na expressão ( 3.9 ) ,vamos definir :
h.3k -- y.Jk - q.Jk 9
que denominamos multiplicador de Lagrange equivalente .
Veremos uma interessante associação entre o sinal dos multiplicadores de
Lagrange equivalentes e os valores das restrições .
PROPOSIÇÃO 2 :
Se h F > O , então -hj(xk)+clf > hj(xk)-cj-
Demonstração :
Por hipótese temos : h: > O , logo da expressão ( 3.10 ) obtemos :
11- . y1 tga (hj(* k ) - E;-)

I -
1 J[$$a: (h, (xk) - &:-)r 1
+( 2 ~ ) ~
Fazendo-se :
podemos escrever a desigualdade anterior como :
u ~ . [ v ~ + ( T ? ) ~> ] v ~ . [ u ~ + ( $ ) ~ ] Z
u2>> v' u 2 - 2 > o o

(u + v).(u - v ) > o
Como u +v > O ,então a desigualdade anterior nos dá :
ou seja :
Como vimos , a relaxação de cada restrição de igualdade implica porém numa
duplicação de restrições a serem consideradas, m = 2p . Numa primeira vista, este
aumento do número de restrições poderia comprometer seriamente essa estratégia, podendo
até mesmo inviabilizá-la . Todavia, devemos esclarecer, que em métodos do tipo
penalidades ou lagrangeanos , normalmente a maior parte dos custos computacionais
decorrem dos custos de avaliação das funções intervenientes no problema e de seus
gradientes . Como no problema ( 3.5 ) , as restrições dadas por ( 3.5.a ) e ( 3.5.b )
envolvem as mesmas funções, podemos concluir que essa proposta não implica num
aumento do custo computacional proporcional ao aumento do número de restrições.
Durante a resolução da seqüência de minimizações ( 3.6 ), pretende-se efetuar
uma conveniente manipulação das folgas zj' e rj- de modo a buscar uma crescente
aproximação do problema relaxado ( 3.5 ) ao problema original ( 3.1 ), no limite, obtendo-
se a equivalência . Além do mais , espera-se que nesse processo iterativo , a partir de
um certo ponto somente um dos lados das retrições ( 3.5.a ) ou ( 3.5.b ) seja violado ,
permitindo o reajuste repetitivo da correspondente folga, de sorte a provocar sua
convergência a zero enquanto que a outra folga permanece constante.
Na verdade, esse mecanismo acima idealizado equivale ao uso de uma estratégia de
definição de conjunto ativo (correspondente às folgas que convergem a zero) mantendo
todavia salvaguardas como proteção a uma definição equivocada desse conjunto ativo.
Essas salvaguardas são desempenhadas pelas penalizações correspondentes ao lado oposto
( lado em que a folga permanece constante ) .

Inspirado nas idéias acima expostas surge de uma forma natural o Algorítmo I,
destinado a resolver o problema de programação não-linear com restrições de igualdades
( 3.1 ) ,que apresentamos a seguir :
ALGORÍTMOI
PENALIZAÇÃO HZPERBÓLICAPARA RESTRIÇÕES DE IGUALDADES
Faça k = O , ajl = ao , j = l ,..., p , 7' = TO , sendo O < d < 7d2
e z O >0 .
Tome ponto inicial xO
2 - "CONTAGEM DA ITERAÇÃO"
Faça k : = k + l
3 - TESOLUÇÃO DO SUBPROBLEMA"
Resolver o problema de minimização irrestrita
conforme definido em ( 2.50 ) a partir de um ponto inicial xk" , achando
um ponto ótimo intermediário xk .

4 - "TESTE DE VIABILIDADE"
Teste se o ponto xk obtido é viáuel para o problema relaxado( 3.5 )
Se for viável vá para a passo 6.
k k 7l
af:=pa,+(l-p)2 , = , .p , O < p < 1
Faça :
Va pam o passo 3
7 - "CÁLCULO DAS DISTÂNCIAS SIGNLFICATIVAS9'
Calcule as distâncias a esquerda e a direita do valor h, (xk) as folgas .
8 - "TESTES DE WOLAÇÃO PARA CADA RESTRTCÃO"
Para cada restrição j = 1, ... ,p faça :

8A - : ( " Se o ponto xk for tal que a distância a direita for significativamente
maior do que a distância à esquerda ,processa a diminuição da folga inferior " ).
Se [ d j ' > d j - ] e [ h j ( ~ ~ ) < 12 ,~ com

. ~ ~p =
definido em ( 2.62 )
k -
k+l-- - Ej
1o
Então faça :
k+l + k +
Ej = Ej
8B : ( "Se o ponto xk for tal que a distância à esquerda for significativamente
maior do que a distância à direita ,processa a diminuição da folga superior " ) .
Se [ dj- > dj' ] e [ h j ( x k ) > - 2 b . ~] ~, com =

II."
k +
1o
Então faça :
k+l - k -
8C - : "Diminuição de ambas as folgas se não houver proximidade significativa"
Em caso contrário,
R-i1 - k
r, =-100z
k+l + k
Faça : &i = +I00 z
Vá para o passo 2 .
~ ~ s c u s s AINICIAL
o DO ALGORÍTMO
A estrutura do algorítmo é constituída de tal forma que ,para cada restrição o
- E; ) seja reduzido manotonamente .

intervalo entre as folgas ( ~j'
Este procedimento tem como perspectiva forçar uma aproximação gradativa dos
pontos de múillnos intermediários xk ao ponto ótimo x*
Figura 7 : Redução do intervalo entre as folgas

A figura 7 dá uma idéia de como a região viável relaxada vai gradativamente
se aproximando do espaço viável ( variedade de dimensão ( n - p ) , definido por
S = ( x € R n/ h ( x ) = O ; j = 1 , . . . , p } ,quando as folgas são diminuidas
provocando ,dessa maneira os deslocamentos indicados pelas setas.
Outra componente fundamental do algorítmo é o processo de awnento do
ângulo a ( quando necessário ) com o objetivo de obter pontos de ótimo
intermediários xk viáveis .
A última componente do algorítmo , também fundamental , é a diminuição do
parâmetro .r: , com o objetivo de aproximar o problema penalizado gradativamente do
problema original .
CONDIÇÕES DO PROBLEMA
A fim provarmos a convergência do Algoritmo I, primeiramente é necessário que
estabeleçamos algumas condições sobre o problema a ser resolvido .
( C1 ) : As funções .
f ( .) e h ( ) ; j = 1 ,. m são duas vezes
continuamente diferenciáveis
( C2 ) : Os gradientes Vhj ( x* ) ; j = 1 , ... ,m são linearmente independentes,
dessa forma existe um único multiplicador de Lagrange dado por h* = (hi*,h2*, ... ,
L*) tal que :
V f ( x * ) i- h*.Vh(x*) = O
( C3 ) : A matriz Hessiana da função Lagrangeana 1( x ,h ) dada por
é positiva definida sobre o plano tangente correspondente às restrições, isto é :
para V z € R n , z f O tal que zt.Vhj(x*) = O , j = l ,..., p
( C4 ) : Existe um E > O tal que o conjunto defhído por :
+
S, = { X ; hj(x) 5 Ej , hj(x) 2 E j l , . , =) é limitado.
( C5 ) : Não-degenerescência ou complementaridade estrita, isto é , hj* # 0,
j = 1,...,p.
( C6 ) : O problema penalizado ( 3.6 ) tem solução xk .
( C7 ) : O problema original ( 3.1 ) tem solução ótima x* .
Vamos também apresentar alguns resultados que serão utilizados nos nossos
desenvolvimentos teóricos de forma a obter a convergência do algorítmo .

RESULTADO 1 : ( Mínimo viável )
Se as condições ( C1 ) , ... , ( C6 ) forem obedecidas ,existe a ( z0 ) tal que ,para
todo a no intervalo a I a < d 2 e para todo z no intervalo O I z I 7" ,
qualquer ponto de mínimo x ( a ,T ) da função objetivo modificada F( x , a , z ) é
viável .
Demonstração : Ver Xavier [ 62 ]
RESULTADO 2 : ( Teorema da função implícita ) ,Ver Avriel [ 4 ]
Suponha que as funções qj a valores reais defhidas sobre um conjunto D ,e

continuamente diferenciáveis num conjunto aberto D1 c D c R"'~, onde p > O e
<pj ( xO, yO) = O para j = 1 , ... , m e ( xO, yO) E D1 . Suponha que a matriz
Jacobiana a' O'( ' tenha posto m . Então, existe uma vizinhança C& (xO,yO)c DI ,
8.xj
um conjunto aberto Da c RP contendo yO, e funções & ; k = 1 , ... ,m a valores
reais continuamente diferenciáveis sobre Dz , tais que as seguintes condições são
satisfeitas :
xk0 = $k(yO) ; k = 1 , ..., m (3.11 )
Para todo y E D2, temos :

Jacobiana 8.Y i (x,Y ) tem posto m . Além do mais ,para y E D2 as derivadas
8.xj
parciais de $k( y ) são as soluções do conjunto das equações lineares.
RESULTADO 3 :
Seja x* um ponto de mínimo local para a problema ( 3.1 ) ,este ponto x* seja
um ponto regular e ademais o par ( x* , h* ) satisfaça à condição ( C3 ) . Então , a
matriz
J = [v 2 ~ ( x *I*)
vh(x*)'
, Vh(x*)
O 1 é não-singular .
Demonstração :
Suponhamos que a matriz J seja singular , então existem vetores y E R" ,
z E Rm, ambos não-nulos tais que , o par ( y , z ) esteja no espaço nulo de J , ou
equivalentemente:
Multiplicando a expressão ( 3.16 ) por yf , e usando ( 3.17 ),necessariamente
devemos ter :
Agora, usando a condição ( C3 ) , que trata da suficiência de segunda ordem ,
podemos concluir que y = O . Assim, o sistema acima se reduz a Vh(x*).z = 0.
Finalmente ,usando a condição ( C2 ) ,devemos ter z = O . Isto contradiz o fato de y
e z não poderem ser ambos iguais a zero, portanto ,a matriz J é não-singular.
RESULTADO 4 :
Tomando as hipóteses do Resultado 3 verdadeiras , então existe um escalar

6 > O e funções continuamente diferenciáveis x ( . ) : Q( 0 , 6 ) + R" e h( . ) :
Q( 0,6 ) + R" tais que x ( O ) = x* , h ( O ) = h* ,e para todo E E Q( 0 , s ) o
par { x ( E ) ,h ( E ) ) são mínimo local e multiplicador de Lagrange para o problema :
rninimizar f (x )
sujeitoà: h(x) = E
Alémdomais, V,f[x(~)]=-h(€) , 'v' ~€Q(0,6). ( 3.19 )
Este teorerna é um resultado da aplicação direta do teorema da função
implícita. Abaixo reproduzimos a demonstração dada em Bertsekas [ 12 1.

Demonstração :
Considere o sistema de equações em ( x ,h ,E ) dado por :
que tem ( x* , h*, 0 ) como solução . Além do mais , o Jacobiano deste sistema com
respeito à ( x , h ) nesta solução é a matriz invertível J do Resultado 3 .

Consequentemente pelo Resultado 2 , teorema da função implícita, existe um 6>O e
hnqões x ( . ) E C' , h ( . ) E C' sobre R( 0 , 6 ) tais que :
Para E suficientemente pequeno , os vetores x ( E ) e h( E ) satisfazem as
condições de suficiência para o problema ( 3.18 ) , em vista do fato de que eles o
satisfazem, por hipótese para E = 0 . Consequentemente , 6 pode ser escolhido de
modo que o par { x ( E ) , h ( E ) ) seja um mínimo local e o correspondente
multiplicador de Lagrange para o problema ( 3.18 ) .
Agora, do sistema (3.22 ) temos :
V e x ( ~ ) . v f [ x ( ~ )+] V , x ( ~ ) . V h [ x ( ~ ) l . h ( =
~ )0
Por outro lado , diferenciando a relação e = h[ x ( E ) ] , em relação a E
obtemos :
I = V,h[x(e)] = V,X(E).~~[X(E)]
Combinando ( 3.23 ) e ( 3.24 ) , temos :
V,f[x(~)] = - h(€) .
Estabelecidos os resultados iniciais ,vamos agora nos deter a análise do funcionamento
do algorítmo até a sua convergência.
A cada iteração k , no passo 3 , é feita a muiimização irrestrita do problema
( 3.6 ), obtendo-se um ponto ótimo intermediário 2 ,ou seja :
xk E argrnin{F(x,ak,zk)),
Dessa forma ,o ponto 2 satisfaz ao sistema :
No passo 4 testa-se a viabilidade do ponto xk . Se o ponto for inviável é
executado o passo 5 do algorítmo ,onde há um acréscimo monótono do parâmentro a da
função hiperbólica .
E a vista do Resultado 1 , Xavier [ 62 ] , haverá um certo valor a ( E ) qile
certamente o ponto de mínimo xk da função objetivo modificada F( x , ak, rk) é
viável para o problema relaxado ( 3.5 ) . Assim , O algorítmo sempre trabalha com
pontos xk viáveis ,isto vale dizer que :

+
hj ( xk ) = ej ; zj- 5 €Ij I zj ( 3.27 )
Devemos ainda considerar que a partir do momento em que ak > a ( E ) ,o
algorítmo executará o passo 6 , em que há uma redução do parâmentro .r: de
penalização .
O passo 7 é um passo intermediário destinado unicamente a calcular os valores
das restrições decorrentes das folgas ( distâncias a esquerda dj- e à direita dj' ).
Vamos agora analizar o passo 8 , que é o mais crítico do algoritmo no que
concerne a sua convergência.
Nesse ponto vamos por facilidade de apresentação , desenvolvimento e sem qualquer
perda de generalidade supor que os multiplicadores de Lagrange do problema original
( 3.1 ) , sejam todos positivos , isto é , hj > O , j = 1 , ... ,p .

Analisando a construção do algorítmo ,para cada restrição j = 1 , ... ,p podemos
particionar a seqüência de iterações no passo 8 segundo as três alternativas
mutuamente exclusivas abaixo apresentadas :
Alternativa 1 :
A partir de uma dada iteração , sempre o teste do passo 8A é satisfeito , ou
seja, sempre são executadas as instruções 8A.1 e 8A.2 .

Alternativa 2 :
A partir de uma dada iteração , sempre o teste do passo 8B é satisfeito ,ou
seja, sempre são executadas as instruções 8B.1 e 8B.2.
Alternativa 3 :
O passo 8C é executado infinitas vezes, não necessariamente consecutivas.
Analisaremos , abaixo , cada uma dessas sequências alternativas :
Discussão inicial da alternativa 3 :
Nessa situação , pela construção do algorítmo , as instruções ( 8C.1 ) e ( 8C.2 )
são executadas infinitas vezes, ( não necessariamente consecutivas ). Como zk + 0,
conforme o passo 6 ,necessariamente devemos ter :
Por ( 3.28 ) e pela viabilidade sj- < hj ( xk ) < cjf , dada no passo 4 ,
podemos concluir que :
Nessa situação , certamente existe uma iteração K3 tal que para toda iteração
k > K3 ,o teste do passo 8B é sempre satisfeito .
Nesse caso ,pela viabilidade do ponto xk temos :

+
hj(xk) I~j
e pela satisfação do teste 8B temos :
hj(xk) > - @.'Ck.
Considerando as duas desigualdades imediatamente acima temos :
-2P.Tk < hj(xk) 5 €j+ ( 3.29 )
Como :E + O , pela instrução ( 8B.1 ) e rk -+ 0 , conforme o passo 6 ,

necessariamente devemos ter :
hj(xk) +O ,
Nessa última situação , suponhamos que para toda iteração k > I(4 , sempre o
teste do passo 8A é satisfeito .
Nesse caso ,pela viabilidade do ponto xk temos :
hj ( xk) > E[ >
e pela satisfação do teste 8A temos :
hj ( x k ) < 2p.Z
Considerando as duas desigualdades imediatamente acima, temos :
q- < hj( xk) < 2p.rk

Como ~ i - 0 ,pela hstruçih ( 8A.1 ) e .rk + O , confome o passo 6 ,
necessariamente devemos ter :
Síntese das alternativas 1 , 2 e 3
Considerando a validade das expressões ( 3.28a ) ou ( 3.30 ) ou ( 3.32 ) ,

podemos concluir que :
h j ( x k ) -+O ; j = 1 , ...,p ( 3.33 )
ou seja, a seqüência de pontos ótimos intermediários se aproximam da região viável
do problema original .
Pela condição C4 , o conjunto S, é compacto , assim a seqüência ( xk ) é
limitada e dessa forma possui urna subseqüência convergente . Tomando-se sem perda
de generalidade a subseqüência como a própria seqüência, temos
Usando o &to das fun@es hj( .) serem contínuas , ( ccmdição €1 ), temos :
Por outro lado ,em virtude da expressão ( 3.33 ) , temos :
- -
implicando que hj (x) = O, j = í , ... ,p , ou seja, que o ponte x é vihel para
o problema original ( 3.1 ).

Para provar que ;é solução ótima do problema original ( 3.1 ) ,devemos ter :
f(x*) = f(X).
Vejamos :
Corno xk é solução Ótba do problema relaxado ( 3.5 ) em qualquer iteração k ,
temos :
F ( x * , c x ~ , z ~2 )F ( x ~ , c x ~ , T ~ )
Tomando o limite temos :
lim F ( X * , C X ~ , T2~ )lirn F ( x ~ , c z ~ , z ~ )

k-tw k w
Considerando que X e x* são viáveis e o fato de que o algoritmo gera uma
seqüência { 1k} tal que O < .rk+' < .rk , k+m

1im r k = O e usando as propriedades
da função penalidade hiperbólica em [ 63 ] ,temos :

- - -
F(x*,a,O) 2 F ( x , a ,O) z
f(x*) 2 f(X) (A)
Por outro lado , considerando que x* é solução ótima do problema original
( 3.1 ) e , como ié viável para este mesmo problema, temos :
f(x*) 5 f(X) (=v

Por ( A ) e ( B ) ,podemos concluir que :
Pelo exposto qcima ,foi qqmonstrado o seguinte teorww:

TEOREMA DA CONVERGÊNCIA PRIRIAL
Sendo xk , como dejinido anteriormente , um ponto tal que :
F ( x k , a k ,T ~ =
) min, F ( x , a k , z k ) ,
-
então existe uma subseguência convergente xk x , e o limite x é um ponto
ótimo para o problema original (3.1 ) .
Provado o teorema da convergência , vamos nos aprofundar nas análises das
alternativas consideradas anteriormente .
Será visto abaixo que , somente a alternativa 1 é válida . Esse resultado tem o
importante significado : A região viável do problema relaxado sempre tem um amplo
interior .
Analisaremos ,outrossim , o comportamento da seqüência dos multiplicadores de
Lagrange equivalentes hj" ,gerada pelo algoritmo .
Análise da viabilidade da alternativa 3 :
Como xk é um ponto ótimo para o problema relaxado , ele satisfaz o sistema
de equações :
No ponto ótimo do problema original, as condições de KKT de primeira ordem
nos fornece :
De outro lado ,considerando xk -t i,ponto ótimo do problema original ,visto
no teorema de convergência, usando a continuidade das funções Vf ( . ) e Vhj ( . ) ,
j = 1 ,. ,p dada pela condição C1 e a independência linear dos gradientes
Vhj ( ) ,j = 1 , . , p dada pela condição C2 , podemos concluir , conforme

estabelecido pelo Resultado 4 , que existe uma vizinhança R1 ( x*, 61 ) em que os
multiplicadores equivalentes hjk , j = 1 , ... ,p , correspondentes aos pontos xk serão
positivos , pois terão o mesmo sinal dos multiplicadores ótimos , por hipótese ,
supomos serem todos positivos.
No processo iterativo do algorítmo , se numa dada iteração o passo 8C for
executado , então na iteração imediatamente seguinte , certamente o teste 8A será
satisfeito , ( ou seja, as instruções 8A.1 e 8A.2 serão executadas ) pelas razões a
seguir apresentadas .
Considerando que os multiplicadores equivalentes são positivos , visto logo

acima, e usando a proposição 2 , temos :
-hj(xk) + E', > hj(4) - E; ( 3.34 )
Dado que na iteração anterior as instruções 8C.1 e 8C.2 foram executadas ,
temos :
- cj- = + Ej ,
4-
( 3.35 )
De ( 3.34 ) e ( 3.35 ) podemos concluir que hj ( xk) < O . Assim, a segunda
parte do teste 8A [ hj( xk ) < 20 .rk ] será também satisfeita pois >0 e z > O .
Vale dizer , o lado correto da região viável será acionado na iteração

imediatamente seguinte à execução de um passo 8C .
Vamos mostrar a seguir ,que não somente nesta iteração imediatamente seguinte,
o teste 8A será satisfeito , como também em todas as demais iterações seguintes .
De fato , como hj* > O , j = 1 ,... ,p , existirá uma iteração K1 tal que :
hjh > hj*/2. , j = 1 , ... ,p ( 3.36)
para todo k > K1 .
Como definimos em ( 3 . 1 0 ) 2,jk = p: - qjk ,temos :
p j k - q; > hj*/2 ( 3.37 )
Como p: > O e $ > O ,então será observada a relação :
pjk > hj*/2 ( 3.38 )
De outro lado , se o passo 8C fosse executado infinitas vezes ,teríamos por
força da instrução 8C.3 que a + 7612 . Ademais , para que o passo 8C seja
executado é necessário que o teste de 8A seja falso , ou seja, pelo menos uma das
relações
dj+ > dj- ( 3.39 )
hj( xk ) < 20.7' ( 3.40 )
não seja verdadeira .
Como > O ,face a Proposição 2 ,o primeiro teste ( df > dj' ) não falhará .
Se por acaso o segundo teste [ hj ( xk) < 28..rk ] falhar , ou seja ,se tivermos
[ hj ( xk) > 2 8 . e ] ,também será verdadeira a relação :
h j ( x k ) - q > 28.8 , €;<O. ( 3.41 )

: definido em ( 3.9a) corresponde ao negativo da derivada
Relembrando que p
da função penalidade hiperbólica e considerando o fato de que a -+ xI2 ,visto logo
acima, e fazendo uso da Propriedade 1 da penalização hiperbólica , ( capítulo 2 ),
podemos concluir que se ( 3.41 ) for válida , necessariamente o valor de pjk vai
para zero . A figura 8 tem o objetivo de tornar mais clara essa conclusão .
-
Assim ,haverá um valor a tal que CLjk i hj*/2 , violando a expressão ( 3.38 ).
Dessa forma podemos concluir que o segundo teste não falhará , ou seja , após
-
a > a o algorítmo certamente executará o passo 8A.
-1 C I I I I I I I I I
4 -3 -2 -1 O 1 2 3 4
Figura 8 : Acréscimo da inclinação da função penalidade

Análise da viabilidade da alternativa 2 :
Observa-se de outro lado que pela primeira parte do teste 8B ,temos :
h j ( $ ) - cj- > - h j ( x k ) + c; ( 3.42)
Face à desigualdade ( 3.42 ) , pela proposição 2 , podemos concluir que os
multiplicadores de Lagrange equivalentes 3Ljk são negativos . Dessa forma o passo 8B
não é aceito , pois contraria a hipótese dos multiplicadres equivalentes serem
positivos .
h á l i s e da viabilidade da alternativa 1 :
Por exclusão , esta é a única alternativa viável e tem uma grande implicação
prática : a região viável na sequência de problemas relaxados mantém-se sempre com
um amplo interior, como afirmamos anteriormente.
Se em caso contrário , a alternativa 3 fosse observada , certamente teríamos um
fechamento monótono da região viável . Simultaneamente ocorreria o consequente
crescimento do mau condicionamento da função objetivo do problema relaxado . Em
síntese , tal ocorrência inviabilizaria em termos práticos a validade da presente
proposta metodológica .
Vamos agora analisar o comportamento da sequência dos multiplicadores de
Lagrange equivalentes gerados pelo algorítmo .
Considerando a função objetivo penalizada do problema ( 3.6 ) , temos num
ponto ótimo intermediário xk observada a seguinte condição :
v ~ F ( X , C X ~ ,=T O~ )
Tomando -se o limite na expressão acima, temos :

k
Considerando que lim x = x* e fazendo uso da condição ( C1 ) ,temos :
k+m
lirn [ V f ( x * ) -
k+m
c
j=l
hj*Vhj(x*) ] = O
Como os gradientes Vhj ( x* ) são L.I. ( condição ( C2 ) ,logo esse sistema tem
solução única ,donde podemos concluir que :
lim
k-tm
~ > h= h*.
Pelo acima exposto ,demonstramos o seguinte teorema :
TEOREMA DE CONVERGÊNCIA DUAL
A seqüência dos multiplicadores equivalentes :A gerada pelo algoritmo I
converge para o multiplicador ótimo do problema original Aj* .
Esse resultado tem de outro lado um outro importante significado prAtico : o
passo 5 do algorítmo é executado um número finito de vezes.
Supondo verdadeira a hipótese contrária , implicaria em a -+ n / 2
concornitantemente a ocorrência cíclica de pontos de mínimos intermediários xk , no
passo 3 do algorítmo, inviáveis , ou seja ,pontos em que hj (xk ) - ~ j -< O , para

algum índice j .
Pela dekígão ( 3 . l O ) , hjk = Cljk - qjb , e nesta hipótese pela característica da
penalização adotada, teríamos ~ 1 ; -+ O e pôr isso h>h + a> , O que é um absurdo.
RESULTADOS COMPUTACIONAIS DOS PROBLEMAS
RESTRITOS A IGUALDADES
Esta seção tem como objetivo a apresentação dos resultados computacionais
obtidos com a implementação do método de penalização hiperbólica \desenvolvido
para solucionar os problemas de programação não-linear , sujeito somente a restrições
de igualdades.
O algorítmo I utilizado para resolver esses problemas mencionados acima , foram
implementados em FORTRAN e os valores de tempo de CPU foram obtidos usando
um Intel 486 de 33MHz .
A rninirnização irrestrita foi feita utilizando-se uma rotina da Harwell Library
que basicamente irnplementa o método Quasi-Newton com atualização BFGS,
(Broyden - Fletcher - Goldfarb - Shanno ) .
Os parâmetros do algorítmo I foram escolhidos conforme abaixo explicado:
1 - ESCOLHA DO PARÂMETRo ao:
Basicamente deve ser um valor tal que a minimização irrestrita da função
objetivo penalizada tenha ponto de mínimo ,ou seja ,
infx F ( x , a 0 , ~ O) = FO > - oo
Em particular , pequenos valores de ao podem produzir divergência da
minimização irrestrita . Nesse sentido ,uma necessária salvaguarda é tomada no início
do algorítmo ,a fim de evitar essa dificuldade.
2 - ESCOLHA DAS FOLGAS E ',E - :
Em todos os casos vinculamos esses parâmetros ao parâmetro de penalidade
zO, rigorosamente ,como especificamos no algorítmo I .
3 - ESCOLHA DO PARÂMETRO TO :
Adotamos em todos esses experimentos computacionais o valor z0 = 0.01 .

Alternativamente poderíamos adotar a escolha proposta por Fiacco & McCormick [ 25 ]
P (xO , a O , ~)"l F (xO , a O , z O) = 0.1
Devemos enfatizar que para todos os 12 problemas testados , o algorítmo I
obteve a solução ótima especificada na referência do Hock & Schittkowiski [ 34 1.
Para ilustrar o mecanismo de funcionamento do algorítmo I , primeiramente são
apresentados nas Tabelas 1 , 2 e 3 os resultados computacionais, obtidos na resolução
de um problema teste muito simples.
EXEMPLO 1 :
minimizar f(x) = x12 + x~~
sujeito à : h ( x ) = 2x1 + x;! - 1 = O
e tem como solução ótima o ponto x* = ( 0.4, 0.2 ) e h* = 0.4
Adotamos os seguintes parâmetros iniciais no passo 1 do algorítmo I.
xO = ( 2 , - 1 ) , z0 = 0.1000000E-01 e ao = 0.114576E+01.
DESCRI~ÃO DAS TABELAS
As colunas da Tabela 1 representam , na ordem , o número da rninimização
irrestrita k , o valor do parâmetro ângulo da penalização hiperbólica ak ,O valor do
parâmetro distância da penalização hiperbólica zk ,as componentes do ponto solução
de cada minimização irrestrita sik ; i = 1, 2 , e fhalmente o número de Passos de

cada minimização irrestrita .
As colunas da Tabela 2 representam na ordem , o número da minimização
irrestrita k ,o valor das folgas à esquerda E[ e à direita E: ,o valor da restrição de

igualdade e os multiplicadores de Lagrange h: associados às restrições de
desigualdades .
Finalmente, na Tabela 3, temos ,o número da rninimização irrestrita k , os valores
.
da função objetivo modificada F ( ) do problema irrestrito , da função penalidade
. .
P ( ) e da função objetivo f ( ) do problema original .
Após a descrição apresentada acima ,podemos observar nas Tabelas 1 e 2 , que
os pontos xk encontrados na minimização irrestrita até a iteração k = 7 , são

inviáveis em relação ao problema relaxado ( 3.5 ) ,porque os valores de h ( xk ) estão
situados fora do intervalo definido pelas folgas da relaxação .

Em função dessa inviabilidade , o algorítmo executa o passo 5 , em que é
efetuado o aumento do parâmetro ângulo a , deixando o parâmetro distância z
constante ,conforme pode ser visto na segunda e terceira colunas da Tabela 1 .
A partir da iteração k = 8 , as rninimizações irrestritas produzem pontos xk
viáveis para o problema relaxado ( 3.5 ) , pois os valores de h ( xk ) estão dentro do
intervalo definido pelas folgas ( Veja Tabela 2 ) .
Com relação aos parâmetros da função penalidade, podemos ver que o ângulo
a permanece constante , e a distância z decresce até encontrar o ponto ótimo x* ,
no limite ,( veja Tabela 1 ) .
Na Tabela 3 ,podemos observar a convergência dos valores da função objetivo
modificada ao valor da função objetivo do problema original do problema original .
Podemos , sobretudo , observar nas tabelas 1e 2 , as convergências das
seqüências ( xk ) e ( hk ) aos valores otimais especificados acima na descrição do
exemplo 1 .
TABELA 1 : Resultados Computacionais do Problema Teste 1 . Parte 1 / 3
Iteração ak T~ xlk ~2~ PASSOS

k
Iteração €i h (xk hk
k
Iteração k F ( xk ,ak ,Z~ ) P ( xk ,$ ,Z~ ) f(xk )

Para uma melhor avaliação do desenvolvimento do algorítmo I ,selecionamos
alguns problemas testes do livro Hock e Schittkowski [ 34 ] seguindo a indicação
recomendada pelo " Ad Hoc Cornmittee to Revise Guidelines for Reporting
Computational Experiments in Mathematical Programming " da Mathematical
Programming Society ,vide Jackson et all. [ 36 ] .
Os pontos iniciais xO e , os valores ótimos x* e h* , para todos os

problemas selecionados são os mesmos apresentados no livro [ 34 ] .
Destaque-se que o algoritmo resolveu eficiente e eficazmente todos os
problemas abaixo relacionados .
Problema 7
minimjzar f ( x ) = h( 1 + x12) - x2
sujeito à : h ( x ) = (1 + x12 )2 + ~2~ - 4 = O
Ponto inicial : x 0 = ( 2 , 2 )
Solução ótima encontrada na 5Vteração em 0.99 segundos de CPU .
X* = ( 0 , 1.7320 ) e h* = 0.2887
Problema 27
minimizar f(x) = O.Ol(x1 - + (x2 - ~ 1 ~ ) ~
sujeito à : h ( x ) = xl + x32 + 1 = 0
Ponto inicial xO = ( 2 , 2 , 2 )
Solução ótima encontrada na 7" itração em 1.32 segundos de CPU.
X* = ( - 1 , 1 , 0 ) e h* = 0.4
Problema 39
minimizar f(x) = - xl
sujeito à : hl ( x ) = x2 - xI3 - x~~= O
h2(x) = x12 - x2 - a2= O

Ponto inicial xO = ( 2 , 2 , 2 , 2
Solução ótima encontrada na 7" iteração em 1.48 segundos de CPU
x* = (1,1,0,0 ) , hl* = 1 e h2* = 1
Problema 42
minimizar f(x) = (xl - + (x2 - 2 ) 2 + (x3 - 3 ) ' + (x4 - 4 ) 2
sujeito à : h ~x( ) = xl - 2 = O
h2(x) = ~3~ t a2- 2 = O
Ponto inicial xO = ( l 9 1 , 1 , l
Solução ótirna encontrada na 8" iteração em 1.64 segundos de CPU .
x* = ( 2 , 2 , 0 . 6 & ,0.8& ) , Ai* = 2.5355 e h2* = 2
Problema 61
minimizar f ( x ) = 4x12 + 2x2 + ZX; - 33x1 + 16x2 - 24x3

sujeito à : hl ( x ) = 3 xl - 2 x~~- 7 = O
h2(x) = 4x1 - x32 - 11 = O
Ponto inicial xO = ( o,O,O 1

Solução ótirna encontrada na 5" iteração em 1.1 segundos de CPU .
X* = ( 5.32677015, - 2.11899863 , 3.21046423 ) ,

AI * = 1.7378 e Az* = 0.8877
Problema 77
ininimiz~ ( x l - 1 ) 2 + ( ~ 1 - X 2 ) 2 + ( ~ 3+- (~~) 2q - 1 +

) ~( ~ ~ - 1 )
sujeito à : x ? . ~+ sen( a - x5 ) - 2& = O
X:, f ~ 3 ~ -~ 8x - 4 112
~ = O
Ponto inicial xO = ( 2 , 2 , 2 , 2 , 2 )

X* = ( 1.166172,1.182111,1.380257,1.506036,0.610920 )
hl * = 0.08554 e h2* = 0.03188
Problema 78
minimizar f(x) = xi.x2.x3.x4.~5
sujeitoà: hl(x) = x r 2 + x Z 2+x: + a 2 + ~ 5- 210 = O
h2(x) = x2.x3 - 5 %.x5 = 0
h3 ( x ) = x13 + x23 + 1 = 0
Ponto inicial x0 = ( - 2 , 1 . 5 , 2 , - 1 , - 1 )
Solução ótima encontrada na 6" iteração em 1.54 segundos de CPU .

X*= ( - 1.717142,1.595708 , 1.827248 ,- 0.763642, - 0.763643 ) e
h1 * = 0.7035 , h2* = 0.7444 e h3* = 0.09681
Problema do Bazaraa [ 6 ]
minimizar f(x) = (Xl - 2 ) 4 + (X1 - 2 ~ 2 ) ~
sujeito à : h (x ) = xl 2 - x2 = O
Ponto inicial xO = ( 2 , 1 )
X* = ( 0.94558 , 0.89344 ) e hl * = 3.3706

PROBLEMAS DEGENERADOS
A teoria anteriormente desenvolvida considerava a hipótese de não-
degenerescência dos multiplicadores de Lagrange ,ou seja, hj # O ;j = 1 ,... ,p .

A despeito da exigência teórica dessa condição , submetemos o Algorítmo I a
problemas que não a atendem, ou seja , problemas na literatura denominados duais
degenerados .
A seguir estão descritos alguns problemas degenerados do livro [ 34 ] resolvidos
pelo método de penalização hiperbólica:
Problema Degenerado 50 :
minimizar ( X ~ - X ~ ) ~ + ( X ~ - X ~ ) ~ + ( X ~ - X ~ ) ~ + ( X ~ - X ~
sujeito a : x ~+ 2x2 + 3x3 - 6 = O
x2 + 2x3 + 3x4 - 6 = O
~3 + 2% -i- 3x5 - 6 = O
Ponto inicial xO= ( 3 5 , - 3 1 , 11 , 5 , - 5 )
X* = (l,l,l,l,l) , h * = 0 ,h2*=0 e h3*=0
minimizar ( Xl + x2 )2 + ( x2 + x3 )2
sujeitoa: xl + 2x2 + 3x3 - 1 = O
Ponto inicial xO = ( - 4 , 1 , 1 )
Solução ótima encontrada na 3"teração em 0.65 segundos de CPU .
x* = ( - 0.5 , - 0.5 , 0.5 ) e hl * = O

minimizar ( x l - X 2 ) 2 + ( ~ 3 - - 1)4+(~5-1)6
sujeito a : xi2 + sen( ~q - xs ) - 1 = O
xz + -2 = o
Panto inicial xQ = ( 0.7 ,L75 , O 5 .2,2 )
Sol~qãoótima encontrada na 10" iterag5i-a em t.1 segundos de CPV .
x* = ( 1,1,1,1,1 ) , Ai* = O e A2*=O
Por concisão apresentaremos a seguir, unicamente os resultados computacionais
obtidos para o problema degenerado 4 6 ,
Destacamos ,entretanto ,que esses resultados são similares aos outros casos .
TABELA 4 : Resultados Computacionais do Problema Teste 46. Parte 1 / 4

TABELA 5 : Resultados Computacionais do Problema Teste 46. Parte 2 I 4
TABELA 6 : Resultados Computacionais do Problema Teste . Parte 3 I 4
Iteração k hik ~2~

Iteração F ( xk ,ak ,T~ ) P ( xk ,ak ,T~ ) f(xk ) Passos

k
Devemos enfatizar que para todos os 12 problemas testados , o algorítmo I ,
obteve a solução ótima da referência do Hock e Sdhittkowiski [ 34 1.
Este feito nos permite acreditar que o algorítmo I possa ter similar sucesso
face a outros problemas práticos e da literatura .

RESOLUÇÃO DO PROBLEMA GERAL DE
PROGRAMAÇÃO NÃO - LINEAR VIA PENALIZAÇÃO

HIPERB~LICA
De posse dos resultados obtidos na resolução dos problemas de programação
não-linear com restrições de igualdades , via penalização hiperbólica , apresentaremos
neste capítulo um algorítmo para resolução de problemas de programação não-linear
com restrições de igualdades e desigualdades .
Para resolvermos o problema geral de programação não-linear da forma :
transforma-se cada restrição de igualdade em duas restrições de desigualdades
produzindo um problema rigorosamente equivalente ao problema ( 4.1 ) , isto é ,

minirnizar f ( x )
-
sujeitoà:gi(x)> O , i = 1 , ..., m
-
hj(x) 2 O , j = 1,...,p
-
hj(x) r O , j = 1 , ...,p
Seguindo o mesmo argumento do método de penalização hiperbólica, descrito
no capítulo 2 , relaxa-se as restrições de desigualdades provenientes de cada restrição
de igualdade , colocando-se as folgas superiores zj+ e inferiores E; obtendo-se o
problema :
minimizar
sujeito a :
+
com c j ' I O e cj 2 0 , j = l ,..., p ,
Pelo fato do problema ( 4.3 ) se encontrar na f o m com somente restrições de
desigualdades , aplica-se então o método de penalização hiperbólica , resolvendo-se

uma sequência de problemas irrestritos da forma :
-
com m = m + 2p e onde a h ç ã o I ( . ) é definida como:
A função de penalidade P ( . ) , define-se como anteriormente em ( 3.7 ) por :
Inspirado no algorítmo O de Xavier [ 62 ] e no algorítmo I apresentado neste
trabalho ,no capítulo anterior ,desenvolvidos para resolver ,respectivamente , problemas
de programação não-linear com restrições de desigualdades e problemas de
programação não-linear com restrições de igualdades , apresentaremos a seguir o
algorítmo XI com o objetivo de resolver problemas de programação não-linear com
restrições simultaneamente de igualdades e desigualdades .

PENALIZAÇÃO HIPERBÓLICA PARA RESTRIÇ~ES DE
IGUALDADES E DESIGUALDADES
Faça k = O , aj1 = ao , j = 1 ,... ,p , sendo O < ao < n/2 , =TO
e .cO>O
Tome ponto inicial xO
= - 100 , j = 1, ... ,p
Calcule :
.E; = + 10021 , j = 1, ... ,p
2 - "CONTAGEM DA ITERAÇÃO"
Faça k : = k + l
3- a ~ ~ DO ~SUBPROBLEMA"
~ ~ ~ ç Ã ~
Resolver o problema de rninimização irrestrita
conforme definido em ( 4.4 ) a partir de um ponto inicial xk-I, achando
um ponto ótimo intermediário xk .

4 - "TESTE DE VIABILIDADE"
Teste se o ponto xk obtido é viável para a problema relaxado ( 4.3 )
Se for viável, vá para o passo 6 .
qk:=p q k + ( I - p ) . n / 2 , j = l ,..., p e O < p < 1
,Vá para o passo 3
7 - "CÁLCULO DAS DISTÂNCIAS SIGNIFICATIVAS "
CalcuIe as distâncias ?
esquerda
i e à direita do valor hj (xk) às folgas :
8 - "TESTE DE T I T - I O L APARA
C ~ ~ CADA R DE IGUALDADE "
E S ~ Ã O
Para cada restrição j = 1 ,. ,p faça :

8A - : ("Se o ponto xk for tal que a distância a direita for significativamente
maior do que a distância à esquerda,processa a diminuição da folga inferior" )
Então faça :
&jk+l + = &jk +
8B - :("Se oponto xk for tal que a distância SL esquerda for significativamente
maior do que a distância à direita ,processa a diminuição da folga superior " )
Então faça :
I Ejk+l + = +E
EIk+l - = Ejk -
: 1 10 ,
7
(8B.1 )
( 8B.2 )
8C -:"Diminuição de ambas as folgas se não houver proximidade significativa"
Em caso contrário,
k+l- = -
&j 100 ' c ~ ( 8C.l)
Faça : E?+ -
- + 100 zk ( 8C.2 )
ajk+l = p.c$ + ( 1 - p ).n/2 ( 8C.3 )
j = l , , p e O< p < l
Vá para o passo 2.
Neste ponto , devemos ressaltar que o algorítmo II é uma modificação do
algorítmo I para incorporar as restrições de desigualdades.
Chamamos a atenção , que as únicas diferenças são : a defkição da função
objetivo moditlcada ,no passo 3 , e o teste de viabillidade incluindo as restrições de
desigualdades ,no passo 4 .
Os parâmetros ao , E + , E ' e TO do algorítmo I1 foram os mesmos
escolhidos para o algorítmo I ,codorme foi apresentado no capítulo 3 .
Como já referido anteriormente , em se tratando do parâmetro ao ,pequenos
valores podem produzir divergência da minirnização irrestrita . No problema-teste HS
- 112 este efeito é particularmente suscetível, pois também envolve o parâmetro 7".
Normalmente os resultados computacionais são um tanto insensíveis a escolha
inicial de .c0. Entretanto ,existem casos em que tal escolha se torna de fundamental
importância pois , conforme especificação do algorítmo II , existe uma vinculação entre
as folgas e o parâmetro TO.
Esse particular exemplo , HS -112 , possui uma função objetivo com uma
coercividade intrínsica muito forte .
Assim , grandes folgas aumentam a região viável permitindo valores muito
pequenos das componentes do vetor " x " , gerando valores extremamentes negativos
do valor da função objetivo do problema HS - 112 ,e entrando numa região em que

a superioridade da coercividade da função objetivo em relagão a penalização se
estabelece de forma irreversível . Para o problema HS - 112 foram adotados os
seguinte valores ao = 0.900 JZ+ 2 e 7" = 0.0001

RESULTADOS COMPUTACIONAIS DOS PROBLEMAS
RESTRITOS A IGUALDADES E DESIGUALDADES
Esta seção tem como objetivo a apresentação dos resultados computacionais
obtidos com a implementação do método de penalização hiperbólica desenvolvido
para solucionar os problemas de programação geral não-linear , sujeito a restrições
de igualdades e desigualdades ,usando o algorítmo 11,acima descrito .
A fim de ilustrar em maiores detalhes o ltùncionamento do algorítmo I1 , são
apresentados nas Tabelas 8 , 9 , 10 e 11 os resultados computacionais produzidos na
resolução somente do problema teste :
EXEMPLO 2 :
minimizar f ( x ) = xl 2 + ~ +2x2
2 ~
2
sujeito a : h (x) = x12 + x2 - 1 = 0
cuja solução ótima é o ponto x* = ( 1 , O ) com Ai* = 2 e h2* = 1
Para este particular problema , adotamos os seguintes parâmetros iniciais no
passo 1 do algorítmo 11:
A descrição das Tabelas 8 , 9 , 10 e 11 é semelhante às apresentadas
anteriormente .
k k
Iteração ak T~ x1 x2 PASSOS
Iteração ;C h (xk) ~k
k
Iteração Lk kzk
k
TABELA 11 : Resultados Computacionais do Problema Teste 2. Parte 4 1 4
Iteração k F ( xk ,ctk ,T~ ) P ( xk ,ak ,T~ )

Para urna melhor avaliação da eficácia do algorítmo I1 , seguindo a recomendação
dada em " Ad Hoc Committee to Revise Guidelines for Reporting Computational
Experiments in Mathematical Programming " da Mathematical Programming Society ,
vide Jackson et all. [ 3 6 ] , selecionamos um conjunto de problemas-teste do livro Hock
e Schittkowski [ 34 1.
Unicamente devido a questões de concisão, nos atemos aos 15 problemas abaixo
descritos ,observando que nos demais o desempenho do algorítmo LI foi análogo .
Problema 32
lxhknizar (xl 3x2 + x3 )2 + 4 ( XI - ~ 2 ) ~
sujeito à : xi 2 O , i = 1,2,3
3
6x2 + 4x3 - XI - 3 2 O
1-xi-xz-x3=0
Ponto inicial xO = ( 0.1 , 0.7 ,0.2 )

Solução ótima encontrada na 9" iteração em 1.92 segundos de CPU
X* = ( 0,0,1) , hi* = 4.0032 , h2* = 1.9988 e f ( x * ) = 1
Problema 41
minimizar 2 - x1 x2 x3
sujeito a : xl + 2 x2 + 2 x3 - = O
0 I x i I 1 , i=1,2,3
OIx,12
Ponto inicial xO = ( 2 , 2 , 2 , 2 )
Solução ótima encontrada na 6" iteração em 1.60 segundos de CPU.
X* = ( 213 , 113, 113, 2 ) , h* = 0.111 e f(x* ) = 1.9259259

Problema 53
miaifnizar (xl-x2)2+(X2+X3-2)2+ (Xq-1)2+(X5-1)2
sujeito a : xl + 3 x2 =O
x3 + Xq - 2x5 = o
x;? - x5 = o
- 1 0 I x 5~10 , i = 1 , ..., 5
Ponto inicial xO= ( 2 , 2 , 2 , 2 , 2 )
Solução ótima encontrada na 9Vteração em 2.95 segundos de CPU.

X* = 1/43( - 3 3 , 1 1 , 2 7 , - 5 , 1 1 ) , f(x*) ~4.093023
AI* = 5.9535 , h2* = 2.0465 e h3* = 2.05
Problema 55
minimizar xl + 2x2 + 4x5 + exp( x l . & )

sujeito à : xl + 2 x2 + 5 ~g - 6 = O
xl+Xz+x3-3=0
&+Xs+Xg-2=O
x1+Xq-1=0
X2fXg-2=0
x3+Xg-2=0
xi>O , i = l , ..., 6
Xl I I , a s 1
Ponto inicial xO = ( 1 , 2 ,O , O , O , 2 )
x* = ( 1 ,413 , 113 , 0 , 113 ,513 ) , A*mx = 0.6666 e h*,, = 0.3332
f (x* ) = 6.3333
Problema 60
minimizar ( xl - 1 )2 + ( x1 - x2 )2 + ( x2 - x3 )4
sujeito à : x l ( l + x?) + x: - 4 - 3& = 0
-1OIx; I 1 0 , i = 1 , ..., 10
Ponto inicial xo = ( 2,2,2 )
Solução ótima encontrada na 7" iteração em 1.71 segundos de CPU,
X* = ( 1.104859, 1.196674, 1.535262 ) e f ( x* ) = 0.032568
Problema 63
minimizar 1000 - x12 - 2x22 - x32 - - x1.q

~ 1 . ~ 2
sujeito à : xi 2 O 9 i = 1,2,3
8x1 + 14x2 + 7x3 - 56 = O
x12 + xz2 + ~3~ - 25 = O
Ponto inicial xO = ( 2 ,2 ,2 ) . Solução ótima encontrada na 5Vteração em
1.26 segundos de CPU. X+ = ( 3.512118 , 0.216988 , 3.552174 )

Li* = 0.2749 , h2* = 1.2234 e f ( x* ) = 961.7154
Problema 71
minimizar ( x1 + x2
~1x4 + x3 ) + x3
sujeito à : x1 xz x3 - 25 2 O
xi2 + x; + x32 + w2 = o
l 5 x i r 5 , i = 1 , ..., 4
Ponto inicial x" = ( 1 ,5 , 5 , 1 ) . Solução ótima encontrada na 5" iteração
em 1.49 segundos de CPU. x* = ( 1 ,4.742999 ,3.82ll5O , 1.379408 )
hl* = 1.0879 , h2* = 0.1615 e f (x* ) = 17.0140

Problema 1 do Bazaraa [ 6 ]
minimizar (Xl - 2 )2 + % x22
sujeito a : - xl + x2 + 1 2 O
2xi + 3x2 - 4 = o
Ponto inicial x" = ( 2 , 0 ) . Solução ótima encontrada na 7Vteração em 1.32
segundos de CPU . x* = ( 1.7187 , 0.1875 ) com Ai* = 0.0 e A2* = 0.2
Problema 2 do Bazaraa [ 6 ]
minimizar x? + 4 ~2~
sujeito à : xi 2 O 9 i = 1,2,3,4
X l + 2x2 - x3 - 1 =o
-x1+x2+Xq=O
Ponto inicial x" = ( 2 A 3 J )
Solução ótima encontrada na 8"teração em 1.92 segundos de CPU
x* = ( 0.5 , 0.25 , 0 , 0.25 ) com 3L1* = 1 e h2* = 1
Problema 73
minimizar 24.55 XI + 26.75 x2 + 39 x3 + 40.50 ~4
sujeitoa: 2 . 3 ~ ~ + 5 . 6 ~ 2 + I l . l x ~ + 1 . 3 q - 5 ~ 0
+ ~4 1 . 8 ~+~52.1 ~4
12xl + 1 1 . 9 ~ - 21 -
2 312
1.645 ( 0.28 x12 + O. 19 ~2~ + 20.5 ~3~ i- 0.62 q ) 2 O
xl+X:!+x3+Xq-1=0
Xi 2 O , i = 1 , ..., 4
Ponto inicial xO = ( 1 , 1 , 1 , 1 )
Solução encontrada na 9Vteração em 2.20 segundos de CPU.

X+ = ( 0.6355214, 0.3064E-10, 0.3127019, 0.05177656 ) ,f ( x* ) = 29.8943
?LI*= 0.2433 , h2* = 0.411 , h3* = 0.580 e h4* = 18.37
Problema 81
minimizar e x p ( x l x z x 3 ~ ~0.5(x13
)- +x23 + 1)2
sujeito à : - 2.3 I xi I 2.3 ; i = 1,2
-3.2 5 xj 5 3 . 2 ; j = 3,4,5
x: + ~2~ + x~~+ x~~+ x~~- 10 = O
x2 X3 - 5x4 xg = o
3
xl + x23 + 1 = 0
Ponto inicial xO = ( - 2 ,2 , 2 ,- 1 , - 1 )
Solução ótima encontrada na 3-m 1.21 segundos de CPU

X* = ( - 1.717142,1.159541, 1.827248, - 0.763647, - 0.763639)
hi* = 0.0373 , h2* = 0.0396 , h3* = 0.0495 e f (x* ) = 0.05394
Problema 111
sujeito à : exp(x1) + 2 exp(x2) +2exp(x3) + exp(a) + exp(xlo) - 2 = O
exp(x4 ) + 2 exp(x5 ) + exp(& ) + exp(x7) - 1 = O
exp(x3) + exp(x-/) + exp(xs) + 2 exp(x9) + exp(x10) - 1 = O
- 100 Ixi I 100 ,i = 1 , .,. , 10

Valores de cj ,j = 1 ,...,I0
Ci = -6.089 , c2 = -17.164 , C,= -34,054 , C, = -5.914 , cs = -24.721
c6 = - 14.986 , C7 = - 24.100 , C8 = - 10.708 , Cg = -26.662 , c10 = - 22.179
Ponto inicial xO= ( - 2.3 , ... , - 2.3 )
Solução ótirna encontrada na 7" iteração em 5.21 segundos de CPU.
X* = ( - 3.2030 , - 1.9123 , - 0.2444 , - 23.73 , - 0.7216 , - 7.2645 , - 3.5959 ,
- 4.0190, - 3.2895 , - 2.3337 )

h*mx = 15.57 , h*,, = 10.59 e f ( x* ) = - 47.75967
Problema 112
sujeito a : xl + 2 x2 + 2 x3 + + XIO - 2 = O
x,+2x'j+Xg+x7- 1 = o
x3 + x7 + Xg + 2x9 + x10 - 1 = o
xi21.E-6 , i = l ,..., 1O
Valores de cj ,j = 1 ,... , 10
Ci = - 6.089 , cz = - 17.164 , c3 = - 34.054 , c4 = - 5.914 , c5 = - 24.721

c6 = - 14.986 , C7 = - 24.100 , C* = - 10.708 , Cg = - 26.662 , Cio = - 22.179
Ponto inicial xO = ( 0.1 , ... , 0.1 )

X+ = ( 0.046680 , 0.147730 , 0.783153 , 0.001414 , 0.485246, 0.000693 ,
0.027399, 0.017947, 0.037314, 0.096871 )
h*,, = 15.20 , h*,, = 9.774 e f (x* ) = - 47.76109

Problema 114
minimizar 5.04 xl + 0.035 x2 + 10 x3 + 3.36 x5 - 0.063 a x7
sujeito a : gl(x) = 35.82 - 0.222~10- bx9 2 O
g z ( x ) = - 1 3 3 + 3 x 7 - axlo 2 0
g3 ( x ) = - g~( x ) + ( l / b - b)x9 2 0
g4(x) = -g2(x) f ( l / a - a)xlo 2 0
g5 ( x ) = 1.12 xl + 0.13167 xl xs - 0.00667 xl xs2 - a & 2 0
g6 ( X ) = 57.425 + 1.098 xs - 0.038 xs2 + 0.325 & - a x7 2 0
g7(x) = -g5(x) + ( l / a - a ) a 2 O
g s ( x ) = - g 6 ( ~ )i- ( l / a - a)x7 2 0 a = 0.99
h1 ( x ) = 1 . 2 2 ~ 4- xl - x5 = O b = 0.9
hs(x) = 9 8 0 0 0 ~ ~ / +( ~1 40 0
~ 0~ ~ -~ ~6) = O
~ ~ ( x ) = ( x ~ + x s -) %
/ x= ~O
0.00001 5 XI 5 2000 , 85 5 5 93
0.00001 I ~2 I 16000 9 90 I x7 5 95
0.00001 r x3 r 1200 , 3 I xs 5 12
0.00001 5 a 5 5000 9 1.2 5 x 9 5 4
0.00001 5 ~5 5 2000 , 145 5 X ~ OI 162

Ponto inicial xO= ( 1745 , 12000 , 110 ,3048 , 1974 ,89.2 ,92.8 , 8 ,3.6 , 145 )

x* = ( 1698.091, 15816.30, 54.0974, 3031.223, 2000, 90.1157, 95,
10.492, 1.5616, 153.535 ) , f(x* ) = - 1768.74 ,

h*, = 311.77 e h*-=0.6815
Problema 119
16
sujeito à : 2
j=l
b, Xj - Ci = 0
Valores de ai, , bij e Ci nas tabelas em anexo
Ponto inicial x = ( 1O , ... , 10 )

x* = ( 0.039847, 0.791983 , 0.202870, 0.844357, 1.269906, 0.934739, 1.681962,
0.155294, 1.567870 , O , O , O , 0.660203 , O , 0.674255 , O )
h*mx = 30.03 , h*,, = 0.383 e f ( x* ) = 0.24489969'7

Tabela 12 : Valores de aij para o problema 119.
Tabela 13 : Valores de bij e cj para o problema 119:
Neste trabalho , conforme proposta apresentada na introdução , consideramos
primeiramente o problema de programação não- linear sujeito a restrições de igualdades.
Foi apresentado um novo método para resolução desse problema, que se fundamentou
na utilização da penalização hiperbólica. Esse método se constitui na relaxação das
restrições de igualdades , através de folgas superiores e inferiores , criando uma região
viável com interior não-vazio . Seguindo essas idéias , foi apresentado o algorítmo I para
resolução do problema acima citado , e foi desenvolvida a correspondente teoria de
convergência.
Na avaliação dessa metodologia , resolvemos vários problemas testes relacionados
no livro de Hock e Shittkowiski [ 34 1. Os resultados obtidos se comportaram conforme
a teoria desenvolvida .
Ressaltamos que até mesmo os experimentos realizados com problemas testes
degenerados ( que ferem às condições pré-estabelecidos para desenvolvimento da teoria
de convergência ) foram coroadas de pleno sucesso no que se refere ao critério de
robustez e , até mesmo , de eficiência . Todavia ,para problemas maiores avaliamos que o
comportamento oscilatório dos valores das folgas superiores e inferiores podem diminuir
a eficiência do método.
Através da consolidação dos resultados previamente estabelecidos , estendemos
nossos estudos a resolução do problema geral de programação não-linear sujeito a
restrições de igualdades e desigualdades. Apresentamos o algorítmo I1 e o submetemos

a um conjunto de problemas testes , também relacionados em Hock e Schittkowiski
[ 34 ] ,onde obtivemos igual sucesso na resolução desses problemas.
Fundamentado no sucesso demonstrado nesse conjunto de problemas resolvidos ,
acreditamos que a presente metodologia se constitui em uma alternativa válida para
resolução de problemas práticos.
Com relação ao problema geral de programação não-linear faz-se , todavia ,
necessário um desenvolvimento teórico analisando suas propriedades de convergência.
Tais estudos podem ter como ponto de partida as idéias relacionadas nos trabalhos
previamente desenvolvidos sobre resolução do problema restrito a desigualdades ,
descrito por Xavier [ 62 ] em combinação com a teoria apresentada para resolução do
problema restrito a igualdades ,descrito neste trabalho.
Devemos agora destacar algumas características da metodologia adotada que
julgamos ser de particular importância.
DIFERENCIABILIDADE
Uma primeira característica é que a função de penalidade hiperbólica P ( y , h ,.r: )
é continuamente diferenciável , qualquer que seja a ordem da derivada considerada, e
segundo quaisquer das variáveis y , h ou z , isto é , P E C" . Assim , a

diferenciabilidade intrínsica oferecida pela h ç à o penalidade permite o perfeito
funcionamento dos métodos que fazem o uso de informações das derivadas de primeira
ordem, gradientes ,e de segunda ordem, matriz hessiana .

PONTO INICIAL
Uma outra característica se relaciona com o ponto inicial , pois não existe a
necessidade de um ponto especial satisfazendo quer as restrições de igualdades quer as
restrições de desigualdades ,para o início do processamento dos algorítmos .
A despeito desses pontos positivos , ressaltados , temos clareza que essa

metodologia não se constitui em um recurso necessariamente ótimo e fechado para
resolver qualquer tipo de problema, e em particular , para tratar de uma forma única
qualquer tipo de restrição de igualdade ou de desigualdade.
É possível fazer uma combinação da penalização hiperbólica com o método do
gradiente reduzido generalizado . Tal combinação poderia ser feita da seguinte maneira :
somente as restrições não-lineares seriam tratadas pela penalização hiperbólica , enquanto
que as restrições lineares seriam tratadas dentro do enfoque GRG. Produziríamos assim,
um problema penalizado unicamente com restrições lineares . Para esse problema ,
usaríamos o método GRG , que conforme sobejamente registrado na literatura possui
um excelente desempenho.
Alternativamente ao método GRG ,poderíamos de uma forma similar considerar a
combinação com outros métodos primais como : gradiente projetado , gradiente reduzido
e ,até mesmo ,direções viáveis.

Da mesma forma podemos conjecturar a possibilidade de combinarmos com o
método de programação quadrática sequencial , vide Martinez [ 43 ] , usando-se a
penalização hiperbólica como função mérito .
LAGRANGEANO HIPERB~LICO
Outra extensão natural da metodologia é fazer uso das informações dos
multiplicadores de Lagrange dadas pela penalização hiperbólica de modo a criar um
algorítmo tipo Lagrangeano Aumentado , conforme detalhado em Xavier [ 63 ] como
também em Xavier e Maculan [ 65 ] .
EXPERIMENTAÇÃO COMPUTACIONAL
A despeito dos resultados computacionais realizados propomos um
aprofundamento da experimentação computacional tratando da eficiência , medida em
tempo de CPU , do número de iterações ou da comparação com outros algorítmos
alternativos, seguindo rigorosamente os cânones especificados em JACKSON et al. [ 3 6 1.
EXTRAPOLAÇÃO
Finalmente , propomos um desenvolvimento da teoria e implementação de
mecanismos de extrapolação , que os resultados computacionais obtidos insinuam
claramente seguindo as mesmas linhas descritas em Xavier e Maculan [ 66 ] .
Essas serão algumas das linhas de estudos que deverão desenvolver este trabalho.
BIBLIOGRAFIA
[ 1 ] ABADIE, J. & CARPENTIER, J. - Generalization of the Wove Reduced Gradient
Method to the case of Nonlinear Constraints, In: Optimization, ed. R. Fletcher,
Academica Press, London, pp. 37-47,1969.
[ 2 ] ABADIE, J. & GULGOU, J. - Numerical Experiments with the GRG Method, In:
Integer and Nonlinear Programming, ed. J. Abadie, North-Holland, Amsterdan, pp.
520-536, 1970.
[ 3 ] ARROW, K. J. ; GOULD,F..J. & HOWE, S. M. - A General Saddle Point Result for
Constraints Optimization . Mathematical Programming ,Vo1.5 ,pp. 225-234, 1973.
[ 4 ] AVRIEL, M. - Nonlinear Programming Analysis and Methods. Prentice - Hall ,

Englewood ClBs . 1976.
[ 5 ] BARD, Y. & GREENSTADT, J. L. - A ModiJied Newton Method for Optimization with
Equalify Constraints , ed. R. Fletcher ,Academic Press ,London ,New York , pp.
299 - 306 ,1969.
[ 6 ] BAZARAA, M. S. ; SHERALI, H. D. & SHETTY, C. M. - Nonlinear Programming ,
Theory and Algorithms. John Wiley and Sons, New York, Second, 1973.
[ 7 ] BEALE, E. M. L. - Numerical Methods in Nonlinear Programming Problems with

Simple Constraints. SIAM Joumal on Control and Optitnization ,20 ,pp. 141-148,
1967.
[ 8 ] BEALE, E. M. L. - Numerical Methods in Nonlinear Programming. J. Abadie ed.

North - Holland ,Amsterdan ,1967.
[ 9 ] BERTSEKAS, D. P. - Combined Prima1 Dual and Penalty Methods for Constrained
Minimization. SIAM J. Control ,pp. 521 - 544 , 1975a.

[10] BERTSEKAS, D. P. - On Penalty and Multiplier Methods for Constrained
Minimization. SIAM J. Control and Optimization, vol. 14, pp. 216 - 235 , 1975a.
[ 11 ] BERTSEKAS, D. P. - Multiplier Methods :A Survey . Automatica, pp. 133 - 143 ,

1975b.
[ 12 ] BERTSEKAS, D. P. - Constrained Optimization and Lagrange Multiplier Methods.

Academic Press , San Diego , 1982.
[ 13 ] BIGGS , M. C. - Constrained Minimization Using Recursive Equality Quadratic

Programming in Numerical Methods for Nonlinear Optimization. F. A. Lootsma
ed. ,Academic Press, London ,New York ,pp. 41 1 - 428 , 1972.
[ 14 ] BOX ,M. J. ; DAVIES ,D. & SWANN ,W. H. - Nonlinear Optimization Technique.
ICI. Monograph , Oliver and Boyd ,Edinburgh , 1969.
[ 15 ] CAMP , G. D. - Inequality Constrained Stationary Value Problems. Operations

Research , 3 ,pp. 548 - 550 , 1955.
[ 16 1 CARROL , C. W. - An Operations Research Approach to the Economic Optimization
of a Kraft Pulping Process , Ph.D. Thesis , Institute of Paper Chemistry, Appleton,
Winsconsin , 1959.
[ 17 ] CARROL , C. W. - m e Created Response Surface Techniquefor Optimizing Nonlinear
Systems . Operations Research ,vol. 9 ,pp. 169 - 184 , 1961.
[ 18 ] CASTILHO CÁRDENAS ,R . A . - Métodos de Lagrangeano Aumentado Usando
Funções de Penalidades Generalizadas para Problemas de Programagão
Não-Linear . Tese de D . Sc . , COPPE / UFRJ ,Rio de Janeiro ,Brasil, 1998 .
[ 19 ] COLVILLE, A. R. - A Comparative Study on Problems Programming Codes, In :
Proceedings of the Princeton Symposium on Mathematical Programming. ed. H.
W . Kuhn ,Princeton University Press , 1970.

[ 20 ] COURANT , R. - Variational Methods for the Solution of Problems of Equilibrium
and Vibrations . Bull. Ann. Math. Society, 49 ,pp. 1 - 23 , 1943.
[ 21 ] EL - ALEM , M. M. - A Global Convergence Theory for a Class of Trust Region

Algorithms for Constrained Optimization . Ph.D. Thesis , Rice University ,
Houston Texas , 1988.
[ 22 1 EVANS , J. P. ; GOULD , F. J. & TOLLE , J. W. - Exact Penalty Functions in
Nonlinear Programming . Math. Progr. , 4 ,pp. 72 - 97 ,1973.
[ 23 ] FIACCO , A. V. & McCORMICK , G. P. - The Sequential Unconstrained

Minimization Technique for Nonlinear Programming : A Prima1 Method .
Management Science ,Vol. 10 ,pp. 360 - 364 , 1964.
[ 24 ] FIACCO , A. V. & McCORMICK , G. P. - Extensions of SUMT for Nonlinear
Programming :Equality Constraints and Extrapolation. Management Science . Vol
12, pp. 816 - 828,1966.
[ 25 ] FIACCO , A. V. & McCORMICK , G. P. - Nonlinear Programming Sequential

Unconstrained Minimization Technique . Jonh Wiley ,New York , 1968 .
[ 26 ] FLETCHER ,R. - An Ideal Penalty Function for Constrained Optimization . Journal of
the Institute of Mathematics and its Applications . V015 ,pp. 3 19 - 342 , 1975.
[ 27 ] FLETCHER ,R. - Practical methods of Optimization , Constrained Optimization . Vol
2 , John Wiley & Sons ,New York and Toronto , 1981.
[ 28 ] FLETCHER , R. - Penalty Functions , In Mathematical Programming - The State of

Art . ( A. Bachen , M. Grotschel e B. Komte , editores ) , Springer - Verlag ,
Berlin ,pp. 87 - 144 , 1983.
[ 29 ] FRISCH , K. R. - licze Logarithmic Potential Method of Convex Programming.
University Institute of Economics Oslo ,Memorandum ,may 13 ,1955.
[ 30 ] GILL , P. E. ; MüRRAY , W. & WRIGHT , M. H. - Practical Optimization .

Academic Press ,London and New York , 1981.
[ 31 ] HAARHOFF , P. C. & BUYS , J. D. - A New Method for the Optimization of a

Nonlinear Function Subject to Nonlinear Constraints. The Computer Journal , vol.
134,119 ,pp. 178 - 184, 1970.
[ 32 ] HESTENES , M. R. - Multiplier and Gradient Methods. Joumal of Optimization

Theory and Applications ,vol. 4 ,pp. 303 - 320 , 1969.
[ 33 ] HZMMELBLAU , D. M. - Applied Nonlinear Programming. McGraw - Hill , New

York ,1972.
[ 34 ] HOCH , W. & SCHiTTKOWSKI , K. - The Examples for Nonlinear Programming

Codes . Springer - Verlag ,Berlin and Heidelberg , 1981.
[ 35 ] HUARD ,P. - Resolution of Mathematical Programming with Nonlinear Constraints by
the Methods of Centers . In Nonlinear Prograrnming , J. Abadie ed. , 1967.
[ 36 ] JACKSON , R. H. F. ; CHAIR ; PAUL T. BOGGS ; STEPHEN ; G. NASH &
SUSAN POWELL - Report of the Ad Hoc Committee to Revise the Guidelines
for Reporting Computational Experiments , In Mathematical Programming , 1989.
[ 37 ] KORT ,B. W. & BERTSEKAS ,D. P. - Combined Prima1 Dual and Penal@ Methods
for Convex Programming . SIAM Journal Control and Optirnization ,vol. 14 , pp.
268 - 294,1976.
[ 38 ] KOWALIK , J. - Nonlinear Procedures and Desigin Optimization . Acta Polytechica

Scandinavica , 13 ,pp. 1 - 47 , 1966.
[ 39 ] KUHN , W. W. & TUCKER , A. W. - Nonlinear Programming , Proc. 2nd Berkeley
Symp. on Mathematical Statistics and Probability. University of California Press ,
Berkeley ,pp. 48 1 - 492 , 1951.
[ 40 ] LOOTSMA ,F. A. - Constrained Optimization via Penalty Functions. Philips Research

Reports , 2 3 , pp. 408 - 423 , 1968.
[ 41 1 LOOTSMA , F. A. - A Survey of Methods for Solving Constrained Minimization
Problems via Unconstrained Minimization . In: Numerical Method for Nonlinear
Optimizations . ed. F. A. Lootsma ,Academic Press ,London ,pp. 313 - 347, 1972.
[ 42 ] LUENBERGER ,D. G. - Introduction to Linear and Nonlinear Programming. Addison
Wesley ,Medo Park ,1973.
[ 43 ] MARTINEZ , J. M. & SANTOS , S. A. - Métodos Computacionais de Otimizaqão ,
20" Colóquio Brasileiro de Matemática ,IMPA ,Rio de Janeiro ,Brasil, 1995.
[ 44 ] MIELE ,A. ; GRAGG ,E. E. ; IYER ,R. R. & LEVY ,A. V. - Use the Augmented
Penalty Function in Mathematical Programming Problems . Journal of
Optimization Theory and Applications . Vol. 8 ,pp. 115 - 130 , 1971a .
[ 45 ] MIELE , A. ; GRAGG, E. E. & LEVY , A. V. - Use the Augmented Penalty

Function in Mathematical Programming Problems , Part 2 . Journal of
Optimization Theory and Applications . Vol. 8 ,pp. 131 - 153 , 1971b.
[ 46 ] MIELE , A. ; MOSELEY , P. E. & GRAGG , E. E. - A ModiJication of the

Method of Multipliers for Mathematical Programming Problems , In Techniques
of Optimization. Balakrishnan A. V. ed. ,Academic Press ,New York , pp. 247 -
260 , 1972a.
[ 47 ] MIELE , A. ; MOSELEY , P. E. ; LEVY , A. V. & COGGIN , G. M. - On the
Method of Multipliers for Mathematical Programming Problems. Journal of
Optimization Theory and Applications. Vol. 10 ,pp. 01 - 33 , 1972b.
[ 48 ] MINOUX , M. - Mathematical Programming Theory and Algorithms. John Wiley and
Sons , Chichester , 1986.
[ 49 ] OSBORNE ,M.R. & RYAN , D. M. - On Penalty Function Methods for Nonlinear

Programming Problems. J. Math. Analysis and Applications.,31, pp.557-578 , 1970
[ 50 ] PIERRE , D. A. & LOWE , M. J. - Mathematical Programming via Augmented
Lagrangians , An Introduction with Computer Programs. Addison - Wesley,
Reading , 1975.
[ 5 1 ] POLAK ,E. - Computational Methods in Optimization , A Unified Apprach. Academic
Press ,New York , 1971.
[ 52 ] POWELL ,M. J. D. - A Method for Nonlinear Constraints in Minimization Problems,
In Optimization. Fletcher R. ed. ,Academic Press ,London ,pp. 283 - 298 , 1969.
[ 53 ] POWELL , M. J. D. - Algorithms for Nonlinear Constraints that use Lagrangian

Functions. Mathematical Programming. Vol. 14 ,pp. 224 - 248 , 1978.
[ 54 ] ROCKAFELLAR ,R. T. - Convex Analysis . Princeton University Press , Princeton ,

New Jersey , 1970.
[ 55 ] ROCKAFELLAR , R. T. - A Dual Approach in Solving Nonlinear Programming

Problems by Unconstrained Optmization . Mathematical Programming. Vol. 5 ,
pp. 354 - 373 , 1973a.
[ 56 ] ROCKAFELLAR , R. T. - The Multiplier Method of Hestenes and Powell Applied to

Convex Programming. Journal of Optimization Theory and Applications. Vol. 12 ,
nQ 6 ,pp. 555 - 562 , 1973b.

[ 57 ] ROCKAFELLAR , R. T. - Augmented Lagrange Multiplier and Duality in Nonconvex
Programming . SIAM Journal of Control. Vol. 12 ,pp. 268 - 285 , 1974.
[ 58 ] ROSEN ,J. B. - The Gradient Projectionfor Nonlinear Programming - Part I :Linear
Constraints . Journal Soc. Ind. Appl. Math. Vol. 8 ,pp. 181 - 217 , 1960.
[ 59 ] ROSEN , R. T. - The Gradient Projection for Nonlinear Programming - Part II :
Nomlinear Constraints . Journal Soc. Ind. Appl. Math.. Vol. 9 , pp. 514 - 532 ,
1961.
[ 60 ] WILSON , R. B. -A Simplicial Algorithm for Concave Programming. Unpublished
Ph.D. Dissertation, Haward University Graduate School of Business Adrninistration
Boston , 1963.
[ 61 ] WOLFE ,P. - Methods of Nonlinear Programming . The Reduced Gradient Method,
í n : Recent Advances in Mathematical Programming. eds. Graves and Wolle,
McGraw-Hill ,New York ,pp. 67 - 86 , 1963.
[ 62 ] XAVIER , A. E. - Penalização Hiperbólica - Um Novo Método para Resolução de

Problemas de Otimização . Tese de M. Sc. COPPE / UFRJ , Rio de Janeiro ,
Brasil , 1982.
[ 63 ] XAVIER , A. E. - Penalização Hiperbólica - Uma Abordagem Lagrangeana .

Trabalho Apresentado no XVI CNMAC ,Friburgo ,Rio de Janeiro , 1981.
[ 64 ] XAVIER , A. E. - Penalização Hiperbólica . Tese de D. Sc. COPPE / UFRJ ,Rio de
Janeiro ,Brasil , 1992 .
[ 65 ] XAVIER ,A . E. & MACULAN , N. - Hiperbolic Lagrangean :A New Method of
Multiplier .Trabalho a ser publicado . Rio de Janeiro ,Brasil , 1995.

[ 66 ] XAVIER ,A . E . & MACULAN ,N. - Extrapolação em Penalização Hiperbólica. II
Congresso Latino Americano de Investigação Operativa e Inginieria de Sistemas
( Trabalhos selecionados ) ,Buenos Aires ,pp. 24 - 38 , 1984.
[ 67 ] ZANGWILL , W. L. - Nonlinear Programming via Penalty Functions. Management

Science . Vol. 13 ,pp. 344 - 358 ,1967.
[ 68 ] ZANGWILL ,W. L. - Nonlinear Programming - A Unzjied Approach . Prentice Hall ,

Inc. Englewood Cliffs ,New York , 1969.

Untitled

Enviado por

Direitos autorais:

Formatos disponíveis

Untitled

Enviado por

Dados do documento

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Untitled

Enviado por

Direitos autorais:

Formatos disponíveis

UM NOVO ALGORÍTMO DE PENALIZAÇÃO HIPERBÓLICA PARA

RESOLUÇÃO DO PROBLEh4A DE PROGRAMAÇÃO NÃO-LINEAR COM

Turíbio José Gomes dos Santos

TESE SUBMETIDA AO CORPO DOCENTE DA COORDENAÇÃO DOS

RIO DE JANEIRO - RJ - BRASIL

Um novo algorítmo de penalização hi-

perbólica para resolver o problema de progra-

mação não-linear sujeito a restrições de igual-

dades . [ Rio de Janeiro ] 1998

XIII , p. 29,7 cm (COPPE 1 UFRJ,

D.Sc. ,Engenharia de Sistemas e Computação

Tese - Universidade Federal do Rio de

1. Otimização , 2 . Programação Não-Linear

3 . Método de Penalidade , 4 . Lagrangeano.

Ao Programa de Engenharia de Sistemas e Computação da COPPE 1 UFRJ pelo

apoio na realização deste doutorado .

Aos professores Paulo Roberto , Susana Scheimberg , Clovis Gonzaga , Adilson

Ao professor Adilson Xavier , a quem muito admiro pelo espírito de pesquisa,

agradeço profundamente a sua confiança , solidariedade , amizade , e pela riqueza e

Ao professor Roberto Quirino , pelo incentivo , apoio , compreensão e amizade ,

Aos meus pais Avelino e Lôide ,muito presentes e solidários me incentivando e

dando forças para a elaboração deste trabalho .

compreensão e amizade, desde o início deste trabalho .

Aos meus colegas da UFPb e em particular aos professores do Departamento de

Matemática da UFPb-JP, pela contiança, incentivo e apoio em todos os momentos.

ajudar em qualquer problema, agradeço por suas amizades.

A CAPES / PICD , pelo apoio financeiro durante todo o período de estudos e

para a obtenção do grau de Doutor em Ciências (D. Sc. ).

UM NOVO ALGORÍTMO DE PENALIZAÇÃO HIPERBÓLICA

PARA RESOLVER O PROBLEMA DE PROGRAMAÇÃO NÃO-

LINEAR SUJEITO A RESTRIÇÕES DE IGUALDADES

Turíbio José Gomes dos Santos

Orientador : Adilson Elias Xavier

Programa : Engenharia de Sistemas e Computação

O presente trabalho mostra um novo algorítmo para resolução do problema de

programação não-linear com restrições de igualdades. Para isso , se utiliza do método

de penalização hiperbólica , originalmente desenvolvido para resolução de problemas de

programação não-linear com restrições de desigualdades.

Através da consolidação de resultados previamente estabelecidos , apresentamos

ademais, um outro algorítmo que contempla a resolução dos problemas de programação

não-linear simultaneamente com restrições de igualdades e desigualdades.

O desempenho computacional desses algorítmos é ilustrado através da resolução

de um conjunto de problemas -teste da bibliografia.

for the degree of Doctor of Science.(D. Sc. ).

A NEW ALGORITHM OF HIPERBOLIC PENALIZATION TO

TO SOLVE THE NONLINEAR PROGRAMMNIG PROBLEMS

SUBJECT TO EQUALITY CONSTRAINTS

Turíbio José Gomes dos Santos

Chaimian: Adilson Elias Xavier

Department : Systems Engineering and Computer Sciences

problems with inequality constraints.

By the consolidation of previously established results , it is presented additionally

with equality and inequality constraints simultaneously.

The computational performance of these algorithm is exhibited through the

solution of a set of test-problerns extracted fiom the literature.

ÍNDICE DAS TABELAS ............................................................................... xi

NOTAÇÕES ...................................................................................................... xii

MÉTODOS UTILIZADOS PARA RESOLUÇÃO DE PROBLEMAS

DE PROGRAMAÇÃO NÃO-LINEAR COM RESTRIÇÕES ........................ 18

MÉTODO DE D ~ E Ç Õ E SVIÁVEIS .............................................................. 18