Spectral estimates for unreduced symmetric KKT systems arising from Interior Point methods

Benedetta Morini (benedetta.moriniunifi.it)
Valeria Simoncini (valeria.simonciniunibo.it)
Mattia Tani (mattia.tani2unibo.it)

Abstract: We consider symmetrized KKT systems arising in the solution of convex quadratic programming problems in standard form by Interior Point methods. Their coefficient matrices usually have 3x3 block structure and, under suitable conditions on both the quadratic programming problem and the solution, they are nonsingular in the limit. We present new spectral estimates for these matrices: the new bounds are established for the unpreconditioned matrices and for the matrices preconditioned by symmetric positive definite augmented preconditioners. Some of the obtained results complete the analysis recently given by Greif, Moulding and Orban in [SIAM J. Optim., 24 (2014), pp. 49-83]. The sharpness of the new estimates is illustrated by numerical experiments.

Keywords: convex quadratic programming, interior point methods, indefinite linear systems, eigenvalue bounds, preconditioners.

Category 1: Nonlinear Optimization (Quadratic Programming )

Citation: Numerical Linear Algebra with Applications, 23(5),pp. 776-800, 2016. DOI: https://doi.org/10.1002/nla.2054

Download: [PDF]

Entry Submitted: 05/16/2014
Entry Accepted: 05/16/2014
Entry Last Modified: 03/29/2021

Modify/Update this entry