A note on hybrid preconditioners for large-scale normal equations arising from interior-point methods. (English) Zbl 1190.65055
Summary: A previously developed approach by S. Bocanegra, F. F. Campus, and A. R. L. Oliveira [Comput. Optim. Appl. 36, No. 2–3, 149–164 (2007; Zbl 1148.90350)] 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.
MSC:
65F10 | Iterative numerical methods for linear systems |
65K05 | Numerical mathematical programming methods |
65F08 | Preconditioners for iterative methods |
65F50 | Computational methods for sparse matrices |
90C51 | Interior-point methods |
90C05 | Linear programming |