Computing a hybrid preconditioner approach to solve the linear systems arising from interior point methods for linear programming using the conjugate gradient method

May 18, 2014 Posted by admin

Carla T. L. S. Ghidini, A. R. L. Oliveira and D. C. Sorensen
University of Campinas (UNICAMP), 13083-859 Campinas – SP, Brazil Department of Computational and Applied Mathematics,Rice University Houston Texas, U.S.A.

Abstract
In this work, iterative methods are used to solve the linear systems of equations arising from interior point methods. Since these systems of equations are very ill-conditioned near a solution, the design of specially tailored preconditioners is an important implementation issue. On the other hand, the early linear systems of equations do not present the same features and 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. During the initial iterations, a controlled Cholesky factorization is used. As convergence takes place, a splitting, the splitting preconditioner is adopted. Its major advantage is its excellent behavior near a solution of the linear program. 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 results regarding both: speed and robustness. An effective implementation of the splitting preconditioner relies upon finding a suitable set of linearly independent columns to form a nonsingular matrix from the constraint matrix. Several strategies to help finding such set of columns are presented. Numerical experiments are carried out in order to illustrate the performance of the given strategies.

Keywords: linear programming, interior point methods, preconditioning.

SUBSCRIBERS CAN VIEW / DOWNLOAD THIS FULL ARTICLE BY CLICKING HERE.

ACCESS THIS INDIVIDUAL ARTICLE FOR $25.00

Comments are closed.

  • Research Subjects

  • Archives

  • Annals of Management Science (AMS)

    AMS Cover
  • ISSN 2161-5012 (Print Version)
    ISSN 2161-5004 (Online Version)