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

• Ano de defesa: 2005
• Autor(a) principal: Silvana Bocanegra
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; UFMG
• Palavras-chave em Português: matemática computacional; otimização; Algoritmos; Programação linear; Computação
• Link de acesso: http://hdl.handle.net/1843/RVMR-6JTN72

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.