К вопросу об эффективности параллельных алгоритмов глобальной оптимизации функций многих переменных
Коварцев А.Н., Попова-Коварцева Д.А.

Аннотация:
Рассматривается проблема построения эффективных параллельных алгоритмов глобальной оптимизации. Приведены результаты качественного анализа возможности преодоления экспоненциального роста сложности задачи глобальной оптимизации для функций общего вида при использовании часто применяемых алгоритмических приёмов ускорения сходимости (условия Липшица, редукции, локальной техники). Показано, что построение эффективных алгоритмов глобальной оптимизации для размерностей 100 и более переменных возможно для частных постановок задач, учитывающих специфические особенности оптимизируемой функции. В качестве примера приведён класс «хороших» функций.

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.

Литература:

  1. Орлянская, И.В. Современные подходы к построению методов глобальной оптимизации / Орлянская И.В. // Электронный журнал «Исследовано в России». - 2007. С. 189-192: [web-сайт] <http://zhurnal.ape.relarn.ru/articles/2002/189.pdf >
  2. Немировский, А.С. Сложность задач и эффективность методов оптимизации / Немировский А.С., Юдин Д.Б. – М.: Наука, 1979. 384 с. ]
  3. Евтушенко, Ю.Г.. Метод половинного деления для глобальной оптимизации функции многих переменных / Евтушенко Ю.Г., Ратькин В.А. // Техническая кибернетика. - 1987. №1. – С. 119-127
  4. Стронгин Р.Г. Поиск глобального оптимума / Стронгин Р.Г. - М.: Знание, 1990. – 240 с.
  5. Гришагин В.А. Параллельный метод решения многомерных многоэкстремальных задач с невыпуклыми ограничениями / Гришагин В.А., Сергеев Я.Д. // V международный научно-практический семинар «Высокопроизводительные параллельные вычисления на кластерных системах». - 2005. Н. Новгород, ННГУ. - С. 74-82

References:

  1. Orlyanskaya, I.V. Current approaches to the development of methods of global optimization / Orlyanskaya I.V. // Electronic Journal "Investigated in Russia". - 2007. P. 189-192: [web-site] – (in Russian). http://zhurnal.ape.relarn.ru/articles/2002/189.pdf
  2. Nemirovsky, A.S. Complexity of the tasks and the effectiveness of optimization methods / Nemirovsky A.S., Yudin D.B. - Moscow: Nauka, 1979. 384 p. – (in Russian).
  3. 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).
  4. Strongin, R.G. Search of global optimum / Strongin R.G. - M.: Knowledge, 1990. – 240 p. – (in Russian).
  5. Grishagin, V.A. A parallel method for solving multi-dimensional multiextremal problems with nonconvex limitations / Grishagin V.A., Sergeyev Y.D. // V  international scientific-practical seminar «High performance parallel computing on cluster systems». - 2005. N. Novgorod, N. Novgorod State University. – P. 74-82. – (in Russian).
© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 332-56-22, факс: +7 (846) 332-56-20