The complexity of the computation of the global extremum in a class of multi-extremum problems

A. G. Perevozchikov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 30 (1990) no. 3, pp. 379-387

Résumé

Unconditional global minimization of a Lipschitz function in $E^n$ is considered, and a difference method for solving the problem, accurate to within $\varepsilon_0>0$, is proposed. In the general case this involves computing $O(\varepsilon_0^{-n})$ values of the function. A special class of functions is introduced, with the property that the measure of the set of $\varepsilon$-optimal points increases at a power rate $O(\varepsilon^{rn})$, $r\in(0,1]$. It is shown that for a successive search algorithm of the branch and-bound type, the total number of computed values of a function in the class may be reduced to $O(\varepsilon_0^{-n(1-r)})$, $r1$ and to $O(\ln\varepsilon_0^{-1})$ if $r=1$.