Global minimization of indefinite quadratic functions subject to box constraints

A branch-and-bound algorithm is proposed for global minimization of indefinite quadratic functions subject to box constraints. Branching is done according to the sign of first-order derivatives. New tests based on the compatibility of signs of several first-order derivatives and on various bounding procedures, allow curtailment of the search. Computational experiments are reported. Comparison is made with an interval arithmetic implementation. © 1993 John Wiley & Sons, Inc.