Locatelli presents a multilevel view of global optimization (GO) problems. He shows that a GO problem can often be seen at different levels, displaying a similar structure, even if different objects are observed at each level.
First, the multilevel structure of GO problems is illustrated by using the analogy of the jewel problem: a big box contains smaller boxes, each of them containing smaller boxes, and so on. At the last level, each of the smallest boxes contains a jewel with a given value. The jewel problem consists of looking for the jewel with the highest value. That problem can be solved through successive local searches, each of them (except for the last level) consisting of evaluating a node at the level immediately above. The author points out that the difficulty of a given global minimization problem is not strictly related to the number of local minima of the objective function, but, rather, to how chaotic the positions of the local minima are. The subdivision of levels allows for the introduction of a formal measure of chaos, based on the first level at which a single object or a few objects are observed. A few examples of standard test functions are studied, ranging from “easy” to “very difficult,” where one has to go up to level three in order to observe a single object. Finally, the author claims that the identification of the degree of difficulty of a GO problem is practically fruitful, since it allows for the proposal of appropriate solving tools.