Método de pontos interiores com corretor Quasi-Newton

Abstract

Neste trabalho, foram estudados métodos de pontos interiores em problemas de programação linear com o objetivo de propor um algoritmo preditor-corretor que utilizasse uma abordagem Quasi-Newton, na expectativa de que isso tornasse o método mais barato computacionalmente. Para a elaboração deste algoritmo, primeiramente foi estudada a teoria dos métodos de pontos interiores. Em seguida, estudou-se a teoria de convergência do método de Broyden, um famoso método Quasi-Newton, para auxiliar na elaboração de uma teoria de convergência para o algoritmo proposto. Com base em dois métodos preditores-corretores encontrados na literatura, um algoritmo preditor-corretor é proposto no qual o passo preditor, de modo usual, realiza um passo de Newton, enquanto que o passo corretor realiza alguns passos Quasi-Newton. Inspirando-se na demonstração da convergência local do método de Broyden, provou-se a convergência local do algoritmo proposto. Uma implementação computacional deste algoritmo foi feita na linguagem Julia para que aspectos práticos do algoritmo pudessem ser observados. Foram realizados testes tanto em problemas pequenos quanto problemas grandes. Nos problemas pequenos, os resultados foram excelentes, tendo ocorrido a convergência para a solução em todos os problemas testados. Já em problemas grandes presentes na biblioteca NETLIB, o algoritmo também foi capaz de resolver a maioria deles, embora tenha tido um desempenho inferior a uma implementação computacional de um método preditor-corretor fornecida pelo pacote da linguagem Julia chamado Tulip.

In this work, it was studied interior point methods in linear programing problems with the objective of proposing a predictor-corrector algorithm that uses a Quasi-Newton approach. In order to elaborate this algorithm, firstly the theory of interior point methods was studied. Then, the local convergency theory of the Broyden's method, a famous Quasi-Newton method, was studied to assist in the elaboration of a local convergency theory for the proposed algorithm. Based in two predictor-corrector algorithms found in the literature, a predictor-corrector algorithm was proposed, in which the predictor step, as usual, performs one Newton step, while the corrector step performs a few Quasi- Newton steps. Taking inspiration from the proof of the local convergence of the Broyden's method, it was proved the local convergence of the proposed algorithm. A computational implementation of this algorithm was made in Julia language so that practical aspects of the algorithm could be observed. Tests were made both in small problems and big problems. In small problems, the results were excelent, where convergence to the solution has ocurred in all problems tested. In problems from the NETLIB test set, the algorithm was also able to solve most of them, although it performed worse than a computational implementation of a predictor-corrector algorithm provided by a Julia language package named Tulip.