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

作者：Velazco M I; Oliveira A R L^*; Campos F F

来源：Optimization Methods and Software, 2010, 25(2): 321-332.

DOI：10.1080/10556780902992829

• interior-point methods
• preconditioners
• iterative methods

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.

• 出版日期2010