Бурятского государственного университета
имени Доржи Банзарова
АвторизацияРУСENG

Архив выпусков 2012-2015

Библиографическое описание:
Сороковиков П. С.
МОДИФИКАЦИИ АЛГОРИТМОВ НЕЛОКАЛЬНОГО ОДНОМЕРНОГО ПОИСКА, ОСНОВАННЫЕ НА УСЛОВИИ ГЁЛЬДЕРА // Вестник БГУ. Математика, информатика. - 2019. №4. . - С. 40-56.
Заглавие:
МОДИФИКАЦИИ АЛГОРИТМОВ НЕЛОКАЛЬНОГО ОДНОМЕРНОГО ПОИСКА, ОСНОВАННЫЕ НА УСЛОВИИ ГЁЛЬДЕРА
Финансирование:
Работа выполнена при финансовой поддержке РФФИ, проект №19-37-90065.
Коды:
DOI: 10.18101/2304-5728-2019-4-40-56УДК: 519.853
Аннотация:
Задача одномерного поиска глобального минимума невыпуклой функции часто возникает в качестве вспомогательной при решении многомерных оптимизационных задач. В течение множества лет методы нелокальной одномерной оптимизации разрабатывались рядом специалистов из России и стран зарубежья. В статье рассматриваются предложенные модификации алгоритмов нелокального одномерного поиска, основанные на условии Гёльдера. Указанные модификации реализованы в виде библиотеки алгоритмов и интегрированы в рамках единого программного комплекса. Библиотека включает в себя модификации методов Ю. Г. Евтушенко, Р. Г. Стронгина и комбинированный алгоритм, основанный на методах «парабол» и Стронгина. На сформированной автором коллекции тестовых задач произведены многовариантные вычисли- тельные эксперименты сравнения реализованных алгоритмов при различных значениях показателя Гёльдера. Анализ выполненных экспериментов показал, что обобщение алгоритмов на основе условия Гёльдера дает в ряде случаев значительный эффект ускорения перед алгоритмами, основанными на условии Липшица. В ходе тестирования выявлены наиболее предпочтительные значения показателя Гёльдера и лидирующие алгоритмы. Проведенные экспериментальные исследования подтвердили пригодность реализованных модификаций для поиска глобального минимума невыпуклой функции одной переменной.
Ключевые слова:
нелокальный одномерный поиск; условие Гёльдера; метод Евтушенко; метод Стронгина; глобальный минимум; библиотека алгоритмов; программная реализация.
Список литературы:
Евтушенко Ю. Г. Методы поиска глобального экстремума // Исследование операций. 1974. № 4. С. 39–68.

Жиглявский А. А., Жилинскас А. Г. Методы поиска глобального экстремума. М.: Наука, 1991. 248 с.

Пиявский С. А. Один алгоритм отыскания абсолютного экстремума функций // Журнал вычислительной математики и математической физики. 1972. Т. 12. C. 885–896.

Стронгин Р. Г. Численные методы в многоэкстремальных задачах (информационно-статистические алгоритмы). М.: Наука, 1978. 240 с.

Brent R. P. Algorithms for minimization without derivatives. New Jersey: Pren- tice Hall, 1973. 195 p.

Timonov L. N. An Algorithm for Search of a Global Extremum // Engineering Cybernetics. 1977. Vol. 15, No. 3. P. 38–44.

Horst R., Pardalos P. M. Handbook of global optimization. Springer Science & Business Media, 2013. 880 p.

Kushner H. J. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise // Journal of Basic Engineering. 1964. Vol. 86, No. 1. P. 97–106.

Schoen F. On a sequential search strategy in global optimization problems // Calcolo. 1982. Vol. 19, No. 3. P. 321–334.

Galperin E. A. The cubic algorithm // Journal of Mathematical Analysis and Applications. 1985. Vol. 112, No. 2. P. 635–640.

Hansen P., Jaumard B., Lu S. H. Global optimization of univariate Lipschitz functions: I. Survey and properties // Mathematical programming. 1992. Vol. 55, No. 1. P. 251–272.

Zhigljavsky A., Zilinskas A. Stochastic Global Optimization. Springer Sci- ence-Business Media, 2008. 262 p.

Жиглявский А. А. Математическая теория случайного глобального поиска. Л.: Изд-во Ленингр. ун-та, 1985. 296 с.

Горнов А. Ю. Применение сплайн-аппроксимации для конструирования алгоритмов оптимизации с новыми вычислительными свойствами // Дискретная оптимизация и исследование операций: тр. всерос. конф. Владивосток, 2007. С. 99.

Pintér J. D. Convergence properties of stochastic optimization proce- dures // Optimization. 1984. Vol. 15, No. 3. P. 405–427.

Goryachih A. A Class of Smooth Modification of Space-Filling Curves for Global Optimization Problems // Models, Algorithms, and Technologies for Network Analysis. 2016. P. 57–65.

Булатов В. П., Хамисов О. В. Метод отсечения в E^n+1 для решения задач глобальной оптимизации на одном классе функций // Журнал вычислительной математики и математической физики. 2007. Т. 47, № 11. С. 1830–1842.

Зароднюк Т. С., Горнов А. Ю. Технология поиска глобального экстремума в задаче оптимального управления // Современные технологии. Системный ана- лиз. Моделирование. 2008. № 3. С. 70–76.

Растригин Л. А. Системы экстремального управления. М.: Наука, 1974. 632 с.