The General Branch and Bound Algorithm

 

Both find_roots and find_global_min are based on the following abstract procedure. Such procedures are called branch and bound procedures: An initial search region is considered, and possibly subdivided into subregions ("branching"). Each of the subregions is in turn considered (by "bounding" an objective function value, etc.), and possibly subdivided in the same way as the initial region.

Here, the search region is a box , that is an interval vector . For example, a search region could be

Algorithm 1 (Abstract Branch-and-Bound Pattern for Optimization)

INPUT: an initial box .

OUTPUT: a list of boxes that have been proven to contain critical points and a list of boxes with small objective function values, but which could not otherwise be resolved.

1. Initialize a list of boxes by placing the initial search region in .
2. DO WHILE .
   1. Remove the first box from . (Note: The boxes in are in general inserted in a particular order, depending on the actual algorithm.);
   2.   (Process ) Do one of the following:
      • reject ;
      • reduce the size of ;
      • determine that contains a unique critical point, then find the critical point to high accuracy;
      • subdivide to make it more likely to succeed at rejecting, reducing, or verifying uniqueness.
   3.   Insert one or more boxes derived from onto , or , depending on the size of the resulting box(es) from Step 2b and whether the (possible) computational existence test in that step has determined a unique critical point.
   END DO

End Algorithm 1

In GlobSol, the rejection proceeds with an elementary application of interval arithmetic, as described in §5.2. Existence / uniqueness verification is done with interval Newton methods, as in §6.

Subdivision proceeds by generalized bisection, epsilon-inflation, and box complementation. For details, see, [8], especially [8, Chapter 5,].