Geodesic
The complexity of the computation of the global extremum in a class of multi-extremum problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 30 (1990) no. 3, pp. 379-387 
A. G. Perevozchikov. The complexity of the computation of the global extremum in a class of multi-extremum problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 30 (1990) no. 3, pp. 379-387. http://geodesic.mathdoc.fr/item/ZVMMF_1990_30_3_a3/
@article{ZVMMF_1990_30_3_a3,
     author = {A. G. Perevozchikov},
     title = {The complexity of the computation of the global extremum in a~class of multi-extremum problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {379--387},
     year = {1990},
     volume = {30},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_1990_30_3_a3/}
}
TY  - JOUR
AU  - A. G. Perevozchikov
TI  - The complexity of the computation of the global extremum in a class of multi-extremum problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 1990
SP  - 379
EP  - 387
VL  - 30
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_1990_30_3_a3/
LA  - ru
ID  - ZVMMF_1990_30_3_a3
ER  - 
%0 Journal Article
%A A. G. Perevozchikov
%T The complexity of the computation of the global extremum in a class of multi-extremum problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 1990
%P 379-387
%V 30
%N 3
%U http://geodesic.mathdoc.fr/item/ZVMMF_1990_30_3_a3/
%G ru
%F ZVMMF_1990_30_3_a3

Voir la notice de l'article provenant de la source Math-Net.Ru

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$.

[1] Sukharev A. G., “Globalnyi ekstremum i metody ego otyskaniya”, Matem. metody v. issl. operatsii, Izd-vo MGU, M., 1981, 4–37 | MR

[2] Evtushenko Yu. G., “Chislennyi metod poiska globalnogo ekstremuma funktsii (perebor na neravnomernoi setke)”, Zh. vychisl. matem. i matem. fiz., 11:6 (1971), 1390–1403 | Zbl

[3] Volkov E. A., “O poiske maksimuma funktsii i priblizhennom reshenii sistemy nelineinykh uravnenii”, Tr. MIAN SSSR, 131, M., 1974, 64–80 | Zbl

[4] Vasilev N. S., “K otyskaniyu globalnogo minimuma kvazivognutoi funktsii”, Zh. vychisl. matem. i matem. fiz., 23:2 (1983), 307–313 | MR

[5] Vasilev N. S., “Aktivnyi vychislitelnyi metod poiska globalnogo minimuma vognutoi funktsii”, Zh. vychisl. matem. i matem. fiz., 24:1 (1984), 152–156 | MR

[6] Nilson N. Dzh., Printsipy iskusstvennogo intellekta, Mir, M., 1985 | MR

[7] Vasilev F. P., Chislennye metody resheniya ekstremalnykh zadach, Nauka, M., 1980 | MR

[8] Fedorov V. V., Chislennye metody maksimina, Nauka, M., 1979 | MR

[9] Fikhtengolts G. M., Kurs differentsialnogo i integralnogo ischisleniya, v. 1, Nauka, M., 1969