On efficiency of parallel algorithms
for global optimization of functions of several variables
A.N. Kovartsev, D.A. Popova-Kovartseva
Full text of article: Russian language.
Abstract:
We consider the problem of constructing efficient parallel algorithms for global optimization. The results are of given the qualitative analysis of the possibility of overcoming the exponential growth of global optimization problems for functions of general form, using the commonly used algorithmic techniques to accelerate convergence (Lipschitz conditions, reduction, local technique). Shown that the construction of efficient algorithms for global optimization, for the dimensions of 100 or more variables, is possible for specific problems, taking into account the specific characteristics of the function being optimized. The class of "good" functions is shown, as an example.
Key words:
global optimization, smooth function, parallel algorithms, analysis of algorithms.
References:
- Orlyanskaya, I.V. Current approaches to the development of methods of global optimization / I.V. Orlyanskaya // Electronic Journal "Investigated in Russia". – 2007. – P. 189 - 192: [web - site] http://zhurnal.ape.relarn.ru/articles/2002/189.pdf. – (in Russian).
- Nemirovsky, A.S. Complexity of the tasks and the effectiveness of optimization methods / A.S. Nemirovsky, D.B. Yudin. – Moscow: “Nauka” Publisher, 1979. – 384 p. – (in Russian).
- Yevtushenko, Y.G. Method of half division for global optimization of functions of many variables, Yevtushenko Y.G., Ratkin V.A. // Technical Cybernetics. - 1987. № 1. - P. 119-127. – (in Russian).
- Strongin, R.G. Search of global optimum / R.G. Strongin. – Moscow: “Znanie” Publisher, 1990. – 240 p. – (in Russian).
- Grishagin, V.A. A parallel method for solving multi-dimensional multiextremal problems with nonconvex limitations / V.A. Grishagin, Ya.D. Sergeyev // V international scientific-practical seminar «High performance parallel computing on cluster systems». Nigniy Novgorod, “Nigniy Novgorod State University” Publisher. 2005. – P. 74-82. – (in Russian).
© 2009, IPSI RAS
Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; E-mail: ko@smr.ru; Phones: +7 (846) 332-56-22, Fax: +7 (846) 332-56-20