The most widely used guaranteed methods for global optimization are probably the interval-based branch-and-bound techniques. In these techniques, we start with a single box – the entire function domain – as a possible location of the global minimizer points, and then, in each step, subdivide some of the boxes, use interval computations to compute the enclosure [ F(X), F(X) ⊇ f(X) ] of the range f(X) of the objective function f(x) on each new sub-box X, and, based on these computations, eliminate the boxes which cannot contain a global minimizer point. The computational efficiency of these methods strongly depends on which boxes we select for sub-division. Traditionally, for sub-division, the algorithms selected a box with the smallest value of F(X). Recently, it was shown that the algorithm converges much faster if we select, instead, a box with the largest possible value of the ratio (&ftilde;−F(X)) / (F(X)−F(X)), where &ftilde; is a current upper bound on the actual global minimum. In this paper, we give a theoretical justification for this empirical criterion. Namely, we show that: first, this criterion is the only one that is invariant w.r.t. some reasonable symmetries; and second, that this criterion is optimal in some reasonable sense.
