Aimo Törn: Global Optimization


Previous slide - Next slide

Complexity of Problems

Embedded or isolated global minimizers.

Embedded global minimum means that there exist non-global minimizers near a global minimizer, so that exploration (eg. adaptive sampling) near these leads to detecting better and better minima and eventually the global minimum. One such case is that the minima are at the surface of a bowl with the global minimum at the bottom.

If the global minimum is embedded this means that the region of attraction of f* may be found by such an exploration even if the size of the region of attraction is small.

The number of local minimizers.

The number of minimizers and the size of the region of attraction of the global minimum can be expected to be dependent of each other. One would expect that the size is a decreasing function of the number of minimizers.

However, it is an important feature of its own, because local search will become increasingly ineffective for an increasing number of local minimizers. So for instance in the extreme case when all points are local minimizers local search will be completely unproductive.