On the solution of equality constrained quadratic programming problems arising in optimization

Nicholas I M Gould, Mary E. Hribar, Jorge Nocedal

Research output: Contribution to journalArticlepeer-review

159 Scopus citations

Abstract

We consider the application of the conjugate gradient method to the solution of large equality constrained quadratic programs arising in nonlinear optimization. Our approach is based implicitly on a reduced linear system and generates iterates in the null space of the constraints. Instead of computing a basis for this null space, we choose to work directly with the matrix of constraint gradients, computing projections into the null space by either a normal equations or an augmented system approach. Unfortunately, in practice such projections can result in significant rounding errors. We propose iterative refinement techniques, as well as an adaptive reformulation of the quadratic problem, that can greatly reduce these errors without incurring high computational overheads. Numerical results illustrating the efficacy of the proposed approaches are presented.

Original languageEnglish (US)
Pages (from-to)1376-1395
Number of pages20
JournalSIAM Journal on Scientific Computing
Volume23
Issue number4
DOIs
StatePublished - 2002

Keywords

  • Conjugate gradient method
  • Iterative refinement
  • Nonlinear optimization
  • Pre-conditioning
  • Quadratic programming

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On the solution of equality constrained quadratic programming problems arising in optimization'. Together they form a unique fingerprint.

Cite this