This article is cited in 6 papers

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

A. G. Perevozchikov

Moscow

Abstract: 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)})$, $r<1$ and to $O(\ln\varepsilon_0^{-1})$ if $r=1$.

UDC: 519.85

MSC: Primary 90C30; Secondary 90C60, 90C35, 65K05

Received: 11.01.1989
Revised: 25.09.1989

 English version: USSR Computational Mathematics and Mathematical Physics, 1990, 30:2, 28–33

Bibliographic databases:

• 
•