Escolha otimizada de parâmetros em métodos de pontos interiores para programação linear

Autor(es)

Luiz Rafael dos Santos

• Tipo de documento: Tese de Doutorado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica
• Data de defesa: 2014-07-31

Membros da banca

Aurelio Ribeiro Leite de Oliveira; Francisco de Assis Magalhães Gomes Neto; Marta Inês Velazco Fontova; Pedro Augusto Munari; Luís Felipe Cesar da Rocha Bueno

• Orientador: Aurelio Ribeiro Leite de Oliveira; Fernando Rocha Villas Bôas

Resumo

Neste trabalho, propomos um método de pontos interiores do tipo preditor-corretor para programação linear em um contexto primal-dual, em que o próximo iterado será escolhido através de um subproblema de minimização de uma função de mérito polinomial a três variáveis: a primeira variável é o tamanho de passo, a segunda define a trajetória central e a última modela o peso que uma direção corretora deve ter. A minimização da função de mérito é feita sujeitando-a à restrições definidas por uma vizinhança da trajetória central que permite passos largos. Dessa maneira, combinamos diferentes direções, tais como preditora, corretora e de centralização com o objetivo de obter uma direção melhor. O método proposto generaliza grande parte dos métodos de pontos interiores preditores-corretores, a depender da escolha do valor das variáveis acima descritas. É feita, então uma análise de convergência do método proposto, considerando um ponto inicial que tem bom desempenho na prática, e que resulta em convergência linear dos iterados em complexidade polinomial. São feitos experimentos numéricos, utilizando o conjunto de testes Netlib, que mostram que essa abordagem é competitiva, quando comparada a implementações de pontos interiores bem estabelecidas como o PCx (AU)

• Processo FAPESP: 08/09685-8 - Escolha Adiada de Parâmetros em Métodos de Pontos Interiores para Programação Linear
• Beneficiário: Luiz Rafael dos Santos
• Modalidade de apoio: Bolsas no Brasil - Doutorado