Iterative solution of linear systems arising from interior point methods

Neste trabalho, consideramos o método preditor-corretor, que é uma das variantes mais importantes dos métodos de pontos interiores devido à sua eficiência e convergência rápida. No método preditor-corretor, é preciso resolver dois sistemas lineares a cada iteração para determinar a direção preditora-corretora. A resolução desses sistemas é o passo que requer mais tempo de processamento, devendo, assim, ser realizada de maneira eficiente. Para obter a solução dos sistemas lineares do método preditor-corretor, consideramos dois métodos do subespaço de Krylov: MINRES e GC (método dos gradientes conjugados). Para que esses métodos convirjam mais rapidamente, um precondicionador especialmente desenvolvido para os sistemas lineares oriundos dos métodos de pontos interiores é usado. Experimentos computacionais, em um conjunto variado de problemas de programação linear, foram realizados com o intuito de analisar a eficiência e robustez dos métodos de solução dos sistemas lineares.In this work, we consider the predictor-corrector method, which is one of the most important variants of interior point methods due to its efficiency and fast convergence. In the predictor-corrector method, we must solve two linear systems at each iteration to determine the predictor-corrector direction. The solution of these systems is the step that requires more processing time and should therefore be performed efficiently. For the solution of linear systems are two Krylov subspace methods considered: MINRES and CG(the conjugate-gradient method). For these methods a preconditioner specially developed for linear systems arising from interior point methods is used. Computational experiments on a set of linear programming problems were performed in order to analyze the efficiency and robustness of the methods when solving such linear systems