Properties and numerical testing of a parallel global optimization algorithm

In the framework of multistart and local search algorithms that find the global minimum of a real function f(x), x ∈ S ⊆ Rn, Gaviano et alias proposed a rule for deciding, as soon as a local minimum has been found, whether to perform or not a new local minimization. That rule was designed to minimize the average local computational cost eval1(·) required to move from the current local minimum to a new one. In this paper the expression of the cost eval2(·) of the entire process of getting a global minimum is found and investigated; it is shown that eval2(·) has among its components eval1(·) and can be only monotonically increasing or decreasing; that is, it exhibits the same property of eval1(·). Moreover, a counterexample is given that shows that the optimal values given by eval1(·) and eval2(·) might not agree. Further, computational experiments of a parallel algorithm that uses the above rule are carried out in a MatLab environment.