Feasibility Verification and Upper Bound Computation in Global Minimization Using Approximate Active Index Sets

Summary

We propose a new upper bounding procedure for global minimization problems with continuous variables and possibly nonconvex inequality and equality constraints. Upper bounds are crucial for standard termination criteria of spatial branch-and-bound (SBB) algorithms to ensure that they can enclose globally minimal values sufficiently well. However, whereas for most lower bounding procedures from the literature, convergence on smaller boxes is established, this does not hold for several methods to compute upper bounds even though they often perform well in practice. In contrast, our emphasis is on the convergence. We present a new approach to verify the existence of feasible points on boxes, on which upper bounds can then be determined. To this end, we resort to existing convergent feasibility verification approaches for purely equality and box constrained problems. By considering carefully designed modifications of subproblems based on the approximation of active index sets, we enhance such methods to problems with additional inequality constraints. We prove that our new upper bounding procedure finds sufficiently good upper bounds so that termination of SBB algorithms is guaranteed after a finite number of iterations. Our theoretical findings are illustrated by computational results on a large number of standard test problems. These results show that compared with interval Newton methods from the literature, our proposed method is more successful in feasibility verification for both, a full SBB implementation (42 instead of 26 test problems) and exhaustive sequences of boxes around known feasible points (120 instead of 29 test problems).