Um Algoritmo de Ponto Interior-Inviável com Complexidade O[sqrt(n)L] Iterações para Programação Linear

Informações:

Publicações do PESC

Título
Um Algoritmo de Ponto Interior-Inviável com Complexidade O[sqrt(n)L] Iterações para Programação Linear
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
7/8/1998
Resumo
Neste trabalho descrevemos a teoria de ponto-interior-inviável existente na literatura e construímos um algoritmo de ponto-interior-inviável para a programação linear. Iniciamos o estudo deste algoritmo com um algoritmo conceitual primal que usa oráculo e nos fornece uma estratégia para manipularmos os parâmetros associados às viabilidade e otimalidade. Este algoritmo indica um caminho para o estudo da complexidade em iterações. Então, especificamos o oráculo e desenvolvemos um algoritmo completo que atinge a complexidade O[sqrt(n)L] iterações para passos curtos, com uma abordagem primal-dual tal que permitimos inviabilidade primal, mas mantemos viabilidade dual.
Abstract
In this work we describe the theory of infeasible-interior-point existing in the literature and we propose an infeasible-interior-point algorithm for linear programming. We start the studv of this algorithm with a primal conceptual algorithm that uses an oracle. and provides a strategy to manipulate the parameters associated with feasibility and optimality. This indicates a way toward the study of complexity in iterations. Then, we specify the oracle and develop a complete algorithm which achieves the complexity O[sqrt(n)L]-iteration for short steps with a primal-dual aproach such that we permit primal infeasibility, but we maintain dual feasibility.
Arquivo
729.pdf
Topo