Optimal and sub-optimal stopping rules for the multistart algorithm in global optimization (Q1802958)

This paper proposes stopping rules for the multistart algorithm for the global optimization problem `\(\text{Max}_{x\in K} f(x)\), \(K\subset R^ k\), \(k\geq 1\)'. The algorithm consists in sequentially performing local optimizations from randomly choosen starting points. The algorithm will eventually succeed in locating the global optimum. A crucial point is the decision at each step whether to stop or continue performing local optimizations. The authors introduce a cost criterion \(L(t^ 1,t^ 2,\dots,t^ n; c)=-t^*_ n+ nc\), where \(t_ i\) is the function value at the local optimum during the \(i\)th local search and \(c>0\) is a fixed constant. \(n\) is the number of local searches. Stopping rules can be deduced by considering the \(t_ i\)s as realizations of discrete random variables. This approach leads to the definition of two stopping rules. The 1-step rule gives good results in terms of computational cost vs. final accuracy.