Switching preconditioners using a hybrid approach for linear systems arising from interior point methods for linear programming

In general, interior point methods are successful in solving large-scale linear programming problems. Their effectiveness is determined by how fast they calculate each solution of a linear system. When solving large-scale linear systems, iterative methods are useful options since they require slightly more computational memory in each iteration and preserve the sparsity pattern of the matrix system. In this context, a common choice is the conjugate gradient method using a preconditioning strategy. Choosing a single preconditioner that fits well during all iterations of the optimization method is not an easy task, because the distribution of the eigenvalues of the system matrix may vary significantly from the first to the last iterations. In order to simplify this task, one can use different preconditioners in different iterations, in a hybrid preconditioner strategy. In the case of symmetric positive definite systems, the Controlled Cholesky Factorization achieves excellent performance for the first interior point iterations, whereas the Splitting preconditioner is very useful in the last iterations. However, since we apply a hybrid approach combining both preconditioners, it is necessary to decide when using each preconditioner. This paper addresses the critical issue of choosing between the two preconditioners of the hybrid strategy by using the condition number of the matrix system. The Ritz values obtained from the conjugate gradient method provide an approximation to the eigenvalues, which offers an estimate of the condition number. The main contribution of this research is a new heuristic to switching the preconditioners based on the estimated condition number. Numerical results for large-scale problems show that our choice to change the preconditioners adds both speed and robustness to a hybrid approach that combines the Controlled Cholesky Factorization and the Splitting preconditioner.