Um Algoritmo Novo Baseado no Algoritmo Von Neumann
para Programação Linear
Jair da Silva,
Aurelio R. L. Oliveira,
E-mail: [email protected],
[email protected] ,
Marta I. Velazco
E-mail: [email protected]
Depto de Matemática, Estatı́stica e Computação Cientı́fica, UNICAMP, IMECC,
13083-859, Campinas, SP
1
Introdução
2
Descrição do Problema
Consideremos o problema de encontrar uma
solução factı́vel do conjunto de restrições lineNeste trabalho, generalizamos a idéia apresen- ares:
tada por João Gonçalves, Robert Storer e Jacek
Gondzio em [7], para desenvolver o algoritmo
P x = 0,
de ajustamento pelo par ótimo. Gonçalves, eset x = 1,
(1)
tudou em sua tese de PhD [6] o algoritmo de
x ≥ 0,
Von Neumann e apresentrou quatro novos alm×n , x ∈ Rn e e ∈ Rn é o vetor
goritmos baseado neste, sendo que o algoritmo onde P ∈ R
de ajustamento pelo par ótimo foi o algoritmo com todas as coordenadas iguais a um, e as cocom o melhor desempenho na prática. O algo- lunas de P tem norma um, isto é, ||Pj || = 1,
ritmo Von Neumann foi apresentado por Dant- para j = 1, . . . , n. Geometricamente as coluzig no inı́cio dos anos 1990 [2, 3] e depois mais nas Pj podem ser vistas, como pontos sobre a
tarde foi estudado por Epelman e Freund [4, 5], hiperesfera m-dimensional com raio unitário e
este algoritmo possui propriedades interessan- centro na origem (ver figura 1). O problema
tes, como simplicidade e convergência inicial acima então pode ser descrito como de atribuir
rápida, porém, ele não é muito prático para ponderações xj não negativos às colunas Pj de
resolver problemas lineares, visto que sua con- modo que depois de reescalado seu centro de
gravidade seja a origem.
vergência é muito lenta.
O algoritmo de ajustamento pelo par ótimo
herda as melhores propriedades do algoritmo
Von Neumann. Embora Gonçalves prove que
em termos de convergência o algoritmo de ajustamento pelo par ótimo é superior ao algoritmo
Von Neumann, ainda assim, ele também não é
prático para resolver problemas lineares, visto
que sua convergência também é muito lenta.
P1
Ps
0
P2
k−1
u
k
b
Pn
k−1
b
P3
Ao generalizar a idéia de Gonçalves, Storer e Gondzio em [7] para o algoritimo de
ajustamento do par ótimo, desenvolvemos um Figura 1: Ilustração do algoritmo Von Neumann
novo método para resolver problemas de programação linear. Do ponto de vista computaciNote que qualquer problema de programação
onal, este algoritmo será utilizado em conjunto linear pode ser reduzido ao problema (1). Para
com um método primal-dual de ponto interior ver isto consideremos o problema na forma
infactı́vel, para acelerar a convergência deste. padrão:
ct x
minimizar
s.a
Ax = b,
x ≥ 0,
(2)
e, ze ∈ Rn , ye+ , ye− ∈ Rm .
x
Na forma matricial temos
b = 0,
Abα
b = 1,
et α
b ≥ 0,
α
onde A ∈ Rm×n , c, x ∈ Rn , e b ∈ Rm . O dual
de (2) é dado por
(3)
onde y ∈ Rm e z ∈ Rn .
Obter uma solução ótima para o par de problemas (2) e (3) primal e dual é equivalente a
obter uma solução factı́vel para o seguinte problema:
Ax = b,
+ z = c,
ct x − bt y = 0,
x, z ≥ 0.
At y
#
e
α
.
ve
Prova-se em [7] suplemento online que:
e ve, onde ve 6= 0, é solução factı́vel de
a) Se α,
e é uma solução factı́vel para
(7), então α = αe
v
(6).
b) Reciprocamente se α é uma solução
1
e = veα, onde et α+1
factı́vel para (6), então α
é solução factı́vel para (7).
Finalmente consideremos o problema
b=
onde Ab = [Ae − eb] e α
bt y
maximizar
s.a
At y + z = c,
z ≥ 0,
"
(8)
P α = 0,
et α = 1,
α ≥ 0,
(4)
(9)
Como y é uma variável irrestrita, fazemos
Aj
e Aj são as colunas da matriz
y = y + − y − , onde y + ≥ 0 e y − ≥ 0. Assim o onde Pj = ||A
cj ||
b para j = 1, . . . , 2n + 2m + 1.
problema (4) toma a forma
A,
Prova-se em [7] suplemento online que:
Ax = b,
a) Se α é uma solução factı́vel para (9), então
At y + − At y − + z = c,
b
α
é
uma solução factı́vel para (8), onde
(5)
cy x − bt y + + bt y − = 0,
! ,Ã n
!
Ã
x, y + , y − , z ≥ 0.
X αk
αj
bj =
,
α
bk ||
Na forma matricial temos
||Abj ||
||
A
k=1
e =e
Aα
b
α≥0
onde

