Double splitting preconditioner: A new class of preconditioners

Abstract

We propose a splitting preconditioner generalization, where the authors present a new approach to working with the augmented system in the context of interior point methods for linear programming. It is also shown that the splitting preconditioner works very well near to a solution of the linear programming problem, a nice feature, since in such case the linear systems tend to be extremely ill-conditioned.

We introduce a double preconditioner for the augmented system, including three new parameters. In this way, it allowed us a greater range of possibilities for new preconditioners, which we call Double Splitting Preconditioner.

Furthermore, we show an important theorem that tells us that we have a variety of choices for some blocks that make up the double spliting preconditioner and that lead to the same linear system matrix (first block of the doubly splitting matrix) which is the main key to the efficiency of the proposed method. Through new parameters, we obtain a preconditioned matrix with eigenvalues far away to zero. Moreover, through appropriate choices of such parameters, we actually obtain a well conditioned matrix in the final iterations of the interior point method. And in a way, we have a priori knowledge concerning the matrix condition number in the final iterations. In fact, we have some control over the condition number along the whole iterative process.

Therefore, the main objective of this work is to provide a preconditioner that improves the condition number of the preconditioned matrix, and possibly in this way also improves the iteration number and total time required to solve the linear programming problem.

We perform numerical tests using the Matlab software, to verify the efficiency of the proposed method. In this way, we are able to verify the influence of the parameters of the double splitting preconditioner, showing that for convenient values of these parameters, there is a decrease in the number of the iterative method iterations.