Premium
Spectral estimates for unreduced symmetric KKT systems arising from Interior Point methods
Author(s) -
Morini Benedetta,
Simoncini Valeria,
Tani Mattia
Publication year - 2016
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.2054
Subject(s) - karush–kuhn–tucker conditions , mathematics , invertible matrix , interior point method , quadratic programming , limit (mathematics) , quadratic equation , block (permutation group theory) , limit point , convex optimization , mathematical optimization , regular polygon , mathematical analysis , pure mathematics , combinatorics , geometry
Summary We consider symmetrized Karush–Kuhn–Tucker systems arising in the solution of convex quadratic programming problems in standard form by Interior Point methods. Their coefficient matrices usually have 3 × 3 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. Copyright © 2016 John Wiley & Sons, Ltd.