Description of Methods

    Methods with Guarantees
                Bisection Methods
                Interval Methods

These methods are in global optimization also called covering methods or branch-and-bound methods. These methods guarantee that a solution with a given accuracy is obtained. The price paid for this guarantee, however, is that some a priori information of the function must be available.

For bisection methods the information required is that a constant M is known such that the problem function f belongs to the class L(M) of Lipschitz- continuous functions.

When the point cover of the region is dense enough it can then be deduced that the difference between the true global minimum and the best value seen (in some cover point) will be less than some given threshold. [Piyavskii 1972]

For interval methods the function is assumed to be twice differentiable and the first and second derivative are assumed to have a finite number of roots. Using interval arithmetic a union of intervals of decreasing size containing the global minimum is obtained at each step. The algorithm stops when the size reaches some preset limit. [Moore 1966]