Escolha Adiada de Parâmetros em Métodos de Pontos Interiores para Programação Linear

Resumo

A técnica de escolha atrasada dos parâmetros de perturbação e tamanho do passo será utilizada com o objetivo de reduzir o número de iterações necessárias para a convergência dos métodos de pontos interiores do tipo primal-dual. Esta técnica procura reduzir o número de iterações adiando a escolha destes parâmetros obtendo assim pontos com melhores propriedades. Para obter os parâmetros é necessário resolver sistemas lineares adicionais com a mesma matriz. No entanto, na grande maioria das iterações o parâmetro de perturbação ótimo é nulo e identificar a priori esta situação pode levar a implementações muito eficientes, pois seria necessário resolver somente um sistema linear nestas iterações. O objetivo deste projeto consiste em detectar iterações onde uma ou duas resoluções de sistemas lineares são suficientes para obter uma boa direção através tanto de heurísticas quanto propriedades teóricas. Desta forma pretende-se desenvolver uma implementação que reduza o tempo computacional total através da combinação de iterações mais baratas com um menor número de iterações para obtenção da convergência.