A

Ae =  0
ct




x
0
0
0
 y+


At −At I  , α =  −
 y
−bt
bt
0
z
(6) onde n é a dimensão das colunas de P.
b é uma solução
b) Reciprocamente, se α
factı́vel para (8), então α é uma solução factı́vel

para (9), onde




³
´
bj ||
b j ||A
αj = α
,Ã n
X
!
bk || ,
b k ||A
α
k=1
b
concluindo o desejado.


e
e b =  c .
0
Agora consideremos seguinte conjunto de 3 Algoritmo de Von Neumann
restrições lineares
Em 1948, von Neumann propôs para Dantzig, em comunicação privada um algoritmo
e −e
Aeα
bve = 0,
t
para programação linear, que foi divulgado por
(7)
e
e
e α + v = 1,
Dantzig no inı́cio dos anos 1990 em [2, 3]. Dese ve ≥ 0,
α,
crevemos a seguir este algoritmo:
onde


1) O algoritmo inicia-se com qualquer aproe
x
 ye+ 
ximação
inicial da origem, isto é, b0 = P x0 ,


e =  − ,
α
t
0
e x = 1, x0 ≥ 0, onde x0 é arbitrário (por
 ye 
exemplo xj = n1 ,) para j = 1, . . . , n.
ze
1) O algoritmo inicia-se com qualquer apro2) (Cálculo da direção) No inı́cio da iteração
k, k ≥ 1, temos a solução aproximada x = ximação inicial da origem, isto é, b0 = P x0 ,
et x0 = 1, x0 ≥ 0, onde x0 é arbitrário (por
xk−1 , tal que x ≥ 0, e et x = 1. Seja
exemplo xj = n1 ,) para j = 1, . . . , n.
2) (Cálculo da direção) No inı́cio da iteração
bk−1 = P xk−1 , uk−1 = ||bk−1 ||.
k, k ≥ 1, temos a solução aproximada x =
Entre todos os vetores Pj , j = 1, . . . , n en- xk−1 , tal que x ≥ 0, e et x = 1. Seja
contre o vetor Ps que forma o maior ângulo
com o vetor bk−1 :
bk−1 = P xk−1 , uk−1 = ||bk−1 ||.
s+ = argminj=1,...,n Pjt bk−1 .
Entre todos os vetores Pj , j = 1, . . . , n encontre o vetor Ps+ que forma o maior ângulo
3) (Verifica a factibilidade) Seja vk−1 = com o vetor bk−1 :
Pst+ bk−1 . Se vk−1 > 0, pare; o problema (1)
é infactı́vel.
s+ = argminj=1,...,n Pjt bk−1 .
4) (Cálculo da nova aproximação) Na
próxima iteração bk é escolhido como o ponto
Entre todos os vetores Pj , j = 1, . . . , n enmais próximo da origem no seguimento de reta contre o vetor Ps− que forma o menor ângulo
ligando bk−1 e Ps . Isto é feito da seguinte forma com o vetor bk−1 e tal que xs− > 0 :
1−vk−1
,
u2k−1 −2vk−1 +1
k
k−1
b = λb
+ (1 −
λ=
λ)Ps ,
2
uk = λvk−1 + (1 − λ),
xk = λxk−1 + (1 − λ)es ,
s− = argmaxj=1,...,n {Pjt bk−1 | xj > 0}.
3) (Verifica a factibilidade) Seja vk−1 =
onde es é o vetor unitário correspondente ao
Pst+ bk−1 . Se vk−1 > 0, pare; o problema (1)
ı́ndice s. Faça k = k + 1 e volte para o passo
é infactı́vel.
2).
4) (Cálculo da nova aproximação) Resolva o
problema
4
Algoritmo de Ajustamento
pelo Par Ótimo
minimizar ||bk ||2
k−1
s.a
λ1 (1 − xk−1
s+ − xs− )+
λ2 + λ3 = 1,
λ1 ≥ 0,
λ2 ≥ 0,
λ3 ≥ 0.
(10)
O algoritmo de ajustamento pelo par ótimo é
a generalização do “Weight-Reduction” ver [7].
De um certo modo, podemos dizer que o algoritmo de ajustamento pelo par ótimo, prioriza
apenas duas variáveis em cada iteração, porque
k−1
onde bk = λ1 (bk−1 − xk−1
s+ Ps+ − xs− Ps− ) +
ele encontra o valor ótimo para duas coordeλ P + + λ3 Ps− .
nadas e ajusta o restante das coodenadas em 2 s
A próxima iteração é calculada como
função destes valores. Este algoritmo começa
k−1
bk = λ1 (bk−1 − xk−1
s+ Ps+ − xs− Ps− )+
identificando os vetores Ps+ e Ps− que tem o
λ2 Ps+ + λ3 Ps− ,
maior e menor ângulo com o vetor bk−1 , resuk = 
||bk ||,
pectivamente. Então em seguida ele encontra
k−1
+
−

 λ1 xj , j 6= s e j 6= s ,
