A note on hybrid preconditioners for large-scale normal equations arising from interior-point methods

Autor: Frederico Thadeu Assis Figueiredo Campos, Aurelio Ribeiro Leite de Oliveira, M.I. Velazco
Rok vydání: 2010
Předmět:
Zdroj: Optimization Methods and Software. 25:321-332
ISSN: 1029-4937
1055-6788
DOI: 10.1080/10556780902992829
Popis: A previously developed approach for solving linear systems arising from interior-point methods applied to linear programming problems is considered and improved upon. The preconditioned conjugate gradient method is used to solve these systems in two different phases of the interior-point method: during the initial interior-point iterations, an incomplete Cholesky factorization preconditioner with controlled fill-in is used; in the second phase, near the optimal solution, a specialized preconditioner based upon the LU factorization is used to combat the high ill-conditioning of the linear systems in this phase. This approach works better than direct methods on some classes of large-scale problems. New heuristics are presented to identify the change of phases, thus achieving better computational results and solving additional problems. Moreover, new orderings of the constraint matrix columns are presented allowing savings in the preconditioned conjugate gradient method iteration number. Experiments are performed with a set of large-scale problems and both approaches are compared with respect to the number of iterations and running time.
Databáze: OpenAIRE
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje