Optimization Online


Updating constraint preconditioners for KKT systems in quadratic programming via low-rank corrections

Stefania Bellavia (stefania.bellavia***at***unifi.it)
Valentina De Simone (valentina.desimone***at***unina2.it)
Daniela di Serafino (daniela.diserafino***at***unina2.it)
Benedetta Morini (benedetta.morini***at***unifi.it)

Abstract: 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.

Keywords: convex quadratic programming, interior point methods, KKT systems, constraint preconditioners, matrix updates.

Category 1: Nonlinear Optimization (Quadratic Programming )


Download: [PDF]

Entry Submitted: 11/29/2013
Entry Accepted: 11/29/2013
Entry Last Modified: 09/20/2015

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