Algoritmos de Newton-Krylov precondicionados para métodos de pontos interiores

Abstract

Interior point methods have been widely used to solve large-scale linear programming problems. The bulk of the work in these methods is computing the search direction by solving one or more linear systems. The most commom approach in interior point solvers uses Cholesky sparse factorization to solve these systems. In some problems this factorization becomes prohibitive due to storage and time limitations. Iterative approaches are more interesting in these situations. Since these systems are ill-conditioned, it is crucial to develop ecient econditioners. However it is dicult to find a preconditioning strategy that produces good performance of iterative methods over the entire course of the interior point iterations. We are proposing a hybrid approach to solve these systems. The preconditioned conjugate gradient method works in two phases. During phase I it uses a kind of incomplete Cholesky preconditioner such that fill-in can be controlled in terms of available memory. As the optimal solution of the problem is approached, the linear systems become highly ill-conditioned and the method changes to phase II. In this phase a preconditioner based on the LU factorization is found to work better near a solution of the LP problem. Thenumerical experiments reveal that the iterative hybrid approach works better than Cholesky factorization on some classes of large-scale problems.