Содержание к диссертации
Введение
ГЛАВА 1. Безусловная липшицева глобальная оптимизация 11
1.1. Постановка задачи 11
1.2. Способы оценивания константы Липшица 19
1.3. Подходы к решению многомерных задач 27
ГЛАВА 2. Диагональный подход к решению задач глобальной оптимизации 36
2.1. Общая схема диагональных алгоритмов 36
2.2. Диагональные алгоритмы с локальной настройкой 49
2.2.1. Предварительные замечания 49
2.2.2. Вычислительная схема алгоритмов 50
2.2.3. Условия сходимости 54
2.2.4. Численные эксперименты 56
2.3. Избыточность традиционных диагональных стратегий разбиения 63
2.4. Безызбыточная стратегия разбиения и ее реализация 67
ГЛАВА 3. Методы глобальной оптимизации на основе безызбыточной диагональной стратегии разбиения 83
3.1. Диагональный информационно-статистический алгоритм на основе безызбыточных разбиений 84
3.1.1. Предварительные замечания 84
3.1.2. Вычислительная схема алгоритма 86
3.1.3. Условия сходимости 89
3.1.4. Численные эксперименты 95
3.2. Диагональный алгоритм на основе безызбыточных разбиений и множественных оценок константы Липшица 107
3.2.1. Предварительные замечания 107
3.2.2. Оценивание нижних границ значений функции 110
3.2.3. Нахождение недоминируемых гиперинтервалов 114
3.2.4. Вычислительная схема алгоритма и анализ сходимости 123
3.2.5. Численные эксперименты 133
Заключение 149
Список литературы
- Способы оценивания константы Липшица
- Подходы к решению многомерных задач
- Вычислительная схема алгоритмов
- Диагональный алгоритм на основе безызбыточных разбиений и множественных оценок константы Липшица
Введение к работе
Актуальность темы диссертационной работы. Многие задачи принятия оптимальных решений, возникающие в различных областях науки и техники, могут быть сформулированы как задачи оптимизации. Сложность математических моделей проектируемых систем, являющаяся натуральным следствием возрастающей сложности этих систем, значительно затрудняет процедуру поиска наилучшей комбинации управляемых параметров. Трудности численного решения подобных задач во многом связаны с их размерностью и видом оптимизируемой целевой функции, которая в общем случае может быть многоэкстремальной, недифференци-руемой и, более того, задана в форме так называемого "черного ящика", на вход которого подается аргумент, а на выходе наблюдается соответствующее значение функции. При этом может быть недоступна дополнительная информация о функции, такая как, например, ее градиент, и лишь значения целевой функции могут быть использованы в ходе решения задачи. Кроме того, каждое испытание функции (то есть, ее вычисление в некоторой точке допустимой области) может потребовать значительных вычислительных ресурсов.
Увеличение числа прикладных задач, описываемых функциями подобного типа, а также бурное развитие вычислительной техники привели к росту интереса к указанным задачам оптимизации и к развитию глобальной оптимизации как области математического программирования, занимающейся разработкой методов решения многоэкстремальных оптимизационных задач. Подходы глобальной оптимизации существенно отличаются от техники стандартных методов поиска локальных оптимумов функции (часто неспособных найти глобальное решение рассматриваемых многоэкстремальных задач) и характеризуются высокой вычислительной трудоемкостью. Вопросам численного решения таких задач по-
священа обширная литература (см., например, работы Д. И. Батищева,
B. П. Булатова, Ф. П. Васильева, В. П. Гергеля, А. И. Голикова, С. 10. Го
родецкого, В. А. Гришагина, В. Ф. Демьянова, Ю. Г. Евтушенко, В. Г. Жа
дана, А. А, Жиглявского, А. Г. Жилинскаса, В. Г. Карманова, А. Г. Корот-
ченко, В. Н. Малоземова, Н. Н. Моисеева, Й. Б. Моцкуса, Ю. И. Неймарка,
C. А. Пиявского, Э. Полака, Л. А. Растригина, Я. Д. Сергеева, А. С. Стре-
каловского, Р. Г. Стронгина, А. Г. Сухарева, П. Пардалоса, Я. Пинтера,
X. Туя, Д. Уайлда, К. Флудаса, Д. Химмсльблау, Р. Хорста, Д. Б. Юдина
и других). При этом техники решения задач одномерной глобальной оп
тимизации исследованы достаточно глубоко, в то время как построение
эффективных алгоритмов многомерной оптимизации, имеющих большое
практическое значение, продолжает привлекать большое внимание иссле
дователей.
Возможность построения адаптивных схем поиска наилучшего, то есть глобального, решения многоэкстремальных многомерных задач, отличных от переборных схем, предполагает наличие неких априорных предположений о свойствах задачи. Такие предположения служат математическим инструментом для получения оценок глобального решения задачи на основе проведенных испытаний целевой функции и играют существенную роль при построении эффективных алгоритмов глобального поиска. Для многих практических задач (таких как, например, решение нелинейных уравнений и неравенств; регулирование сложных нелинейных систем; оптимизация иерархических моделей, связанных с задачами размещения, системами обслуживания и т.п.) типичным является предположение о липшицевости функций, поскольку относительные вариации функций, характеризующих моделируемую систему, обычно не могут превышать некоторый порог, определяемый ограниченной энергией изменений в системе. Разработкой теории и методов численного решения задач подобного типа занимается липшицева глобальная оптимиза-
ция. Важность данной подобласти глобальной оптимизации объясняется как наличием большого числа прикладных задач, моделируемых при помощи липшицевых функций, так и обширностью класса таких функций.
Учитывая практическую важность задач многомерной липшицевой глобальной оптимизации и существующие сложности на пути их решения, представляются актуальными исследования по разработке эффективных алгоритмов решения подобных задач, чему и посвящена данная диссертационная работа.
Цель работы. В диссертации рассматривается вопрос построения численных методов поиска глобального минимума в задачах многомерной оптимизации, где целевая функция определена на гиперинтервале и удовлетворяет на нем условию Липшица. При этом функция предполагается многоэкстремальной, недифференцируемой, заданной в виде "черного ящика", и вычисление функции даже в одной точке допустимой области требует значительных затрат (времени, машинной памяти и т.п.). Учитывая высокую вычислительную сложность рассматриваемых задач, целью работы является разработка быстрых методов решения таких задач. Основное внимание уделяется использованию новой безызбыточной диагональной стратегии адаптивного разбиения гиперинтервалов, предложенной Я. Д. Сергеевым, которая успешно объединяет в себе идеи кривых, заполняющих пространство, и диагональных алгоритмов.
Научная новизна.
1. Предложена схема построения диагональных алгоритмов глобаль
ной оптимизации, основанная на новой диагональной стратегии разбие
ния гиперинтервалов, которая позволяет избежать генерирования избы
точных точек испытаний целевой функции, характерного для традицион
ных диагональных стратегий разбиения.
2. В рамках введенной схемы предложены новые многомерные
диагональные алгоритмы глобальной оптимизации: информационно-
статистический метод с адаптивной оценкой глобальной константы Липшица и геометрический метод, работающий со множеством оценок константы Липшица.
Предложена новая схема балансирования локальной и глобальной информации в ходе поиска глобального минимума. Показано, что техника локальной настройки на поведение целевой функции может быть успешно применена для построения многомерных геометрических диагональных алгоритмов глобальной оптимизации.
Для всех построенных алгоритмов установлены достаточные условия сходимости к глобальному минимуму.
Для проверки работоспособности алгоритмов глобального поиска предложены генератор классов многомерных многоэкстремальных случайных тестовых функций, предоставляющий информацию о расположении всех точек минимумов и размерах их областей притяжения, и ряд критериев проверки эффективности методов поиска глобального минимума на основе классов тестовых функций.
Практическая ценность работы. Исследования по теме диссертационной работы выполнялись при финансовой поддержке Российского фонда фундаментальных исследований (проекты 01-01-00587 и 04-01-00455-а), Итальянского фонда фундаментальных исследований (проекты FIRB RBNE01WBBB и RBAU0IJYPN), а также гранта Калабрийско-го университета (Козенца, Италия) для молодых ученых (проект Giovani Ricercatori, 2006 г.). Результаты работы используются также в следующих курсах факультета вычислительной математики и кибернетики Нижегородского государственного университета им. Н. И. Лобачевского, посвященных вопросам оптимизации: "Модели и методы принятия решений" (общий курс по специальности "Прикладная информатика"), "Методы принятия решений" (спецкурс магистратуры по специальности "Прикладная математика и информатика"), "Системы поддержки принятия реше-
ний" (спецкурс кафедры математического обеспечения ЭВМ по специальности "Прикладная математика и информатика"), "Параллельные вычисления и методы глобальной оптимизации" (спецкурс кафедры математического обеспечения ЭВМ по специальности "Прикладная математика и информатика").
Апробация работы. Результаты работы были представлены на международных научно-практических семинарах "Высокопроизводительные параллельные вычисления на кластерных системах" (Нижний Новгород,
2002, 2003), VI международном конгрессе "Математическое моделирование" (Нижний Новгород, 2004), итальянских национальных конгрессах "Современная вычислительная математика" (Козенца, Италия,
2005), международном конгрессе "Задачи нелинейной оптимизации большой размерности" (Эриче, Италия, 2004), IV международной конференции "Достижения глобальной оптимизации" (Санторини, Греция, 2003), I международной конференции "Непрерывная оптимизация" (Трой, Нью-Йорк, США, 2004), международном семинаре "Глобальная оптимизация" (Альмерия, Испания, 2005), VIII конгрессе Итальянского общества прикладной математики (Рагуза, Италия, 2006), III международной конференции "Прикладная математика" (Пловдив, Болгария, 2006).
Публикации. Основное содержание диссертации изложено в двадцати одной работе [22,38^0,64,65,89,129,158,159,163-167,219-223,228]
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, двух приложений и списка литературы.
В первой главе производится постановка задачи безусловной липши-цевой глобальной оптимизации как частного случая общей задачи глобальной оптимизации. Рассматриваются основные свойства поставленной задачи и обсуждается влияние информации о константе Липшица на работу методов глобального поиска. Способы получения такой информации иллюстрируются кратким описанием некоторых одномерных ал-
горитмов липшицевой оптимизации. Демонстрируются возможные пути обобщения одномерных методов на многомерный случай.
Вторая глава посвящена рассмотрению диагонального подхода к решению многомерных задач глобальной оптимизации, при котором область поиска последовательно разбивается на гипер интервалы и целевая функция вычисляется в двух вершинах главной диагонали каждого из получаемых гипер интервалов. Данный подход имеет ряд привлекательных теоретических свойств и хорошо зарекомендовал себя при решении поставленной задачи. Описываются стратегии разбиения гиперинтервалов, традиционно применяемые в диагональных алгоритмах, и на их основе конструируются и исследуются два новых диагональных метода с локальной настройкой на поведение целевой функции. Устанавливаются условия сходимости предлагаемых методов и производится их численное сравнение с алгоритмами, использующими в ходе поиска только информацию о глобальной константе Липшица. Обсуждаются сложности, возникающие при использовании традиционных диагональных стратегий разбиения, связанные с генерированием большого количества избыточных точек вычисления функции. Приводится описание безызбыточной диагональной стратегии разбиения гиперинтервалов, позволяющей избежать недостатков традиционных диагональных стратегий. Рассматриваются ее основные свойства, предлагается способ ее эффективной программной реализации, и описываются некоторые детали этой реализации.
В третьей главе показывается, как безызбыточная стратегия разбиения может быть использована для построения быстрых диагональных алгоритмов глобальной оптимизации. Предлагаются и всесторонне изучаются два новых диагональных метода с использованием указанной стратегии и с различными подходами к получению информации о константе Липшица: в первом из методов адаптивно оценивается глобальная константа Липшица, во втором оценка выбирается из множества возможных зна-
чений от нуля до бесконечности. Устанавливаются условия сходимости предлагаемых методов. Приводятся результаты их численного тестирования и сравнения с некоторыми популярными алгоритмами глобальной оптимизации. Результаты экспериментов демонстрируют превосходство новых методов как по числу проводимых испытаний целевой функции, так и по качественному исследованию области поиска, характеризуемому количеством генерируемых гиперинтервалов.
В заключении приводятся основные результаты диссертационной работы.
В приложении А обсуждается вопрос численного тестирования алгоритмов глобальной оптимизации и детально описывается генератор классов многомерных и многоэкстремальных тестовых функций, который для всех генерируемых функций предоставляет информацию о расположении точек минимумов и о размерах их областей притяжения. Генератор использовался в диссертационной работе при проведении численных экспериментов. С момента создания (2003 г.) он уже был запрошен компаниями и исследовательскими организациями из более чем 20 стран мира.
Наконец, приложение В посвящено рассмотрению некоторых критериев сравнения методов глобальной оптимизации с использованием классов тестовых функций.
В заключение автор выражает глубокую признательность своему научному руководителю профессору Ярославу Дмитриевичу Сергееву за внимание и поддержку в работе.
Способы оценивания константы Липшица
В литературе рассматривается множество различных алгоритмов решения задачи (1.7)-19)(см.,например,[35,39,56,73,84,98,114,116,140,154,176,178,198,210,212,227,235,239,240,246]). Они могут быть разделены как минимум на четыре группы в зависимости от способа получения оценки константы Липшица L из (1.9). К первой группе относятся алгоритмы, в которых применяется оценка L, заданная априорно (см., например, [56,98,140,143,151,176,178,227,246]). Такие алгоритмы важны с теоретической точки зрения, но их применение на практике ограничено, так как при указанных предположениях о целевой функции априорная информация о константе Липшица часто недоступна. Вторая группа включает алгоритмы, адаптивно оценивающие в ходе поиска глобальную константу Липшица во всей области D из (1.8) (адаптивная глобальная оценка, см. [39,51,71,73,151,198,235]), что является более практичным подходом. Однако получаемая при этом оценка константы Липшица может давать слабую информацию о поведении целевой функции в каждой конкретной подобласти области поиска. Алгоритмы с использованием адаптивного оценивания локальных констант Липшица Li в различных зонах Д С D области поиска D (адаптивные локальные оценки, см. [63,164,184,210,235]), формирующие третью группу, позволяют настроиться на локальное поведение целевой функции в различных регионах допустимой области. Наконец, к четвертой группе принадлежат алгоритмы, в которых оценки константы Липшица выбираются из некоторого множества возможных значений (см. [124,125,153,154,223]).
Отметим, что константа Липшица существенно влияет на скорость сходимости алгоритмов липшицевой глобальной оптимизации, поэтому столь важным является вопрос ее корректной оценки (см., например, [63,143,149,154,177,198,210,235]). Заниженная оценка истинной константы Липшица L может привести к потери глобального решения. В то же время слишком большое значение константы L для минимизируемой целевой функции предполагает (вследствие условия Липшица (1.9)) сложную структуру функции с резкими перепадами ее значений и узкими зонами притяжения точек минимумов. Поэтому завышенная оценка константы L, не соответствующая истинному поведению функции, влечет за собой медленную сходимость алгоритма к точке глобального минимума. На рис. 1.3 (из работы [235]) приведен пример одномерной функции с большим значением глобальной константы Липшица L на интервале [а, Ь]. Точка глобального минимума х находится в широком интервале [а, с], где локальная константа Липшица мала. Глобальная же константа Липшица совпадает с локальной константой интервала [с, 6], который очень узок. В этой ситуации методы, использующие в ходе поиска только информацию о глобальной константе L (или о ее оценке), будут работать медленно на интервале [а, с], несмотря на простоту функции в этой подобласти и малость локальной константы Липшица, поскольку глобальная константа Липшица велика. Таким образом, поведение метода в окрестности х" будет зависеть от локальной константы интервала [с, Ь] (и глобальной для всей области определения [а, &]), который не только мал и находится далеко от точки х , но еще и содержит точку глобального максимума. Поэтому использование только глобальной информации о поведении целевой функции в ходе ее минимизации может замедлить сходимость алгоритма к точке глобального минимума.
Традиционным приемом преодоления этой трудности (см., например, [140,151]) является остановка метода глобального поиска и подключение некоего локального алгоритма, который улучшает полученное решение на заключительной фазе поиска. При этом подходе возникают некоторые сложности, связанные с сопряжением глобальной и локальной процедур. Одной из них является вопрос об определении момента остановки глобального алгоритма: преждевременная остановка может привести к потере глобального решения, поздняя остановка замедляет поиск. Как было показано в работах [63,210,235], оценивание локальных констант Липшица и балансирование локальной и глобальной информации в процессе поиска глобального минимума преодолевают указанные сложности и позволяют существенно ускорить работу алгоритма (важность такого оценивания была отмечена и в некоторых других работах, например, [94,177,198]). Интересным является также подход, при котором объединение локальной и глобальной информации в ходе решения задачи (1.7)-(1.9) осуществляется путем выбора оценок константы Липшица из множества возможных значений от нуля до бесконечности (см. [125,153,154,223]).
Подходы к решению многомерных задач
Проблема определения новой точки испытания функции на каждой итерации многомерных алгоритмов, конструирующих вспомогательные функции вида (1.12), и, в частности, многомерного алгоритма Пиявского была исследована в целом ряде работ. В [56] было замечено, что точка хк+1 глобального минимума вспомогательной функции Fk(x) принадлежит конечному множеству точек локальных минимумов Fk(x), которое может быть получено при решении системы квадратичных уравнений. Глубокий анализ алгоритма построения нижних огибающих функций Fk(x) из (1.12) был проведен также в [178,179], где предлагается более экономный способ нахождения локальных минимумов функций Fk(x), связанный с решением систем N линейных (где N есть размерность задачи) и одного квадратичного уравнений. Алгебраические техники, призванные избежать решения некоторых систем уравнений, заведомо несоответствующих точкам глобального минимума функций Fk(x), были рассмотрены в [70]. Дальнейшее сокращение необходимых систем урав нений было предложено в [143]. В работах [94,175,246,247,249] рассматриваются и другие вспомогательные функции, сходные с (1.12). Однако, несмотря на многочисленные попытки по уменьшению вычислительной сложности многомерного алгоритма Пиявского и схожих с ним методов, быстрый рост числа уравнений с возрастанием размерности пространства поиска и увеличением количества проводимых испытаний функции существенно ограничивает применение данных алгоритмов при решении прикладных задач.
Для упрощения определения нижних границ значений функции f(x) и выбора новых точек испытаний во многих многомерных методах применяется техника адаптивного разбиения области поиска D — [а, 6] из (1.8) на множество подобластей Д. При этом на каждой итерации к таких алгоритмов рассматривается разбиение {Dk} области D такое, что м D = [)Dit ДП 2 = J(A)n ( ,-)» гф (1.14) где М = М(к) есть количество подобластей Д на текущей к-й итерации алгоритма и 5(Д) обозначает границу подобласти Д. Аппроксимация функции f(x) в каждой подобласти Д из {Dk} производится на основании результатов испытаний f(x) в точках х D.
Различные стратегии адаптивного разбиения области поиска были предложены в литературе (см., например, монографии [151,198] и библиографические ссылки в них). Например, широко применяются разбиения области D на гиперинтервалы с вычислением целевой функции в центральных точках (так называемые "центральные" схемы разбиения, см. [30,125-127,153,154,176,177] и др.) или в вершинах главной диагонали каждого из гиперинтервалов (так называемые "диагональные" схемы разбиения, см. [39,130,151,184,195,198,214,216,223] и др.). В рамках интервального анализа интенсивно развивается техника множественного разбиения (см., например, [104,109,110,135,200]). Рассматриваются так Оценивание нижней границы значений липшицевой функции }{х) на гиперинтервале Д = [щ, Ь{] на основании результатов испытаний /(ж), проведенных в двух вершинах главной диагонали Д же более сложные стратегии разбиения, основанные на симплексах (см., например, [17,107,148,151]) и на различных вспомогательных функциях (см., например, [42-44,91,94,99,102,161,247]). Были предложены также общие теоретические схемы, позволяющие исследовать алгоритмы разбиения с единых позиций (см., например, [150,151,198,213]).
При разбиении области D на гиперинтервалы Д (см. (1.14)) и вычислении целевой функции, скажем, в центральной точке каждого гиперинтервала Д построение конуса из (1.12) осуществляется только в гиперинтервале Д, независимо от других конусов. Это избавляет от необходимости нахождения пересечения конусов и упрощает вычисление нижних границ значений f(x) при выборе точки нового испытаний по правилу, схожему с (1.13) (см., например, [125,126,154,176]).
При вычислении функции /(ж) в двух точках гиперинтервала (как в диагональных алгоритмах, см., например, [195,198]) удается достичь более точной (по сравнению с центральными схемами, проводящими испытания функции в одной точке каждого гиперинтервала) оценки наименьшего значения f{x) без значительного увеличения вычислительных затрат. Такими двумя точками могут быть, например, вершины щ и Ь{ главной диагонали гиперинтервала Д. При этом, в силу условия Липшица (1.9), график целевой функции должен находиться над пересечением графиков iV-мерных конусов С\(х,Ь) и Ci{x,L) (см. двумерный пример на рис. 1.7), имеющих угловой коэффициент L (где L есть оценка константы L из (1.9), L L) и расположенных в границах гиперинтервала Д. Вершины этих конусов в (JV + 1)-мерном пространстве задаются, соответственно, координатами (ец,/(а )) и (6$,/(& )).
При этом вершины а; и 6j главной диагонали каждого гиперинтервала Д текущего разбиения области D могут быть рассмотрены как конечные точки одномерного интервала, вдоль которого поведение целевой функции fix) может быть оценено на основании результатов испытаний f(a.i) и f{bi). При выполнении определенных условий, информация о значениях функции на главной диагонали может быть обобщена на многомерное пространство, что позволяет делать заключения о значениях f(x) на всем многомерном гипериптервале Д. Тем самым техника разбиения области поиска на гиперинтервалы с испытанием функции в двух вершинах главной диагонали каждого из получаемых гиперинтервалов допускает естественное обобщение (см., например, [39,164,195,197,198,216]) многих одномерных алгоритмов на многомерный случай.
Таким образом, диагональные алгоритмы, с одной стороны, точнее оценивают наименьшие значения функции на гиперинтервалах по сравнению с алгоритмами, использующими центральные схемы разбиения. С другой стороны, они могут быть построены путем обобщения эффективных одномерных методов па многомерный случай, что открывает интересные перспективы в создании новых быстрых алгоритмов глобальной оптимизации и, следовательно, имеет большое практическое значениє. Поэтому диссертационная работа посвящена рассмотрению именно диагональных алгоритмов.
В заключение отметим, что многие алгоритмы решения общей задачи глобальной оптимизации (1.1) имеют похожую структуру. В связи с этим был предложен ряд теоретических схем, описывающих и изучающих такие алгоритмы в рамках единой теории (например, методы ветвей и границ [147,150,151,198], одномерные характеристические алгоритмы [19,21,138], алгоритмы адаптивного разбиения [195,196,198]). Теоретический анализ большинства из методов, рассмотренных в данной главе (а также и многих других, которые не являются, например, ни характеристическими алгоритмами, ни алгоритмами адаптивного разбиения, см. [11,17,95,102,130,131,214,235] и др.), может быть успешно проведен в рамках схемы алгоритмов "Divide The Best" [213].
Вычислительная схема алгоритмов
Приведем формальную схему НДАЛН, используя обозначения, введенные в параграфе 2.1 при описании диагональной схемы.
Шаг 1. Инициализация: Провести два первых испытания целевой функции в вершинах гиперинтервала D, т.е. xl a, zl = /(ж1) и х2 = 6, z2 = f(x2), и установить текущее число испытаний целевой функции р(1) := 2. Установить текущее разбиение области поиска {D1} : {D} и текущее количество гиперинтервалов М(1) := 1. Вычислить оценку Ai локальной константы Липшица в начальном гиперинтервале D = [а,Ь] (очевидно, в данном случае она совпадает с оценкой глобальной константы) по формуле , ./(а)-/(Ь) а-Ь Установить счетчик итераций к := 1. Предположим теперь, что уже было выполнено некоторое число к 1 итераций диагонального алгоритма. Итерация к-\-1 состоит из следующих шагов.
Увеличить счетчик итераций й:=Н1и перейти на Шаг 2. Прокомментируем введенный метод НДАЛН. Ключевая идея НДАЛН - оценивание локальных констант Липшица путем балансирования локальных и глобальных данных. В отличие от традиционного под-хода (см. [195,198]), при котором используется оценка К глобальной константы L из (2.3) в форме (2.25), локальные оценки К{, 1 і M(k), в форме (2.18) являются результатом сопряжения локальной и глобальной информации, представленной значениями Аг- и 7ь соответственно. Если главная диагональ гиперинтервала D\ мала (по сравнению с текущей максимальной длиной dmax всех главных диагоналей в разбиении области D), то (см. формулы (2.19)-(2.21)) 7» является также малым значением и локальная информация, выражаемая величиной А;, имеет решающее влияние (см. (2.18)) на оценку К{. Если же гиперинтервал D{ достаточно велик (длина его главной диагонали о{ — bi\\ близка к величине dmax), то локальная информация представляется ненадежной и предпочтение отдается глобальной информации, выражаемой величиной из (2.19).
Значения г,Си{ влияют на оценку К{ как глобальные параметры. При увеличении параметров г и С повышается надежность метода при работе на всей области D. Параметр 0 является малой константой, обеспечивающей корректную работу НДАЛН в случае, когда f(xl) const во всех точках испытаний х1 (важность этого параметра видна из формул (2.17)-(2.18) и (2.24)-(2.25)).
Условия сходимости Изучим свойства сходимости бесконечной (є О в условии остановки (2.23)) последовательности {хр } точек испытаний, порождаемой методом НДАЛН при минимизации лип-шицевой функции f{x) из (2.1), В дальнейшем множество предельных точек последовательности {хр кЦ будем обозначать как X . Теорема 2.1 Пусть точка х есть предельная точка последовательности {xv &}. Тогда для всех точек испытаний хр Є {жр } выполняется неравенство f(xp ) f{x ). При этом если наряду с х существует другая предельная точка х" Xі, то f(x ) = f(x"). Доказательство Так как НДАЛН построен в рамках диагональной схемы и, следовательно, принадлежит классу алгоритмов "Divide The Best" [213], утверждение теоремы может быть получено как частный случай общей теории сходимости из [213]. D
Следующая теорема 2.2 представляет достаточные условия глобальной сходимости НДАЛН. Теорема 2.2 Пусть, начиная с некоторой итерации к алгоритма НДАЛН, для гиперинтервала Dj, j = j(k), содержащего точку глобального минимума х целевой функции f(x) из (2.1), выполняется неравенство Kj{k) 2Hjt k k , (2.27) где
Тогда x является предельной точкой последовательности {хр(кЦ, порождаемой методом НДАЛН. Доказательство Покажем сначала, что оценки К {{к) локальных констант Липшица L( (см. (2.18)) ограничены. Действительно, так как справедливы оценки L со, г 1, С 0 и 0, то верна следующая цепочка неравенств О г Кг{к) [г + С) max{L, } оо, к 1. (2.29) Предположим теперь, что существует предельная точка х х последовательности {xpW}. В силу (2.17), (2.24), (2.25) и (2.29), для гиперинтервала Di, і = i(k), содержащего точку х на fc-й итерации алгоритма справедливо lim Ri(k) = f(x ). (2.30) fc-ЇОО Рассмотрим гиперинтервал Dj, j j(k), такой, что ему принадлежит точка глобального минимума х Є Dj, и предположим, что точка х не является предельной точкой последовательности {хр(кЦ.
Диагональный алгоритм на основе безызбыточных разбиений и множественных оценок константы Липшица
Предварительные замечании В предыдущем параграфе был рассмотрен многомерный информационно-статистический алгоритм решения задачи (2.1)-(2.3) па основе безызбыточпой стратегии разбиения гиперинтервалов. В нем использовалась адаптивная оценка константы Липшица L. В данном параграфе мы продолжим построение быстрых алгоритмов липшицевой глобальной оптимизации с применением безызбыточной диагональной стратегии разбиения п представим еще один многомерный диагональный алгоритм [223] (см. также [65,167,220-222]), в котором на каждой итерации оценка константы Липшица выбирается из множества возможных значений от нуля до бесконечности.
Идея использования множественных оценок константы Липшица была предложена в алгоритме DIRHCT [154], где применяются разбиения области D на гиперинтсриалы с вычислением целевой функции в центральных точках (так называемые "центральные" схемы разбиения). В силу относительной простоты и успешного тестирования па ряде функций из литературы и па некоторых прикладных задачах DIRECT на шел широкое применение в решении практических задач (см., например, [88,96,97,108,113,124,145,170,183,192,203,245]).
Однако, как было отмечено многими авторами (см., например, [108, 113,119,153]), существуют некоторые сложности при работе с методом DIRECT. Прежде всего, возникает вопрос об условии остановки алгоритма, так как DIRECT использует и с вое і і работе множество оценок константы Липшица L (а не един сто с иную такую опенку, как, например, алгоритм Пиявского [56]), Несмотря па многочисленные попытки по введению некоторого осмысленного критерия остановки (см., например, [96,108,113,124]), наиболее практичным для инженерных приложений остается условие остановки по достижении допустимого вычислительного ресурса (например, максимального количества испытаний).
Другое важное наблюден не относится к стратегии разбиения и проведения вычислений в алгоритме DIRECT [154], относительная простота которой создает ряд проблем. Как было подчеркнуто в [108,119,170], DIRECT быстро обнаруживает окрестности локальных минимумов, но весьма медленно сходится к точке глобального решения. Такое поведение алгоритма может иметь несколько причин. Первой из них может быть избыточное (особенно при решении задач большой размерности, см. [153]) разбиение гиперинтервалов вдоль всех сторон максимальной длины. Другой возможной причиной медленной сходимости метода DIRECT является чрезмерно частое разбиение мелких пшеринтервало», расположенных вблизи точек локальных (и не глобальных) минимумов. Наконец, DIRECT (как и большинство алгоритмов на основе центральных схем разбиения) использует в ходе работы ограниченную информацию о поведении целевой функции /(ж), получаемую путем испытания f[x) только в одной центральной точке каждого гиперпптервала, без учета соседних гиперинтервалов. Одним из нежелательных эффектов применения такой схемы вычисления функции является (как было замечено в [152]) медленная сходимость алгоритма к точке глобального минимума и случае ее расположения на границе допустимой области.
С целью преодоления указан и i,i х ограничении были предложены некоторые модификации алгоритма DIRHCT. Например, в [153] рассматривались разбиения только одной из максимальных сторон каждого гиперинтервала, чтобы ускорить сходимость метода при решении задач большой размерности. Попытки уменьшить число разбиений гиперинтервалов вблизи точек локальных минимумов путем изменения параметра алгоритма (в определенной степени влияющего на степень разбиения малых подынтервалов, см. [154]) предпринимались, например, в [113,П9,124,153,154]). К сожалению, в таком случае алгоритм становится слишком чувствительным к настройке данного параметра, что может особенно негативно сказаться при решении сложных задач глобальной оптимизации. В [192,245] была предложена идея разбиения на каждом шаге алгоритма пшерпптервалов с наименьшими значениями функции в центральных точках для каждой группы пшеринтервалов с одинаковой длиной главных диагоналей. Такая идея позволяет относительно легко распараллелить алгоритм (см. [245]), по приводит к быстрому росту количества гиперинтервалов, разбиваемых па отдельной итерации метода, и, следовательно, к резкому замедлению поиска при большом числе итераций. В [124,125] рассматривалась другая идея, в большей степени ориентированная на исследование локальных улучшений значений целевой функции. Результаті.!, полученные в [124,125], показывают, что такая модификация алгоритма DIRHCT приемлема в основном при решении задач малой размерности с единствен пой точкоїі глобального минимума и с небольшим числом точек локальных минимумов.
Целью настоящего параграфа является построение нового алгоритма (в дальнейшем называемого Новым Диагональным Алгоритмом со Множеством Оценок липшпцевых констант, 11ДАМО), который ориентирован
(в отличие от метода, предложенного в [124,125]) на решение сложных многомерных многоэкстрсмальиых задач (2.1)-(2.3). В нем используется безызбыточная стратегия разбиения гипернптервалов, усиленная новой техникой выбора гипернптерпалов для разбиения. Предлагается также новая процедура оценивания нижних [ранни значений целевой функции на гиперинтервалах, которая успешно сочетается с идеей (введенной в алгоритме DIRECT) выбора оценок константы Липшица из множества возможных значений. Как демонстрируют результаты проведенных численных экспериментов, применение алгоритма ПДЛМО при решении сложных многомерных задач ведет к значительным улучшениям по сравнению с использованием алгоритма DIRHCT [154] и его модификации [124,125]. Дальнейший материал параграфа организован следующим образом. Вначале рассматриваются процедуры оценивания нижних границ значений функции на гииерпнтервалах и выбора "педомииируемых" гиперинтервалов для возможного разбиения, которые используются в НДАМО. Затем приводятся вычислительная схема нового алгоритма и анализ его сходимости. После этого описываются и исследуются результаты численных экспериментов, проведенных па более чем 1600 многоэкстрсмальиых тестовых функциях.
