Efficient Preconditioners for Interior Point Methods via a new Schur Complement-Based Strategy

DOI10.1137/21M1416552zbMATH Open1508.65020arXiv2104.12916MaRDI QIDQ6366189FDOQ6366189

Publication date: 26 April 2021

Abstract: We propose a novel preconditioned inexact primal-dual interior point method for constrained convex quadratic programming problems. The algorithm we describe invokes the preconditioned conjugate gradient method on a new reduced Schur complement KKT system, in implicit form. In contrast to standard approaches, the Schur complement formulation we consider enables reuse of the factorization of the KKT matrix with rows and columns corresponding to inequality constraints excluded, across all interior point iterations. Further, two new preconditioners are presented for the resulting reduced system, that alleviate the ill-conditioning associated with slack variables in primal-dual interior point methods. Each of the preconditioners we propose also provably reduces the number of unique eigenvalues for the coefficient matrix, and thus the CG iteration count. One preconditioner is efficient when the number of equality constraints is small, while the other is efficient when the number of remaining degrees of freedom is small. Numerical experiments with synthetic problems and problems from the Maros-M'esz'aros QP collection show that our preconditioned inexact interior point solvers are effective at improving conditioning and reducing cost. Across all test problems for which the direct method is not fastest, our preconditioned methods achieve a reduction in cost by a geometric mean of

1.432

relative to the best alternative preconditioned method for each problem.

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Computational methods for sparse matrices (65F50) Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10)

This page was built for publication: Efficient Preconditioners for Interior Point Methods via a new Schur Complement-Based Strategy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6366189)