Domain Contraction in Nonlinear Programming: Minimizing a Quadratic Concave Objective Over a Polyhedron

Using linear underestimating approximations and their dual solutions, we develop new results for the nonconvex problem of minimizing a quadratic concave function under linear constraints. For solving this problem, which has such important management applications as economies of scale, fixed charge, and quadratic assignment problems, some results provide and tighten bounds on the global minimum value, while others identify the domains of the variables which may be excluded from further consideration. This leads to successive reduction of domains containing a global solution, called domain contraction, and ideally, to a solution with the objective value within some acceptable error level. For most results, specific problem instances are provided to establish their use in theory.

In practice, experience with solving the problems presented here indicates that a combination of the proposed domain contraction via linear underestimation and its dual information with the branch and bound approach offers a computational strategy competitive with the currently dominant methods: combinations of branch and bound with (1) cutting planes, (2) relaxation, or (3) domain partitioning. Problems with up to 100 variables and up to 50 linear constraints (50 × 100), comparable in difficulty and size with the largest published in the literature, are solved and included in the initial implementation of the approach.