para
os valores xks+ , xks− e λ onde xkj = λxk−1
j
λ2 ,
j = s+ ,
todo j 6= s+ e j 6= s− , que minimiza a distância xj = 

λ3 ,
j = s− .
de bk a origem satisfazendo a convexidade e as
restrições de não negatividade. Este problema
Faça k = k + 1 e volte ao passo 2.
de otimização tem a solução facilmente calcuPara resolver o problema (10), inicialmente
lada examinando as condições Karush-Kuhn- eliminamos a variável λ1 . Temos que
Tucher (KKT).
1 − λ2 − λ3
Descrevemos o algoritmo de ajustamento
(11)
λ1 =
k−1
pelo par ótimo a seguir:
1 − xk−1
s+ − xs−
então substituindo (11) em (10), podemos re- duas coordenadas em cada iteração. Vamos nos
escrever o problema como
referir a este, como o algoritmo para 2 variáveis.
Utilizando a mesma idéia contida neste algominimizar ||bk ||2
ritmo podemos generalizá-lo e construir o algos.a
1 − λ2 − λ3 ≥ 0,
(12) ritmo para p variáveis. A idéia central utilizada
λ2 ≥ 0,
no algoritmo para 2 variáveis para dar prioriλ3 ≥ 0.
dade as duas coordenadas é resolver o subproblema (10). Este subproblema pode ser genek−1
1−λ2 −λ3
k
k−1
onde b =
(b
− xs+ Ps+ −
1−xk−1
−xk−1
ralizado, e ao invés de utilizarmos duas colu+
−
s
s
k−1
xs− Ps− ) + λ2 Ps+ + λ3 Ps− .
nas para formular o problema, podemos utilizar
Definindo g1 (λ2 , λ3 ) = λ2 + λ3 − 1, qualquer quantidades de colunas e assim dar
g2 (λ2 , λ3 ) = −λ2 , g3 (λ2 , λ3 ) = −λ3 . As res- importância a quantas variáveis desejarmos.
trições do problema (12) podem ser reescriA maneira como escolhemos as variáveis para
tas como g1 (λ2 , λ3 ) ≤ 0, g2 (λ2 , λ3 ) ≤ 0 e dar prioridade é livre e podemos escolhe-las,
g1 (λ2 , λ3 ) ≤ 0. Denotando a função obje- de acordo com o problema que iremos resoltivo por f (λ2 , λ3 ) e seja (λ2 , λ3 ) uma solução ver. Uma escolha natural se vamos construir
factı́vel. Pela convexidade da função objetivo e um algoritmo para p variáveis, é tomarmos p/2
restrições, se (λ2 , λ3 ) é uma solução ótima lo- colunas que fazem o maior ângulo com o vetor
cal, ela também é uma solução ótima global. bk e as outras p/2 colunas são as que fazem o
Assim (λ2 , λ2 ) satisfaz a condição necessária menor ângulo com o vetor bk , se p for impar
(KKT) dada por
colocamos uma coluna a mais para o conjunto
de vetores que formam o maior ângulo com o
vetor bk por exemplo.
3
X
∇f (λ2 , λ3 ) +
∇µi gi (λ2 , λ3 ) = 0,
Ainda não conseguimos formalizar todos os
i=1
casos do problema geral. Neste trabalho apreµi gi (λ2 , λ3 ) = 0, para i = 1, 2, 3,
sentaremos o caso particular p = 4.
µi ≥ 0, para i = 1, 2, 3,
O algoritmo de ajustamento ótimo para 4 coonde os escalares µi são os multiplicadores de ordenadas segue as mesmas linhas do algoritmo
Lagrange. Da convexidade da função objetivo de ajustamento pelo par ótimo:
e restrinções, as condições KKT são também
1) O algoritmo inicia-se com qualquer aprosuficientes. Resolvemos o problema (11) sele- ximação inicial da origem, isto é, b0 = P x0 ,
cionando uma solução factı́vel entre todas as et x0 = 1, x0 ≥ 0, onde x0 é arbitrário (por
possibilidades que satisfazem a condição KKT. exemplo xj = 1 ,) para j = 1, . . . , n.
n
Isto é feito analisando os seguintes casos:
2) (Cálculo da direção) No inı́cio da iteração
(a)λ2 = λ3 = 0;
k, k ≥ 1, temos a solução aproximada x =
xk−1 , tal que x ≥ 0, e et x = 1. Seja
(b)λ2 = 0, 0 < λ3 < 1;
(c)λ2 = 0, λ3 = 1
(d)0 < λ2 < 1, λ3 = 0
(e)0 < λ2 < 1, 0 < λ3 < 1, λ2 + λ3 − 1 = 0;
(f)λ2 = 1, λ3 = 0;
bk−1 = P xk−1 ,
uk−1 = ||bk−1 ||.
Entre todos os vetores Pj , j = 1, . . . , n encontre os vetores Ps+ , i = 1, 2 que fazem o maior
i
(g)0 < λ2 < 1, 0 < λ3 < 1, λ2 + λ3 − 1 6= 0;
ângulo
com
o
vetor
bk−1 .
Para cada caso acima substituimos os valoEntre todos os vetores Pj , j = 1, . . . , n enres conhecidos na equação KKT e resolvemos o
contre os vetores Ps− , i = 1, 2 que fazem o mesistema linear.
i
nor ângulo com o vetor bk−1 e tal que x−
i > 0,
i = 1, 2.
5 Algoritmo de Ajustamento
3) (Verifica a factibilidade) Seja v
=
Ótimo para p Coordenadas maximoi=1,2 P t+ bk−1 . Se vk−1 > 0, pare;k−1
o pros
i
O algoritmo de ajustamento pelo par ótimo blema (1) é infactı́vel.
4) (Cálculo da nova aproximação) Resolva o
construı́do por Gonçalves em sua tese prioriza
subproblema
minimizar
s.a
Definindo g1 (λ2 , λ3 , λ4 , λ5 ) =
||bk ||2
Ã
λ1 1 −
+
2
X
i=1
4
X
xk−1
s+
i
−
2
X
i=1
!
gi (λ2 , λ3 , λ4 , λ5 ) = −λi , para i = 2, . . . , 5.
As restrições do problema (15) podem
(13) ser reescritas como gi (λ2 , λ3 , λ4 , λ5 ) ≤ 0,
para i = 1, . . . , 5. Denotando a função
objetivo por f (λ2 , λ3 , λ4 , λ5 ) então a
condição necessária (KKT) é dada por
xk−1
s−
i
λi+1 = 1,
λi ≥ 0, para, i = 1, . . . , 5,

