Bound constrained quadratic programmering solved via piecewise quadratic functions: implementation

Hans Bruun Nielsen

For a copy of this paper, either

Abstract

A bound constrained quadratic program is solved via a dual problem, which is the minimization of an unbounded, piecewise quadratic function. The dual problem involves a lower bound of lambda_1, the smallest eigenvalue of a symmetric, positive matrix, and is solved by Newton iteration with line search. The report describes the implementation of the algorithm, including estimation of lambda_1, how to get a good starting point for the iteration, and up and downdating of Choleky factorization. Results of extensive testing and comparison with other methods for constrained QP are given.

Key words: Bound constrained quadratic programming, Huber's M-estimator, Condition estimation, Newton iteration, Factorization update.

IMM Technical Report 21/96

Last modified January 15, 1997

For further information, please contact, Finn Kuno Christensen, IMM
Bldg. 321, DTU, Phone: (+45) 4588 1433. Fax: (+45) 4588 1397, E-mail: fkc@imm.dtu.dk