Inertia-controlling methods for general quadratic programming

P. F. Gill, W. Murray, M. A. Saunders, M. H. Wright

Research output: Contribution to journalArticlepeer-review

Abstract

Active-set quadratic programming (QP) methods use a working set to define the search direction and multiplier estimates. In the method proposed by Fletcher in 1971, and in several subsequent mathematically equivalent methods, the working set is chosen to control the inertia of the reduced Hessian, which is never permitted to have more than one nonpositive eigenvalue. (Such methods will be called inertia-controlling.) This paper presents an overview of a generic inertia-controlling QP method, including the equations satisfied by the search direction when the reduced Hessian is positive definite, singular and indefinite. Recurrence relations are derived that define the search direction and Lagrange multiplier vector through equations related to the Karush-Kuhn-Tucker system. Discussion is included of connections with inertia-controlling methods that maintain an explicit factorization of the reduced Hessian matrix.

Original languageEnglish (US)
Pages (from-to)1-36
Number of pages36
JournalSIAM Review
Volume33
Issue number1
DOIs
StatePublished - 1991

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Inertia-controlling methods for general quadratic programming'. Together they form a unique fingerprint.

Cite this