A weighted gram-schmidt method for convex quadratic programming

Philip E. Gill, Nicholas I.M. Gould, Walter Murray, Michael A. Saunders, Margaret H. Wright

Research output: Contribution to journalArticlepeer-review

Abstract

Range-space methods for convex quadratic programming improve in efficiency as the number of constraints active at the solution decreases. In this paper we describe a range-space method based upon updating a weighted Gram-Schmidt factorization of the constraints in the active set. The updating methods described are applicable to both primal and dual quadratic programming algorithms that use an active-set strategy. Many quadratic programming problems include simple bounds on all the variables as well as general linear constraints. A feature of the proposed method is that it is able to exploit the structure of simple bound constraints. This allows the method to retain efficiency when the number of general constraints active at the solution is small. Furthermore, the efficiency of the method improves as the number of active bound constraints increases.

Original languageEnglish (US)
Pages (from-to)176-195
Number of pages20
JournalMathematical Programming
Volume30
Issue number2
DOIs
StatePublished - Oct 1984

Keywords

  • Active-Set Methods
  • Bound Constraints
  • Convex Quadratic Programming
  • Range-Space Methods
  • Updated Orthogonal Factorizations

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A weighted gram-schmidt method for convex quadratic programming'. Together they form a unique fingerprint.

Cite this