ads:
Grasielli Gava
Alternativas para Resoluc¸
˜
ao de Sistemas
N
˜
ao-Lineares Especiais
Florian´opolis
Marc¸o de 2007
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Grasielli Gava
Alternativas para Resoluc¸
˜
ao de Sistemas
N
˜
ao-Lineares Especiais
Dissertac¸˜ao apresentada ao Curso de P´os-
Graduac¸˜ao em Matem´atica e Computac¸˜ao Ci-
ent´ıfica, do Centro de Ciˆencias F´ısicas e Ma-
tem´aticas da Universidade Federal de Santa Ca-
tarina, para obtenc¸˜ao do grau de Mestre em Ma-
tem´atica, com
´
Area de Concentrac¸˜ao em Ma-
tem´atica Aplicada.
Orientador:
Prof. Dr. M
´
ario C
´
esar Zambaldi
U F S C
Florian´opolis
Marc¸o de 2007
ads:
Aos meus pais,
aos meus irm˜aos,
aos amigos que estiveram ao meu lado
e ao Rodrigo.
Agradec¸o o apoio financeiro do CNPq.
Resumo
Neste trabalho fazemos um estudo e implementac¸˜ao computacional de alguns m´etodos
num´ericos para resoluc¸˜ao de sistemas n˜ao-lineares especiais. Consideramos sistemas com
restric¸˜oes de caixas abordados por meio de t´ecnicas de regi˜ao de confianc¸a espec´ıficas. Re-
solvemos tamb´em o problema de quadrados m´ınimos n˜ao-lineares por meio de t´ecnicas de
penalizac¸˜ao para o sistema n˜ao-linear associado.
Abstract
In thiswork we make astudy and computationalimplementationofsome numerical methods
for the solution of special nonlinear systems of equations. We solve some systems with bound
constraints by using trust region techniques. We also solve nonlinear least squares problems by
using penalization techniques designed to nonlinear systems.
Sum
´
ario
Introduc¸
˜
ao p.8
1 Elementos de Otimizac¸
˜
ao para Sistemas de Equac¸
˜
oes N
˜
ao-lineares p.11
1.1 M´etodo de Newton para sistemas de equac¸˜oes n˜ao-lineares . . . . . . . . . . p.12
1.2 M´etodo de Broyden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.12
1.3 M´etodos de busca linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.14
1.4 M´etodos de regi˜ao de confianc¸a . . . . . . . . . . . . . . . . . . . . . . . . p.16
1.5 Problema de quadrados m´ınimos n˜ao-lineares . . . . . . . . . . . . . . . . . p.19
1.5.1 M´etodo de Gauss-Newton . . . . . . . . . . . . . . . . . . . . . . . p.19
1.5.2 M´etodo Levenberg-Marquardt . . . . . . . . . . . . . . . . . . . . . p.20
2 Sistemas N
˜
ao-lineares com Restric¸
˜
oes de Caixa p.22
2.1 Introduc¸˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.22
2.2 O algoritmo e sua implementac¸˜ao . . . . . . . . . . . . . . . . . . . . . . . p.23
2.3 An´alise de convergˆencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.29
2.4 Resultados num´ericos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.33
3 O Problema de Quadrados M
´
ınimos N
˜
ao-lineares Restrito via Penalizac¸
˜
ao p.37
3.1 M´etodo Newton-Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . p.37
3.2 Penalizac¸˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 39
3.2.1 An´alise de convergˆencia . . . . . . . . . . . . . . . . . . . . . . . . p.42
3.3 Resultados num´ericos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.45
3.3.1 Fluxo de potˆencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.45
3.3.1.1 Modelagem do problema . . . . . . . . . . . . . . . . . . p. 47
3.3.1.2 O problema sem soluc¸˜ao . . . . . . . . . . . . . . . . . . p.49
3.3.1.3 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . p.50
3.3.2 Outras aplicac¸˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.52
Conclus
˜
ao p.54
Refer
ˆ
encias p.56
Ap
ˆ
endice A -- Problemas p.58
A.1 Problemas referentes ao cap´ıtulo 2 . . . . . . . . . . . . . . . . . . . . . . . p.58
A.2 Problemas referentes ao cap´ıtulo 3 . . . . . . . . . . . . . . . . . . . . . . . p.78
8
Introduc¸
˜
ao
Sistemas de equac¸˜oes n˜ao-lineares aparecem em grande parte dos modelos matem´aticos
provenientes de problemas da vida real.
´
E o caso de sistemas de potˆencias em engenharia
el´etrica, equac¸˜oes diferenciais parciais n˜ao-lineares em v´arias ´areas, entre outras aplicac¸˜oes.
Em geral, os m´etodos para resoluc¸˜ao desses modelos s˜ao baseados em linearizac¸˜oes suces-
sivas entre outras t´ecnicas espec´ıficas. Usualmente m´etodos numericamente eficientes devem
ser adequados `as caracter´ısticas dos sistemas, como por exemplo, o grau de n˜ao-linearidade ou
o n´umero de vari´aveis.
Um sistema n˜ao-linear pode ser representado por:
F(x) = 0, F :
n
→
n
. (1)
O que referenciamos no t´ıtulo deste trabalho de sistemas n˜ao-lineares especiais, s˜ao siste-
mas mais espec´ıficos que (1). Neste trabalho consideramos dois modelos centrais. O primeiro
deles consiste em limitar o dom´ınio `a restric¸˜oes de caixas. Neste caso o sistema ´e descrito por:
F(x) = 0,
l ≤ x ≤ u.
(2)
A introduc¸˜ao dessas restric¸˜oes merece uma t´ecnica espec´ıfica para sua resoluc¸˜ao, como
veremos na seq¨uˆencia do trabalho, e que n˜ao ´e usual para a resoluc¸˜ao de (1). Para obter um
algoritmo robusto, devemos incorporar t´ecnicas que o fazem independente do ponto inicial.
Uma forma cl´assica e conhecida ´e a estrat´egia de busca linear usando como func¸˜ao de m´erito a
soma de quadrados das componentes de F. Alternativamente, a t´ecnica de regi˜ao de confianc¸a
para o sistema com restric¸˜oes de caixa. Ela se adequa precisamente ao uso das restric¸˜oes por
meio do uso do escalamento da regi˜ao de confianc¸a.
O m´etodo apresentado aqui, descrito em [1], utiliza regi˜oes de confianc¸a elipsoidais, defi-
nidas por Coleman e Li [2], originalmente descritas por Dikin [3]. Em cada passo do m´etodo,
uma func¸˜ao quadr´atica ´e minimizada em uma regi˜ao de confianc¸a el´ıptica que depende dos
limitantes l e u. Assim, evita-se a minimizac¸˜ao da func¸˜ao quadr´atica na caixa.
9
Outro problema interessante e relacionado `a (1) consiste em considerar algumas equac¸˜oes
para as quais n˜ao existe soluc¸˜ao. Pode ser representado assim:
F(x) =
f(x)
c(x)
,
em que c(x) = 0, e em geral f(x) 0. Assim o problema de interesse fica
min
x∈
n
1
2
||f(x)||
2
2
s.a. c(x) = 0.
(3)
Em geral, problemas como estes s˜ao abordados por m´etodos de quadrados m´ınimos n˜ao-
lineares. No problema de quadrados m´ınimos n˜ao-lineares em que a restric¸˜ao c(x) = 0 n˜ao
aparece, o mais comum ´e utilizarmos m´etodos como Gauss-Newton e Levenberg-Marquardt.
Como em (3) aparecem restric¸˜oes, ele pode ser resolvido utilizando-se a func¸˜ao Lagrangiano.
A motivac¸˜ao principal para resoluc¸˜ao deste modelo ´e o fato de que est´avamos investigando
as soluc¸˜oes do problema de fluxo de potˆencias [4], um sistema n˜ao-linear do tipo (1). Uma
forma mais elaborada do modelo, considerando as especificidades do problema pr´atico em
engenharia el´etrica, ´e relaxar algumas equac¸˜oes de modo que n˜ao tenham ra´ızes. Economi-
camente este fato ´e muito importante, significando por exemplo, permitir que certas regi˜oes
estejam muito mais sujeitas `a falta de energia que outras, evitando carregamento ou colapso do
sistema el´etrico em hor´arios de pico. Ent˜ao, como algumas equac¸˜oes n˜ao apresentam zeros, a
id´eia ´e trat´a-las de modo distinto das outras. Isto, como veremos mais adiante, permite trabalhar
apenas com informac¸˜oes de primeira ordem ao contr´ario das t´ecnicas usuais para o problema
de quadrados m´ınimos n˜ao-lineares.
Neste trabalho fazemos um estudo e implementac¸˜ao computacional de alguns m´etodos
num´ericos para resoluc¸˜ao de sistemas n˜ao-lineares especiais. Consideramos sistemas com
restric¸˜oes de caixas abordados por meio de t´ecnicas de regi˜ao de confianc¸a espec´ıficas. Damos
ˆenfase ao problema de fluxo de potˆencias sem soluc¸˜ao real. Resolvemos tamb´em o problema de
quadrados m´ınimos n˜ao-lineares por meio de t´ecnicas de penalizac¸˜ao para o sistema n˜ao-linear
associado.
O trabalho est´a organizado como se segue. No Cap´ıtulo 1 apresentamos os t´opicos de
otimizac¸˜ao n˜ao-linear cl´assicos, que ser˜ao referenciados durante o trabalho. No Cap´ıtulo 2
tratamos de m´etodospara a resoluc¸˜ao de (2). No Cap´ıtulo 3 descrevemos o modelo das equac¸˜oes
da rede el´etrica que d˜ao origem ao problema mais relevante do tipo (3); estudamos tamb´em
10
m´etodos de resoluc¸˜ao. Conseq¨uˆencias, conclus˜oes e futuras linhas de seq¨uˆencia do trabalho
fecham este trabalho.
11
1 Elementos de Otimizac¸
˜
ao para
Sistemas de Equac¸
˜
oes N
˜
ao-lineares
Neste cap´ıtulo apresentamos alguns conceitos e resultados que vamos explorar nos cap´ıtulos
que se seguem. Esta exposic¸˜ao resumida tem apenas o prop´osito de referˆencia usada neste
trabalho. Detalhes podem ser encontrados em textos cl´assicos como [5] e [6].
Vamos considerar dois problemas centrais em otimizac¸˜ao n˜ao linear. Um sistema de equa-
c¸˜oes n˜ao-lineares consiste em obter x ∈
n
tal que
F(x) = 0 (1.1)
em que F :
n
→
n
´e continuamente diferenci´avel.
Uma forma de resolver (1.1) ´e exigir a reduc¸˜ao de ||F(x)||
2
se poss´ıvel para 0. Nosso pro-
blema pode ser reescrito como
min
x∈
n
1
2
|| F(x)||
2
2
, (1.2)
onde o quadrado da norma tem a vantagem de deixar a func¸˜ao objetivo continuamente dife-
renci´avel. Embora nem toda soluc¸˜ao de (1.2) seja soluc¸˜ao de (1.1) poder´ıamos pensar em utili-
zar um m´etodo de minimizac¸˜ao para resolver o sistema n˜ao-linear. Neste caso seria importante
usar a estrutura do problema (1.1). A direc¸˜ao de Newton de (1.1) ´e uma direc¸˜ao de descida para
(1.2). Outro ponto de conex˜ao ´e que estrat´egias globais para (1.1) est˜ao baseadas em (1.2). Isso
veremos mais adiante.
No que se segue, descrevemos resumidamente os m´etodos de Newton e Broyden para sis-
temas n˜ao-lineares e examinaremos suas propriedades de convergˆencia local. Para obter a con-
vergˆencia global, apresentaremos os m´etodos de busca linear e m´etodos de regi˜ao de confianc¸a.
Apresentaremos tamb´em uma introduc¸˜ao sobre o problema de quadrados m´ınimosn˜ao-lineares.
12
1.1 M
´
etodo de Newton para sistemas de equac¸
˜
oes n
˜
ao-linea-
res
O m´etodo de Newton para sistemas de equac¸˜oes n˜ao-lineares consiste em resolver uma
seq¨uˆencia de problemas aproximados ao nosso problema original, com o objetivo de nos apro-
ximar da soluc¸˜ao de (1.1).
A cada iterac¸˜ao k, constr´oi-se um modelo M
k
aproximado de F e encontra-se a soluc¸˜ao x
k+1
de M
k
(p) = 0.
Sabemos que
F(x + p) = F(x) +
1
0
F
′
(x + tp)pdt (1.3)
em que F
′
representa o Jacobiano de F.
Obtemos o modelo M
k
, aproximando a integral em (1.3) pelo termo linear F
′
(x)p, obtendo
M
k
(p) = F(x
k
) + F
′
(x
k
)p.
Assim, x
k+1
= x
k
+ p
k
em que p
k
´e a soluc¸˜ao do sistema linear
F
′
(x
k
)p
k
= −F(x
k
). (1.4)
Se a aproximac¸˜ao x
k
est´a pr´oxima de uma soluc¸˜ao x
∗
e o Jacobiano F
′
´e uma func¸˜ao
cont´ınua de x, o m´etodo de Newton possui convergˆencia local superlinear, e, se a aproximac¸˜ao
x
k
est´a pr´oxima de uma soluc¸˜ao x
∗
e o Jacobiano F
′
´e Lipschitz cont´ınuo, ent˜ao o m´etodo de
Newton possui convergˆencia local quadr´atica.
1.2 M
´
etodo de Broyden
Como visto acima, o m´etodo de Newton possui boa convergˆencia local, mas possui o in-
conveniente de calcular o Jacobiano de F em cada iterac¸˜ao. As direc¸˜oes quase-Newton s˜ao uma
alternativa atraente, j´a que n˜ao requerem o c´alculo do Jacobiano e ainda alcanc¸am a raz˜ao de
convergˆencia superlinear. Em sistemas grandes, estes m´etodos tˆem a vantagem de trabalhar di-
retamente com formas n˜ao fatoradas das aproximac¸˜oes para a inversa do Jacobiano, com custo
inferior `a resoluc¸˜ao do sistema n˜ao-linear.
13
Os m´etodos quase-Newton constr´oem, em cada iterac¸˜ao, uma aproximac¸˜ao para o Jacobi-
ano de F. O Jacobiano aproximado B(x
k
) ´e usado no lugar de F
′
(x
k
) em (1.4). Assumindo que
B(x
k
) seja n˜ao-singular, o passo para a pr´oxima iterac¸˜ao ser´a a soluc¸˜ao de
B(x
k
)p
k
= −F(x
k
).
As matrizes de aproximac¸˜ao geradas pelos m´etodos quase-Newton devem ser uma boa
aproximac¸˜ao do Jacobiano ao longo da direc¸˜ao p
k
, para isso exige-se que M
k+1
seja igual `a
F ao menos nas duas ´ultimas aproximac¸˜oes, x
k
e x
k+1
. Assim, como M
k+1
(0) = F(x
k+1
), basta
exigirmos
M
k+1
(−p
k
) = F(x
k+1
) − B(x
k+1
)p
k
= F(x
k
),
ou seja,
B(x
k+1
)p
k
= F(x
k+1
) − F(x
k
).
Considerando s
k
= x
k+1
− x
k
e y
k
= F(x
k+1
) − F(x
k
) obtemos a equa¸c˜ao secante:
y
k
= B(x
k+1
)s
k
, (1.5)
que garante a boa concordˆancia de B(x
k+1
) e F
′
(x
k+1
) ao longo de p
k
.
No m´etodo de Broyden a matriz B
k+1
= B(x
k+1
) ´e atualizada da seguinte forma
B
k+1
= B
k
+
(y
k
− B
k
s
k
)s
T
k
s
T
k
s
k
. (1.6)
Segundo [6, Lema 11.4], a atualizac¸˜ao de Broyden ´e a atualizac¸˜ao que faz as menores
mudanc¸as poss´ıveis na matriz B
k
(medida pela norma Euclideana ||B
k
− B
k+1
||), dentre as que
satisfazem (1.5).
O desempenho do m´etodo depende muito da escolha de B
0
= B(x
0
), algumas implementa-
c¸˜oes recomendam escolher B
0
como sendo F
′
(x
0
) ou alguma aproximac¸˜ao por diferenc¸as finitas
desta matriz.
14
1.3 M
´
etodos de busca linear
Podemos obter algoritmos com convergˆencia global, aplicando os m´etodos de busca linear
para a func¸˜ao f(x) =
1
2
|| F(x)||
2
2
. Na estrat´egia de busca linear, ap´os escolhermos a direc¸˜ao de
busca p
k
, buscamos ao longo desta direc¸˜ao, a partir da aproximac¸˜ao x
k
, uma nova aproximac¸˜ao
x
k+1
com um valor de func¸˜ao menor, ou seja, f(x
k+1
) < f(x
k
).
A nova aproximac¸˜ao ser´a dada por:
x
k+1
= x
k
+ α
k
p
k
,
em que o escalar positivo α
k
´e chamado de comprimento do passo, e pode ser encontrado
resolvendo-se aproximadamente o seguinte problema de minimizac¸˜ao unidimensional
min
α>0
φ(α
k
),
sendo φ(α
k
) = f(x
k
+ α
k
p
k
).
A condic¸˜ao de que f(x
k+1
) = f(x
k
+ α
k
p
k
) < f(x
k
) n˜ao garante que {x
k
} convirja para
um minimizador de f. Podemos ter reduc¸˜oes muito pequenas no valor de f em relac¸˜ao ao
tamanho dos passos e tamb´em podemos tomar passos muito pequenos em relac¸˜ao `a taxa de
decrescimento inicial de f.
Para evitar que a func¸˜ao tenha um decr´escimo muito pequeno em relac¸˜ao ao seu valor
anterior, podemos exigir que a reduc¸˜ao em f seja proporcional ao tamanho do passo α
k
e `a sua
derivada direcional na direc¸˜ao p
k
, ∇f(x
k
)
T
p
k
, que representa a taxa de decr´escimo da func¸˜ao
nesta direc¸˜ao. Assim queremos encontrar α
k
entre os α que satisfazem
f(x
k
+ αp
k
) ≤ f(x
k
) + c
1
α∇f(x
k
)
T
p
k
, (1.7)
com c
1
∈ (0, 1). Esta desigualdade ´e chamada Condi¸c˜ao de Armijo [6].
Paraevitarmos passos muitopequenos, inclui-se umacondic¸˜ao que teste a inclinac¸˜ao φ
′
(α) =
∇f(x
k
+ αp
k
)
T
p
k
decorrente da escolha de α:
∇f(x
k
+ αp
k
)
T
p
k
≥ c
2
∇f(x
k
)
T
p
k
,
com c
2
∈ (c
1
, 1), c
1
escolhido na condic¸˜ao (1.7). Essa condic¸˜ao, chamada de Condi¸c˜ao de Cur-
15
vatura, exige que a inclinac¸˜ao de φ em α
k
seja maior do que a inclinac¸˜ao de φ em 0. Lembrando
que φ(0) = f(x
k
), esta exigˆencia garante que α
k
n˜ao ser´a escolhido pequeno demais.
As condic¸˜oes de Armijo e de curvatura juntas s˜ao chamadas de Condi¸c˜oes de Wolfe [6].
A convergˆencia global depende n˜ao somente de uma boa escolha de α
k
, mas tamb´em de
uma boa escolha para a direc¸˜ao de busca. Considerando θ
k
como o ˆangulo entre p
k
e a direc¸˜ao
de descida −∇f(x
k
) = −F
′
(x
k
)
T
F(x
k
), a direc¸˜ao p
k
dever´a satisfazer
cosθ
k
= −
p
T
k
∇f(x
k
)
||p
k
||||∇f(x
k
)||
> 0,
ou seja, p
k
dever´a ser uma direc¸˜ao de descida para F.
Segundo [6, Teorema 11.6], no caso da busca linear que escolhe α
k
satisfazendo as condi-
c¸˜oes de Wolfe, se garantirmos que
cosθ
k
≥ δ, para algum δ ∈ (0, 1) e para todo k suficientemente grande, (1.8)
ent˜ao F
′
(x
k
)
T
F(x
k
) → 0. Al´em disso, quando ||F
′
(x
k
)
−1
|| ´e limitada em uma vizinhanc¸a D do
conjunto de n´ıvel L = {x : f(x) ≤ f(x
0
)} temos que F(x
k
) → 0, ou seja, que a aproximac¸˜ao
x
k
dever´a se aproximar de um ponto limite x
∗
que resolve o problema de equac¸˜oes n˜ao-lineares
F(x) = 0.
O passo de Newton (1.4) ´e uma direc¸˜ao de descida para f, e assim, podemos ver que
cosθ
k
= −
p
T
k
∇f(x
k
)
||p
k
||||∇f(x
k
)||
=
|| F(x
k
)||
2
|| F
′
(x
k
)
−1
F(x
k
)|||| F
′
(x
k
)
T
F(x
k
)||
≥
1
|| F
′
(x
k
)
T
||||F
′
(x
k
)
−1
||
=
1
κ(F
′
(x
k
))
em que κ(F
′
(x
k
)) ´e o n´umero de condic¸˜ao de F
′
(x
k
). Assim se κ(F
′
(x
k
)) ´e uniformemente
limitado para todo k, ent˜ao cosθ
k
´e limitado no estilo de (1.8).
O mesmo acontece em um algoritmo de busca linear quase-Newton, com p
k
= −B
−1
k
∇f(x
k
),
pois tudo o que precisamos ´e que os n´umeros de condic¸˜oes de {B
k
} sejam uniformemente limi-
tados. O seguinte teorema, devido a Dennis e Mor´e, mostra que se a direc¸˜ao de busca de um
m´etodo Quase-Newton aproxima muito bem a direc¸˜ao de Newton, ent˜ao o comprimento de
passo unit´ario ir´a satisfazer as condic¸˜oes de Wolfe assim como as aproximac¸˜oes convergem
para a soluc¸˜ao.
Teorema 1 Seja f :
n
→ , f ∈ C
2
(D), em que D ´e um conjunto aberto, convexo de e ∇
2
f
16
´e Lipschitz cont´ınua em D. Considere uma seq¨uˆencia {x
k
} gerada por x
k+1
= x
k
+ α
k
p
k
, em que
∇f(x
k
)
T
p
k
< 0 para todo k e α
k
´e escolhido para satisfazer as condi¸c˜oes de Wolfe com c
1
<
1
2
.
Se x
k
→ x
∗
∈ D, em que ∇
2
f(x
∗
) ´e positiva definida, e se
lim
k→∞
||∇f(x
k
) + ∇
2
f(x
k
)p
k
||
||p
k
||
= 0 (1.9)
ent˜ao existe um ´ındice k
0
≥ 0 tal que para todo k ≥ k
0
, α
k
= 1 ´e admiss´ıvel. Al´em disso,
∇f(x
∗
) = 0, e se α
k
= 1 para todo k ≥ k
0
, ent˜ao {x
k
} converge superlinearmente para x
∗
.
A condic¸˜ao (1.9) ´e necess´aria e suficiente para a taxa de convergˆencia superlinear dos
m´etodos quase-Newton.
Assim, se utilizarmos a estrat´egia de busca linear, os m´etodos de direc¸˜ao de descida con-
vergem, desde que a escolha do passo satisfac¸a as condic¸˜oes de Wolfe, ou alguma condic¸˜ao
equivalente.
1.4 M
´
etodos de regi
˜
ao de confianc¸a
No m´etodo de busca linear descrito acima, tratamos exclusivamente com o problema de
encontrar um comprimento de passo aceit´avel em uma direc¸˜ao de busca dada. Se a direc¸˜ao
de busca n˜ao for satisfat´oria, significa que o modelo utilizado n˜ao est´a representando adequa-
damente a func¸˜ao f. Caso isso acontec¸a, os algoritmos de busca linear mant´em essa mesma
direc¸˜ao de busca e calculam um novo comprimento de passo.
Na estrat´egia de regi˜ao de confianc¸a, em cada iterac¸˜ao ´e constru´ıdo um modelo quadr´atico
de f e uma regi˜ao em que considera-se que o modelo represente a func¸˜ao adequadamente e
minimiza-se este modelo na regi˜ao, da´ı o nome regi˜ao de confianc¸a, ou seja, primeiro escolhe-
mos o comprimento m´aximo para o passo e depois, utilizando o modelo, escolhemos a direc¸˜ao
do passo. Dependendo do resultado obtido com esta minimizac¸˜ao, algumas decis˜oes s˜ao toma-
das: aceitar ou n˜ao o minimizador como um novo ponto (uma nova aproximac¸˜ao); aumentar,
reduzir, ou deixar inalterada a regi˜ao de confianc¸a
Considerando ent˜ao o modelo
m
k
(p) = f
k
+ ∇f
T
k
p +
1
2
p
T
H
k
p,
em que f
k
= f(x
k
), ∇f
k
= ∇f(x
k
) e H
k
´e a hessiana ∇
2
f(x
k
) ou uma aproximac¸˜ao dela, precisa-
17
mos resolver o seguinte problema
min
p∈
n
m
k
(p) sujeito a ||p|| ≤ ∆
k
, (1.10)
em que ∆
k
> 0 ´e o raio da regi˜ao de confianc¸a. Para a convergˆencia global, ´e suficiente en-
contrar uma soluc¸˜ao aproximada para o problema (1.10), mais adiante apresentaremos uma
das formas de encontrar essa soluc¸˜ao. Outras formas de encontrar soluc¸˜ao aproximada ou at´e
mesmo soluc¸˜oes exatas podem ser obtidas em [6] e [3].
A escolha do raio de regi˜ao de confianc¸a em cada iterac¸˜ao depender´a do desempenho da
direc¸˜ao na iterac¸˜ao anterior, precisamos saber se a reduc¸˜ao obtida no modelo foi t˜ao boa quanto
a reduc¸˜ao da func¸˜ao. Para isso, dada uma direc¸˜ao p
k
, vamos nos basear na seguinte raz˜ao
ρ
k
=
f(x
k
) − f(x
k
+ p
k
)
m
k
(0) − m
k
(p
k
)
,
ou seja, a raz˜ao entre a reduc¸˜ao real da func¸˜ao e a reduc¸˜ao prevista pelo modelo.
Se ρ
k
est´a pr´oximo de 0 ou ´e negativo, significa que a concordˆancia entre o modelo e a
func¸˜ao sobre este passo ´e ruim, assim diminui-se o raio da regi˜ao de confianc¸a e minimiza-se o
mesmo modelo quadr´atico sob esse raio menor. Se ρ
k
est´a pr´oximo de 1, ent˜ao a concordˆancia
entre m
k
e f est´a muito boa e podemos aumentar o raio para a pr´oxima iterac¸˜ao. Se ρ
k
´e positivo
mas n˜ao est´a t˜ao pr´oximo de 1, o raio n˜ao ´e alterado.
Decidido o tamanho da regi˜ao de confianc¸a, precisamos agora resolver (1.10). Vamos en-
contrar uma soluc¸˜ao aproximada p
k
que est´a dentro da regi˜ao de confianc¸a e dˆe uma reduc¸˜ao
suficiente no modelo. A reduc¸˜ao suficiente ser´a quantificada em termos do ponto de Cauchy,
que iremos denotar por p
C
k
. O ponto de Cauchy ´e o minimizador do modelo m
k
(·) ao longo
da direc¸˜ao de m´aximo declive, restrito `a bola de raio ∆
k
em torno de x
k
, e pode ser calculado,
segundo [6], da seguinte forma:
p
C
k
= −τ
k
∆
k
||∇f
k
||
∇f
k
em que
τ
k
=
1, se ∇f
T
k
H
k
∇f
k
≤ 0;
min(||∇f
k
||
3
/(∆
k
∇f
T
k
H
k
∇f
k
), 1), caso contr´ario.
V´arios algoritmos que geram soluc¸˜oes aproximadas p
k
para o subproblema (1.10) comec¸am
18
calculando o ponto de Cauchy e ent˜ao tentam melhor´a-lo. Essa ´e a id´eia do m´etodo dogleg que
vamos descrever abaixo.
Quando H
k
´e positiva definida, o minimizador irrestrito de m
k
´e dado pela direc¸˜ao de New-
ton p
N
k
= −H
−1
k
∇f(x
k
). Se este for um ponto vi´avel para (1.10), ou seja, se ||p
N
k
|| ≤ ∆, ele ser´a
uma soluc¸˜ao e a´ı,
p
k
= p
N
k
.
Quando ∆
k
for muito pequeno, a soluc¸˜ao de (1.10) ser´a dada pelo ponto de Cauchy, assim
p
k
= −∆
∇f
k
||∇f
k
||
Para valores intermedi´arios de ∆
k
a soluc¸˜ao exata do problema de regi˜ao de confianc¸a segue
uma trajet´oria curva como a que est´a apresentada pela chamada trajet´oria ´otima na figura 1.
D
k
p
I
N
Novo
passo
P
assodeNewton
Passodo
Dogleg
Trajetória
ótima
Passode
Cauchy
R
e
g
i
ã
o
d
e
c
o
n
f
i
a
n
ç
a
p
x
k
k
k
Figura 1: O passo do m´etodo dogleg.
O m´etodo dogleg encontra uma soluc¸˜ao aproximada trocando a trajet´oria ´otima por um ca-
minho com dois segmentos de reta. O primeiro segmentovaida aproximac¸˜ao x
k
ao minimizador
irrestrito ao longo da direc¸˜ao de m´axima descida definido por
p
I
k
= −
∇f
T
k
∇f
k
∇f
T
k
B
k
∇f
k
∇f
k
,
enquanto o segundo vai de p
I
k
a p
N
k
. Esta trajet´oria pode ser escrita como
p
k
=
µp
I
k
, 0 ≤ µ ≤ 1,
p
I
k
+ (µ − 1)(p
N
k
− p
I
k
), 1 ≤ µ ≤ 2.
Assim, no caso em que p
N
k
est´a fora da regi˜ao de confianc¸a, o passo doglegser´a a intersecc¸˜ao
da trajet´oria definida acima com o raio da regi˜ao de confianc¸a, este ponto de intersecc¸˜ao pode
19
ser calculado analiticamente, como pode ser visto em [6].
1.5 Problema de quadrados m
´
ınimos n
˜
ao-lineares
O problema de quadrados m´ınimos n˜ao-lineares ´e mais freq¨uentemente encontrado no con-
texto de ajuste de curvas, mas pode aparecer tamb´em quando um sistema de equac¸˜oes n˜ao-
lineares tem mais equac¸˜oes do que inc´ognitas.
´
E um caso especial de minimizac¸˜ao irrestrita, e,
por isso, aproveitando as vantagens da estrutura do problema pode-se modificar as t´ecnicas de
minimizac¸˜ao irrestrita e criar algoritmos mais adequados ao problema.
Dada a func¸˜ao r :
n
→
m
, m ≥ n, o problema de quadrados m´ınimos n˜ao-lineares
consiste em encontrar x ∈
n
para o qual G(x) =
m
i=1
(r
i
(x))
2
´e minimizado, em que r
i
(x) denota
a i-´esima componente da func¸˜ao r.
Embora a minimizac¸˜ao possa ser feita por um m´etodo de minimizac¸˜ao irrestrita padr˜ao, em
muitos casos ´e vantajoso levar em conta as propriedades da func¸˜ao G. As derivadas de G(x)
podem ser expressas em termos do Jacobiano J de r da seguinte forma:
∇G(x) =
m
j=1
r
j
(x)∇r
j
(x) = J(x)
T
r(x)
e
∇
2
G(x) =
m
j=1
∇r
j
(x)∇r
j
(x)
T
+
m
j=1
r
j
(x)∇
2
r
j
(x)
= J(x)
T
J(x) +
m
j=1
r
j
(x)∇
2
r
j
(x). (1.11)
Podemos ent˜ao observar que a Hessiana da func¸˜ao objetivo G(x) consiste de uma combina-
c¸˜ao das informac¸˜oes de primeira e segunda ordem. Muitos algoritmos para quadrados m´ınimos
n˜ao-lineares exploram a estrutura da Hessiana considerando que para o res´ıduo || r
j
(x)|| pequeno,
o termo J(x)
T
J(x) dominar´a o segundo termo de (1.11).
1.5.1 M
´
etodo de Gauss-Newton
O m´etodo Gauss-Newton [7] pode ser visto como uma modificac¸˜ao do m´etodo de Newton
para minimizac¸˜ao irrestrita de G com busca linear. Aqui, o segundo termo de (1.11) ´e exclu´ıdo
20
e obtemos a direc¸˜ao de busca p
k
, resolvendo
J(x
k
)
T
J(x
k
)p
k
= −J(x
k
)
T
r(x
k
). (1.12)
Note que o sistema (1.12) envolve apenas as derivadas de primeira ordem de r. A soluc¸˜ao
de (1.12) ´e uma soluc¸˜ao do problema de quadrados m´ınimos n˜ao-lineares
min
p∈
n
1
2
||J(x
k
)p + r(x
k
)||
2
2
, (1.13)
e ´e ´unica se J(x
k
) tem posto completo. O vetor que resolve (1.13) ´e chamado de direc¸˜ao de
Gauss-Newton e ser´a denotado por p
GN
.
Uma vantagemdo m´etodo Gauss-Newton ´e que quando J(x
k
) tem posto completo, a direc¸˜ao
p
GN
´e uma direc¸˜ao de descida para G. Assim, ´e uma direc¸˜ao adequada para a busca linear e
portanto localmente convergente para quase todos os problemas de quadrados m´ınimos n˜ao-
lineares.
Uma alternativa para o m´etodo Gauss-Newton ´e o m´etodo de Levenberg-Marquardt.
1.5.2 M
´
etodo Levenberg-Marquardt
O m´etodo Levenberg-Marquardt [7] ´e uma modificac¸˜ao do m´etodo Gauss-Newton, no sen-
tido que usa a estrat´egia de regi˜ao de confianc¸a ao inv´es da estrat´egia de busca linear. A direc¸˜ao
de busca do m´etodo Levenberg-Marquardt ´e definida como a soluc¸˜ao das equac¸˜oes
(J(x
k
)
T
J(x
k
) + η
k
I)p
LM
k
= −J(x
k
)
T
r(x
k
) (1.14)
em que η
k
´e um escalar n˜ao-negativo.
Pode-se mostrar que, dado η
k
> 0 existe ∆ = ∆(η
k
) > 0 tal que o vetor p
LM
k
´e a soluc¸˜ao do
subproblema restrito
min
p∈
n
1
2
||J(x
k
)p + r(x
k
)||
2
2
s.a. ||p||
2
≤ ∆.
O uso de t´ecnicas baseadas em regi˜ao de confianc¸a evita uma das fragilidades do m´etodo
Gauss-Newton,isto ´e, ´e adequado quando o jacobiano J(x) tem posto deficiente, ou est´a pr´oximo
disto. Outra vantagem ´e que quando o passo de Gauss-Newton ´e muito longo, o passo de
21
Levenberg-Marquardt est´a pr´oximo de estar em uma direc¸˜ao de descida .
22
2 Sistemas N
˜
ao-lineares com Restric¸
˜
oes
de Caixa
2.1 Introduc¸
˜
ao
Seja F : X →
n
, F ∈ C
2
(X), em que X ⊆
n
´e um conjunto aberto contendo a caixa
n-dimensional
Ω = {x ∈
n
; l ≤ x ≤ u}.
Os vetores l ∈ ( ∪ −∞)
n
e u ∈ ( ∪∞)
n
s˜ao cotas inferiores e superiores para as vari´aveis
de forma que Ω tenha interior n˜ao vazio.
O problema ´e encontrar um vetor x ∈
n
satisfazendo
F(x) = 0, x ∈ Ω. (2.1)
Problemas constitu´ıdos de sistemas n˜ao-lineares F(x) = 0 com restric¸˜oes de desigualda-
des e possivelmente com restric¸˜oes de caixa, podem ser colocados na forma (2.1) atrav´es da
introduc¸˜ao das vari´aveis de folga. Uma observac¸˜ao importante ´e que a formulac¸˜ao (2.1) per-
mite remover as descontinuidades quando a func¸˜ao F n˜ao est´a definida em todo o espac¸o
n
.
M´etodos globalmente convergentes para o problema irrestrito F(x) = 0 podem ser impr´o-
prios para resolver (2.1). Esses m´etodos, como por exemplo o m´etodo de Newton globalizado,
podem gerar soluc¸˜oes falsas (vetores que satisfazem F(x) = 0 mas que n˜ao est˜ao em Ω) t˜ao
r´apido quanto soluc¸˜oes significativas. Mesmo que uma soluc¸˜ao significativa esteja no interior
do conjunto vi´avel, tomar um ponto inicial numa vizinhanc¸a dessa soluc¸˜ao n˜ao garante que as
soluc¸˜oes falsas sejam evitadas.
Segundo [1], uma forma simples de resolver sistemas de equac¸˜oes n˜ao-lineares com restri-
c¸˜oes de caixa ´e transformar (2.1) em um problema de programac¸˜ao n˜ao-linear usando a norma
23
Euclidiana de F como func¸˜ao objetivo. Considerando as diferenc¸as importantes entre equac¸˜oes
n˜ao-lineares e o problema de minimizac¸˜ao, ´e essencial estudar algoritmos espec´ıficos para re-
solver (2.1) em sua forma original, explorando suas principais caracter´ısticas.
O m´etodo apresentado a seguir combina id´eias do m´etodo cl´assico de regi˜ao de confianc¸a
para resolver o sistema de equac¸˜oes n˜ao-lineares irrestrito F(x) = 0, x ∈
n
, e a abordagem
afim escala para a soluc¸˜ao de problemas de otimizac¸˜ao restritos dada por [2]. Uma propriedade
importante do m´etodo ´e a exigˆencia de que todas as aproximac¸˜oes estejam no interior estrito de
Ω.
2.2 O algoritmo e sua implementac¸
˜
ao
Para definir um processo iterativo robusto, o m´etodo de Newton pode ser incorporado em
um esquema de regi˜ao de confianc¸a globalmente convergente. No m´etodo cl´assico de regi˜ao de
confianc¸a, uma regi˜ao em torno da aproximac¸˜ao corrente x
k
´e definida e dentro dessa regi˜ao o
seguinte modelo quadr´atico
m
k
(p) =
1
2
|| F
′
k
p + F
k
||
2
=
1
2
|| F
k
||
2
+ F
T
k
F
′
k
p +
1
2
p
T
F
′T
k
F
′
k
p (2.2)
´e confi´avel para ser uma representac¸˜ao adequada da func¸˜ao de m´erito
f(x) =
1
2
|| F(x)||
2
.
Portanto, a direc¸˜ao de busca p
k
´e o vetor soluc¸˜ao do subproblema
min
p
{m
k
(p); ||p| | ≤ ∆
k
}, (2.3)
para um raio da regi˜ao de confianc¸a ∆
k
dado. Quando o sistema n˜ao-linear ´e restrito, temos
que levar em conta que a exigˆencia da viabilidade estrita pode levar a problemas que impedem
a convergˆencia da seq¨uˆencia {x
k
} para uma soluc¸˜ao de (2.1). Para prevenir estes problemas,
Bellavia, Macconi e Morini [1] usaram a estrat´egia afim escala proposta por Coleman e Li [2].
Considere o gradiente F
′T
(x)F(x) da func¸˜ao de m´erito f e tome v(x) como a func¸˜ao vetorial
com componentes v
i
(x), i = 1, 2, ..., n, dadas por
24
v
i
(x) = x
i
− u
i
, se (F
′T
(x)F(x))
i
< 0 e u
i
< ∞;
v
i
(x) = x
i
− l
i
, se (F
′T
(x)F(x))
i
≥ 0 e l
i
> −∞;
v
i
(x) = −1, se (F
′T
(x)F(x))
i
< 0 e u
i
= ∞;
v
i
(x) = 1, se (F
′T
(x)F(x))
i
≥ 0 e l
i
= −∞.
(2.4)
Tomando D(x) como a matriz diagonal de escala tal que
D(x) = diag(|v
1
(x)|
−1/2
, |v
2
(x)|
−1/2
, . . . , |v
n
(x)|
−1/2
),
podemos considerar a regi˜ao de confianc¸a el´ıptica
|| D
k
p|| ≤ ∆
k
.
Assim, a fim de determinar x
k+1
, um passo p
k
´e calculado resolvendo-se o seguinte subpro-
blema de regi˜ao de confianc¸a el´ıptico
min
p
{m
k
(p); ||D
k
p|| ≤ ∆
k
}. (2.5)
No contexto de sistemas n˜ao-lineares irrestritos, se x
k
´e uma boa aproximac¸˜ao da soluc¸˜ao,
o m´etodo de Newton pode ser aplicado e o passo p
N
k
dado por
F
′
k
p
N
k
= −F
k
resolve (2.5) se ∆
k
´e grande o suficiente para que ||D
k
p
N
k
|| ≤ ∆
k
seja satisfeito.
Por outro lado, se ||D
k
p
N
k
|| > ∆
k
, calculamos uma soluc¸˜ao aproximada de (2.5) reescalando
a vari´avel p de maneira que a regi˜ao de confianc¸a seja esf´erica na vari´avel escalada. Definindo
p = D
k
p e substituindo em (2.5), obtemos:
min
p
m
k
(p) = f
k
+ ∇f
T
k
D
−1
k
p +
1
2
p
T
(D
−1
k
F
′
T
k
F
′
k
D
−1
k
)p
s.a ||p|| ≤ ∆
k
(2.6)
Se ||p
N
k
|| = ||D
k
p
N
k
|| > ∆
k
, calculamos uma soluc¸˜ao aproximada de (2.6) usando o m´etodo
dogleg [6]. De acordo com o cap´ıtulo 1, a trajet´oria curva ´otima ´e aproximada por um caminho
constitu´ıdo de dois segmentos, o primeiro segmento une a aproximac¸˜ao x
k
ao minimizador
25
irrestrito p
I
k
de m
k
(p) ao longo da direc¸˜ao de m´axima descida D
−1
k
∇f
k
:
p
I
k
= −
|| D
−1
k
∇f
k
||
2
|| F
′
k
D
−2
k
∇f
k
||
2
D
−1
k
∇f
k
, (2.7)
enquanto o segundo segmento conecta p
I
k
`a p
N
k
. O m´etodo dogleg aproxima a soluc¸˜ao p
k
de
(2.6) calculando o minimizador do modelo m
k
ao longo desse caminho, ou seja,
p
k
=
∆
k
D
−1
k
∇f
k
/||D
−1
k
∇f
k
||, se ||p
I
k
|| ≥ ∆
k
p
I
k
+ (1 − µ)(p
N
k
− p
I
k
), caso contr´ario
(2.8)
em que µ ´e a soluc¸˜ao positiva da seguinte equac¸˜ao
||p
I
k
+ (1 − µ)(p
N
k
− p
I
k
)||
2
= ∆
2
k
. (2.9)
Por fim, para voltar ao espac¸o original e calcular uma soluc¸˜ao aproximada p
k
de (2.5),
simplesmente fazemos p
k
= D
−1
k
p
k
. Note que para pequenos valores de ∆
k
, a direc¸˜ao de p
k
´e a
direc¸˜ao de m´axima descida escalada d
k
dada por
d
k
= −D
−2
k
∇f
k
. (2.10)
A discuss˜ao acima leva ao seguinte algoritmo:
Algoritmo 1: M´etodo Dogleg
Entrada: p
N
k
, ∇f
k
, D
k
e ∆
k
se ||D
k
p
N
k
|| ≤ ∆
k
ent
˜
ao1
p
k
= p
N
k
e pare.2
fim3
Calcule p
I
k
usando (2.7).4
se ||p
I
k
|| ≥ ∆
k
ent
˜
ao5
p
k
= ∆
k
D
−1
k
∇f
k
/||D
−1
k
∇f
k
||6
sen
˜
ao7
p
N
k
= D
k
p
N
k
8
Calcule µ resolvendo (2.9) e tome p
k
= p
I
k
+ (1 − µ)(p
N
k
− p
I
k
).9
fim10
Tome p
k
= D
−1
k
p
k
.11
26
Para manter a viabilidade estrita das iterac¸˜oes, s˜ao feitas, quando necess´ario, restric¸˜oes
adequadas sobre a escolha do passo. Assim, o m´etodo pode lidar com problemas em que a
func¸˜ao F n˜ao est´a definida fora de Ω.
A fim de garantir que x
k+1
esteja no interior de Ω, calcula-se o tamanho do passo ao longo
de p
k
at´e a fronteira, isto ´e
λ(p
k
) =
∞, se Ω =
n
;
min
1≤i≤n
Λ
i
(p
k
), se Ω ⊂
n
;
em que
Λ
i
(p
k
) =
max
l
i
−(x
k
)
i
(p
k
)
i
,
u
i
−(x
k
)
i
(p
k
)
i
, se (p
k
)
i
0;
∞, se (p
k
)
i
= 0.
Note que se λ(p
k
) > 1, ent˜ao x
k
+ p
k
est´a no interior de Ω; caso contr´ario, um passo para
tr´as ao longo de p
k
ser´a necess´ario para ficar dentro de Ω.
Basta considerar agora
x
k+1
= x
k
+ α(p
k
),
em que o passo α(p
k
) ´e definido por
α(p
k
) =
p
k
, se λ(p
k
) > 1,
max{θ, 1 −||p
k
||}λ(p
k
)p
k
, caso contr´ario,
(2.11)
e θ ∈ (0, 1) ´e uma constante fixa independente de k.
O objetivo do m´etodo de regi˜ao de confianc¸a ´e obter uma nova aproximac¸˜ao que permanec¸a
no interior da regi˜ao de confianc¸a e que resulte numa boa reduc¸˜ao no modelo. A reduc¸˜ao
suficiente ´e quantificada em termos do minimizador de m
k
ao longo da direc¸˜ao de m´axima
descida d
k
dada por (2.10), sujeito aos limites da regi˜ao de confianc¸a, isto ´e, em termos do
ponto de Cauchy:
27
p
C
k
= τ
k
d
k
= τ
k
D
−2
k
∇f
k
, (2.12)
em que τ
k
= argmin
τ>0
{m
k
(τd
k
) : || τD
k
d
k
|| ≤ ∆
k
} (ver [6]).
Testamos assim, se o passo α(p
k
) satisfaz a seguinte condic¸˜ao:
ρ
c
k
(p
k
) =
m
k
(0) − m
k
(α(p
k
))
m
k
(0) −m
k
(α(p
C
k
))
≥ β
1
, (2.13)
em que β
1
∈ (0, 1) ´e uma constante dada.
A soluc¸˜ao do subproblema de regi˜ao de confianc¸a (2.5), satisfaz (2.13), mas se um passo
para tr´as ao longo de p
k
for necess´ario, isto ´e, se α(p
k
) p
k
, ent˜ao a condic¸˜ao (2.13) n˜ao ´e
necessariamente satisfeita.
Para que exista uma boa concordˆancia entre o modelo m
k
e a func¸˜ao objetivo f, exigimos
que α(p
k
) satisfac¸a a condic¸˜ao padr˜ao:
ρ
f
k
(p
k
) =
f(x
k
) − f(x
k
+ α(p
k
))
m
k
(0) − m
k
(α(p
k
))
≥ β
2
, (2.14)
em que β
2
∈ (0, 1] ´e uma constante dada.
28
As considerac¸˜oes acima nos levam ao seguinte m´etodo:
Algoritmo 2: M´etodo de Regi˜ao de Confianc¸a Escalado
Entrada: x
0
∈ int(Ω), ∆
0
> 0
Escolha θ ∈ (0, 1), β
1
∈ (0, 1], β
2
e β
3
tais que 0 < β
2
< β
3
< 1, δ
1
e δ
2
tais que
0 < δ
1
< 1 < δ
2
.
k = 01
Calcule a matriz D
k
.2
Tome ρ
f
k
(p
k
) = 0.3
enquanto ρ
f
k
(p
k
) < β
2
fac¸a4
Encontre p
k
= argmin
||D
k
p||≤∆
k
m
k
(p).
5
Calcule o ponto de Cauchy p
C
k
usando (2.12).6
Calcule α(p
k
) e α(p
C
k
) usando (2.11).7
Calcule ρ
c
k
(p
k
) usando (2.13).8
se ρ
c
k
(p
k
) ≤ β
1
ent
˜
ao9
p
k
= p
C
k
10
fim11
Tome ∆
∗
k
= ∆
k
e ∆
k
= δ
1
∆
k
.12
Calcule ρ
f
k
(p
k
) usando (2.14).13
fim14
Tome x
k+1
= x
k
+ α(p
k
) e ∆
k
= ∆
∗
k
.15
se ρ
f
k
(p
k
) ≥ β
3
ent
˜
ao16
∆
k+1
= δ
2
∆
k
17
sen
˜
ao18
∆
k+1
= ∆
k
19
fim20
k = k + 121
Como podemos observar na linha 9 do algoritmo, se a condic¸˜ao (2.13) n˜ao ´e v´alida, ou seja,
se o passo encontrado n˜ao ´e t˜ao bom quanto o passo de Cauchy, tomamos p
k
= p
C
k
.
O passo ´e analisado tamb´em pela condic¸˜ao (2.14) e com base nela, na linha 4 ´e que o passo
´e aceito ou rejeitado. Se a condic¸˜ao (2.14) ´e v´alida, a linha 14 ´e finalizada com sucesso e
x
k
+ α(p
k
) ´e a pr´oxima iterac¸˜ao. Caso contr´ario, na linha 12 diminui-se o tamanho da regi˜ao de
confianc¸a, tomando
29
∆
k
= min{α
1
∆
k
, α
2
|| D
k
α(p
k
)||},
para α
1
, α
2
tais que 0 < α
1
≤ α
2
< 1 e um novo passo deve ser calculado na linha 5.
Se o tamanho da regi˜ao de confianc¸a ´e muito pequeno quando comparado com a con-
cordˆancia entre o modelo e a func¸˜ao objetivo, o m´etodo permite, na linha 17, que o tamanho da
regi˜ao de confianc¸a seja aumentado, tomando
∆
k+1
= max{∆
k
, 2||D
k
α(p
k
)||}.
Em cada iterac¸˜ao, resolve-se aumentar ∆
k
se a condic¸˜ao (2.14) ´e satisfeita para uma cons-
tante β
3
∈ (0, 1) tal que β
3
> β
2
.
2.3 An
´
alise de converg
ˆ
encia
As propriedades de convergˆencia do m´etodo descrito na sec¸˜ao anterior foram investigadas
em [1]. Vamos apresentar algumas dessas propriedades.
Sejam {x
k
} a seq¨uˆencia gerada pelo m´etodo proposto, r > 0 e L =
∞
k=0
{x ∈ Ω/||x − x
k
|| ≤ r}.
Suponha que
(H1) F
′
´e Lipschitz cont´ınua em L, com constante de Lipschitz igual a 2γ
L
;
(H2) || F
′
(x)|| ´e limitada superiormente em L.
Para os resultados de convergˆencia do m´etodo, vamos assumir que a seq¨uˆencia {x
k
} ´e limi-
tada. Assim, evitamos as falhas devido `a falta de pontos limite.
Note que se {x
k
} ´e limitada, ent˜ao existe uma constante χ
D
> 0 tal que
|| D
−1
(x)|| < χ
D
, x ∈ L. (2.15)
Ainda, se a hip´otese (H1) ´e satisfeita, F
′
(x)
T
F(x) ´e Lipschitz cont´ınua em L com constante
2γ
L
γ + γ
2
em que γ = max{sup
x∈L
f(x), sup
x∈L
|| F
′
(x)||} e se a hip´otese (H2) ´e satisfeita existe um
escalar positivo χ
g
tal que o gradiente F
′T
k
F
k
da func¸˜ao de m´erito f satisfaz
|| F
′T
k
F
k
||
∞
< χ
g
, (2.16)
30
para todo x ∈ L.
O teorema 2, que ser´a provado por contradic¸˜ao, juntamente com o Lema 1, nos diz que se
a seq¨uˆencia {x
k
} ´e limitada ent˜ao todos os seus pontos limites s˜ao pontos estacion´arios para o
problema min
Ω
f.
Lema 1 [8, Lema 2.1] Seja x
k
∈ Ω. Ent˜ao D
−1
k
F
′T
k
F
k
= 0 se e somente se x
k
´e um ponto
estacion´ario para o problema min
Ω
f.
Prova: Ver [2].
Teorema 2 [1, Teorema 3.1] Suponha que (H1) e (H2) s˜ao satisfeitas. Se {x
k
} ´e limitada, ent˜ao
lim
k→∞
|| D
−1
k
F
′T
k
F
k
|| = 0.
Prova: Pela hip´otese (H2), segue que existe uma constante positiva χ
B
> 0 tal que ||F
′T
k
F
′
k
|| <
χ
B
, ∀x
k
∈ L. Ent˜ao, por [2, Teorema 3.4] temos que
liminf
k→∞
|| D
−1
k
F
′T
k
F
k
|| = 0. (2.17)
De (2.15) e (2.16) existe uma constante χ
f
> 0 tal que
|| D(x)
−1
F
′
(x)
T
F
′
(x)D(x)
−1
|| < χ
f
, x ∈ L.
Sendo pred(p
k
) = m
k
(0) − m
k
(α(p
k
)) e usando [1, Lema 3.3] obtemos
pred(p
k
) ≥
1
2
β
1
|| D
−1
k
F
′T
k
F
k
||min
∆
k
,
|| D
−1
k
F
′T
k
F
k
||
χ
f
,
θ||D
−1
k
F
′T
k
F
k
||
χ
g
,
e (2.14) fornece
f(x
k
) − f(x
k
+ α(p
k
)) ≥ β
2
pred(p
k
)
≥
1
2
β
1
β
2
|| D
−1
k
F
′T
k
F
k
||min
∆
k
,
|| D
−1
k
F
′T
k
F
k
||
χ
f
,
θ||D
−1
k
F
′T
k
F
k
||
χ
g
(2.18)
Agora vamos supor que exista uma seq¨uˆencia {m
i
} tal que ||D
−1
m
i
F
′T
m
i
F
m
i
|| ≥ ε
1
para algum
ε
1
∈ (0, 1). Usando (2.17) podemos afirmar que para qualquer ε
2
∈ (0, ε
1
) existe uma sub-
seq¨uˆencia de {m
i
}, sem perda de generalidade vamos assumir que ´e a seq¨uˆencia inteira, e uma
seq¨uˆencia {l
i
} tal que
31
|| D
−1
k
F
′T
k
F
k
|| ≥ ε
2
, m
i
≤ k < l
i
|| D
−1
l
i
F
′T
l
i
F
l
i
|| < ε
2
. (2.19)
Ent˜ao de (2.18)
f(x
k
) − f(x
k+1
) ≥
1
2
β
1
β
2
ε
2
min
∆
k
,
ε
2
χ
f
,
θε
2
χ
g
, m
i
≤ k < l
i
.
Agora, de (2.15) temos que ||x
k+1
− x
k
|| = ||α(p
k
)|| ≤ ||D
−1
k
||∆
k
≤ χ
D
e a´ı
f(x
k
) − f(x
k+1
) ≥
1
2
β
1
β
2
ε
2
min
||x
k+1
− x
k
||
χ
D
,
ε
2
χ
f
,
θε
2
χ
g
, m
i
≤ k < l
i
. (2.20)
A seq¨uˆencia {f(x
k
)} converge, pois ´e n˜ao-crescente e limitada inferiormente por zero. Por-
tanto, f(x
k
) − f(x
k+1
) tende `a zero.
De (2.20) segue que
f(x
k
) − f(x
k+1
) ≥ ε
3
||x
k+1
− x
k
||, m
i
≤ k < l
i
,
para i suficientemente grande e ε
3
=
1
2
β
1
β
2
ε
2
/χ
D
. Ent˜ao, usando a desigualdade triangular
obtemos
f(x
m
i
) − f(x
k
i
) ≥ ε
3
||x
m
i
− x
k
i
||, m
i
≤ k
i
< l
i
, (2.21)
e podemos concluir que ||x
m
i
− x
k
i
|| tende `a zero. Ainda, pela continuidade Lipschitz de F
′T
F e
do fato que ||x
m
i
− x
k
i
|| tende `a zero, segue que
|| F
′T
m
i
F
m
i
− F
′T
k
i
F
k
i
|| ≤ ε
2
, (2.22)
para i suficientemente grande.
Sem perda de generalidade, assuma que toda a seq¨uˆencia x
l
i
converge para um ponto, diga-
mos x
∗
. De (2.21) temos que {x
m
i
} converge para x
∗
tamb´em.
Se (F
′
(x
∗
)
T
F(x
∗
))
j
0 para algum 1 ≤ j ≤ n, ent˜ao (2.4) implica |(v
m
i
)
j
− (v
l
i
)
j
| ≤ |(x
m
i
)
j
−
(x
l
i
)
j
| para i suficientemente grande. Conseq¨uentemente ||(D
−1
m
i
− D
−1
l
i
)F
′T
l
i
F
l
i
|| → 0 e portanto
||(D
−1
m
i
− D
−1
l
i
)F
′T
l
i
F
l
i
|| ≤ ε
2
, (2.23)
32
para i suficientemente grande. Finalmente, de ||D
−1
m
i
F
′T
m
i
F
m
i
|| ≥ ε
1
, (2.19), (2.22), (2.23) e
|| D
−1
m
i
F
′T
m
i
F
m
i
|| ≤ ||D
−1
m
i
|| · ||F
′T
m
i
F
m
i
− F
′T
l
i
F
l
i
|| + ||(D
−1
m
i
− D
−1
l
i
)F
′T
l
i
F
l
i
|| + ||D
−1
l
i
F
′T
l
i
F
l
i
||,
temos
ε
1
≤ (χ
D
+ 2)ε
2
,
isto ´e, uma contradic¸˜ao desde que ε
2
∈ (0, ε
1
) pode ser arbitrariamente pequeno.
Observe que pode acontecer de nenhum ponto limite de {x
k
} satisfazer F(x) = 0. Neste
caso, a matriz D(x)
−1
F
′
(x)
T
´e singular em cada ponto limite x
∗
. O fato de D(x
∗
)
−1
F
′
(x
∗
)
T
ser
singular ocorre ou se F
′
(x
∗
) ´e singular ou se D(x
∗
)
−1
´e singular. Este ´ultimo caso ocorre quando
x
∗
est´a na fronteira de Ω.
No Teorema 3, encontramos as propriedades de convergˆencia do m´etodo quando {x
k
} tem
pelo menos um ponto de acumulac¸˜ao x
∗
tal que F(x
∗
) = 0 e F
′
(x
∗
) ´e invert´ıvel.
Teorema 3 Suponha que (H1) e (H2) s˜ao satisfeitas. Se {x
k
} ´e limitada e existe um ponto limite
isolado x
∗
tal que F
′
(x
∗
) ´e invert´ıvel e F(x
∗
) = 0, ent˜ao
1. ||F
k
|| → 0 e x
k
→ x
∗
;
2. se o ponto limite x
∗
∈ int(Ω), ent˜ao x
k
→ x
∗
q-quadraticamente.
Prova: Ver [1].
O Teorema 3 diz que se x
∗
´e um ponto limite da seq¨uˆencia {x
k
} e se F
′
(x
∗
) ´e n˜ao-singular,
ent˜ao {x
k
} converge para x
∗
. Al´em disso, quando x
∗
∈ int(Ω) a convergˆencia ´e quadr´atica. Se
n˜ao supormos a posic¸˜ao de x
∗
, as propriedades de convergˆencia local do m´etodo podem ser
vistas no seguinte resultado.
Teorema 4 Sejam {x
k
} a seq¨uˆencia gerada pelo m´etodo proposto, e ζ
k
tal que α(p
N
k
) = ζ
k
p
N
k
.
Suponha que exista uma solu¸c˜ao x
∗
de (2.1) tal que F
′
(x
∗
) ´e n˜ao-singular. Se a seq¨uˆencia {x
k
}
converge para x
∗
e eventualmente p
N
k
resolve (2.5) e satisfaz (2.13) e (2.14), ent˜ao
1. Se ζ
k
´e limitada fora do 0, ||F(x
k
)|| → 0 q-linearmente.
33
2. Se ζ
k
→ 1, ent˜ao x
k
→ x
∗
q-superlinearmente.
3. Se eventualmente ζ
k
= 1, ent˜ao x
k
→ x
∗
q-quadraticamente.
Prova: Ver [1].
Deste resultado podemos observar que a convergˆencia local quadr´atica para uma soluc¸˜ao na
fronteira da caixa n˜ao ´e garantida. Isto deve-se ao fato de que nem sempre o passo de Newton
p
N
k
resolve o subproblema de regi˜ao de confianc¸a (2.5). A exigˆencia da viabilidade estrita das
iterac¸˜oes pode inibir a convergˆencia local r´apida j´a que, eventualmente, se a iterac¸˜ao n˜ao for
vi´avel o escalamento produzir´a um passo α(p
N
k
) = ζ
k
p
N
k
tal que ζ
k
→ 1. Neste caso, a taxa de
convergˆencia ser´a superlinear.
2.4 Resultados num
´
ericos
Nesta sec¸˜ao apresentamos os resultados da implementac¸˜ao computacional do algoritmo
descrito na sec¸˜ao 2.2. O Algoritmo foi implementado utilizando o software Matlab vers˜ao
R2006a, e os parˆametros utilizados foram: θ = 0, 99995, β
1
= 0, 1, β
2
= 0, 25, β
3
= 0, 75,
α
1
= 0, 25 e α
2
= 0, 5.
Foram extra´ıdos 31 problemas testes da p´agina eletrˆonica http://www. polymath-software.
com/library, a qual possui uma s´erie de problemas que permite ao usu´ario comprovar o desem-
penho de seus algoritmos. Todos esses problemas prov´em de modelos matem´aticos relacio-
nados `a fenˆomenos f´ısicos, e, os aqui apresentados possuem de 2 `a 14 vari´aveis. A maioria
dos problemas possuem mais de um ponto inicial. Como o m´etodo exige viabilidade estrita,
foram testados apenas aqueles em que o ponto inicial estivesse no interior da regi˜ao vi´avel Ω,
totalizando assim, 107 testes.
A tabela 1 mostra os resultados dos problemas, em que no modelo quadr´atico (2.2) foi
usado exatamente F
′
(x), ou seja, a direc¸˜ao de Newton. Em comparac¸˜ao com os resultados
apresentados em [9], listamos na tabela 1 o n´umero de testes, NT, o n´umero de testes bem
sucedidos, NS, a m´edia de iterac¸˜oes, MIT e a m´edia de avaliac¸˜oes da func¸˜ao F, MAF, para dois
diferentes valores do raio inicial da regi˜ao de confianc¸a (∆
0
= 1 e ∆
0
= ||D
−1
0
∇f
0
||). Observamos
que dos 107 testes, 74 foram bem sucedidos quando escolhemos o raio da regi˜ao de confianc¸a
igual a 1 e 77 com raio igual a ||D
−1
0
∇f
0
||. O desempenho do m´etodo foi ligeiramente afetado
quando mudamos o raio de regi˜ao de confianc¸a, podemos destacar os problemas: Threeq3,
Threeq5, Threeq6, Sixeq4b, Seveneq1, Teneq1a, 14eq1. Em todos esses problemas o n´umero
34
m´edio de iterac¸˜oes e de avaliac¸˜oes de F foi menor com ∆
0
= ||D
−1
0
∇f
0
||, mas novos testes devem
ser realizados para estabelecer a escolha adequada do raio inicial de regi˜ao de confianc¸a.
O m´etodo n˜ao obteve convergˆencia nos problemas Sixeq1 e Sixeq4a com nenhuma das es-
timativas inicias. Em algumas, o n´umero m´aximo de avaliac¸˜oes da func¸˜ao F foi atingido e em
outras o raio da regi˜ao de confianc¸a tornou-se muito pequeno. Esses problemas s˜ao caracteriza-
dos naquela colec¸˜ao, como problemas de alta dificuldade, o primeiro pode possuir soluc¸˜ao fora
do conjunto vi´avel e a func¸˜ao F do segundo problema possui uma descontinuidade dentro do
conjunto vi´avel.
Tabela 1: Direc¸˜oes obtidas combinadas por Newton.
Raio=1 Raio=||D
−1
0
∇ f
0
||
Problema
NT NS MIT MAF NT NS MIT MAF
Twoeq2 4 2 8 9 4 2 5 6
Twoeq3 5 3 11 12 5 4 8 9
Twoeq4a 3 3 4 5 3 3 5 6
Twoeq4b 3 3 4 5 3 3 6 7
Twoeq5a 4 4 4 5 4 4 5 7
Twoeq5b 4 4 6 7 4 4 8 9
Twoeq6 4 4 9 15 4 4 8 12
Twoeq7 4 4 7 8 4 4 8 10
Twoeq8 4 2 4 5 4 2 4 5
Twoeq9 4 4 307 343 4 4 310 348
Twoeq10 4 4 6 7 4 4 8 10
Threeq1 4 4 21 27 4 4 27 34
Threeq2 4 1 5 6 4 1 5 6
Threeq3 4 4 14 15 4 4 5 6
Threeq4a 4 1 5 6 4 1 5 6
Threeq4b 4 4 7 8 4 4 6 8
Threeq5 4 1 20 28 4 3 6 7
Threeq6 4 4 103 144 4 4 74 109
Threeq8 1 1 6 7 1 1 5 6
Fiveq1 4 2 9 10 4 2 13 14
Sixeq1 4 0 - - 4 0 - -
Sixeq2a 2 1 3 4 2 1 3 4
Sixeq2b 2 1 4 5 2 1 4 5
Sixeq2c 2 1 3 4 2 1 3 4
Sixeq3 4 2 9 11 4 3 7 9
Sixeq4a 3 0 - - 3 0 - -
Sixeq4b 4 3 343 385 4 3 7 8
Seveneq1 3 2 22 31 3 2 12 16
Seveneq2a 3 1 5 6 3 1 4 5
Teneq1a 2 2 13 14 2 2 8 9
14eq1 2 2 10 11 2 1 5 7
Na tabela 2 apresentamos os resultados de mais 6 testes feitos com problemas encontrados
em [10], os problemas possuem de 2 `a 10 vari´aveis.
35
Como podemos ver, o m´etodo obteve convergˆencia para o problema Test1 e para o pro-
blema Test25 a convergˆencia foi obtida somente quando considerado o raio 1, no caso do raio
|| D
−1
0
∇f
0
||, o m´etodo acusou erro 3, o que significa que o tamanho da regi˜ao de confianc¸a tornou-
se muito pequeno. O m´etodo acusou erro 6 no problema Test3 , significando que as iterac¸˜oes se
aproximaram muito da fronteira da caixa e portanto a matriz de escala D n˜ao pode ser calculada.
Tabela 2: Problemas diversos.
Raio=1 Raio=||D
−1
0
∇ f
0
||
Problema
MIT MAF MIT MAF
Test1 14 19 16 26
Test25 11 13 erro 3
Test3 erro 6 erro 6
Test5 n˜ao convergiu 6 7
Test38 n˜ao convergiu n˜ao convergiu
Test110 4 5 3 5
O m´etodo poderia ter acusado 4 outros erros: erro 1, indicando que o n´umero m´aximo de
iterac¸˜oes (1000) foi atingido, erro 2, indicando que o n´umero m´aximo de avaliac¸˜oes da func¸˜ao
F (1000) foi atingido, erro 4, significando que nenhuma melhora para o res´ıduo n˜ao-linear foi
obtida, e, por fim, erro 5, indicando que a norma do gradiente escalado da func¸˜ao de m´erito se
tornou muito pequena.
Nas tabelas 3 e 4 foram feitos testes com os mesmos problemas citados acima, s´o que no
modelo quadr´atico (2.2) ´e usado B
k
em lugar de F
′
(x), em que B
k
´e dada pela matriz de correc¸˜ao
da f´ormula de Broyden (1.6). Usamos como aproximac¸˜ao inicial B
0
para o m´etodo de Broyden
a matriz F
′
(x
0
) calculada por diferenc¸as finitas.
Observamos que em v´arios casos, o m´etodo convergiu para as mesmas soluc¸˜oes obtidas
quando consideramos a direc¸˜ao de Newton. Acreditamos que os casos e que o m´etodo n˜ao
obteve convergˆencia, deva-se ao fato de que a direc¸˜ao obtida pelo m´etodo de Broyden nem
sempre ´e uma direc¸˜ao de descida. Entretanto, estes teste servem para avaliar o comportamento
de um m´etodo Quasenewtoniano padr˜ao com um esquema de regi˜ao de confianc¸a para sistemas
n˜ao-lineares, o que n˜ao vimos at´e agora na literatura. Como obtivemos a convergˆencia para
v´arios casos, n˜ao podemos considerar que o m´etodo n˜ao seja efetivo, dado que seu custo por
iterac¸˜ao ´e muito inferior ao m´etodo de Newton para problemas com muitas vari´aveis, o que
pode torn´a-lo, eventualmente, eficiente do ponto de vista computacional.
36
Tabela 3: Direc¸˜oes obtidas combinadas por Broyden.
Raio=1 Raio=||D
−1
0
∇ f
0
||
Problema
NT NS MIT MAF NT NS MIT MAF
Twoeq2 4 1 11 14 4 1 10 12
Twoeq3 5 2 22 28 5 3 10 12
Twoeq4a 3 3 6 7 3 3 11 8
Twoeq4b 3 2 7 8 3 3 9 10
Twoeq5a 4 4 8 11 4 3 8 9
Twoeq5b 4 2 8 9 4 3 12 14
Twoeq6 4 3 36 56 4 3 39 58
Twoeq7 4 1 8 9 4 1 8 9
Twoeq8 4 1 5 6 4 1 5 6
Twoeq9 4 0 - - 4 0 - -
Twoeq10 4 2 7 8 4 3 10 11
Threeq1 4 0 - - 4 1 24 31
Threeq2 4 1 19 26 4 1 19 26
Threeq3 4 4 15 16 4 4 6 7
Threeq4a 4 1 8 9 4 1 8 9
Threeq4b 4 2 10 12 4 2 10 12
Threeq5 4 0 - - 4 0 - -
Threeq6 4 0 - - 4 1 74 103
Threeq8 1 1 10 11 1 1 8 9
Fiveq1 4 2 42 55 4 2 20 25
Sixeq1 4 0 - - 4 0 - -
Sixeq2a 2 1 7 9 2 1 7 9
Sixeq2b 2 1 11 15 2 1 38 58
Sixeq2c 2 0 - - 2 0 - -
Sixeq3 4 0 - - 4 2 23 28
Sixeq4a 3 0 - - 3 0 - -
Sixeq4b 4 0 - - 4 0 - -
Seven1 3 0 - - 3 0 - -
Seven2a 3 0 - - 3 1 9 10
Teneq1a 2 0 - - 2 0 - -
14eq1 2 1 204 278 2 0 - -
Tabela 4: Problemas diversos.
Raio=1 Raio=||D
−1
0
∇ f
0
||
Problema
MIT MAF MIT MAF
Test1 24 34 28 40
Test25 erro 3 erro 3
Test3 erro 6 erro 6
Test5 n˜ao convergiu erro 3
Test38 erro 3 erro 3
Test110 5 7 5 7
37
3 O Problema de Quadrados M
´
ınimos
N
˜
ao-lineares Restrito via Penalizac¸
˜
ao
Neste cap´ıtulo trataremos de sistemas do tipo (1.1) que n˜ao possuem soluc¸˜ao, ou seja, pro-
blemas em que n˜ao existe x ∈
n
tal que F(x) = 0. Dentre os v´arios problemas pr´aticos
que apresentam este tipo de modelagem, podemos citar o importante problema de encontrar
o m´ınimo corte de carga em um sistema el´etrico, que aparece em sistemas de potˆencia. Este
problema ser´a abordado na sec¸˜ao 3.3.1 deste trabalho.
Embora o sistema n˜ao-linear n˜ao tenha soluc¸˜ao, em muitas aplicac¸˜oes ´e conveniente impor
que algumas equac¸˜oes n˜ao-lineares n˜ao admitam res´ıduo. Desse modo, definindo h :
n
→
m
e c :
n
→
p
, este problema, tema central deste cap´ıtulo, pode ser transformado em um
problema de quadrados m´ınimos n˜ao-lineares restrito:
min
x∈
n
1
2
||h(x)||
2
2
sujeito a c(x) = 0. (3.1)
Neste caso,
F(x) =
h(x)
c(x)
.
Apresentaremos dois m´etodos de resolver (3.1): o primeiro trabalha com as condic¸˜oes de
KKT [6] do problema, e o segundo, descrito na sec¸˜ao 3.2, substitui o problema original restrito
por uma seq¨uˆencia de problemas irrestritos.
3.1 M
´
etodo Newton-Lagrange
Uma forma de resolver (3.1) ´e aplicar o m´etodode Newton para as condic¸˜oesde otimalidade
de KKT do problema.
38
Considerando a func¸˜ao Lagrangeana
L(x, λ) =
1
2
h(x)
T
h(x) − λ
T
c(x)
e A(x) ∈
p×n
como a matriz Jacobiana das restric¸˜oes, ou seja,
A(x)
T
= [∇c
1
(x), ∇c
2
(x), . . . , ∇c
p
(x)],
temos que as condic¸˜oes de primeira ordem para o caso de igualdade restrita formam o seguinte
sistema de n + p equac¸˜oes em n + p inc´ognitas x e λ:
G(x, λ) =
R(x)
T
h(x) − A(x)
T
λ
c(x)
= 0,
em que R(x)
T
= [∇h
1
(x), ∇h
2
(x), . . . , ∇h
m
(x)].
Neste momento temos ent˜ao um sistema de equac¸˜oes n˜ao-lineares dado pelo gradiente do
Lagrangiano. Podemos assim, utilizar o m´etodo de Newton para obter a soluc¸˜ao (x
∗
, λ
∗
).
O Jacobiano de G(x, λ) ´e dado por
W(x, λ) =
R(x)
T
R(x) +
m
i=1
h
i
(x)∇
2
h
i
(x) −
p
i=1
λ
i
∇
2
c
i
(x) −A(x)
T
A(x) 0
.
Na k-´esima iterac¸˜ao do m´etodo de Newton temos que resolver o sistema linear,
W(x
k
, λ
k
)
∆x
k
∆λ
k
=
−R(x
k
)
T
h(x
k
) + A(x
k
)
T
λ
k
−c(x
k
)
. (3.2)
Assim, sendo α
k
a correc¸˜ao do passo de Newton obtido pela busca linear na direc¸˜ao obtida
por (3.2), obtemos,
x
k+1
= x
k
+ α
k
∆x
k
;
λ
k+1
= λ
k
+ α
k
∆λ
k
.
A busca linear ´e um dos poss´ıveis m´etodos de globalizac¸˜ao do m´etodo de Newton. Neste
39
trabalho o parˆametro α
k
´e obtido pela minimizac¸˜ao unidimensional da seguinte func¸˜ao de
m´erito:
M(x, λ) =
1
2
∇L(x, λ)
T
∇L(x, λ).
Como ´e conhecido, o processo de minimizac¸˜ao unidimensional n˜ao deve ser exato e, por-
tanto, v´arias estrat´egias inexatas de busca podem ser empregadas.
3.2 Penalizac¸
˜
ao
Uma importante classe de m´etodos para otimizac¸˜ao restrita procura converter problemas
complexos em uma subseq¨uˆencia de problemas irrestritos. Um importante e bem conhecido
procedimento ´e o chamado m´etodo de penalidade, em que a n˜ao satisfac¸˜ao de uma restric¸˜ao
´e sancionada com o acr´escimo de um parˆametro de penalizac¸˜ao para cada restric¸˜ao na func¸˜ao
objetivo, de maneira que as restric¸˜oes sejam incorporadas na func¸˜ao objetivo a qual queremos
minimizar.
Nesta sec¸˜ao discutiremos a penalidade externa, muitas vezes chamada simplesmente de pe-
nalidade. Na penalidade externa o custo do parˆametro acrescentado na func¸˜ao objetivo aumenta
proporcionalmente `a medida que as restric¸˜oes s˜ao violadas. A soluc¸˜ao de um problema penali-
zado externamente geralmente est´a fora do conjunto vi´avel, mas tende `a viabilidade `a medida
que o parˆametro de penalidade cresce.
O princ´ıpio da penalidade externa ´e a utilizac¸˜ao de uma func¸˜ao cont´ınua que se anula no
conjunto a ser penalizado e ´e positiva fora dele. Assim, definindo Ω
1
= {x ∈
n
; c(x) = 0},
para penalizar o problema (3.1) basta escolher P :
n
−→ , P ∈ C
0
(
n
) tal que
P(x)
= 0, se x ∈ Ω
1
;
> 0, se x Ω
1
.
Dessa maneira, a func¸˜ao objetivo para o problema penalizado P
ρ
(x) associado `a (3.1) ´e
P
ρ
(x) =
1
2
||h(x)||
2
2
+ ρP(x),
em que ρ > 0 ´e o parˆametro de penalidade. Portanto, o problema penalizado associado `a (3.1) ´e
40
min
x∈
n
P
ρ
(x). (3.3)
Note que, uma vez fixado ρ ∈ , a resoluc¸˜ao de (3.3) produz uma soluc¸˜ao x(ρ), que, como
veremos mais adiante, para um aumento gradativo do parˆametro de penalizac¸˜ao ρ e uma escolha
prop´ıcia para P(x), geramos uma seq¨uˆencia que converge para a soluc¸˜ao do problema original
(3.1).
Poder´ıamos considerar as func¸˜oes de penalidade exatas, em que a soluc¸˜ao do problema
penalizado (3.3) ´e exatamente a soluc¸˜ao do problema original (3.1), para um valor finito do
parˆametro de penalizac¸˜ao. A vantagem ´e que com estas func¸˜oes, n˜ao seria preciso resolver uma
seq¨uˆencia infinita de subproblemas.
Entretanto, uma desvantagem ´e que a maioria das func¸˜oes de penalidade exatas s˜ao n˜ao-
diferenci´aveis na soluc¸˜ao. Uma dessas func¸˜oes bem conhecida ´e a baseada na || · ||
1
que para o
conjunto Ω
1
´e da forma
P(x) =
p
i=1
|c
i
(x)| = ||c(x)||
1
. (3.4)
Propriedades de convergˆencia dos subproblemas penalizados associados `a (3.1), para um
parˆametro ρ finito e para a func¸˜ao (3.4) s˜ao citadas em [11]. Dificuldades podem surgir se o
parˆametro ρ n˜ao for escolhido adequadamente, pois a convergˆencia da soluc¸˜ao do subproblema
para a soluc¸˜ao do problema original depende muito da escolha de ρ. Se ρ for muito pequeno,
a func¸˜ao penalizada pode ser inferiormente ilimitada. Por outro lado, se ρ for muito grande,
surgem os problemas de mal condicionamento.
Neste trabalho, vamos considerar a seguinte func¸˜ao de penalidade
P(x) =
p
i=1
c
2
i
(x) = ||c(x)||
2
2
,
tamb´em conhecida como func¸˜ao de penalidade quadr´atica. Assim, dado ρ > 0, definimos
Q
ρ
(x) =
1
2
||h(x)||
2
2
+
ρ
2
||c(x)||
2
2
(3.5)
e resolvemos, para uma seq¨uˆencia {ρ
k
}
k∈
, com ρ
k
→ ∞, o problema irrestrito
41
min
x∈
n
Q
ρ
k
(x).
As considerac¸˜oes acima levam ao seguinte algoritmo
Algoritmo 3: Penalidade Externa
Entrada: ρ
1
≥ 0, x
0
∈
n
, ǫ
0
> 0
k = 11
Calcular x
k
= x(ρ
k
) como soluc¸˜ao aproximada de2
min
x∈
n
Q
ρ
k
(x) (3.6)
e terminar quando ||∇Q
ρ
k
(x)|| ≤ ǫ
k
.3
Escolher ρ
k+1
> ρ
k
4
k = k + 1 e voltar ao passo 2.5
Segundo [11] e [6], os parˆametros de penalizac¸˜ao podem ser atualizados da seguinte forma:
ρ
1
= 1, ρ
k
= 10ρ
k−1
, e ainda aconselha-nos a usar x
k−1
como ponto inicial para resolver o
subproblema (3.6).
Note que, resolver (3.6) equivale a resolver o seguinte problema
min
x∈
n
1
2
h(x)
√
ρ
k
c(x)
2
2
, (3.7)
o qual pode ser resolvido, por exemplo, pelo m´etodo de Levenberg-Marquardt da sec¸˜ao 1.5.
Assim, dado x
k
∈
n
, considere
F
ρ
k
(x
k
) =
h(x
k
)
√
ρ
k
c(x
k
)
e defina J
ρ
k
(x
k
) o Jacobiano de F
ρ
k
em x
k
. Portanto, um passo do m´etodo Levenberg-Marquardt
a partir de x
k
para o problema (3.7) consiste em resolver o sistema linear
(J
ρ
k
(x
k
)
T
J
ρ
k
(x
k
) + η
k
I)p
k
= −J
ρ
k
(x
k
)
T
F
ρ
k
(x
k
), (3.8)
para algum η
k
> 0 devidamente escolhido, chamado neste trabalho de parˆametro de Levenberg-
Marquardt.
42
Note que resolver o sistema (3.8) ´e equivalente a resolver o subproblema
min
p∈
n
||J
ρ
k
(x
k
)p + F
ρ
k
(x
k
)||
2
2
+ η
k
||p||
2
2
,
ou ainda,
min
p∈
n
J
ρ
k
(x
k
)
√
η
k
I
p +
F
ρ
k
(x
k
)
0
2
2
(3.9)
que ´e um problema de quadrados m´ınimos linear.
Uma outra alternativa para resolver o problema (3.7) ´e usar um m´etodo diretamente para
F
ρ
k
(x) = 0, por exemplo o m´etodo de Newton. Esta estrat´egia ser´a empregada nos testes
num´ericos.
3.2.1 An
´
alise de converg
ˆ
encia
Para a an´alise de convergˆencia do m´etodo de penalidade quadr´atica vamos definir f(x) =
1
2
||h(x)||
2
2
em (3.5).
Teorema 5 [6, pag. 496] Suponha que cada x
k
´e o minimizador global de Q
ρ
k
(x) no Algoritmo
3 e que ρ
k
→ ∞. Ent˜ao todo ponto limite x
∗
da seq¨uˆencia {x
k
} ´e uma solu¸c˜ao do problema (3.1).
Prova: Seja x uma soluc¸˜ao global de (3.1), isto ´e
f(x) ≤ f(x), para todo x com c
i
(x) = 0, i ∈ E,
em que E representa um conjunto finito de ´ındices e [c
i
(x)]
i∈E
= c(x).
Como x
k
minimiza Q
ρ
k
(·) para cada k, n´os temos que Q
ρ
k
(x
k
) ≤ Q
ρ
k
(x), assim obtemos a
desigualdade
f(x
k
) +
ρ
k
2
i∈E
c
2
i
(x
k
) ≤ f(x) +
ρ
k
2
i∈E
c
2
i
(x) = f(x). (3.10)
Organizando a equac¸˜ao obtemos
i∈E
c
2
i
(x
k
) ≤ 2
[f(x) − f(x
k
)]
ρ
k
. (3.11)
43
Suponha que x
∗
´e um ponto limite de {x
k
}, de modo que exista uma subseq¨uˆencia K tal que
lim
k∈K
x
k
= x
∗
.
Tomando o limite com k → ∞, k ∈ K, em ambos os lados de (3.11), n´os obtemos
i∈E
c
2
i
(x
∗
) = lim
k∈K
i∈E
c
2
i
(x
k
) ≤ lim
k∈K
2
[f(x) − f(x
k
)]
ρ
k
= 0,
em que a ´ultima desigualdade segue de ρ
k
→ ∞. Agora, x
∗
´e vi´avel, pois c
i
(x
∗
) = 0 para todo
i ∈ E. Al´em disso, tomando o limite com k → ∞, k ∈ K em (3.10), temos pela n˜ao-negatividade
de ρ
k
e de cada c
2
i
(x
k
) que
f(x
∗
) ≤ f(x
∗
) + lim
k∈K
ρ
k
2
i∈E
c
2
i
(x
k
) ≤ f(x),
Como x
∗
´e um ponto vi´avel e f(x
∗
) ≤ f(x), conclu´ımos que x
∗
´e tamb´em um minimizador
global.
Para que um ponto limite da seq¨uˆencia x
k
seja soluc¸˜ao do problema (3.1), o teorema apre-
sentado acima exige que resolvamos o passo 2 do Algoritmo 3 exatamente. Como nem sempre
isso ´e poss´ıvel, o pr´oximo teorema apresenta-nos propriedades de convergˆencia da seq¨uencia x
k
quando diminu´ımos a tolerˆancia, ou seja, quando permitimos a minimizac¸˜ao inexata de Q
ρ
k
.
Teorema 6 [6, pag. 497] Se a tolerˆancia ǫ
k
no Algoritmo 3 satisfaz
lim
k→∞
ǫ
k
= 0
e o parˆametro de penalidade satisfaz ρ
k
→ ∞, ent˜ao para todos os pontos limites x
∗
da
seq¨uˆencia {x
k
} no qual os gradientes das restri¸c˜oes ∇c
i
(x
∗
) s˜ao linearmente independentes, te-
mos que x
∗
´e um ponto KKT para o problema (3.1). Al´em disso para uma subseq¨uˆencia infinita
K tal que lim
k∈K
x
k
= x
∗
temos que
lim
k∈K
−ρ
k
c
i
(x
k
) = λ
∗
i
, para todo i ∈ E,
em que λ
∗
´e o vetor contendo os multiplicadores de Lagrange que satisfaz as condi¸c˜oes KKT.
Prova: Diferenciando Q
ρ
k
(x), obtemos
44
∇Q
ρ
k
(x
k
) = ∇f(x
k
) +
i∈E
ρ
k
c
i
(x
k
)∇c
i
(x
k
).
Aplicando o crit´erio de parada do Algoritmo 3, temos que
∇f(x
k
) +
i∈E
ρ
k
c
i
(x
k
)∇c
i
(x
k
)
≤ ǫ
k
. (3.12)
Reagrupando esta express˜ao (em particular usando a desigualdade ||a|| − ||b|| ≤ ||a + b||),
obtemos
i∈E
c
i
(x
k
)∇c
i
(x
k
)
≤
1
ρ
k
[ǫ
k
+ ||∇f(x
k
)||]. (3.13)
Quando tomamos o limite com k → ∞ para k ∈ K o termo entre colchetes do lado direito
tende `a ||∇f(x
∗
)|| e, como ρ
k
→ ∞, o lado direito tende a zero. Assim, tomando o limite k → ∞
em (3.13), obtemos
i∈E
c
i
(x
∗
)∇c
i
(x
∗
) = 0.
Como por hip´otese os gradientes das restric¸˜oes ∇c
i
(x
∗
) s˜ao linearmente independentes, te-
mos que c
i
(x
∗
) = 0 para todo i ∈ E e portanto x
∗
´e vi´avel.
Usando A(x) para denotar a matriz dos gradientes das restric¸˜oes, isto ´e,
A(x)
T
= [∇c
i
(x)]
i∈E
,
e λ
k
para denotar o vetor −ρ
k
c(x
k
), temos como em (3.12) que
A(x
k
)
T
λ
k
= ∇f(x
k
) −∇Q
ρ
k
(x
k
), ||∇Q
ρ
k
(x
k
)|| ≤ ǫ
k
.
Para todo k ∈ K suficientemente grande, a matriz A(x
k
) tem posto completo, e portanto
A(x
k
)A(x
k
)
T
´e n˜ao-singular. Multiplicandoa ´ultima express˜ao por A(x
k
) e reagrupando os termos
obtemos
λ
k
= [A(x
k
)A(x
k
)
T
]
−1
A(x
k
)[∇f(x
k
) − ∇Q
ρ
k
(x
k
)].
45
Assim, tomando o limite quando k
k∈K
−−−→ ∞, encontramos
lim
k∈K
λ
k
= λ
∗
= [A(x
∗
)A(x
∗
)
T
]
−1
A(x
∗
)∇f(x
∗
).
Tomando o limite em (3.12), conclu´ımos que
∇f(x
∗
) − A(x
∗
)
T
λ
∗
= 0
Assim, x
∗
´e um ponto KKT, com um ´unico vetor multiplicador de Lagrange.
Com isso, usando os teoremas anteriores garantimosconvergˆencia para pontosestacion´arios
do problema (3.1), desde que para um dado parˆametro de penalidade ρ
k
sejam encontrados
pontos estacion´arios do subproblema irrestrito (3.7).
3.3 Resultados num
´
ericos
O m´etodo de penalizac¸˜ao descrito na sec¸˜ao 3.2 e o m´etodo Newton-Lagrange, da sec¸˜ao
3.1 ser˜ao agora aplicados ao problema de fluxo de carga em redes de energia el´etrica [12] e
`a problemas diversos da literatura encontrados em [10] e [13]. Daremos nessa primeira sec¸˜ao
uma breve explicac¸˜ao sobre a formulac¸˜ao do problema de fluxo de carga.
3.3.1 Fluxo de pot
ˆ
encia
O c´alculo de fluxo de potˆencia (ou fluxo de carga) em uma rede de energia el´etrica consiste,
essencialmente, na determinac¸˜ao do estado da rede, da distribuic¸˜ao dos fluxos e de outras gran-
dezas de interesse. Nesse tipo de problema, a rede ´e representada por um conjunto de equac¸˜oes
e inequac¸˜oes alg´ebricas.
Classificamos dois grupos que comp˜oem um sistema de energia el´etrica: as barras, que
compreendem os geradores, cargas, reatores e capacitores, e os circuitos, que compreendem as
linhas de transmiss˜ao, transformadores e defasadores (elementos que interligam as barras).
As equac¸˜oes alg´ebricas b´asicas do fluxo de carga s˜ao obtidas impondo-se a conservac¸˜ao das
potˆencias ativa e reativa em cada n´o da rede, ou seja, a potˆencia l´ıquida injetada deve ser igual
a soma das potˆencias que fluem pelos componentes internos das barras.
A cada barra s˜ao definidas 4 vari´aveis correspondentes `a tens˜ao nodal e `a injec¸˜ao de potˆen-
46
cia na barra:
• V
k
- magnitude da tens˜ao nodal;
• θ
k
- ˆangulo da tens˜ao nodal;
• P
k
- injec¸˜ao l´ıquida de potˆencia ativa;
• Q
k
- injec¸˜ao l´ıquida de potˆencia reativa.
Duas dessas vari´aveis s˜ao dados do problema e as duas outras devem ser calculadas. De-
pendendo de quais s˜ao dadas e quais s˜ao inc´ognitas, definem-se trˆes tipos b´asicos de barras:
Tabela 5: Tipos de barras.
Tipo Dados Inc
´
ognitas Caracter
´
ısticas
PQ P
k
, Q
k
V
k
, θ
k
Representam as barras de carga
PV P
k
, V
k
Q
k
, θ
k
Representam as barras de gerac¸˜ao
Folga V
k
, θ
k
P
k
, Q
k
Fornecem a referˆencia angular e fecham o
balanc¸o de potˆencia do sistema
O conjunto de equac¸˜oes do problema do fluxo de carga ´e formado por duas equac¸˜oes para
cada barra
P
k
=
m∈Ω
k
P
km
(V
k
, V
m
, θ
k
, θ
m
) e Q
k
=
m∈Ω
k
Q
km
(V
k
, V
m
, θ
k
, θ
m
)
em que k = 1, . . . nb, sendo nb o n´umero de barras e Ω
k
´e o conjunto de barras vizinhas `a barra
k (duas barras s˜ao vizinhas quando existe um circuito interligando-as).
Seja I
km
a corrente em uma linha de transmiss˜ao (que liga a barra k `a barra m). A injec¸˜ao
l´ıquida de corrente na barra k ´e obtida aplicando-se a primeira lei de Kirchhoff:
I
k
+ I
sh
k
=
m∈Ω
k
I
km
, k = 1, . . . , nb.
Esta express˜ao, utilizando as equac¸˜oes nodais da rede el´etrica, pode ser escrita na seguinte
forma matricial:
I = YE,
47
em que I ´e o vetor das injec¸˜oes de corrente, cujas componentes s˜ao I
k
, k = 1, . . . , nb; o vetor
E representa as tens˜oes nodais cujas componentes s˜ao E
k
= V
k
e
jθ
k
e a matriz Y = G + jB
´e denominada matriz de admitˆancia nodal, sendo G a matriz de condutˆancia e B a matriz de
susceptˆancia. Os elementos da matriz Y s˜ao obtidos da seguinte maneira:
Y
km
= −y
km
e Y
kk
= jb
sh
k
+
m∈Ω
k
(jb
sh
km
+ y
km
),
em que b
sh
k
corresponde `a susceptˆancia de equipamentos reativos conectados `a barra k, b
sh
km
´e a
metade da susceptˆancia shunt do circuito conectando as barras k e m; e y
km
´e a admitˆancia s´erie
do circuito conectando as barras k e m. Vale a pena observar que, em geral, a matriz ´e esparsa,
pois Y
km
= 0 sempre que entre as barras k e m n˜ao existirem circuitos conectando-as.
As equac¸˜oes de potˆencia ativa e reativa s˜ao deduzidas aplicando as leis de Kirchhoff, e s˜ao
dadas por:
P
cal
k
= G
kk
V
2
k
+ V
k
m∈Ω
k
V
m
[G
km
cos(θ
k
− θ
m
) + B
km
sen(θ
k
− θ
m
)] (3.14)
Q
cal
k
= −B
kk
V
2
k
+ V
k
m∈Ω
k
V
m
[G
km
cos(θ
k
− θ
m
) + B
km
sen(θ
k
− θ
m
)] (3.15)
em que k = 1, . . . , nb e Ω
k
´e o conjunto de ´ındices das barras vizinhas `a barra k, excluindo a
pr´opria barra k.
3.3.1.1 Modelagem do problema
As equac¸˜oes b´asicas dofluxo de carga representadas por (3.14) e (3.15), formam um sistema
de 2nb equac¸˜oes com 4nb inc´ognitas, com as seguintes caracter´ısticas:
• nb equac¸˜oes do tipo (3.14);
• nb equac¸˜oes do tipo (3.15);
• 4nb vari´aveis (para cada barra k associam-se V
k
, θ
k
, P
k
, Q
k
).
O fluxo de carga b´asico em redes de energia consiste em resolver este problema definindo
parte das vari´aveis (2nb vari´aveis) e calculando as demais. Consideremos o problema em que
s˜ao dados P
k
e Q
k
para as barras PQ, P
k
e V
k
para as barras PV e V
k
e θ
k
para a barra Vθ (folga)
48
e pede-se para calcular V
k
e θ
k
nas barras PQ, θ
k
nas barras PV e P
k
e Q
k
na barra de folga
(consideramos apenas uma barra de folga).
Sejam npq e npv, respectivamente, o n´umero de barras PQ e PV da rede. Podemos decom-
por o problema descrito acima, em dois subsistemas de equac¸˜oes alg´ebricas:
Subsistema 1: Neste subproblema s˜ao dados P
k
e Q
k
nas barras PQ e P
k
e V
k
nas barras PV.
Pretende-se calcular V
k
e θ
k
nas barras PQ e θ
k
nas barras PV, ou seja, trata-se de um sistema
de (2npq + npv) equac¸˜oes alg´ebricas n˜ao-lineares com o mesmo n´umero de inc´ognitas:
P
dado
k
− P
cal
k
= 0 para as barras PQ e PV;
Q
dado
k
− Q
cal
k
= 0 para as barras PQ.
Resolvido o Subsistema 1 ser´a conhecido o estado (V
k
,θ
k
) para todas as barras da rede.
Subsistema 2: Conhecidos (V
k
,θ
k
), deseja-se calcular P
k
e Q
k
na barra de folga, e Q
k
nas barras
PV. Trata-se de um sistema com npv+2 equac¸˜oes alg´ebricas n˜ao-lineares com o mesmo n´umero
de inc´ognitas.
As inc´ognitas do Subsistema 1 podem ser agrupadas no vetor x dado a seguir:
x =
V
θ
em que V ´e o vetor de magnitude das tens˜oes das barras PQ e θ ´e o vetor dos ˆangulos das
tens˜oes das barras PQ e PV. As express˜oes que formam o Subsistema 1, podem ser reescritas
do seguinte modo:
∆P
k
= P
dado
k
− P
cal
k
= 0 para as barras PQ e PV;
∆Q
k
= Q
dado
k
− Q
cal
k
= 0 para as barras PQ.
em que ∆P
k
e ∆Q
k
s˜ao respectivamente os balanc¸os de potˆencia ativa e reativa na barra k.
As func¸˜oes ∆P
k
e ∆Q
k
podem ser colocadas na forma vetorial
∆P = P
dado
− P
cal
(V, θ)
∆Q = Q
dado
− Q
cal
(V, θ)
em que P
cal
(V, θ) ´e o vetor das injec¸˜oes de potˆencia ativa nas barras PQ e PV, e Q
cal
(V, θ) o das
injec¸˜oes de potˆencia reativa nas barras PQ.
49
Considerando a func¸˜ao vetorial dada por
F(x) =
∆P
∆Q
o Subsistema 1 pode ser colocado na forma
F(x) = 0.
3.3.1.2 O problema sem soluc¸
˜
ao
Pode-se dividir o estado da rede em trˆes n´ıveis: regi˜ao de operac¸˜ao, regi˜ao de emergˆencia e
regi˜ao sem soluc¸˜ao real.
A regi˜ao de operac¸˜ao caracteriza-se por apresentar pontos em que as equac¸˜oes est´aticas do
fluxo de carga possuem soluc¸˜ao real F(x) = 0 e n˜ao h´a violac¸˜ao dos limites operacionais.
´
E
nessa regi˜ao que se deseja que os sistemas de energia el´etrica operem.
Na regi˜ao de emergˆencia, as equac¸˜oes est´aticas do fluxo de carga apresentam soluc¸˜ao real,
por´em com violac¸˜oes de um ou mais limites operacionais. A princ´ıpio, ´e poss´ıvel operar nesta
regi˜ao por um intervalo de tempo limitado, mas o importante ´e, a partir de um ponto de operac¸˜ao
nessa regi˜ao, utilizar mecanismos que possibilitem a migrac¸˜ao desse ponto para a regi˜ao de
operac¸˜ao.
A regi˜ao sem soluc¸˜ao ´e aquela onde as equac¸˜oes est´aticas do fluxo de carga n˜ao apresentam
soluc¸˜ao real. Qualquer tentativa de operar no sistema nesta regi˜ao pode causar instabilidade na
tens˜ao e at´e mesmo o colapso da tens˜ao. Esse fenˆomeno pode ser observado em duas situac¸˜oes:
quando o sistema el´etrico torna-se carregado devido ao aumento de demanda e/ou quando o
sistema sofre uma contingˆencia severa.
Vamos utilizar-nos do procedimento de penalizac¸˜ao para resolver o problema de fluxo de
carga, visando encontrar a partir de um ponto na regi˜ao sem soluc¸˜ao, um ponto na regi˜ao de
emergˆencia. Ser´a considerada a existˆencia de barras de injec¸˜ao nula, nas quais n˜ao pode haver
res´ıduos de potˆencias. Assim, ao transformar uma barra PV (digamos a barra k) em uma barra
PQ, exige-se que ∆P
k
= 0 e ∆Q
k
= 0, ou seja, nessa barra n˜ao pode haver res´ıduos de potˆencias
ativa e reativa. Isto significa que as barras PV transformadas em PQ passam a ser tratadas como
barras de injec¸˜ao nula.
Como em [14] vamos considerar o seguinte problema
50
min
x∈
n
1
2
||h(x)||
2
2
s.a c(x) = 0
sendo que no vetor c(x) :
n
→
p
est˜ao contidas as equac¸˜oes dos balanc¸os de potˆencias
(∆P, ∆Q) para as barras de injec¸˜ao nula, e em h(x) est˜ao as demais equac¸˜oes de F(x). O valor
de p depende do sistema el´etrico em quest˜ao, sendo que em problemas reais, p encontra-se
entre 10% a 15% do n´umero de barras.
Obtemos ent˜ao um problema na forma de (3.1), que ser´a resolvido atrav´es da teoria descrita
nas sec¸˜oes anteriores.
3.3.1.3 Resultados
Os m´etodosNewton-Lagrangee de Penalizac¸˜ao foram implementadosutilizando o software
Matlab vers˜ao R2006a. Fizemos os testes para o problema de fluxo de potˆencia em que as
estimativas iniciais utilizadas foram V
0
= [1; 1; . . . ;1], θ
0
= [0; 0; . . . ;0]. Para o m´etodo de
penalidade ρ
1
= 1 e ρ
k+1
= 10 · ρ
k
e para o m´etodo de Newton-Lagrange λ
0
= [0;0;. . . ; 0].
Os resultados referente ao m´etodo Newton-Lagrangeano para os sistemas de 6, 30 e 57
barras s˜ao apresentados nas tabelas 6, 7 e 8 respectivamente, que mostram a evoluc¸˜ao da con-
vergˆencia do gradiente do Lagrangeano em cada iterac¸˜ao.
Tabela 6: Sistema de 6 barras
Iterac¸˜ao Grad. do Lagrangeano
1 4.7098e+00
2 1.3514e+00
3 3.0659e-01
4 1.1519e-01
5 2.7824e-02
6 1.5370e-03
7 5.3066e-06
Tabela 7: Sistema de 30 barras
Iterac¸˜ao Grad. do Lagrangeano
1 1.0494e+01
2 1.0141e+00
3 3.4897e-01
4 1.1138e-01
5 2.9974e-02
6 5.6653e-03
7 1.1400e-03
8 6.4668e-05
51
Tabela 8: Sistema de 57 barras
Iterac¸˜ao Grad. do Lagrangeano
1 2.1407e+02
2 7.5749e+01
3 1.9875e+01
4 1.3723e+01
5 7.4064e+00
6 4.5129e+00
7 2.4919e+00
8 1.3279e+00
9 5.9365e-01
10 6.9662e-01
11 2.2048e-01
12 3.0670e-02
13 1.6098e-02
14 7.8667e-03
15 2.3935e-03
16 2.6047e-04
Podemos observar que o processo de convergˆencia fica gradativamente mais lento a medida
que a dimens˜ao aumenta (7 iterac¸˜oes em 6 barras e 16 iterac¸˜oes em 57 barras).
Um fato relevante a ser destacado ´e que, para as dimens˜oes acima reportadas, o m´etodo de
Newton n˜ao exigiu o procedimento de busca, ou seja, α
k
= 1 em todas as iterac¸˜oes. Isto geral-
mente n˜ao ocorre com dimens˜oes maiores, em que o procedimento de busca ´e freq¨uentemente
requisitado para obter um decr´escimo suficiente.
Apesar do passo completo de Newton ser aceito, esperar-se-ia que o processo de con-
vergˆencia apresentasse ordem quadr´atica [5]. Este fato tem repercuss˜oes tanto te´oricas quanto
pr´aticas. Do ponto de vista te´orico, este comportamento linear da convergˆencia do m´etodo
de Newton nos leva a supor que a Hessiana do Lagrangiano ´e singular na soluc¸˜ao. Este fato
tamb´em nos conduz a cogitar como estaria se comportando o ˆangulo das direc¸˜oes de Newton
com o gradiente do Lagrangiano, dado que o avanc¸o em cada iterac¸˜ao ´e relativamente pequeno.
Do ponto de vista pr´atico, as observac¸˜oes acima induzem a um estudo num´erico e tamb´em
da estrutura do problema. Na pr´atica, pelo comportamento dos resultados, devemos verificar
um mau condicionamento da matriz Jacobiana, em paralelo `a sua singularidade te´orica.
O emprego de um m´etodo iterativo linear, considerando futuras abordagens ao problema
com dimens˜ao maior, poderia ser aconselh´avel. Entretanto, os resultados acima mostram, em
princ´ıpio, que esta estrat´egia pode apresentar resultados indesej´aveis, j´a que um precondicio-
nador baseado numa fatorac¸˜ao incompleta de uma matriz mal condicionada dificilmente apre-
sentar´a bons resultados. Uma observac¸˜ao na estrutura da matriz ´e necess´aria para afirmar com
52
mais clareza sobre usar ou n˜ao os m´etodos iterativos.
Os mesmos 3 sistemas foram testados com o m´etodo de penalizac¸˜ao. A tentativa de re-
solver F
ρ
k
(x) = 0 pelo m´etodo de Newton puro gerou um mal condicionamento no Jacobiano
do sistema. Este fato parece ter uma relac¸˜ao com a convergˆencia linear obtida pelo m´etodo
Newton-Lagrange. Assim, resolvemos o problema (3.7) pelo m´etodo de Levenberg-Marquardt
da sec¸˜ao 1.5.2 com a atualizac¸˜ao η
k
= ||F
ρ
k
||
2
2
e utilizando a func¸˜ao \ do Matlab para o pro-
blema (3.9). No problema do fluxo de potˆencia, o subsistema 1 possui a mesma quantidade de
inc´ognitas e de equac¸˜oes, desta forma a func¸˜ao \ do Matlab resolver´a o problema (3.9) atrav´es
da eliminac¸˜ao gaussiana.
O n´umero de iterac¸˜oes referente ao m´etodo de penalizac¸˜ao descrito na tabela 9 refere-se `a
soma do n´umero de iterac¸˜oes para resolver (3.9) para cada k.
Tabela 9: N´umero de iterac¸˜oes.
Iterac¸˜oes
Problema
Penalizac¸˜ao Newton-Lagrange
sistema de 6 barras 17 7
sistema de 30 barras 20 8
sistema de 57 barras 41 16
Quando utilizamos o m´etodo de penalizac¸˜ao, precisamos resolver v´arios problemas do tipo
(3.9) de dimens˜ao n (n colunas), enquanto que na utilizac¸˜ao do m´etodo Newton-Lagrange o
sistema (3.2) tem dimens˜ao n + p. A tabela 10 apresenta as dimens˜oes dos sistemas de cada
m´etodo, relacionados aos problemas de 6, 30 e 57 barras. Podemos observar, conforme a tabela
9, que apesar de o m´etodo de penalizac¸˜ao levar mais iterac¸˜oes para alcanc¸ar a soluc¸˜ao, os
sistemas relacionados ao m´etodo s˜ao menores. Al´em disso, os sistemas relacionados ao m´etodo
de penalizac¸˜ao trabalham apenas com o Jacobiano da func¸˜ao F
ρ
k
, enquanto que os relacionados
ao m´etodo Newton-Lagrange utilizam a Hessiana da func¸˜ao f e o Jacobiano das restric¸˜oes.
Tabela 10: Dimens˜oes dos sistemas.
Problema Penalizac¸˜ao Newton-Lagrange
sistema de 6 barras 9 11
sistema de 30 barras 53 65
sistema de 57 barras 106 138
3.3.2 Outras aplicac¸
˜
oes
Para analisar o desempenho do m´etodo de penalizac¸˜ao, outros testes foram feitos com pro-
blemas de [10] e [13]. O m´etodo convergiu para a soluc¸˜ao em 13 problemas dos 17 testados.
53
Nesses testes o problema (3.7) foi resolvido atrav´es do m´etodo de Newton puro para siste-
mas n˜ao-lineares, ou seja, para cada ρ
k
encontramos a soluc¸˜ao de
F
ρ
k
(x) = 0. (3.16)
Ao resolver o problema (3.16), se atingirmos o n´umero m´aximo de iterac¸˜oes, ou seja, se
o crit´erio de convergˆencia n˜ao for satisfeito, o valor obtido como ponto inicial para a iterac¸˜ao
seguintedo Algoritmo 3 pode n˜ao ser um valorsatisfat´orio. Acreditamos que o mal desempenho
do m´etodo nos problemas Test27, Test42 e Test316 se deva ao fato de usarmos o m´etodo de
Newton puro, pois, para todo ρ
k
, ao resolvermos o sistema (3.16) atingimos o n´umero m´aximo
de iterac¸˜oes. Isso indica que um algoritmo mais adequado deve ser usado na resoluc¸˜ao dos
subproblemas (3.7).
Problema Resultado
Test26 n˜ao convergiu
Test27 n˜ao convergiu
Test28 convergiu
Test42 n˜ao convergiu
Test48 convergiu
Test49 convergiu
Test50 convergiu
Test51 convergiu
Test52 convergiu
Test77 convergiu
Test79 convergiu
Test216 convergiu
Test269 convergiu
Test316 n˜ao convergiu
Test344 convergiu
Test345 convergiu
Test373 convergiu
54
Conclus
˜
ao
Neste trabalho estudamos e implementamos m´etodos alternativos para resoluc¸˜ao de alguns
sistemas n˜ao-lineares especiais.
Os sistemas n˜ao-lineares com restric¸˜oes de caixas, foram abordados com t´ecnicas de regi˜ao
de confianc¸a adequadas `as restric¸˜oes seguindo as linhas gerais de [1]. Implementamos o m´etodo
dogleg com combinac¸˜oes de direc¸˜oes de Cauchy-Newton e Cauchy-Broyden. Este estudo
nos facilitou a compreens˜ao da importˆancia do escalamento das regi˜oes de confianc¸a para as
restric¸˜oes de caixa, assim como a robustez da direc¸˜ao de Newton para o bom desempenho
do m´etodo. Ressaltamos que o m´etodo Broyden por ter obtido a convergˆencia para a mesma
soluc¸˜ao de Newton para v´arios problemas, pode ser uma alternativa para sistemas grandes, em
que o custo do c´alculo da direc¸˜ao ´e essencial. Uma alternativa para estes casos seria o m´etodo
de regi˜ao de confianc¸a do gradiente conjugado de Steihaug [6]. Nele a direc¸˜ao inicial de Cauchy
vai sendo atualizada passo a passo pelas f´ormulas CG, parando em geral muito antes do passo
final, que seria Newton.
Os problemas de quadrados m´ınimos n˜ao-lineares s˜ao muito representativos. O caso das
equac¸˜oes da rede el´etrica ´e um modelo relevante em engenharia. Neste caso, apresentamos este
modelo com detalhes como parte do nosso estudo. O problema cl´assico nessa aplicac¸˜ao t´ıpica
´e o caso particular denominado Fluxo de Potˆencias, em que o modelo ´e um sistema n˜ao-linear
usual. A opc¸˜ao de incorporar equac¸˜oes que n˜ao apresentam zeros permite tornar o modelo
mais representativo em termos da engenharia el´etrica. Para estes problemas apresentamos uma
id´eia nova: resolvˆe-lo usando a estrutura mais pr´oxima poss´ıvel do sistema n˜ao-linear associ-
ado. Mais precisamente, ao inv´es do sistema n˜ao-linear com penalizac¸˜ao diretamente, usamos
o m´etodo de Levenberg-Marquardt. Esta ´e uma alternativa interessante ao m´etodo do Lagran-
geano que usa sistemas lineares maiores al´em de informac¸˜oes de segunda ordem. Embora
tenhamos verificado que o n´umero de iterac¸˜oes lineares aumenta, o importante aqui ´e ressaltar a
convergˆencia do m´etodo `a mesma soluc¸˜ao. Isso nos permite cogitar futuras pesquisas usando es-
tas id´eias com um conjunto de testes mais representativos. Em alguns testes menores, extra´ıdos
de [10] e [13], verificamos que trabalhar com o sistema n˜ao-linear penalizado diretamente re-
sulta em convergˆencia `a mesma soluc¸˜ao da formulac¸˜ao de quadrados m´ınimos. Finalmente
ressaltamos que o contexto deste trabalho foi empregar m´etodos num´ericos baseados em mo-
55
delos mais simples para modelos mais elaborados. Este estudo, assim como a implementac¸˜ao
computacional nos permitiram aprender conceitos b´asicos por´em fundamentais em otimizac¸˜ao
num´erica.
56
Refer
ˆ
encias
[1] BELLAVIA, S.; MACCONI, M.; MORINI, B. An affine scaling trust-region approach to
bound-constrained nonlinear systems. Applied Numerical Mathematics, v. 44, p. 257–280,
2003.
[2] COLEMAN, T. F.; LI, Y. An interior trust region approach for nonlinear minimization
subject to bounds. SIAM Journal on Optimization, v. 6, p. 418–445, 1996.
[3] CONN, A. R.; GOULD, N. I. M.; TOINT, P. L. Trust-region methods. Philadelphia: Society
for Industrial and Applied Mathematics, 2000. 959 p. (MPS-SIAM series on optimization).
ISBN 0-89871-460-5.
[4] BARBOZA, L. V. An´alise do M´aximo Carregamento de Sistemas de Potˆencia via M´etodos
de Pontos Interiores. 208 f. Dissertac¸˜ao (P´os-Graduac¸˜ao em Engenharia El´etrica) — Univer-
sidade Federal de Santa Catarina, Santa Catarina, 1997.
[5] DENNIS JR., J. E.; SCHNABEL, R. B. Numerical methods for unconstrained optimiza-
tion and nonlinear equations. Philadelphia: Society for Industrial and Applied Mathematics,
1996. 378 p. (Classics in applied mathematics, 16). ISBN 0-89871-364-1.
[6] NOCEDAL, J.; WRIGHT, S. J. Numerical optimization. New York: Springer-Verlag New
York, Inc., 1999. 636 p. (Springer Series in Operations Research). ISBN 0-387-98793-2.
[7] GILL, P. E.; MURRAY, W.; WRIGHT, M. H. Practical optimization. London: Academic
Press, 1981. 401 p. ISBN 0-12-283952-8.
[8] FRANCISCO, J. B.; KREJI
´
C, N.; MART
´
INEZ, J. M. An interior-point method for solving
box-constrained underdetermined nonlinear systems. Journal of Computational and Applied
Mathematics, v. 177, p. 67–88, 2005.
[9] BELLAVIA, S.; MACCONI, M.; MORINI, B. STRSCNE: A scaled trust-region solver
for constrained nonlinear equations. Computational Optimization an Applications, v. 28, p.
31–50, 2004.
[10] HOCK, W.; SCHITTKOWSKI, K. Test Examples for Nonlinear Programming Codes.
Berlin, Heidelberg, New York: Springer, 1981. 178 p. (Lecture Notes in Economics and
Mathematical Systems, 187).
[11] MART
´
INEZ, J. M.; SANTOS, S. A. M´etodos Computacionais de Otimiza¸c˜ao. Rio de
Janeiro: IMPA, 1995. 256 p. (20
o
Col´oquio Brasileiro de Matem´atica). ISBN 8524400927.
[12] MONTICELLI, A. J. Fluxo de carga em redes de energia el´etrica. S˜ao Paulo: Editora
Edgar Bl¨ucher Ltda, 1983. 164 p.
57
[13] SCHITTKOWSKI, K. More Test Examples for Nonlinear Programming Codes. Berlin,
Heidelberg, New York: Springer Verlag, 1987. 261 p. (Lecture Notes in Economics and
Mathematical Systems, 282). ISBN 3-540-17182-7.
[14] FRANCISCO, J. B. M´etodos Num´ericos Aplicados `a Resolu¸c˜ao das Equa¸c˜oes da Rede
El´etrica. 71 f. Dissertac¸˜ao (Mestrado em Matem´atica e Computac¸˜ao Cient´ıfica) — Universi-
dade Federal de Santa Catarina, Santa Catarina, 2002.
58
AP
ˆ
ENDICE A -- Problemas
Abaixo apresentamos a formulac¸˜ao dos problemas que foram utilizados nos testes dos
cap´ıtulos 2 e 3. Esses problemas foram extra´ıdos da p´agina eletrˆonica http://www.polymath-
software.com/library, de [10] e de [13].
A.1 Problemas referentes ao cap
´
ıtulo 2
1. Twoeq2
F(x) =
120x
1
− 75k(1 − x
1
)
−x
1
(873 − x
2
) + 11(x
2
− 300)
em que k = 0, 12e
12581
x
2
−298
298x
2
.
Limitantes: l = [−0, 01; −∞] e u = [1, 1; +∞].
Estimativas iniciais: x = [1; 400], x = [0; 300], x = [0, 5; 320] e x = [0;350].
Soluc¸˜ao: [0, 9638680512795;346, 16369814640].
2. Twoeq3
F(x) =
k
√
1 − x
1
0,91−0,5x
1
9,1−0,5x
1
−
x
2
1
(1−x
1
)
2
Kp
x
2
(1, 84x
1
+ 77, 3) − 43260x
1
− 105128
em que
• k = e
−149750
x
2
+92,5
;
• Kp = e
42300
x
2
−24,2+0,17ln(x
2
)
.
59
Limitantes: l = [0; −∞] e u = [1; +∞].
Estimativas iniciais: x = [0, 5;1700], x = [0;1600], x = [0;1650], x = [0, 9;1600] e
x = [0, 9; 1700].
Soluc¸˜ao: [0, 5333728995523;1637, 70322946500].
3. Twoeq4a
F(x) =
ln(γ
2
) + ln(t2) + v1
x
2
·t2−x
1
·t1
t1·t2
ln(γ
1
) + ln(t1) −v2
x
2
·t2−x
1
·t1
t1·t2
em que
• t = 58, 7;
• pw1 = 21;
• v1 =
pw1/46,07
pw1/46,07+100−pw1/86,18
;
• P2 = 10
6,87776−1171,53/(224,366+t)
;
• P1 = 10
8,04494−1554,3/(222,65+t)
;
• γ
2
=
760
P2
;
• γ
1
=
760
P1
;
• v2 = 1 − v1;
• t1 = v1 + v2 · x
2
;
• t2 = v2 + v1 · x
1
;
• g2calc = e
−ln(t2)−v1·(x
2
·t2−x
1
·t1)/(t1·t2)
;
• g1calc = e
−ln(t1)+v2·(x
2
·t2−x
1
·t1)/(t1·t2)
.
Limitantes: l = [0; 0] e u = [+∞;+∞].
Estimativas iniciais: x = [0, 1; 0, 1], x = [0, 5;0, 5] e x = [0, 8;0, 8].
Soluc¸˜ao: [0, 0785888476379;0, 3017535930592].
4. Twoeq4b
F(x) =
t1 · t2 ·ln(γ
2
) + ln(t2) + v1(x
2
· t2 − x
1
· t1)
t1 · t2 ·ln(γ
1
) + ln(t1) −v2(x
2
· t2 − x
1
· t1)
60
com os mesmos parˆametros, limitantes e estimativas iniciais do problema Twoeq4a.
Soluc¸˜ao: [0, 0785888934885;0, 3017535528355].
5. Twoeq5a
F(x) =
log(γ
1
) − x
1
v2
2
(x
1
·v1/x
2
+v2)
2
log(γ
2
) − x
2
v1
2
(v1+x
2
·v2/x
1
)
2
em que
• t = 70, 9;
• pw1 = 49;
• v1 =
pw1/46,07
pw1/46,07+(100−pw1)/100,2
;
• P2 = 10
6,9024−1268,115/(216,9+t)
;
• P1 = 10
8,04494−1554,3/(222,65+t)
;
• γ
1
=
760
P1
;
• v2 = 1 − v1;
• γ
1
=
760
P2
;
• g1calc = 10
x
1
·v2
2
/(x
1
·v1/x
2
+v2)
2
;
• g2calc = 10
x
2
·v1
2
/(v1+x
2
·v2/x
1
)
2
.
Limitantes: l = [0; 0] e u = [+∞;+∞].
Estimativas iniciais: x = [0, 5; 0, 5], x = [1;1], x = [5;5] e x = [8;2].
Soluc¸˜ao: [0, 7580768059470;1, 1249034445330].
6. Twoeq5b
F(x) =
log(γ
1
) · (x
1
·
v1
x
2
+ v2)
2
− x
1
· v2
2
log(γ
2
) · (v1 + x
2
·
v2
x
1
)
2
− x
2
· v1
2
com os mesmos parˆametros, limitantes e estimativas iniciais do problema Twoeq5a.
Soluc¸˜ao: [0, 7580768059470;1, 1249034445330].
61
7. Twoeq6
F(x) =
x
1
1−x
1
− 5ln
0, 4
1−x
1
x
2
+ 4, 45977
x
2
− (0, 4 −0, 5 · x
1
)
Limitantes: l = [0; −∞] e u = [1; +∞].
Estimativas iniciais: x = [0, 9; 0, 5], x = [0, 5;0, 5], x = [0, 4; 0, 5] e x = [0, 6;0, 1].
Soluc¸˜ao: [0, 7573962468236;0, 0213018765882].
Soluc¸˜ao n˜ao vi´avel: [1, 0989839337750; −0, 1494919668876].
8. Twoeq7
F(x) =
a −
(c+2x
1
)
2
·(a+b+c−2x
1
)
2
x
2
− x
1
x
2
− kp · P
2
· (b − 3x
1
)
3
em que
• a = 0, 5;
• b = 0, 8;
• c = 0, 3;
• kp = 604500;
• P = 0, 00243.
Limitantes: l = [0; −∞] e u = [1; +∞].
Estimativas iniciais: x = [0; −1], x = [0; 1], x = [0, 5; 0, 1] e x = [0, 5;−0, 1].
Soluc¸˜ao 1: [0, 6003231171445;−3, 57990244801].
Soluc¸˜ao 2: [0, 0586545710394;0, 86743788245].
9. Twoeq8
F(x) =
x
1
− 0, 327x
0,804
2
e
−5230
(1,987(373+1840000x
1
)
x
2
− (0, 06 − 161x
1
)
Limitantes: l = [0; −∞] e u = [+∞; +∞].
Estimativas iniciais: x = [0, 0001;0, 01], x = [0, 001;0, 01], x = [0, 0001; 0, 1] e x =
[0, 5;0, 5].
62
Soluc¸˜ao: [0, 0003406054400;0, 0051625241669].
10. Twoeq9
F(x) =
x
1
−
1
(2,28−4log(eps/D+4,67/(Re·x
0,5
1
)))
2
133, 7 −
2x
1
·ρ·x
2
2
·L/D+ρ· g·200
g·144
em que
• L = 6000;
• D = 0, 505;
• ρ = 53;
• g = 32, 2;
• eps = 0, 00015;
• Re =
ρ·D·x
2
13,2·0,000672
.
Limitantes: l = [0; 0] e u = [+∞;+∞].
Estimativas iniciais: x = [0, 1; 10], x = [1;10], x = [0, 1;1] e x = [0, 1; 0, 1].
Soluc¸˜ao: [0, 006874616348157;5, 6728221306731].
11. Twoeq10
F(x) =
1
v1·v2
− 2x
2
c2
(v1+v2·c1)
3
− 2x
1
c4
(v2+v1·c3)
3
v1−v2
(v1·v2)
2
+ 6x
2
· c2
1−c1
(v1+v2·c1)
4
+ 6x
1
· c4
c3−1
(v2+v1·c3)
4
em que
• c1 = e
−α·x
2
;
• c2 = e
−2α·x
2
;
• c3 = e
−α·x
1
;
• c4 = e
−2α·x
1
;
• v2 = 1 − v1;
• α = 0, 4;
• v1 = 0, 5.
63
Limitantes: l = [−∞;−∞] e u = [+∞;+∞].
Estimativas iniciais: x = [0, 1; 0, 1], x = [1;1], x = [10;10] e x = [15;15].
Soluc¸˜ao 1: [1, 6043843214350;1, 6043843214350].
Soluc¸˜ao 2: [2, 9353711137400;2, 9353711137400].
12. Threeq1
F(x) =
x
2
+ x
3
− 1
x
2
−
y1
k1
x
3
−
y2
k2
em que
• y2 = 0, 8;
• y1 = 0, 2;
• p1 = 10
7,62231−
1417,9
191,15+x
1
;
• p2 = 10
8,10765−
1750,29
235+x
1
;
• B = 0, 7;
• A = 1, 7;
• γ
2
= 10
B·x
2
2
(x
2
+B·x
3
/A)
2
;
• γ
1
= 10
A·x
2
3
(A·x
2
/B+x
3
)
2
;
• k2 = γ
2
p2
760
;
• k1 = γ
1
p1
760
.
Limitantes: l = [−∞;0;0] e u = [+∞;1;1].
Estimativas iniciais: x = [100; 0, 2; 0, 8], x = [70; 0, 5; 0, 5], x = [80;0, 2;0, 8] e x =
[80;0, 5;0, 5].
Soluc¸˜ao: [93, 96706523770;0, 0078754574659;0, 9921245425339].
13. Threeq2
F(x) =
x
1
−
z1
1+x
3
(k1−1)
x
2
−
z2
1+x
3
(k2−1)
x
1
+ x
2
− (y1 + y2)
64
em que
• p1 = 10
7,62231−
1417,9
191,15+t
;
• p2 = 10
8,10765−
1750,29
235+t
;
• γ
2
= 10
B·x
2
1
(x
1
+Bx
2
/A)
2
;
• γ
1
= 10
A·x
2
2
(Ax
1
/B+x
2
)
2
;
• k1 = γ
1
p1
760
;
• k2 = γ
2
p2
760
;
• y1 = k1 · x
1
;
• y2 = k2 · x
2
;
• t = 88, 538;
• B = 0, 7;
• A = 1, 7;
• z1 = 0, 2;
• z2 = 0, 8.
Limitantes: l = [0; 0; 0] e u = [1; 1; 1].
Estimativas iniciais: x = [0;1;0, 5], x = [0, 5;0, 5;0, 9], x = [0, 4;0, 6;0, 9] e x =
[0, 1;0, 9;0, 5].
Soluc¸˜ao: [0, 0226974766367;0, 9773025233633;0, 5322677863643].
Soluc¸˜ao n˜ao vi´avel: [0, 6867568052506; 0, 3132431762583;1, 4708209249600].
Soluc¸˜ao falsa: [−7, 97906491100·10
−13
;2, 54516136300·10
−10
;−9, 14388809400·10
9
].
14. Threeq3
F(x) =
F ·
T0−x
1
V
+ 30000 · k ·
x
2
rhocp
− U · A ·
x
1
−x
3
rhocp·V
F ·
Ca0−x
2
V
− kx
2
F j ·
T j0−x
3
3,85
+ U · A ·
x
1
−x
3
62,3·1,0·3,85
em que
• k = 7, 08 · 10
10
e
−30000/1,9872
x
1
;
• rhocp = 50 · 0, 75;
65
• F = 40;
• T0 = 530;
• V = 48;
• U = 150;
• A = 250;
• Ca0 = 0, 55;
• F j = 49, 9;
• T j0 = 530.
Limitantes: l = [−∞;0;−∞] e u = [∞; ∞; ∞].
Estimativas iniciais: x = [100; 0, 2; 0, 8], x = [70; 0, 5; 0, 5], x = [80;0, 2;0, 8] e x =
[80;0, 5;0, 5].
Soluc¸˜ao 1: [671, 27832050250;0, 0354195308679;660, 46287831030].
Soluc¸˜ao 2: [590, 34979512380;0, 3301868979161;585, 72976766210].
Soluc¸˜ao 3: [537, 85475413080;0, 5213904932394;537, 25344007970].
15. Threeq4a
F(x) =
CC
x
1
CA·CB
− KC1
x
2
CY
CB·CC
− KC2
x
3
CA·x
2
− KC3
em que
• CY = x
2
+ x
3
;
• CC = x
1
−CY;
• CA = CA0 − x
1
− x
3
;
• CB = CB0 − x
1
−CY;
• KC1 = 1, 06;
• KC2 = 2, 63;
• KC3 = 5;
• CA0 = 1, 5;
• CB0 = 1, 5.
66
Limitantes: l = [0; 0; 0] e u = [+∞; +∞;+∞].
Estimativas iniciais: x = [0, 7; 0, 2; 0, 4], x = [0;0, 1;0], x = [1;1;1] e x = [10; 10;10].
Soluc¸˜ao: [0, 7053344059695;0, 1777924200537;0, 3739765850146].
16. Threeq4b
F(x) =
CC · x
1
− KC1 ·CA ·CB
x
2
·CY − KC2 ·CB · CC
x
3
− KC3 ·CA · x
2
com os mesmos parˆametros, limitantes e estimativas iniciais do problema Threeq4a.
Soluc¸˜ao: [0, 7053344059695;0, 1777924200537;0, 3739765850146].
Soluc¸˜ao n˜ao vi´avel 1: [0, 0555561340633; 0, 5972196082270;1, 0820734849200].
Soluc¸˜ao n˜ao vi´avel 2: [1, 0701041278950; −0, 3227156095103;1, 1305335070740].
17. Threeq5
F(x) =
−0, 16 · x
1
·
F0
x
3
+ k1(1 − x
1
) − k2 · x
1
0, 16 · F0 ·
T0
x
3
− 0, 16 · x
2
·
F0
x
3
+ 5(k1(1 − x
1
) − k2 · x
1
)
0, 16 · F0 − 0, 4
√
x
3
em que
• k1 = 300000e
−5000/x
2
;
• k2 = 60000000e
−7500/x
2
;
• F0 = 1;
• T0 = 300.
Limitantes: l = [0; −∞;0] e u = [1; +∞;+∞].
Estimativas iniciais: x = [0, 5;500; 0, 5], x = [0, 5;200;0, 1], x = [0, 7; 700;0, 2] e x =
[0, 001;400;0, 01].
Soluc¸˜ao: [0, 0171035426725;300, 08551771340;0, 16].
67
18. Threeq6
F(x) =
0, 1(1 − x
1
) − k1 · x
2
1
−0, 1x
2
+ k1 · x
2
1
− k2 · x
2
0, 1(25 − x
3
) −418 · k1 · x
2
1
− 418 · k2 · x
2
+ Q · 0.00001
em que
• k1 = 11e
−4180
8,314(x
3
+273,16)
;
• k2 = 172, 2e
−34833
8,314(x
3
+273,16)
;
• Q = 5100000.
Limitantes: l = [0; 0; −273.16] e u = [1; 1; +∞].
Estimativas iniciais: x = [0, 5;0, 5;500], x = [0, 1;0, 2;700], x = [0, 9; 0, 8; 200] e x =
[0, 01;0, 01;500].
Soluc¸˜ao: [0, 1578109142617;0, 77071354919;153, 09].
19. Threeq8
F(x) =
70 · 32, 3 − x
1
(144 ·
32,2
62,35
) + k ·45 ·(x
2
+ x
3
)
2
(x
1
− p2) · (144 ·
32,2
62,35
) + k ·24 · x
2
2
(x
1
− p3) · (144 ·
32,2
62,35
) + k ·34 · x
2
3
em que
• p2 = 156, 6 − 0, 00752x
2
2
;
• p3 = 117, 1 − 0, 00427x
2
3
;
• D34 =
2,067
12
;
• D24 =
1,278
12
;
• D45 =
2,469
12
;
• fF = 0, 015;
• π = 3, 1416;
• k24 = 2 · fF ·
125
(60·7,48)
2
·(π·D24
2
/4)
2
·D24
;
• k34 = 2 · fF ·
125
(60·7,48)
2
·(π·D34
2
/4)
2
·D34
;
• k45 = 2 · fF ·
145
(60·7,48)
2
·(π·D45
2
/4)
2
·D45
;
68
Limitantes: l = [0; 0; 0] e u = [+∞; +∞;+∞].
Estimativa inicial: x = [50; 100; 100].
Soluc¸˜ao n˜ao vi´avel 1: [33, 85347741000; −57, 48733479292;109, 47131250920].
Soluc¸˜ao n˜ao vi´avel 2: [57, 12556053860; −51, 75154635713;−92, 91811127982].
Soluc¸˜ao n˜ao vi´avel 3: [33, 85347740990; 57, 48733479339;−109, 47131250920].
20. Fiveq1
F(x) =
F ·
2,88−x
1
V
− k · x
2
1
F ·
66−x
2
V
− dhr · k ·
x
2
1
ρ·cp
− u · a ·
x
2
−x
3
V·ρ·cp
u · a ·
x
2
−x
3
1,82·1000·4184
− fc ·
x
3
−27
1,82
(x
2
−80)/20−x
4
20
m−x
5
τ
i
em que
• k = 0, 0744 · e
−1,182·10
7
/(8314,39∗(x
2
+273,16))
;
• fc = 0, 02 · 50
−m
;
• m = x
5
+ kc ·
10
20
− x
4
;
• F = 0, 0075;
• V = 7, 08;
• dhr = −9, 86 · 10
7
;
• ρ = 19, 2;
• cp = 1, 815 ·10
5
;
• u = 3550;
• a = 5, 4;
• τ
i
= 600;
• kc = 1.
Limitantes: l = [0; −∞;−∞;0;0] e u = [+∞;+∞; +∞;1;1].
Estimativas iniciais: x = [1; 100; 50; 0, 4;0, 25], x = [0, 5; 50; 25; 0, 1; 0, 1],
x = [0, 2; 20;10;0, 01;0, 01] e x = [2; 200;150;0, 8;0, 8].
Soluc¸˜ao: [1, 1206138931808;90;54, 8512245178517;0, 5;0, 3172119884117].
69
21. Sixeq1
F(x) =
x
1
+ x
2
+ x
4
− 0, 001
x
5
+ x
6
− 55
x
1
+ x
2
+ x
3
+ 2x
5
+ x
6
− 110, 001
x
1
− 0, 1x
2
x
1
− 1 · 10
4
· x
3
x
4
x
5
− 55 · 10
14
· x
3
x
6
Limitantes: l = [0; 0; 0; 0; 0; 0] e u = [+∞;+∞;+∞;+∞; +∞; +∞].
Estimativas iniciais: x = [10; 10; 10;10;10;10], x = [1;1;1; 1; 1; 1], x = [0; 0; 0; 0; 0; 0]
e x = [1 · 10
−4
;1 · 10
−3
;0;1 · 10
−4
;55;1 · 10
−4
].
Soluc¸˜ao: [8, 2645·10
−5
;8, 2645·10
−4
;9, 0909·10
−5
;9, 0909·10
−5
;54, 9999;1, 1·10
−10
].
Soluc¸˜ao n˜ao vi´avel 1: [−1 · 10
−10
;−1 · 10
−9
;−1 · 10
−11
;0, 001;55, 001;−0, 001].
22. Sixeq2a
F(x) =
1 − x
1
− k1 · x
1
· x
6
+ kr1 · x
4
1 − x
2
− k2 · x
2
· x
6
+ kr2 · x
5
−x
3
+ 2 · k3 · x
4
· x
5
k1 · x
1
· x
6
− kr1 · x
4
− k3 · x
4
· x
5
1, 5(k2 · x
2
· x
6
− kr2 · x
5
) − k3 · x
4
· x
5
1 − x
4
− x
5
− x
6
em que
• k1 = 31, 24;
• k2 = 2, 062;
• kr1 = 0, 272;
• kr2 = 0, 02;
• k3 = 303, 03;
Limitantes: l = [0; 0; 0; 0; 0; 0] e u = [+∞;+∞;+∞;+∞; +∞; +∞].
Estimativas iniciais: x = [0, 99; 0, 05; 0, 05; 0, 99;0, 05;0] e
x = [0, 05;0, 99;0, 05;0, 05;0, 99;0].
70
Soluc¸˜ao: [0, 970; 0, 980; 0, 0598; 0, 990;9.9751· 10
−5
;0, 0098].
Soluc¸˜ao n˜ao vi´avel: [1, 0333;1, 0222;−0, 0666;−1.0980· 10
−4
;1, 001;−0, 001].
23. Sixeq2b
F(x) =
1 − x
1
− k1 · x
1
· x
6
+ kr1 · x
4
1 − x
2
− k2 · x
2
· x
6
+ kr2 · x
5
−x
3
+ 2 · k3 · x
4
· x
5
k1 · x
1
· x
6
− kr1 · x
4
− k3 · x
4
· x
5
1, 5(k2 · x
2
· x
6
− kr2 · x
5
) − k3 · x
4
· x
5
1 − x
4
− x
5
− x
6
em que
• k1 = 17, 721;
• k2 = 3, 483;
• kr1 = 0, 118;
• kr2 = 0, 033;
• k3 = 505, 051.
com os mesmos limitantes e estimativas iniciais do problema Sixeq2a.
Soluc¸˜ao: [0, 9499; 0, 9666; 0, 1001;0, 9899; 1.0012· 10
−4
;0, 0099].
Soluc¸˜ao n˜ao vi´avel: [1, 0698;1, 0465;−0, 1396;−1.3775· 10
−4
;1, 0038;−0, 0036].
24. Sixeq2c
F(x) =
1 − x
1
− k1 · x
1
· x
6
+ kr1 · x
4
1 − x
2
− k2 · x
2
· x
6
+ kr2 · x
5
−x
3
+ 2 · k3 · x
4
· x
5
k1 · x
1
· x
6
− kr1 · x
4
− k3 · x
4
· x
5
1, 5(k2 · x
2
· x
6
− kr2 · x
5
) − k3 · x
4
· x
5
1 − x
4
− x
5
− x
6
em que
• k1 = 17, 721;
• k2 = 6, 966;
71
• kr1 = 0, 118;
• kr2 = 333, 333;
• k3 = 505, 051.
com os mesmos limitantes e estimativas iniciais do problema Sixeq2a.
Soluc¸˜ao: [0, 9499; 0, 9666; 0, 1001;0, 9899; 1.0013· 10
−4
;0, 0099].
25. Sixeq3
F(x) =
x
1
−
0,2
x
6
+(1−x
6
)·k11/k12
x
2
− x
1
k11
k12
x
3
−
0,8
x
6
+(1−x
6
)·k21/k22
x
4
− x
3
k21
k22
x
1
(1 − k11) + x
3
(1 − k21)
(x
1
− x
2
) + (x
3
− x
4
)
em que
• p1 = 10
7,62231−
1417,9
191,15+x
5
;
• p2 = 10
8,10765−
1750,29
235+x
5
;
• A = 1, 7;
• B = 0, 7;
• γ
11
= 10
A·x
2
3
(A·x
1
/B+x
3
)
2
;
• γ
21
= 10
B·x
2
1
(x
1
+B·x
3
/A)
2
;
• γ
12
= 10
A·x
2
4
(A·x
2
/B+x
4
)
2
;
• γ
22
= 10
B·x
2
2
(x
2
+B·x
4
/A)
2
;
• k11 = γ
11
·
p1
760
;
• k21 = γ
21
·
p2
760
;
• k12 = γ
12
·
p1
760
;
• k22 = γ
22
·
p2
760
;
Limitantes: l = [0; 0; 0; 0; −∞; 0] e u = [1; 1; 1; 1; +∞;1].
72
Estimativas iniciais: x = [0; 1; 1; 0; 100; 0, 8], x = [0, 05; 0, 95; 1; 0; 100;0, 8],
x = [0, 1; 0, 9; 1; 0; 100;0, 8] e x = [0; 1, 0; 0, 3; 0, 7; 100; 0, 8].
Soluc¸˜ao: [0, 0226; 0, 6867; 0, 9773;0, 3132; 88, 5378;0, 7329].
Soluc¸˜ao falsa: [−3, 607·10
−12
;2, 210·10
−10
;2, 255·10
−10
;9, 117·10
−13
;80, 859;6, 610·
10
9
].
26. Sixeq4a
F(x) =
V − vo ·
CAO−x
1
−rA
V − vo ·
CBO−x
2
−rB
V − vo ·
x
3
rC
V − vo ·
x
4
rD
V − vo ·
x
5
rE
5000 · (350 − x
6
) − 25 · (20 + 40) ·(x
6
− 300) + V · SRH
em que
• rA = 2 · r1B;
• rB = r1B + 2 · r2C;
• rC = −3 ·r1B + r2C;
• rD = −r3E − r2C;
• rE = r3E;
• r1B = −k1B ·CA · x
2
;
• r2C = −k2C · x
3
· x
2
2
;
• r3E = k3E · x
4
;
• k1B = 0, 4e
(20000/R)·(1/300−1/x
6
)
;
• k2C = 10e
(5000/R)·(1/310−1/x
6
)
;
• k3E = 10e
(10000/R)·(1/320−1/x
6
)
;
• SRH = −rA · 20000 + 2 ·r2C · 10000 + 5000 · r3E;
• R = 1, 987;
• V = 500;
• vo =
75
3,3
;
• CAO =
25
vo
;
73
• CBO =
50
vo
;
Limitantes: l = [0; 0; 0; 0; 0; −∞] e u = [+∞;+∞;+∞;+∞;+∞; +∞].
Estimativas iniciais: x = [0, 5;0, 01;1;0, 01;1;420], x = [0, 05;0, 001; 1; 0, 05; 1;400] e
x = [0, 1; 0, 2; 0, 5; 0, 1; 0, 7;350].
Soluc¸˜ao: [0, 00266; 0, 03346; 0, 83706;0, 00039;0, 80853;372, 76458].
27. Sixeq4b
F(x) =
V · (−rA) −vo · (CAO − x
1
)
V · (−rB) −vo · (CBO − x
2
)
V · rC − vo · x
3
V · rD − vo · x
4
V · rE − vo · x
5
5000 · (350 − x
6
) − 25 · (20 + 40) ·(x
6
− 300) + V · SRH
com os mesmos parˆametros e limitantes do problema Sixeq4a.
Estimativas iniciais: x = [0, 5;0, 01; 1; 0, 01; 1; 420], x = [0, 05; 0, 001; 1; 0, 05; 1; 400],
x = [0, 1; 0, 2; 0, 5; 0, 1; 0, 7;350] e x = [0, 1; 0, 2; 0, 5; 0, 1; 0, 7;380].
Soluc¸˜ao: [0, 00266; 0, 03346; 0, 8370;0, 00039;0, 8085;372, 76458].
Soluc¸˜ao n˜ao vi´avel: [−0, 00266;−0, 03507;0, 8123;0, 00043;0, 8414; 371, 4219].
28. Seveneq1
F(x) =
0, 5x
1
+ x
2
+ 0, 5x
3
−
x
6
x
7
x
3
+ x
4
+ 2x
5
−
2
x
7
x
1
+ x
2
+ x
5
−
1
x
7
−28837x
1
− 139009x
2
− 78213x
3
+ 18927x
4
+ 8427x
5
+
13492
x
7
− 10690
x
6
x
7
x
1
+ x
2
+ x
3
+ x
4
+ x
5
− 1
400 · x
1
· x
3
4
− 1, 7837 · 10
5
· x
3
· x
5
x
1
· x
3
− 2, 6058 · x
2
· x
4
Limitantes: l = [0; 0; 0; 0; 0; 0; 0] e u = [+∞;+∞; +∞; +∞;+∞;+∞;+∞].
Estimativas iniciais: x = [0, 5; 0; 0; 0, 5; 0; 0, 5;2], x = [0, 2; 0, 2; 0, 2; 0, 2; 0, 2;0, 5;0, 2]
e x = [0, 22;0, 075;0, 001; 0, 58;0, 125;0, 435;2, 35].
74
Soluc¸˜ao: [0, 322; 0, 0092; 0, 046; 0, 618;0, 0037;0, 576;2, 977].
Soluc¸˜ao n˜ao vi´avel: [0, 4569;−0, 0004;−0, 0021;0, 9151;−0, 3695;2, 6105;11, 5004].
29. Seveneq2a
F(x) =
5, 5 ·
x
4
−x
2
x
1
−x
2
−x
3
−
x
2
x
2
+x
3
3, 5 ·
0,888x
1
−x
3
−x
4
x
1
−x
2
−x
3
−
x
3
x
2
+x
3
5, 5 ·
0,0986x
1
−0,01(1,098x
1
−x
2
−9x
4
−x
5
−x
6
+x
7
)−(x
2
+x
5
)
1,098x
1
−x
2
−9x
4
−x
5
−x
6
+x
7
−
x
5
x
5
+x
6
3, 5 ·
0,986x
1
−9x
4
−x
6
−0,0986x
1
+0,01(1,098x
1
−x
2
−9x
4
−x
5
−x
6
+x
7
)
1,098x
1
−x
2
−9x
4
−x
5
−x
6
+x
7
−
x
6
x
5
+x
6
150,2·133,7·0,32
2
x
1
−x
2
−x
3
− x
4
·
x
1
−x
2
−x
3
(0,0986∗x
1
−x
4
)
2
446,8·133,7·0,0032
2
1,098x
1
−x
2
−9x
4
−x
5
−x
6
+x
7
−
x
1
·0,0986−x
4
1,098x
1
−x
2
−9x
4
−x
5
−x
6
+x
7
+ 0, 01
0, 04 ·
74,12·(0,986x
1
−10x
4
)+222,24·(0,0986x
1
−x
4
)+18·(x
4
−x
2
)+278,84x
4
+98,09·0,0136·x
1
98,01
− 0, 0136x
1
− x
7
Limitantes: l = [0; 0; 0; 0; 0; 0; 0] e u = [+∞;+∞; +∞; +∞;+∞;+∞;+∞].
Estimativas iniciais: x = [80;7;60; 7; 0, 5; 4; 0, 05], x = [100;10; 50; 10; 0, 5; 4;0, 05] e
x = [50;5;25;5;0, 5;4;0, 05].
Soluc¸˜ao: [80, 5340; 6, 9725; 61, 1190;7, 2042;0, 5476;3, 6532;0, 05970].
30. Teneq1a
F(x) =
x
1
+ x
4
− 3
2x
1
+ x
2
+ x
4
+ x
7
+ x
8
+ x
9
+ 2x
10
− R
2x
2
+ 2x
5
+ x
6
+ x
7
− 8
2x
3
+ x
5
− 4 · R
x
1
· x
5
− 0, 193 · x
2
· x
4
x
6
·
√
x
2
− 0, 002597 ·
√
x
2
· x
4
· xs
x
7
·
√
x
4
− 0, 003448 ·
√
x
1
· x
4
· xs
x
8
· x
4
− 1, 799 · 10
−5
· x
2
· xs
x
9
· x
4
− 0, 0002155 · x
1
·
√
x
3
· xs
x
10
· x
2
4
− 3, 846 ·10
−5
· x
2
4
· xs
em que
• R = 10;
• xs = x
1
+ x
2
+ x
3
+ x
4
+ x
5
+ x
6
+ x
7
+ x
8
+ x
9
+ x
10
.
75
Limitantes: l
i
= 0 e u
i
= +∞, ∀i.
Estimativas iniciais: x = [1; 1; 10; 1; 1; 1; 0; 0; 0;0] e x = [2; 2; 10;1;1;2;0;0;0;0].
Soluc¸˜ao: [2, 8801; 3, 9506; 19, 9841;0, 1198; 0, 0317;0, 0046;0, 0304;0, 01608;
0, 1205;0, 001].
31. 14eq1
F(x) =
−((x
12
− L0) · k11 + L1) · x
1
+ x
13
· k12 · x
2
L1 · x
1
− (x
13
· k12 + L2) · x
2
+ x
14
· k13 · x
3
+ z1 · F
L2 · x
2
− (x
14
· k13 + B) · x
3
−((x
12
− L0) · k21 + L1) · x
4
+ x
13
· k22 · x
5
L1 · x
4
− (x
13
· k22 + L2) · x
5
+ x
14
· k23 · x
6
+ z2 · F
L2 · x
5
− (x
14
· k23 + B) ∗ x
6
k11 · x
1
+ k21 · x
4
− 1
k12 · x
2
+ k22 · x
5
− 1
k13 · x
3
+ k23 · x
6
− 1
k1f ·z1 + k2f · z2 − 1
k10 ·k11 · x
1
+ k20 ·k21 · x
4
− 1
−x
12
· hv1 + x
13
· hv2 − L1 · hl1 + L0 · h0
−x
13
· hv2 + x
14
· hv3 + hf + L1 · hl1 − L2 · hl2
−x
14
· hv3 + Q + L2 · hl2 − L3 ·hl3
em que
• L0 = x
12
− D;
• L1 = x
13
− D;
• L2 = x
14
+ F − D;
• L3 = B;
• hl1 = x
7
· (29, 6 + 0, 04x
7
) · x
1
+ x
7
· (38, 5 + 0, 025x
7
) · x
4
;
• hv1 = (8003+ x
7
·(43, 8−0, 04x
7
))·k11·x
1
+(12004+ x
7
·(31, 7+ 0, 007x
7
))·k21·x
4
;
• hl2 = x
8
· (29, 6 + 0, 04x
8
) · x
2
+ x
8
· (38, 5 + 0, 025x
8
) · x
5
;
• hv2 = (8003+ x
8
·(43, 8−0, 04x
8
))·k12·x
2
+(12004+ x
8
·(31, 7+ 0, 007x
8
))·k22·x
5
;
• hl3 = x
9
· (29, 6 + 0, 04x
9
) · x
3
+ x
9
· (38, 5 + 0, 025x
9
) · x
6
;
• hv3 = (8003+ x
9
·(43, 8−0, 04x
9
))·k13·x
3
+(12004+ x
9
·(31, 7+ 0, 007x
9
))·k23·x
6
;
76
• hf = x
10
· (29, 6 + 0, 04x
10
) ·z1 + x
10
· (38, 5 + 0, 025x
10
) · z2;
• h0 = x
11
·(29, 6 + 0, 04x
11
) ·k10 ·k11 · x
1
+ x
11
·(38, 5 + 0, 025 · x
11
) ·k20 ·k21 · x
4
;
• k11 = (10
6,80776−935,77/((x
7
−32)·5/9+238,789)
)/P;
• k12 = (10
6,80776−935,77/((x
8
−32)·5/9+238,789)
)/P;
• k13 = (10
6,80776−935,77/((x
9
−32)·5/9+238,789)
)/P;
• k21 = (10
6,85296−1064,84/((x
7
−32)·5/9+232,012)
)/P;
• k22 = (10
6,85296−1064,84/((x
8
−32)·5/9+232,012)
)/P;
• k23 = (10
6,85296−1064,84/((x
9
−32)·5/9+232,012)
)/P;
• k1f = (10
6,80776−935,77/((x
10
−32)·5/9+238,789)
)/P;
• k2f = (10
6,85296−1064,84/((x
10
−32)·5/9+232,012)
)/P;
• k10 = (10
6,80776−935,77/((x
11
−32)·5/9+238,789)
)/P;
• k20 = (10
6,85296−1064,84/((x
10
−32)·5/9+232,012)
)/P;
• F = 1;
• z1 = 0, 40;
• z2 = 1 − z1;
• B = 0, 75;
• D = 0, 25;
• P = 760 ·
120
14,7
;
• Q = 10000;
• y11 = k11 · x
1
;
• y12 = k12 · x
2
;
• rec = y11 ·
D
z1·F
;
Limitantes: l = [0; 0; 0; 0; 0; 0; −∞; 0;0;0;0; 0;0;0] e u
i
= +∞, ∀i.
Estimativas iniciais: x = [0, 1;0, 1;0, 1;0, 1;0, 1;0, 1;100;100;100;100;100;5;5;5] e
x = [0, 5; 0, 4; 0, 3; 0, 3; 0, 4;0, 5; 145;190;210;200; 200;1;1;1].
Soluc¸˜ao: [0, 579; 0, 3957; 0, 2718; 0, 4209, 0, 6043;0, 7281;186, 3785, 200, 5268;
211, 486;200, 1675, 169, 064; 1, 081;1, 0668, 1, 0495].
77
32. Test1
F(x) =
10(x
2
− x
2
1
)
1 − x
1
Limitantes: l = [−∞;−1, 5] e u = [+∞; +∞].
Estimativa inicial: x = [−2; 1].
Soluc¸˜ao: [1;1].
33. Test25
F(x) =
f
1
(x)
f
2
(x)
.
.
.
f
99
(x)
em que f
i
(x) = −0, 011 + e
−
1
x
1
(u
i
−x
2
)
x
3
e u
i
= 25 + (−50ln(0, 011))
2/3
, i = 1, . . . , 99.
Limitantes: l = [−1; 0; 0] e u = [100; 25, 6; 5].
Estimativa inicial: x = [100; 12, 5; 3].
Soluc¸˜ao: [50; 25; 1, 5].
34. Test3
F(x) =
−2 ·10
−5
· (x
2
− x
1
)
1 + 2 · 10
−5
· (x
2
− x
1
)
Limitantes: l = [−∞;0] e u = [+∞; +∞].
Estimativa inicial: x = [10; 1].
Soluc¸˜ao: [0;0].
35. Test5
F(x) =
cos(x
1
+ x
2
) + 2 · (x
1
− x
2
) − 1, 5
cos(x
1
+ x
2
) − 2 · (x
1
− x
2
) + 2, 5
Limitantes: l = [−1, 5;−3] e u = [4; 3].
78
Estimativa inicial: x = [0; 0].
Soluc¸˜ao: [−π/3 + 1/2;−π/3 − 1/2].
36. Test38
F(x) =
−400 · x
1
· (x
2
− x
2
1
) − 2(1 − x
1
)
200(x
2
− x
2
1
) + 20, 2(x
2
− 1) + 19, 8(x
4
− 1)
−360 · x
3
· (x
4
− x
2
3
) − 2(1 − x
3
)
180(x
4
− x
2
3
) + 20, 2(x
4
− 1) + 19, 8(x
2
− 1)
Limitantes: l = [−10; −10; −10;−10] e u = [10; 10; 10; 10].
Estimativa inicial: x = [−3; −1;−3;−1].
Soluc¸˜ao: [1;1; 1; 1].
37. Test110
F(x) =
f
1
(x)
f
2
(x)
.
.
.
f
10
(x)
em que f
i
(x) = 2
log(x
i
−2)
x
i
−2
− 2
log(10−x
i
)
10−x
i
− 0, 2x
−0,8
i
10
j=1
ji
x
j
0,2
, i = 1, . . . , 10.
Limitantes: l
i
= 2, 001 e u = 9, 999, ∀i
Estimativa inicial: x
i
= 9, ∀i.
Soluc¸˜ao: [9, 35025655; . . . ;9, 35025655].
A.2 Problemas referentes ao cap
´
ıtulo 3
1. Test26
79
F(x) =
x
1
− x
2
(x
2
− x
3
)
2
(1 + x
2
2
) · x
1
+ x
4
3
− 3
Estimativa inicial: x = [−2, 6;2; 2].
Soluc¸˜ao: [1; 1; 1] e [a;a;a] em que a =
3
√
α − β −
3
√
α + β − 2/3, α =
√
139/108 e
β = 61/ 54.
2. Test27
F(x) =
0, 1(x
1
− 1)
x
2
− x
2
1
x
1
+ x
2
3
+ 1
Estimativa inicial: x = [2; 2; 2].
Soluc¸˜ao: [−1;1;0].
3. Test28
F(x) =
x
1
+ x
2
x
2
+ x
3
x
1
+ 2x
2
+ 3x
3
− 1
Estimativa inicial: x = [−4; 1; 1].
Soluc¸˜ao: [0, 5;−0, 5;0, 5].
4. Test42
F(x) =
x
1
− 1
x
2
− 2
x
3
− 3
x
4
− 4
x
1
− 2
x
2
3
+ x
2
4
− 2
Estimativa inicial: x = [1; 1; 1; 1].
80
Soluc¸˜ao: [2;2; 0, 6
√
2;0, 8
√
2].
5. Test48
F(x) =
x
1
− 1
x
2
− x
3
x
4
− x
5
x
1
+ x
2
+ x
3
+ x
4
+ x
5
− 5
x
3
− 2(x
4
+ x
5
) + 3
Estimativa inicial: x = [3; 5; −3; 2; −2].
Soluc¸˜ao: [1;1; 1; 1; 1].
6. Test49
F(x) =
x
1
− x
2
x
3
− 1
(x
4
− 1)
2
(x
5
− 1)
3
x
1
+ x
2
+ x
3
+ 4x
4
− 7
x
3
+ 5x
5
− 6
Estimativa inicial: x = [10; 7; 2; −3; 0, 8].
Soluc¸˜ao: [1;1; 1; 1; 1].
7. Test50
F(x) =
x
1
− x
2
x
2
− x
3
(x
3
− x
4
)
2
x
4
− x
5
x
1
+ 2x
2
+ 3x
3
− 6
x
2
+ 2x
3
+ 3x
4
− 6
x
3
+ 2x
4
+ 3x
5
− 6
Estimativa inicial: x = [35; −31; 11; 5; −5].
81
Soluc¸˜ao: [1;1; 1; 1; 1].
8. Test51
F(x) =
x
1
− x
2
x
2
+ x
3
− 2
x
4
− 1
x
5
− 1
x
1
+ 3x
2
− 4
x
3
+ x
4
− 2x
5
x
2
− x
5
Estimativa inicial: x = [2, 5; 0, 5; 2; −1;0, 5].
Soluc¸˜ao: [1;1; 1; 1; 1].
9. Test52
F(x) =
4x
1
− x
2
x
2
+ x
3
− 2
x
4
− 1
x
5
− 1
x
1
+ 3x
2
x
3
+ x
4
− 2x
5
x
2
− x
5
Estimativa inicial: x = [2; 2; 2; 2; 2].
Soluc¸˜ao: [−33;11; 180; −158; 11]/349.
82
10. Test77
F(x) =
x
1
− 1
x
1
− x
2
x
3
− 1
(x
4
− 1)
2
(x
5
− 1)
3
x
4
· x
2
1
+ sen(x
4
− x
5
) −2
√
2
x
2
+ x
4
3
· x
2
4
− 8 −
√
2
Estimativa inicial: x = [2; 2; 2; 2; 2].
Soluc¸˜ao: [1, 166172; 1, 182111;1, 380257;1, 506036;0, 6109203].
11. Test79
F(x) =
x
1
− 1
x
1
− x
2
x
2
− x
3
(x
3
− x
4
)
2
(x
4
− x
5
)
2
x
1
+ x
2
2
+ x
3
3
− 2 −3
√
2
x
2
− x
2
3
+ x
4
+ 2 − 2
√
2
x
1
· x
5
− 2
Estimativa inicial: x = [2; 2; 2; 2; 2].
Soluc¸˜ao: [1, 191127; 1, 362603;1, 472818;1, 635017;1, 679081].
12. Test216
F(x) =
10(x
2
1
− x
2
)
x
1
− 1
x
1
(x
1
− 4) − 2x
2
+ 12
Estimativa inicial: x = [−1, 2;1].
Soluc¸˜ao: [2;4].
83
13. Test269
F(x) =
x
1
− x
2
x
2
+ x
3
− 2
x
4
− 1
x
5
− 1
x
1
+ 3x
2
x
3
+ x
4
− 2x
5
x
2
− x
5
Estimativa inicial: x = [2; 2; 2; 2; 2].
Soluc¸˜ao: [−0, 7674; 0, 2558; 0, 6279; −0, 1163; 0, 2558].
14. Test316
F(x) =
x
1
− 20
x
2
+ 20
0, 01(x
2
1
+ x
2
2
) − 1
Estimativa inicial: x = [0; 0].
Soluc¸˜ao: [7, 071; −7, 071].
15. Test344
F(x) =
x
1
− 1
x
1
− x
2
(x
2
− x
3
)
2
x
1
(1 + x
2
2
) + x
4
3
− 4 − 3
√
2
Estimativa inicial: x = [2; 2; 2].
Soluc¸˜ao: [1, 105; 1, 197; 1, 535].
84
16. Test345
F(x) =
x
1
− 1
x
1
− x
2
(x
2
− x
3
)
2
x
1
(1 + x
2
2
) + x
4
3
− 4 − 3
√
2
Estimativa inicial: x = [0; 0; 0].
Soluc¸˜ao: [1, 105; 1, 197; 1, 535].
17. Test373
F(x) =
x
4
x
5
x
6
x
7
x
8
x
9
x
1
+ x
2
e
−5x
3
+ x
4
− 127
x
1
+ x
2
e
−3x
3
+ x
5
− 151
x
1
+ x
2
e
−x
3
+ x
6
− 379
x
1
+ x
2
e
x
3
+ x
7
− 421
x
1
+ x
2
e
3x
3
+ x
8
− 460
x
1
+ x
2
e
5x
3
+ x
9
− 426
Estimativa inicial: x = [300; −100; −0, 1997; −127; −151; 379;421;460;426].
Soluc¸˜ao: [523, 31; −156, 95; −0, 2; 29, 61;−86, 62;47, 33;26, 24;22, 92;−39, 47].
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
