Введение 3
Обзор литературы 4
Постановка задачи 7
1 Глобальная оптимизация липшицевых функций 8
2 Оптимизация с фиксированной константой Липшица 15
2.1 Алгоритм 15
2.2 Анализ сходимости 17
3 Оптимизация с неизвестной константой Липшица 19
3.1 Алгоритм 19
3.2 Анализ сходимости 20
4 Модификация метода оптимизации с неизвестной константой Липшица 23
4.1 Алгоритм 23
5 Результаты 24
Заключение и выводы 28
Список литературы 29
Целью данной работы является разработка последовательных стратегий, которые приводят к эффективной оптимизации неизвестной функции при единственном предположении, что она имеет конечную константу Липшица. Сначала определяются достаточные условия непротиворечивости общих последовательных алгоритмов и формулируется их ожидаемая минимальная эффективность. Затем анализируется алгоритм LIPO, который предполагает, что константа Липшица известна. Также представлена адаптивная версия этого алгоритма, когда константа Липшица неизвестна и её необходимо оценивать в процессе оптимизации. Наконец, предложен и проанализирован новый алгоритм, где также неизвестна константа Липшица, но изменена стратегия принятия решения для выбора следующей точки вычисления.
В данной работе был представлен новый эффективный алгоритм глобальной оптимизации, основанный на оценке константы Липшица неизвестной функции. Этот алгоритм является модификацией метода AdaLIPO с измененной стратегией принятия решения, а также сравнивался по эффективности с алгоритмом, упомянутым выше, идейным «предком» - LIPO, и методами, которые являются классическими в области решения проблемы глобальной оптимизации, - CMA-ES и Байесовская оптимизация.
Результаты показывают, что представленный алгоритм для тестовых данных всегда работает лучше, чем Байесовская оптимизация и AdaLIPO, и в 6 из 8 случаях лучше, чем CMA-ES. Данные показатели говорят о стабильной эффективности для рассматриваемого класса задач и меньшем пороге сходимости, чем у алгоритмов, поставленных ему в сравнение.
Тем не менее, анализ алгоритма не завершен с аналитической точки зрения, так как доказана лишь его сходимость.
