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 bounded 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 characterized by having the number of convex variables much more than that of concave variables. The advantages of the method is that it uses the rectangular subdivision on the subspace of concave variables. Using a easily constructed convex underestimating function to the objective function, a lower bound is obtained by solving a convex quadratic programming problem. Three variants using exhaustive, adaptive and w-subdivision are discussed. Computational results are presented for problems with 10-20 concave variables and up to 200 convex variables.