bk = λ1 bk−1 −
2
X
xk−1
Ps+ −
s+
2
X
λi − 1 e
i=2
i=1
onde
5
X

∇f (λ2 , λ3 , λ4 , λ5 ) +
5
X
µi ∇gi (λ2 , λ3 , λ4 , λ5 ) = 0,
i=1
xk−1
Ps− 
s−
µi gi (λ2 , λ3 , λ4 , λ5 ) = 0, para i = 1, . . . , 5,
i
j
i
j
i=1
j=1
µi ≥ 0, para i = 1, . . . , 5.
2
4
X
X
Então resolvemos o problema (15) selecio+ λi+1 Ps+ +
λj+1 Ps− .
nando uma solução factı́vel entre todas as posi
j
i=1
i=3
sibilidades que satisfazem a condição KKT. A
A próxima
iteração é calculada como !
Ã
técnica empregada é mesma utilizada no al2
2
X
X
k−1
k−1
k−1
k
goritmo de ajustamento pelo par ótimo, isto
−
xs+ Ps+ −
xs− Ps−
b = λ1 b
i
i
i
i
é, analisamos todos os casos possı́veis de vai=1
i=1
2
4
X
X
lores para as variáveis λi , para i = 2, . . . , 5.
+ λi+1 Ps+ +
λi+1 Ps− ,
Para n = 2 que é o caso do algoritmo de
i
i
i=1
i=3
k
k
ajustamento pelo par ótimo consideramos 7 cau = ||b ||,

