Iterative Optimizers

2Difficulty of the Difficulty

It is difficult to define the difficulty of a problem! We shall do it first in an informal manner:

DEFINITION 2.1.– For a given optimizer, the difficulty of a problem is the effort to find an acceptable solution.

We must now give rigorous meaning, namely quantifiable in this case, to the terms effort and acceptable solution.

2.1. Effort and budgets

Since in practice the optimizers concerned here are computer programs, a simple idea is to consider the computing resources that have been employed, processor time in particular. Storage spaces could also be taken into account, but this is increasingly less a limitation.

However, this measure depends on the computer, on the operating system, on the language in which the code was written and even on the somewhat clever way in which the algorithm was coded. From one researcher to another, results are thus not always reproducible.

Hence, I shall take here another measure, all the more conventional: the number of evaluations made in the search space. Then, the budget will be the maximum number of evaluations allowed. We shall distinguish the partial budget for a single optimizer execution and the total budget, which can be dedicated to optimization. The latter is thus generally the sum of several partial budgets, not necessarily all equal (Clerc 2015).

It should be noted that, depending on algorithms, the effort is not necessarily equal to the number of sampled points, for several reasons:

• – a point can ...