Numerical solution of special linear and quadratic programs via a parallel interior-point method

This paper concerns a parallel inexact interior-point (IP) method for solving linear and quadratic programs with a special structure in the constraint matrix and in the objective function. In order to exploit these features, a preconditioned conjugate gradient (PCG) algorithm is used to approximately solve the normal equations or the reduced KKT system obtained from the linear inner system arising at each iteration of the IP method. A suitable adaptive termination rule for the PCG method enables to save computing time at the early steps of the outer scheme and, at the same time, it assures the global and the local superlinear convergence of the whole method. We analyse a parallel implementation of the method, referring some kinds of meaningful large-scale problems. In particular we discuss the data allocation and the workload distribution among the processors. The results of a numerical experimentation carried out on Cray T3E and SGI Origin 3800 show a good scalability of the parallel code and confirm the effectiveness of the method for problems with special structure. (C) 2003 Elsevier Science B.V. All rights reserved.