Optimization Online


Bounds on Eigenvalues of Matrices Arising from Interior-Point Methods

Chen Greif (greif***at***cs.ubc.ca)
Erin Moulding (moulding***at***math.ubc.ca)
Dominique Orban (dominique.orban***at***gerad.ca)

Abstract: Interior-point methods feature prominently among numerical methods for inequality-constrained optimization problems, and involve the need to solve a sequence of linear systems that typically become increasingly ill-conditioned with the iterations. To solve these systems, whose original form has a nonsymmetric 3x3 block structure, it is common practice to perform block Gaussian elimination and either solve the resulting reduced saddle-point system, or further reduce the system to the normal equations and apply a symmetric positive definite solver. In this paper we use energy estimates to obtain bounds on the eigenvalues of the matrices, and conclude that the original unreduced matrix has more favorable eigenvalue bounds than the alternative reduced versions. We also examine regularized variants of those matrices that allow to do away with typical regularity assumptions.

Keywords: primal-dual interior-point methods, convex quadratic optimization, indefinite linear systems, eigenvalues, condition number, inertia, eigenvalue bounds, regularization

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: Cahier du GERAD G-2012-42, GERAD, Montreal, Canada, 2012.

Download: [PDF]

Entry Submitted: 08/07/2012
Entry Accepted: 08/07/2012
Entry Last Modified: 11/17/2012

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