Complexity Measures Methods for generally solving such essentially unconstrained problems are those containing some technique, which explores the search region A by evaluating f for points spread out in A (eg. random sampling) and then use some local technique to possibly find the global minimum.
We postulate that the complexity in solving such problems is dependent on the following features of the problem:
- The size p* of the region of attraction of the global minimum in relation to A.
- The affordable number of function evaluations Nf.
- Embedded or isolated global minimizers.
- The number of local minimizers.
We discuss briefly how these features influence on the complexity to obtain a solution.
-------
1 A. Törn, M. Ali and S. Viitanen: Stochastic Global Optimization: Problem Classes and Solution Techniques, Journal of Global Optimization 14: 437-447, 1999.