Premium
BFGS‐like updates of constraint preconditioners for sequences of KKT linear systems in quadratic programming
Author(s) -
Bergamaschi L.,
De Simone V.,
Serafino D.,
Martínez A.
Publication year - 2018
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2144
Subject(s) - karush–kuhn–tucker conditions , broyden–fletcher–goldfarb–shanno algorithm , mathematics , mathematical optimization , conjugate gradient method , preconditioner , positive definite matrix , quadratic programming , linear system , factorization , convergence (economics) , computer science , algorithm , eigenvalues and eigenvectors , iterative method , computer network , mathematical analysis , physics , asynchronous communication , quantum mechanics , economics , economic growth
Summary We focus on efficient preconditioning techniques for sequences of Karush‐Kuhn‐Tucker (KKT) linear systems arising from the interior point (IP) solution of large convex quadratic programming problems. Constraint preconditioners (CPs), although very effective in accelerating Krylov methods in the solution of KKT systems, have a very high computational cost in some instances, because their factorization may be the most time‐consuming task at each IP iteration. We overcome this problem by computing the CP from scratch only at selected IP iterations and by updating the last computed CP at the remaining iterations, via suitable low‐rank modifications based on a BFGS‐like formula. This work extends the limited‐memory preconditioners (LMPs) for symmetric positive definite matrices proposed by Gratton, Sartenaer and Tshimanga in 2011, by exploiting specific features of KKT systems and CPs. We prove that the updated preconditioners still belong to the class of exact CPs, thus allowing the use of the conjugate gradient method. Furthermore, they have the property of increasing the number of unit eigenvalues of the preconditioned matrix as compared with the generally used CPs. Numerical experiments are reported, which show the effectiveness of our updating technique when the cost for the factorization of the CP is high.