Academic journal article Annals of Management Science

Computing a Hybrid Preconditioner Approach to Solve the Linear Systems Arising from Interior Point Methods for Linear Programming Using the Conjugate Gradient Method

Academic journal article Annals of Management Science

Computing a Hybrid Preconditioner Approach to Solve the Linear Systems Arising from Interior Point Methods for Linear Programming Using the Conjugate Gradient Method

Article excerpt

(ProQuest: ... denotes formulae omitted.)

1. Introduction

The development of sophisticated software to solve linear optimization problems by interior point methods has started since the early works on this subject. There are three main research lines aimed at improving the efficiency of such methods for solving large-scale problems: reduction of the total number of iterations, techniques to obtain a fast iteration and specific methods for particular classes of problems.

This work addresses the second one. Iterative methods are used to solve the linear systems of equations which are the most expensive step at each iteration of interior point methods. Since such systems are very ill-conditioned near a solution, the design of specially tailored preconditioners is an important implementation issue. On the other hand, since the early linear systems do not present the same features, it is advisable to adopt hybrid preconditioners that begin as a generic preconditioner and adapt during the course of the iteration, becoming ever more specialized as convergence takes place (Bocanegra et al., 2007).

During the initial iterations a controlled Cholesky factorization is adopted (Campos & Birkett, 1998). Its major advantage is the control parameter that allows the preconditioner to vary all way from a diagonal preconditioner to the full Cholesky factorization, if desired. At the onset of convergence, a splitting preconditioner is used (Oliveira & Sorensen, 2005). Its major advantage is its excellent behavior near a solution of the linear program. However, this desirable feature has a price: the preconditioner could be very expensive to compute. A careful implementation must be performed in order to achieve competitive numerical results regarding both: speed and robustness. An effective implementation of the splitting preconditioner depends crucially upon finding a suitable set of linearly independent columns to form a nonsingular matrix, to be factored, from the constraint matrix.

There are several techniques for finding such a set of columns such as the delayed update form for the LU factorization, the symbolic dependent columns, the symbolic independent columns, the combination of symbolic dependent and independent columns and strongly connected components. Some are well known and already applied in other contexts (Coleman & Pothen, 1987; Duff & Reid, 1986; El-Bakry et al., 1994). Others were developed to compute the splitting preconditioner (Oliveira, 1997; Oliveira & Sorensen, 2005). Among the techniques used is the study of the nonzero structure of the constraint matrix to speed up the numerical factorization, such as using key columns, symbolically dependent and independent columns, finding strongly connected components (Oliveira & Sorensen, 2005). Other implementation issues, include ways for changing preconditioners, are also discussed in (Ghidini et al., 2012; Velazco et al., 2010).

The choice of the controlled factorization is justified due to the possibility of computing an inexpensive preconditioner in the initial interior point iterations and, as the linear systems become more ill conditioned, the controlled preconditioner can be improved with just the change of a parameter value. Numerical experiments illustrating the effectiveness of such strategies in order to solve large scale linear programming problems are presented in Bocanegra et al. (2007) and Velazco et al. (2010).

This work is organized as follows: Section 2 presents the predictor-corrector interior point method, defines its search directions and explains how to solve the resulting linear systems of equations. The controlled Cholesky factorization and splitting preconditioners are discussed in this section. Sections 3 and 4 study several techniques in order to achieve an efficient implementation of the splitting preconditioner. In Section 5 the numerical experiments are shown and discussed. Conclusions follow in Section 6. …

Search by... Author
Show... All Results Primary Sources Peer-reviewed


An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.