A DUAL-ACTIVE-SET ALGORITHM FOR POSITIVE SEMIDEFINITE QUADRATIC-PROGRAMMING

Because of the many important applications of quadratic programming, f ast and efficient methods for solving quadratic programming problems a re valued. Goldfarb and Idnani (1983) describe one such method, Well k nown to be efficient and numerically stable, the Goldfarb and Idnani m ethod suffers only from the restriction that in its original form it c annot be applied to problems which are positive semi-definite rather t han positive definite. In this paper, we present a generalization of t he Goldfarb and Idnani method to the positive semi-definite case and p rove finite termination of the generalized algorithm. In our generaliz ation, we preserve the spirit of the Goldfarb and Idnani method, and e xtend their numerically stable implementation in a natural way. (C) 19 97 The Mathematical Programming Society, Inc. Published by Elsevier Sc ience B.V.