Groupe d’études et de recherche en analyse des décisions


Global Minimization of Indefinite Quadratic Functions Subject to Box Constraints

, , et

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 to curtail the search. Computational experiments are reported. Comparison is made with an interval arithmetic implementation.

, 26 pages