Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/306752
Type: TESE DIGITAL
Title: Redução de iterações dos métodos de pontos interiores com iteração continuada
Title Alternative: Interior point methods iteration reduction with continued iteration
Author: Berti, Lilian Ferreira, 1988-
Advisor: Oliveira, Aurelio Ribeiro Leite de, 1962-
Abstract: Resumo: Os métodos de pontos interiores têm sido extensivamente utilizado para resolver os problemas de programação linear de grande porte. Entre todas as variações de métodos de pontos interiores, o preditor corretor com múltiplas correções de centralidade apresenta um grande destaque, devido a sua eficiência e rápida convergência. Este método, necessita resolver sistemas lineares, em cada iteração, para determinar a direção de busca, correspondendo ao passo que requer mais tempo de processamento. Neste trabalho, a iteração continuada é apresentada e introduzida ao método preditor corretor com múltiplas correções de centralidade, com objetivo reduzir o número de iterações e o tempo computacional deste método para determinar a solução de problemas de programação linear. A iteração continuada consiste em determinar uma nova direção combinada com a direção de busca dos métodos de pontos interiores. Apresentamos duas novas direções continuadas e duas formas diferentes de utilizá-las, propondo um aumento no tamanho dos passos a serem dados na direção de busca, acelerando a convergência do método. Além disso, utilizamos o algoritmo de ajustamento ótimo para p coordenadas para determinar melhores pontos iniciais para o método de pontos interiores em conjunto com a iteração continuada. Experimentos computacionais foram realizados e os resultados obtidos ao incorporar a iteração continuada com o método de pontos interiores preditor corretor e as múltiplas correções de centralidade são superiores à abordagem tradicional. A utilização do algoritmo de ajustamento ótimo para p coordenadas na nova abordagem leva a resultados semelhantes

Abstract: The interior point methods have been extensively used to solve large-scale linear programming problems. Among all variations of interior point methods, the predictor corrector with multiple centrality corrections is the method of choice due to its efficiency and fast convergence. This method requires solving linear systems, to determine the search direction corresponding to the step that requires more processing time, in each iteration. In this work, the continued iteration is presented and introduced to the predictor corrector method with multiple centrality corrections, in order to reduce the number of iterations and the computational time to determine the linear programming problems solution. The continued iteration consists of determining a new direction combined with the search direction of the interior point methods. Two new continued directions and two different ways of being used, increasing of the steps sizes taken in the search direction, speeding up the convergence of the method. In addition, we use the optimal adjustment algorithm for p coordinates to determine the best starting point for the interior point method in conjunction with the continued iteration. Computational experiments were performed and the results achieved by incorporating the continued iteration in the predictor corrector interior point method and multiple centrality corrections outperform the traditional approach. Using the optimal adjustment algorithm for p coordinates leads to similar results
Subject: Métodos de pontos interiores
Programação linear
Métodos numéricos
Editor: [s.n.]
Date Issue: 2016
Appears in Collections:IMECC - Dissertação e Tese

Files in This Item:
File SizeFormat 
Berti_LilianFerreira_D.pdf683.94 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.