Redução de iterações dos métodos de pontos interiores com iteração continuada

Autor(es)

Lilian Ferreira Berti

• Tipo de documento: Tese de Doutorado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Ciência da Computação
• Data de defesa: 2016-01-25

Membros da banca

Aurelio Ribeiro Leite de Oliveira; Francisco de Assis Magalhães Gomes Neto; Marta Inês Velazco Fontova; Roberto Quirino do Nascimento; Jair da Silva

• Orientador: Carla Taviane Lucke da Silva Ghidini; Aurelio Ribeiro Leite de Oliveira

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 (AU)

• Processo FAPESP: 11/20623-7 - Redução das Iterações nos Métodos de Pontos Interiores Utilizando Iteração Continuada e Algoritmos Simples
• Beneficiário: Lilian Ferreira Berti
• Modalidade de apoio: Bolsas no Brasil - Doutorado