k−1
+ + − −
sos, para n = 4 temos 30 casos a considerar,
λ1 xj , j ∈
/ {s1 , s2 , s1 , s2 },




+
este
número elevado de casos se deve ao fato

λ2 ,
j = s1 ,

+
que
devemos
levar em consideração as seguinxj =
λ3 ,
j = s2 ,


tes possibilidades para cada valor de λi , para

λ4 ,
j = s−

1,


−
i = 2, . . . , 5 :
λ5 ,
j = s2 .
i) λi = 0, para i = 2, . . . , 5,
Faça k = k + 1 e volte ao passo 2.
ii) λi = 1, para i = 2, . . . , 5,
Analogamente como no algoritmo de ajusiii) 0 < λi < 1, para i = 2, . . . , 5.
tamento pelo par ótimo para resolver o subou seja, as combinações destes valores de λi ,
problema (12) primeiramente eliminamos a
para i = 2, . . . , 5, igualmente como descrito no
variável λ1 do problema. Temos que
algoritmo de ajustamento pelo par ótimo de
5
(a)-(f) geram os 30 casos.
X
1−
λi
i=2
λ1 =
1−
2
X
i=1
xk−1
s+
i
−
2
X
j=1
(14)
xk−1
s−
j
5.1
Propriedades Teóricas do Novo
Método
então substuindo (14) em (13) podemos rees- Nesta subseção, provaremos o desempenho superior do método desenvolvido, em relação ao
crever o problema como
algoritmo de Von Neumann. Também provarek
2
mos que se p2 ≥ p1 então o algoritmo de ajusminimizar ||b ||
5
tamento ótimo para p2 coordenadas possui um
X
(15) desempenho superior em relação ao algoritmo
s.a
1−
λi ≥ 0,
i=2
de ajustamento ótimo para p1 coordenadas.
λ ≥ 0 para i = 1, . . . , 5,
i
onde

