L. Bergamaschi, J. Gondzio, A. Martinez, J. Pearson and S. Pougkakiotis
Abstract
In this paper, we address the efficient numerical solution
of linear and quadratic programming problems, often of large scale.
With this aim, we devise an infeasible interior point method,
blended with the proximal method of multipliers, which in turn
results in a primal-dual regularized interior point method.
Application of this method gives rise to a sequence of increasingly
ill-conditioned linear systems which cannot always be solved
by factorization methods, due to memory and CPU time restrictions.
We propose a novel preconditioning strategy which is based
on a suitable sparsification of the normal equations matrix
in the linear case, and also constitutes the foundation
of a block-diagonal preconditioner to accelerate MINRES
for linear systems arising from the solution of general quadratic
programming problems. Numerical results for a range of test problems
demonstrate the robustness of the proposed preconditioning strategy,
together with its ability to solve linear systems of very large dimension.
Key words: Primal-dual regularization, Proximal point algorithm, Interior point methods, Krylov methods, Preconditioners