Global Minimization in Nonconvex All-Quadratic Programming

This paper describes a branch and bound algorithm for the global minimization of a quadratic objective function subject to quadratic constraints over a bounded interval. No assumptions are made regarding the convexity of either the objective or the constraints. The algorithm consists of three basic steps. First, a local minimum is identified. Next, an interval surrounding this point over which the point is global is determined and eliminated. This interval is determined using linear programming techniques. Finally, bounding convex envelope approximating problems are constructed and solved globally over any remaining intervals. Intervals with bounds greater than the best local minimum objective value are eliminated. Successive iterations of the algorithm take place over the current remaining interval with lowest bound. The algorithm terminates when all intervals have been eliminated. Convergence of the algorithm to a global minimum “within ϵ” in a finite number of iterations is demonstrated.

The algorithm has been programmed and tested on a wide range of problems. Computational results have been encouraging. They indicate that for problems tested the algorithm determined a good feasible local minimum rapidly. As problem size increased the majority of time was spent not in determining a local minimum but in verifying that the minimum was global.