Números de Condicionamento e Propriedades Limites da Direção Afim-escala em Programação Linear
Autores
|
1689 |
715,156
|
|
|
1690 |
715,156
|
Informações:
Publicações do PESC
Título
Números de Condicionamento e Propriedades Limites da Direção Afim-escala em Programação Linear
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
2/3/1998
Resumo
Dois números de condição descritos por Ye, Vavasis, Stewart, Todd e outros, têm sido usados para estudar a complexidade dos algoritmos de pontos interiores. 0 primeiro é dado pela "menor variável grande" na face ótima do problema de programação linear; e o outro pelo supremo das normas de todas as projeções oblíquas sobre o espaço imagem de A'. 0 primeiro tem a desvantagem de depender do conhecimento da partição ótima na sua definição, enquanto que o segundo depende só dos dados, mas não usa a estrutura do problema de programação linear.
A respeito do segundo número provamos que ele é igual ao supremo das normas das projeções oblíquas sobre o espaço nulo de A, e com relação ao primeiro mostramos uma caracterização que não depende de conhecer a partição ótima. Depois estudamos propriedades limites da direção afim-escala. Em particular calculamos um limitante para o ângulo entre todas as direções afim-escala e o vetor de custos. O limitante encontrado está relacionado com a caraterização do número de condição antes mencionado.
Abstract
Two condition numbers described by Ye, Vavasis, Stewart, Todd and others have been used to study the complexity of interior point algorithms. The first one is given bv the "smallest large variable" in the optimal face of the linear programming problem, and the other bv the supreme of the norms of all the oblique projection operators on the range space of AT. The first one has the disadvantage of depending on the knowledge of the optimal partition, and the second one, depends only on the data. but does ilot use ttie structure of the linear prograinriling problem. With respect to the second one, we show that it coincides with the supreme of the norms of all the oblique projections on the null space of A, and with respect to the first one, we give a characterization that does not depend on the knowledge of the optimal partition. Later we study limiting properties of the affine scaling direction. Particularly we compute a bound for the angle between all the affine scaling directions and the cost vector. The bound is related with the characterization of the condition number given above.
Arquivo