1 Homogeneous algorithms of global optimization Елсаков С. М., Ширяев В. И. Petrovac, Montenegro, September 21-25, 2009 Рассматриваются задачи глобальной оптимизации (1) где f(x) – липшицева с константой L, а время вычисления f(x) – значительно. Алгоритм глобальной оптимизации. Требования 1.Однородный алгоритм – эта такой алгоритм, который для двух целевых функций различающихся на константу генерирует одинаковые последовательности точек x i. 2. Представим результаты уже проведенных вычислений в виде функций m k (x) и s k (x), удовлетворяющим следующим условиям: 3. Рассматриваются однородные алгоритмы глобальной оптимизации в форме (2) где P(m,s):R 2 R. Optimization and applications" - OPTIMA 2009

2 АлгоритмТребование однородности Представим в виде Алгоритма 1 Функция m k (x) Функция s k (x) Вспомогате льная задача СходимостьДекомпозиция допустимого множества Информационно -статистические алгоритмы ++ Кусочно- линейная Кусочно- квадратичная Поиск в дискретном множестве К точкам глобального минимума + Алгоритм С. А. Пиявского ++ Кусочно- линейная Поиск в дискретном множестве К точкам глобального минимума + Алгоритмы неравномерных покрытий ++ Липшицева минорантаПоиск в дискретном множестве К точкам глобального минимума + Алгоритмы на основе диагональных кривых ++ Кусочно- линейная Кусочно- квадратичная Поиск в дискретном множестве К точкам глобального минимума + DIRECT Ко всем точкам допустимого множества + LGO ++ Липшицева минорантаСлучайный и локальный поиск Не гарантируетс я - EGO ++ RBF- сплайн Дисперсия стох. процесса МВГКо всем точкам допустимого множества - Примеры алгоритмов глобальной оптимизации

3 Теоретические результаты Принципиальный алгоритм. Алгоритм 1. Шаг 1. Выбрать некоторым образом начальные точки x i. Шаг 2. Вычислить Шаг 3. Вычислить значения f(x k+1 ). Шаг 4. Если выполнено условие выхода φ, то выйти, иначе вернуться на Шаг 2. Теорема 1. Пусть существует дважды непрерывно дифференцируемая функция P(m,s) такая, что для всевозможных функций m k (x) и s k (x), удовлетворяющих условиям А1)-А4), а также А5) А6) алгоритмы вида Алгоритма 1 являются однородными, тогда последовательности точек испытаний генерируемые алгоритмами с функциями P(m,s) и P*(m,s)=Cm+p(s),C=const совпадают.

4 Теорема 2. Для того чтобы множество предельных точек порождаемых однородным алгоритмом с критерием P(m k (x),s k (x))=Cm k (x)+p(s k (x)), совпадало с множеством глобальных минимумов липшицевой функции f(x) с константой Липшица L на компакте X достаточно, чтобы функция p(·) была липшицева и (3) где K>L. Теорема 3. Если для функции s k (x) выполняется условие (А7) то множество предельных точек порождаемых алгоритмом с критерием P(m k (x),s k (x))=2Ks k (x)-m k (x), где K>L+L m, будет совпадать с множеством глобальных минимумов липшицевой функции f(x) с константой Липшица L. Теоретические результаты

5 Шаг 1. Выбрать начальные точки Шаг 2. Вычислить в начальных точках значения Шаг 3. Положить Шаг 4. Построить функции удовлетворяющие условиям А1-А7). Шаг 5.Найти следующую точку для проведения испытаний Шаг 6. Вычислить Шаг 7. Если выполнено условие остановки, то выйти, иначе положить вернуться на шаг 4. Теоретические результаты Теорема 4. Если в качестве критерия остановки выбрать условие вида то однородный алгоритм обеспечит решение задачи (1) с точностью по значению целевой функции не хуже чем Однородный алгоритм глобальной оптимизации

6 Результаты тестирования

7 Предлагаемый алгоритм на основе RBF-сплайнов Использование Partition of unity для m k (x) и s k (x) снижает асимтотически время построения до линейного, а время вычисления значения сплайна до логарифмического от числа точек испытаний. Учет особенностей вспомогательных задач: Известны координаты «почти» всех максимумов Точность решения определяется адаптивно Задача Гришагин GKLS (простой) GKLS (сложный) Branin 6 hump camel Shekel 7Shekel 10Среднее Количество испытаний для обычного алгоритма Количество испытаний для ускоренного алгоритма Увеличение количества испытаний в процентах 20%14%17%-55%114%81%60%36% (4) Рис.1 POU на примере одного разбиения Испытания Минимум Новые испытания Рис. 2. Точки для проведения испытаний