Abstract
In this paper we present a redesign of a linear algebra kernel
of an interior point method to avoid the explicit use of problem matrices.
The only access to the original problem data needed are the matrix-vector
multiplications with the Hessian and Jacobian matrices.
Such a redesign requires the use of suitably preconditioned iterative
methods and imposes restrictions on the way the preconditioner is computed.
A two-step approach is used to design a preconditioner. First, the Newton
equation system is regularized to guarantee better numerical properties
and then it is preconditioned.
The preconditioner is implicit, that is, its computation requires
only matrix-vector multiplications with the original problem data.
The method is therefore well-suited to problems in which matrices are not
explicitly available and/or are too large to be stored in computer memory.
Numerical properties of the approach are studied including the analysis
of the conditioning of the regularized system and that of the preconditioned
regularized system. The method has been implemented and preliminary
computational results for small problems limited to 1 million
of variables and 10 million of nonzero elements demonstrate
the feasibility of the approach.
Key words: Linear Programming, Quadratic Programming, Matrix-Free, Interior Point Methods, Iterative Methods, Implicit Preconditioner.