Модификации алгоритмов нелокального одномерного поиска, основанные на условии Гёльдера
Автор: Сороковиков Павел Сергеевич
Журнал: Вестник Бурятского государственного университета. Математика, информатика @vestnik-bsu-maths
Рубрика: Управляемые системы и методы оптимизации
Статья в выпуске: 4, 2019 года.
Бесплатный доступ
Задача одномерного поиска глобального минимума невыпуклой функции часто возникает в качестве вспомогательной при решении многомерных оптимизационных задач. В течение множества лет методы нелокальной одномерной оптимизации разрабатывались рядом специалистов из России и стран зарубежья. В статье рассматриваются предложенные модификации алгоритмов нелокального одномерного поиска, основанные на условии Гёльдера. Указанные модификации реализованы в виде библиотеки алгоритмов и интегрированы в рамках единого программного комплекса. Библиотека включает в себя модификации методов Ю. Г. Евтушенко, Р. Г. Стронгина и комбинированный алгоритм, основанный на методах «парабол» и Стронгина. На сформированной автором коллекции тестовых задач произведены многовариантные вычислительные эксперименты сравнения реализованных алгоритмов при различных значениях показателя Гёльдера. Анализ выполненных экспериментов показал, что обобщение алгоритмов на основе условия Гёльдера дает в ряде случаев значительный эффект ускорения перед алгоритмами, основанными на условии Липшица. В ходе тестирования выявлены наиболее предпочтительные значения показателя Гёльдера и лидирующие алгоритмы. Проведенные экспериментальные исследования подтвердили пригодность реализованных модификаций для поиска глобального минимума невыпуклой функции одной переменной.
Нелокальный одномерный поиск, условие гёльдера, метод евтушенко, метод стронгина, глобальный минимум, библиотека алгоритмов, программная реализация
Короткий адрес: https://sciup.org/148308950
IDR: 148308950 | УДК: 519.853 | DOI: 10.18101/2304-5728-2019-4-40-56
Software implementation of nonlocal one-dimensional optimization algorithms based on the Holder condition
The problem of one-dimensional search for a global minimum of a nonconvex function often appears as an auxiliary for solving multidimensional optimization problems. For many years, nonlocal one-dimensional optimization methods have been developed by a number of specialists from Russia and foreign countries. The article considers the proposed modifications of nonlocal one-dimensional search algorithms based on the Hölder condition. These modifications are implemented as an algorithms library and integrated into a single software package. The library includes modifications of Yu. G. Evtushenko’s, R. G. Strongin’s methods and a combined algorithm based on the Strongin’s method of "parabolas". We have made multivariant computational experiments to compare the implemented algorithms for various values of the Holder index. An analysis of the performed experiments showed that the generalization of algorithms based on the Holder condition gives in some cases a significant acceleration effect over algorithms based on the Lipschitz condition. During testing the most preferred values of the Holder index and leading algorithms were identified. The conducted experimental studies confirmed the suitability of the implemented modifications for finding the global minimum of the non-convex function of one variable.
Список литературы Модификации алгоритмов нелокального одномерного поиска, основанные на условии Гёльдера
- Евтушенко Ю. Г. Методы поиска глобального экстремума // Исследование операций. 1974. № 4. С. 39-68.
- Жиглявский А. А., Жилинскас А. Г. Методы поиска глобального экстремума. М.: Наука, 1991. 248 с.
- Пиявский С. А. Один алгоритм отыскания абсолютного экстремума функций // Журнал вычислительной математики и математической физики. 1972. Т. 12. C. 885-896.
- Стронгин Р. Г. Численные методы в многоэкстремальных задачах (информационно-статистические алгоритмы). М.: Наука, 1978. 240 с.
- Brent R. P. Algorithms for minimization without derivatives. New Jersey: Prentice Hall, 1973. 195 p.
