Equivalence of some quadratic programming algorithms |
| |
Authors: | Michael J Best |
| |
Institution: | (1) Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada |
| |
Abstract: | We formulate a general algorithm for the solution of a convex (but not strictly convex) quadratic programming problem. Conditions
are given under which the iterates of the algorithm are uniquely determined. The quadratic programming algorithms of Fletcher,
Gill and Murray, Best and Ritter, and van de Panne and Whinston/Dantzig are shown to be special cases and consequently are
equivalent in the sense that they construct identical sequences of points. The various methods are shown to differ only in
the manner in which they solve the linear equations expressing the Kuhn-Tucker system for the associated equality constrained
subproblems. Equivalence results have been established by Goldfarb and Djang for the positive definite Hessian case. Our analysis
extends these results to the positive semi-definite case.
This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A8189. |
| |
Keywords: | Quadratic Programming Equivalence of Algorithms |
本文献已被 SpringerLink 等数据库收录! |
|