bk = λ1 bk−1 −
2
X
+
λi+1 Ps+ +
i=1
i
2
X
i=1
4
X
xk−1
Ps+ −
s+
i
i
λj+1 Ps− .
j=3
j
2
X
j=1

xk−1
Ps− 
s−
j
j
Teorema .1 O decréscimo em ||bk || obtido
por uma iteração do algoritmo de ajustamento
ótimo para p coordenadas, com 1 ≤ p ≤ n, onde
n é dimensão das colunas de P, no pior caso é
igual ao obtido por uma iteração do algoritmo
Von Neumann.
Demonstração: Seja k, k ≥ 1 dado e seja
bk−1 o resı́duo no inı́cio da iteração k. Seja
{Pη+ , . . . , Pηs+ } e {Pη− , . . . , Pηs− } o conjunto
1
1
1
2
de vetores que fazem o maior e menor ângulo
com o vetor bk−1 , respectivamente. Depois da
k-ésima iteração no algoritmo de ajustamento
ótimo para
 p coordenadas temos que

bk = λ1 bk−1 −
s1
X
+
λη+ Pη+ +
i
i=1
i
s1
X
i=1
s2
X
xk−1
Pη+ −
η+
i
i
s2
X
j=1
xk−1
Pη− 
η−
j
j
j
j
onde (λ1 , λη+ , . . . , ληs+ , λη− , . . . , ληs− )
é
a
1
1
1
2
solução ótima do problema (13) priorizando p
coordenadas. Temos que
,
, . . . , λvn xk−1
(λvn , λvn xk−1
+ 1 − λvn , λvn xk−1
η+
η+
η+
1
λvn xk−1
, . . . , λvn xk−1
),
η−
η−
1
bkp2 = λ1 bk−1 −
+
i=1
s1
X
λη + Pη + +
i=1
s1
X
i
i
s2
X
s1
2
xk−1
Pη+ −
η+
i
i
s2
X
j=1

