Optimization Online


BFGS-like updates of constraint preconditioners for sequences of KKT linear systems

Luca Bergamaschi (luca.bergamaschi***at***unipd.it )
Valentina De Simone(valentina.desimone***at***unina2.it)
Daniela di Serafino(daniela.diserafino***at***unina2.it)
Angeles Martinez(acalomar***at***dmsa.unipd.it)

Abstract: We focus on efficient preconditioning techniques for sequences of KKT linear systems arising from the interior point solution of large convex quadratic programming problems. Constraint Preconditioners (CPs), though 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 interior point iteration. We overcome this problem by computing the CP from scratch only at selected interior point 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 for symmetric positive definite matrices proposed by Gratton, Sartenaer and Tshimanga in [SIAM J. Optim. 2011; 21(3):912--935], 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 to 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.

Keywords: KKT linear systems; constraint preconditioners; BFGS-like updates, interior point methods

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Quadratic Programming )


Download: [PDF]

Entry Submitted: 11/04/2016
Entry Accepted: 11/04/2016
Entry Last Modified: 11/04/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society