Updating constraint preconditioners for KKT systems in quadratic programming via low-rank corrections
For practitioners solving large-scale quadratic programs via interior point methods, this provides a more efficient preconditioning strategy, though it is an incremental improvement over existing constraint preconditioners.
This work proposes a procedure to update constraint preconditioners for KKT systems in interior point methods for quadratic programming using low-rank corrections, which reduces computational cost. The method, combined with an adaptive strategy, improves performance on large problems.
This work focuses on the iterative solution of sequences of KKT linear systems arising in interior point methods applied to large convex quadratic programming problems. This task is the computational core of the interior point procedure and an efficient preconditioning strategy is crucial for the efficiency of the overall method. Constraint preconditioners are very effective in this context; nevertheless, their computation may be very expensive for large-scale problems, and resorting to approximations of them may be convenient. Here we propose a procedure for building inexact constraint preconditioners by updating a "seed" constraint preconditioner computed for a KKT matrix at a previous interior point iteration. These updates are obtained through low-rank corrections of the Schur complement of the (1,1) block of the seed preconditioner. The updated preconditioners are analyzed both theoretically and computationally. The results obtained show that our updating procedure, coupled with an adaptive strategy for determining whether to reinitialize or update the preconditioner, can enhance the performance of interior point methods on large problems.