Promising regions in optimization

Question

I have investigated the literature, but I could not find proper explanations. As we know, (meta-)heuristics try to explore promising regions of optimality. The regions are then exploited.

What is the definition of the promising regions in (meta-)heuristic optimization? How can we determine whether the algorithm is in the promising region or not, especially for the problems with unknown optima?

My idea is only that if the algorithm shows continuous improvement, we can say that the region is found. But I am not sure if my idea is totally correct.

Answer 1

The concept of promising regions (unlike many other concepts in optimization) doesn't have a mathematical definition. It is more an analogy people use to justify why exploring some¹ neighborhood of good solutions leads in practice to other good solutions in particular in derivative free optimization.

Different algorithms that exploit promising regions also exploit different things. The crossover heuristic in evolutionary algorithms which combines components of two solutions finds the result promising because assuming the objective is separable in those variables the new assignment is going to have a low value in the separate objectives². Particle Swarm Optimization instead suggest that the space between the best know and the current position of a particle is likely to yield improvements but the local optima close to the particle it knows about also should be exploited.

¹_{by some I mean it doesn't have to be close with regards to $\|\cdot\|_2$ or a similar metric as the crossover example shows}

²_{Assume we minimize $f(x,y)=g(x)+h(y)$ if $x_1,y_1$ and $x_2,y_2$ are good but $g(x_1)<g(x_2)$ but $h(y_1)>h(y_2)$ then $x_1,y_2$ is going to be better. In practice this separability is not known by evolutionary algorithm but if $x_1,y_1$ and $x_2,y_2$ stay successful in the next generation because the worse $x_2,y_1$ was generated there is again a 50% chance of $x_1,y_2$ being generated.}