xk−1
Pη− 
η−
j
j
λη− Pη− .
j
j=1
j
onde (λ1 , λη+ , . . . , ληs+ , λη− , . . . , ληs− )
é
a
1
1
1
2
solução ótima do problema (13) priorizando p2
coordenadas. Temos que a solução ótima de
(13) prioritizando p1 coordenadas
e1, λ
e +, . . . , λ
e + ,λ
e −, . . . , λ
e − ),
(λ
η
ηs
η
ηs
1
λη− Pη− .
j=1

1
3
4
é também uma solução facı́vel para (13) priorizando
°  p2 coordenadas. Então

°
s4
s3
X
X
°
k−1
e 1 bk−1 −
°λ
−
Pη− 
P
xk−1
x
+
°
ηi
ηj−
ηi+
j
°
j=1
i=1
s
s
3
4
° ° ° ° °
X
X
° k ° ° k °
e +P + +
e −P − °
+ λ
λ
η
η
η
η °= °bp1 ° ≥ °bp2 ° ,
i=1
i
i
j=1
j
j
s2
onde λvn é o λ da iteração Von Neumann, é onde bkp1 é o resı́duo obtido por aplicar uma
iteração do algoritmo de ajustamento ótimo
uma solução facı́vel para (13). Então
para p1 coordenadas. Com isto concluimos que
||λvn bk−1 + (1 − λvn )Pη+ || = ||bkvn || ≥ ||bk ||,
a redução em ||bk || por uma iteração do algo1
ritmo de ajustamento ótimo para p2 coordenak
onde bvn é o resı́duo obtido por aplicar uma das no pior caso é igual a redução por uma
iteração do algoritmo Von Neumann. Com isto iteração do algoritmo de ajustamento ótimo
concluimos que a redução em ||bk || por uma para p1 cooordenadas.
iteração do algoritmo de ajustamento ótimo
para p coordenadas no pior caso é igual a
redução por uma iteração do algoritmo Von
6 Conclusões
Neumann.
||bk ||
Teorema .2 O decréscimo em
obtido
por uma iteração do algoritmo de ajustamento
ótimo para p2 coordenadas, no pior caso é igual
ao obtido por uma iteração do algoritmo de
ajustamento ótimo para p1 coordenadas com
p1 ≤ p2 ≤ n, onde n é a dimensão das colunas de P .
Apresentamos um novo algoritmo que em
termos de desempenho é superior ao algoritmo de Von Neumann e ao algoritmo de
Gonçalves. Embora não tenhamos ainda resultados práticos, Gonçalves, Storer e Gondzio
em [7] comprovam que para p = 2, o algoritmo
é superior na prática ao algoritmo de Von Neumann.
O algotimo de ajustamento ótimo para p
coordenadas será utilizado em conjunto com
um algoritmo primal-dual de ponto interior infactı́vel para acelerar a convergência deste.
Demonstração: Seja k, k ≥ 1 dado e seja
bk−1 o resı́duo no inı́cio da iteração k. Seja
{Pη+ , . . . , Pηs+ } e {Pη− , . . . , Pηs− } o conjunto de
1
1
2
1
vetores que formam o maior e menor ângulo
com o vetor bk−1 , respectivamente, para o al7 Agradecimentos
goritmo que prioriza p2 coordenadas, onde s1 +
s2 = p2 e seja {Pη+ , . . . , Pηs+ } e {Pη− , . . . , Pηs− }
À CAPES e ao CNPQ pelo suporte fornecido.
1
1
4
3
o conjunto de vetores que formam o maior e menor ângulo com o vetor bk−1 , respectivamente,
para o algoritmo que prioritiza p1 coordenadas, Referências
onde s3 + s4 = p1 . Depois da k-ésima iteração
no algoritmo de ajustamento ótimo para p2 co- [1] M. S. Bazaraa, H. D. Sherali, and C. M.
ordenadas temos que
Shetty. Nonlinear Programming: Theory
and Algorithms. John Wiley & Sons, New
York, second edition, 1993.
[2] G. B. Dantzig. Converting a converging algorithm into a polynomially bounded algorithm. Technical Report SOL 91-5, Stanford University, 1991
[3] G. B. Dantzig. An ²-precise feasible solution to a linear program with a convexity
constraint in ²12 iterations independent of
problem size. Technical Report SOL 92-5,
Stanford University, 1992.
[4] M. Epelman and R. M. Freund. Condition
number complexity of an elementary algorithm for resolving a conic linear system.
Working Paper OR 319-97, Massachusetts
Institute of Technology, 1997.
[5] M. Epelman and R. M. Freund. Condition
number complexity of an elementary algorithm for computing a reliable solution of
a conic linear system. Mathematical Programing, 88:451-485, 2000.
[6] J. P. M. Gonçalves. A Family of Linear Programming Algorithms Based on
the Von Neumann Algorithm. PhD thesis,
Lehigh University, Bethlehem, PA, 2004.
[7] J. P. M. Gonçalves, R. H. Storer and J.
Gondzio. New Algorithms for Linear Programming Based on an Algorithm by Von
Neumann. Technical Report, Lehigh University, 2005.