ON GLOBALLY SOLVING LINEARLY CONSTRAINED INDEFINITE QUADRATIC MINIMIZATION PROBLEMS BY DECOMPOSITION BRANCH-AND-BOUND METHOD

The global minimization of an indefinite quadratic function over a bou nded polyhedral set using a decomposition branch and bound approach is considered. The objective function consists of an unseparated convex part and a separated concave part. The large-scale problems are charac terized by having the number of convex variables much more than that o f concave variables. The advantages of the the method is that it uses the rectangular subdivision on the subspace of concave variables. Usin g a easily constructed convex underestimating function to the objectiv e function, a lower bound is obtained by solving a convex quadratic pr ogramming problem. Three variants using exhaustive, adaptive and w-sub division are discussed. Computational results are presented for proble ms with 10-20 concave variables and up to 200 convex variables.