автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Диагональные алгоритмы решения задач липшицевой глобальной оптимизации

На правах рукописи

КВАСОВ Дмитрий Евгеньевич

ДИАГОНАЛЬНЫЕ АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ ЛИПШИЦЕВОЙ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Нижний Новгород 2006

Работа выполнена на кафедре математического обеспечения ЭВМ факультета вычислительной математики и кибернетики Нижегородского государственного университета им, Н. И. Лобачевского.

Научный руководитель; доктор физико-математических наук,

профессор Сергеев Ярослав Дмитриевич

Официальные оппоненты: доктор физико-математических наук,

Защита диссертации состоится 22. декабря 2006 г. в $ Г ч. 00 мин. на заседании диссертационного совета Д 212.166.13 при Нижегородском государственном университете им. Н. И. Лобачевского по адресу: 603950, г. Нижний Новгород, пр. Гагарина, 23, корпус 2, конференц-зал.

С диссертацией можно ознакомиться в фундаментальной библиотеке Нижегородского государственного университета им. Н. И. Лобачевского.

профессор Малоземов Василий Николаевич (г. Санкт-Петербург)

кандидат физико-математических наук, доцент Коротченко Анатолий Григорьевич (г. Нижний Новгород)

Ведущая организация: Вычислительный центр РАН (г. Москва)

Автореферат разослан «_» октября 2006 г.

Ученый секретарь

диссертационного совета Д 212.166.13 к.ф.-м.н., доцент

Савельев В. П.

Общая характеристика работы

Актуальность темы диссертационной работы. Многие задачи принятия оптимальных решений, возникающие в различных сферах человеческой деятельности, могут быть сформулированы как задачи математического программирования. Натуральным следствием возрастающей сложности проектируемых систем является сложность их математических моделей, значительно затрудняющая процедуру поиска наилучшей комбинации параметров этих систем. Трудности числешюго решения подобных задач во многом связаны с их размерностью и видом оптимизируемой целевой функции, которая в общем случае может быть многоэкстремальной, недифференцируемой и, более того, задана в форме некоторой процедуры, или симулятора, на вход которого подается аргумент, а на выходе наблюдается соответствующее значение функции. При этом может быть недоступна дополнительная информация о функции, такая как, например, ее градиент, и лишь значения целевой функции могут быть использованы в ходе решения задачи. Кроме того, каждое испытание функции (то есть ее вычисление в некоторой точке допустимой области) может потребовать значительных вычислительных ресурсов.

Увеличение числа прикладных задач, описываемых функциями подобного тппа, а также бурное развитие вычислительной техники привели к росту интереса к указанным задачам оптимизации и к развитию глобальной оптимизации как области математического программирования, посвященной теории и методам решения многоэкс-тремальиых оптимизационных задач. Подходы глобальной оптимизации существенно отличаются от техники стандартных методов поиска локальных оптимумов функцни (часто неспособных найти глобальное решение рассматриваемых мпогоэкстремальных задач) и характеризуются высокой вычислительной трудоемкостью. Вопросы численного решения таких задач широко обсуждаются в литературе (см. работы Д.И, Батищева, В,П. Булатова, Ф.П. Васильева, В.П. Гергеля, А.И. Голикова, С.Ю. Городецкого, В.А. Гришалжа, В.Ф. Демьянова,

Ю.Г, Евтушенко, Ю.М. Ермольева, В.Г. Жадана, A.A. Жигпявскога, А.Г. Жилинскаса, В.Г. Карманова, А.Г. Коротченко, В.Н. Малоземова, H.H. Моисеева, Й.Б. Моцкуса, Ю.И. Неймарка, В.И. Норкииа, С.А. Пиявеюого, Э, Полака, Б.Н, Пшеничного, JI.A. Растрнгина, Я.Д. Сергеева, A.C. Стрекаловского, Р.Г. Стронгина, А,Г. Сухарева, П. Пардалоса, Я. Пинтера, X. Туя, К. Флудаса, Д. Химмельблау, Р. Хорста, Н.З. Шора, Д.Б. Юдина и др.). При этом техники решения задач одномерной глобальной оптимизации исследованы достаточно глубоко, в то время как построение эффективных алгоритмов многомерной оптимизации, имеющих важное практическое значение, продолжает привлекать большое внимание исследователей.

Возможность построения адаптивных схем поиска наилучшего, то есть глобального, решения многоэкстремальных многомерных задач, отличных от переборных схем, связана с наличием неких априорных предположений о свойствах задач. Такие предположения служат математическим инструментом для получения опенок глобального решения задачи на основе проведенных испытаний целевой функции и играют существенную роль при построении эффективных алгоритмов глобального поиска. Для многих практических задач (таких как, например, решение нелинейных уравнений и неравенств; регулирование сложных нелинейных систем; оптимизация иерархических моделей, связанных с задачами размещения, системами обслуживания и т. п.) типичным является предположение о лнпшнцевостн функций, характеризующих моделируемую систему, поскольку отношения их приращений к соответствующим приращениям аргументов обычно не могут превышать некоторый порог, определяемый ограниченной энергией изменений в системе. Разработкой теории н методов численного решения задач подобного типа занимается пшшшцееа глобальная оптимизация. Важность данной подобласти глобальной оптимизации объясняется как наличием большого числа прикладных задач, моделируемых при помощи линшицевых функций, так и обширностью класса таких функций.

Учитывая практическую важность задач многомерной липшицевой

глобальной оптимизации и существующие сложности на пути их решения, представляются актуальными исследования по разработке эффективных алгоритмов решения подобных задач, чему и посвящена данная диссертационная работа.

Цель работы. В диссертации рассматривается вопрос построения численных методов поиска глобального минимума в задачах многомерной оптимизации, где целевая функция определена на гипериитервале и удовлетворяет на нем условию Липшица. При этом функция предполагается многоэкстремальной и недифференцируемой, а ее вычисление даже в одной точке допустимой области может потребовать значительных затрат (времени, машинной памяти и т. п.). Учитывая высокую вычислительную сложность рассматриваемых задач, целью работы является разработка быстрых методов их решения. Основное внимание уделяется использованию новой безызбыточной дп;и опальной стратегии адаптивного разбиения пшершггервалов, предложенной Я. Д. Сергеевым, которая успешно объединяет в себе идеи кривых, заполняющих пространство, и диагональных алгоритмов.

Научная новизна.

1. Предложена схема построения диагональных алгоритмов глобальной оптимизации, основанная на новой диагональной стратегии разбиения гиперинтервалов, которая позволяет избежать генерирования избыточных точек испытаний целевой функции, характерного для традиционных диагональных стратегий разбиения,

2. В рамках введенной схемы предложены новые многомерные диагональные алгоритмы глобальной оптимизации: информационно-статистический метод с адаптивной оценкой глобальной константы Липшица и геометрический метод, работающий со множеством оценок константы Липшица.

3. Предложена новая схема балансирования локальной и глобальной информации в ходе поиска глобального минимума. Показано, что техника локальной настройки на поведение целевой функции может быть успешно применена для построения многомерных геометрических диагональ-

ных алгоритмов глобальной оптимизации (в частности, предложены два новых геометрических диагональных метода с локалыюЙ настройкой).

4. Для всех построенных алгоритмов установлены достаточные условия сходимости к глобальному минимуму.

5. Для проверки работоспособности алгоритмов глобального поиска предложены генератор классов многомерных многоэкстремальных случайных тестовых функций, предоставляющий информацию о расположении всех точек минимумов и размерах их областей притяжения, и ряд критериев численного сравнения методов поиска глобального минимума на классах тестовых функций.

Личный вклад автора. Постановка задачи и методология исследования принадлежат руководителю. Им же предложена новая безызбыточная диагональная стратегия разбиения гиперинтервалов. Соискателем показано, как данная стратегия разбиения может быть применена к построению быстрых диагональных алгоритмов глобальной оптимизации. Ему принадлежат разработка в рамках новой диагональной схемы четырех алгоритмов с различными способами получения оценок константы Липшица, доказательство теорем о достаточных условиях сходимости, систематизация и выполнение исследований, обработка и интерпретация результатов. Соискателем разработана специализированная база данных для хранения поисковой информации и организации работы предложенной диагональной схемы, а также реализована программная система на ее основе. Кроме того, соискателю принадлежат разработка (совместно с руководителем) и программная реализация генератора классов многомерных многоэкстремальных тестовых функций с известным расположением локальных и глобальных минимумов, а также введение в практику ряда критериев численного сравнения алгоритмов глобального поиска на классах тестовых функций.

Практическая ценность работы. Исследования по теме диссертационной работы выполнялись при финансовой поддержке Российского фонда фундаментальных исследований (проекты 01-01-00587 и 04-01-00455-а), Итальянского фонда фундаментальных исследований (проск-

ты F1RB RBNE01WBBB и RBAUOl JYPN), а также гранта Капабрийского университета (г. Козснца, Италия) для молодых ученых (проект "Giovani Ricercatori", 2006 г.). Результаты работы используются также в следующих курсах факультета вычислительной математики н кибернетики Нижегородского государственного университета им. Н.И. Лобачевского, посвященных вопросам оптимизации; "Модели и методы принятия решений" (общий курс по специальности "Прикладная информатика"), "Методы принятия решений" (спецкурс магистратуры по специальности "Прикладная математика и информатика"), "Системы поддержки принятия решений" (спецкурс кафедры математического обеспечения ЭВМ по специальности "Прикладная математика и информатика"), "Параллельные вычисления и методы глобальной оптимизации" (спецкурс кафедры математического обеспечения ЭВМ по специальности "Прикладная математика

и информатика'1).

Апробация работы. Результаты работы были представлены на международных научно-практических семинарах "Высокопроизводительные параллельные вычисления на кластерных системах" (Нижний Новгород, 200!, 2002, 2003), VI международном конгрессе "Математическое моделирование" (Нижний Новгород, 2004), итальянских национальных конгрессах "Современная вычислительная математика" (Козепца, Италия, 2002, 2005), международном конгрессе "Нелинейная оптимизация большой размерности" (Эриче, Италия, 2004), IV международной "конференции "Достижения глобальной оптимизации" (Санторини, Греция, 2003), I международной конференции "Непрерывная оптимизация" (Трой, Нью-Йорк, США, 2004), международном семинаре "Глобальная оптимизация" (Альмерия, Испания, 2005), VIII конгрессе Итальянского общества прикладной математики (Рагуза, Италия, 2006), III международной конференции "Прикладная математика" (Пловдив, Болгария, 2006).

Публикации. Основное содержание диссертации изложено в работах [1J-I21]-

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, двух приложений и списка литературы

из 250 наименований. Основной печатный текст занимает 150 страниц, объем приложений равен 32 страницам. В работе содержатся 32 рисунка и 20 таблиц.

Краткое содержание работы

Во введении обосновывается актуальность темы диссертации, определяются цели исследования, освещаются научная новизна it практическая ценность полученных результатов, дается краткая характеристика диссертационной работы.

Первая глава - "Безусловная липшинева глобальная оптимизация". В этой главе производится постановка задачи безусловной липшнцевой глобальной оптимизации как частного случая общей задачи глобальной оптимизации и обсуждаются некоторые известные алгоритмы ее решения. В работе рассматривается задача вида

/• = /(*•) = min f{x), х е£>, (1)

rue многоэкстремальная целевая функция f(x) определена в Лг-мерном гнперинтервалс D

D = = {х е Ж* : a{j) < х (j) < ЪЦ), 1 <j<N}, (2)

и удовлетворяет в области поиска D условию Липшица с неизвестной константой Липшица L

Ух',х" е D, 0 < L < ос, (3)

«, Ь е Едг есть заданные векторы, || • || обозначает евклидову норму, a a'(j') является j'-й О = 1,2,..., ÎV) компонентой вектора х е K'v, Функция f(x) может быть недифференцируемой, поэтому лишь значения /(ж) в точках х € D могут быть доступны в ходе решения задачи (1}-<3). Предполагается также, что проведение испытания целевой функции (то есть ее вычисление-в некоторой точке допустимой области) требует больших вычислительных затрат.

В частности, в §1.1 дается постановка задачи, рассматриваются ее основные свойства и практическая ценность, В §1.2 обсуждается влияние информации о константе Липшица на скорость сходимости методов липшицевой глобальной оптимизации. Способы получения такой информации иллюстрируются кратким описанием некоторых одномерных алгоритмов липшицевой оптимизации, отдельные идеи которых используются в диссертационной работе при построении новых многомерных методов решения задачи глобальной оптимизации. В частности, кратко описываются метод ломаных (с априорно заданной константой Липшица), информационно-статистический алгоритм (с адаптивной оценкой глобальной константы Липшица), схема локальной настройки (с адаптивным оцениванием локальных констант Липшица) и алгоритм DIRECT (с оцениванием константы Липшица из множества возможных значений). Подчеркивается важность оценивания локальных констант Липшица и балансирования локальной и глобальной информации в ходе поиска глобального минимума для ускорения работы алгоритмов, В §1.3 демонстрируются возможные пути обобщения одномерных методов на многомерный случай (рассматриваются некоторые схемы редукции размерности, кратко обсуждаются различные аспекты обобщения одномерного метода ломаных, а также подходы адаптивного разбиения многомерной области поиска на подобласти).

Вторая глава - "Диагональный подход к решению задач глобальной оптимизации". Эта глава посвящена рассмотрению диагонального подхода, предложенного Я. Пинтером, к решению многомерных задач глобальной оптимизации, при котором область поиска последовательно разбивается на гкперкнтервалы и целевая функция вычисляется в двух вершинах главной диагонали каждого из получаемых гиперинтервалов. Диагональные алгоритмы, построенные в рамках такого подхода, с одной стороны, точнее оценивают наименьшие значения функции на га периптер валах по сравнению с алгоритмами, использующими популярные схемы разбиения е вычислением функция в центральных точках гиперинтервалов. С другой стороны, такие алгоритмы могут быть построены путем обобщения

многих эффективных одномерных методов на многомерный случай, что открывает интересные перспективы в создании новых бысфых алгоритмов глобальной оптимизации и, следовательно, имеет большое практическое значение.

Общая схема диагональных алгоритмов дастся в §2.1. Диагональный алгоритм адаптивно разбивает гиперинтервал поиска D из (2) на множество пшершггервалов Д = 1 < г < М(к), с вершинами и главными диагоналями (Лf{k) есть число гиперинтервалов на A"-ii итерации алгоритма). С целью уменьшения вычислительных затрат при оценивании значений f(x), испытания функции в каждом гиперинтервале Dj производятся только в его двух вершинах щ и Ь,. На каждой итерации производится оценка "пригодности" гиперннтервалов текущего разбиения для дальнейшего поиска глобального минимума, где "пригодность" гипериптервала Д часто может бьггь проинтерпретирована как вероятность принадлежности точки х* глобального минимума f{x) области Д. "Пригодность" гипер интервал а А чнеленио выражается при помощи значения Л,-, называемого характеристикой гиперинтервала. При этом некторыс одномерные характеристики могут быть использованы как прототипы для вычисления характеристики Я,- многомерного гипериптервала А, если рассматривать их (при надлежащей трансформации) на одномерном отрезке, являющемся главной диагональю [а;, гиперинтервала Д. Тем самым диагональный подход допускает естественное обобщение многих одномерных алгоритмов на многомерный случай. Гиперинтервал с "наилучшей" текущей характеристикой (например, с наибольшей) разбивается при помощи некоторой стратегии разбиения, и новые испытания проводятся в вершинах, соответствующих главной диагонали каждого из вновь сгенерированных гиперннтервалов. Задание вида характеристики Л(-) и стратегии разбиения определяют конкретный диагональный метод.

В §2.1 описываются также две стратегии разбиения, традиционно используемые в диагональных алгоритмах: Деление на 2N и Деление пополам. В первом случае гиперинтервал Д, выбранный для разбиения,

делится на 2*v новых гиперинтервала (где N есть размерность задачи), а во втором случае - на два новых гиперинтервала. Гиперплоскости, разделяющие выбранный гиперинтервал Dt, проходят через некую точку St на главной диагонали, расположение которой зависит от конкретной реализации алгоритма, причем в случае применения стратегии Деление па 2Л' используются N взаимно перпендикулярных гиперплоскостей, параллельных координатным плоскостям, а при стратегии Деление пополам - одна гиперплоскость, перпендикулярная стороне Dt с наибольшей длиной. После разбиения Д функция f(x) вычисляется только в вершинах главных диагоналей полученных гиперинтервалов.

В §2.2 предлагаются два новых диагональных алгоритма, обобщающих одномерный геометрический метод Я. Д. Сергеева с локальной настройкой на поведение целевой функции на многомерный случай при помощи днашнальнон схемы. Новые методы отличаются друг от друга стратегиями разбиения области поиска D: один метод использует стратегию Деление на 2*v, другой - Деление пополам. В остальном структура обоих методов идентична, что позволяет провести их описание и исследование в рамках единого алгоритма - Нового Диагонального Алгоритма с Локальной Настройкой (НДАЛН).

Ключевая идея методов НДАЛН заключается в сопряжении локальной и глобальной информации при адаптивном оценивании локальных констант Липшица в различных гиперинтервалах текущего разбиения области поиска D, Если главная диагональ некоторого гиперинтервал а мала (по сравнению с текущей максимальной длиной среди всех главных диагоналей в разбиении области D), то основное влияние на работу методов оказывает локальная информация о поведении функции вблизи вершин рассматриваемого гиперинтервала, а результаты испытаний, проведенных в других гипершггервалах, имеют меньшее значение. При рассмотрении большого гиперинтервала (с длиной его главной диагонали близкой к текущей наибольшей длине) роль глобальной информации повышается, так как в этом случае локальная информация может оказаться ненадежной. Балансирование глобальной и локальной информации в ходе глобально-

го поиска осуществляется таким образом, чтобы обеспечить нахождение глобального решения.

Исследуется характер сходимости методов НДАЛН и устанавливаются достаточные условия глобальной сходимости НДАЛН (теоремы* 2.1 и 2.2). Приводятся результаты численных экспериментов, призванных, с одной стороны, сравнить технику локальной настройкн с традиционным подходом к оцениванию глобальной константы Липшица, а с другой стороны, сравнить стратегии разбиения Деление на и Деление пополам. Показывается, что комбинация техники локальной настройки и стратегии разбиения Деление пополам является самой успешной среди рассмотренных методов на многомерных тестовых функциях из литературы.

В §2.3 традиционные стратегии разбиения исследуются более детально и раскрываются их недостатки. Как стратегия Деление на 2Л', так и стратегия Деление пополам кажутся достаточно эффективными, если рассматривать их на каждой отдельно взятой итерации. Однако отмечается, что обе стратегии в ходе работы алгоритма генерируют (независимо от вида характеристики Д(*)> определяющей, какой гнперинтервал должен быть поделен на каждой итерации) большое число избыточных точек испытаний функции /(х). Причины проведения избыточных испытаний одинаковы для обеих стратегий: (1) на каждой итерации /(х) вычисляется более чем в двух точках в каждой подобласти Д1Р из которых используются только две точки (например, при вычислении характеристики Щ); (2) нет возможности эффективно установить связь между подобластями, полученными на разных итерациях, что влечет за собой потерю информации о близости точек испытаний в многомерном пространстве поиска В С Ел' (в худшем случае поисковая информация дублируется). Такая избыточность ведет как к уменьшению скорости работы алгоритмов, так и к увеличению машинной памяти, требуемой для хранения необходимой поисковой информации.

В §2.4 описываются новая стратегия разбиения гнперинтервалов

"Нумерация тдорсм в автореферат« совпадает с иучсрацнсЗ в тстете диссертации.

(предложенная Я, Д, Сергеевым), се основные свойства и программная реализация. Данная стратегия разбиения успешно решает обе проблемы, обнаруженные при использовании стратегий Деление на 2N и Деление пополам, и не производит характерных для них избыточных вычислений функции, что дает основание называть новую диагональную стратегию разбиения гиперинтервалов безызбыточной. Действительно, во-первых, при ее использовании выбранный гиперинтервап Dt разбивается на три равных гиперинтервала, в которых функция /(ж) вычисляется строго в двух вершинах (теорема 2.3), что соответствует духу диагонального подхода. Во-вторых, использование специальной индексации гиперинтервалов, непосредственно связанной с регулярностью ироцедурьт разбиения, дает возможность (теорема 2.4) вычислять координаты вершин а; и каждого гип ер интервала А по его индексу, позволяя разграничить информацию о гипершпервале (как, например, значение его характеристики) и информацию о вершинах (как, например, значения функции в них). Поэтому координаты вершин вместе с соответствующей поисковой информацией могут быть сохранены в отдельной области данных (массив вершин), на элементы которой устанавливаются ссылки из области машинной памяти, хранящей информацию о гиперинтервалах (список гиперинтервалов). Вся необходимая информация о функции в конкретной вершине вычисляется только один раз, записывается в массив вершин, а затем при необходимости считывается из него. Таким образом, удается избежать избыточных вычислений функции н многократного сохранения информации о точках испытаний, являющихся вершинами нескольких гиперинтервалов одновременно. Кроме того, разбиения осуществляются так, что одна и та же точка испытаний f{x) может принадлежать различным (до 2jV) гиперинтервалам. При этом операция повторного вычисления функции (до 2Л' раз в одной и той же точке) заменяется гораздо менее трудоемкой операцией считывания информации из памяти ЭВМ, что значительно ускоряет процедуру поиска, особенно при увеличении размерности задачи N.

Новая стратегия разбиения является также процедурой, генерирую-

щей последовательность так называемых адаптивных диагональных кривых, схожих с кривыми, заполняющими пространство. Адаптивные диагональные кривые строятся на главных диагоналях гиперинтервалов текущего разбиения области £>. Порядок их разбиения отличается в разных подобластях и определяется заданием характеристик /?{•) гиперинтервалов и видом целевой функции. Конкретный диагональный алгоритм, использующий безызбыточную стратегию разбиения, строит свою собственную последовательность кривых. Если параметры алгоритма заданы надлежащим образом, то такая последовательность становится более плотной в окрестностях точек глобального минимума целевой функции.

Регулярность множества точек испытаний /(ж) при использовании безызбыточной стратегии разбиения позволяет построить специализированную базу данных и эффективно реализовать операции с данными в ней. Структура данных для организации работы новой стратегии разбиения и программная система на ее основе предлагаются в §2.4. Данная система может быть использована не только при решении задач липшн-цевой глобальной оптимизации, но также при анализе общей задачи минимального описания вектор-функции Р(х) = (/1(3;),/2(1),.. .,/„(х)) в Лг-мерном гиперинтервале, если такое описание достигается при помощи диагональных алгоритмов с использованием безызбыточной стратегии разбиения. Термин "минимальное описание" при этом подразумевает получение необходимой информации о поведении функции путем вычисления ее значений в минимально возможном количестве точек х € О,

Третья глава - "Методы глобальной оптимизации на основе безызбыточной диагональной стратегии разбиения".

В этой главе показывается, как безызбыточная стратегия разбиения может быть использована для построения быстрых диагональных алгоритмов глобальной оптимизации. Предлагаются и всесторонне изучаются два новых диагональных метода с использованием указанной стратегии разбиения и с различными подходами к получению информации о константе Липшица: в первом из методов адаптивно оценивается глобальная константа Липшица, по втором оценки константы Липшица выбираются

из множества возможных значений от нуля до бесконечности. Устанавливаются условия сходимости предлагаемых методов. Приводятся результаты их численного тестирования и сравнения с некоторыми известными алгоритмами глобального поиска.

В частности, в §3.1 предлагается Новый многомерный Диагональный Информационно-Статистический Алгоритм (НДИСА) липщнцевой глобальной оптимизации, основанный на использовании безызбыточной стратегии разбиения. Алгоритм НДИСА обобщает одномерный информационно-статистический алгоритм Р. Г. Стронгина на многомерный случай. Выбор данного одномерного метода в качестве базового для многомерного обобщения был мотивирован наличием хороших оценок его скорости сходимости.

Исследуются условия глобальной сходимости предложенного алгоритма (теоремы 3.1-3.3). Показывается, что существует бесконечное множество значений параметра метода, гарантирующих его сходимость только к точкам глобального минимума. Описываются численные эксперименты, проведенные для тестирования НДИСА и его сравнения с известными диагональными методами глобальной оптимизации на классах тестовых функций н на двух существенно многоэкотремальных десятнмер-ных функциях. Результаты экспериментов подтверждают теоретические выводы и демонстрируют превосходство нового метода по сравнению с традиционными диагональными алгоритмами пюбального поиска как по числу проводимых испытаний целевой функции, так и по. качественному исследованию области поиска В, характеризуемому количеством генерируемых гипершггервалов, За счет того, что каждая (внутренняя для области О) точка испытания /(х) может принадлежать до 2Л' гнпериптерва-лам области О с !£л' (п, следовательно, при использовании безызбыточной стратегии разбиения экономятся до вычислений функции), преимущество метода НДИСА увеличивается с ростом размерности задачи.

В §3.2 рассматривается Новый Диагональный Алгоритм со Множеством Оценок липшнцевых констант (НДАМО). В нем используется безызбыточная стратегия разбиения гипсрш1тервалов, усиленная новой

техникой выбора пшеринтервалов для разбиения. Предлагается новая процедура оценивания нижних границ значений целевой функции на ги-периитсрвалах (теорема 3.4), которая успешно сочетается с идеей (введенной в алгоритме DIRECT Д. Р. Джонса и др.) выбора оценок константы Липшица из множества возможных значений. Вводится понятие недоминируемых гиперинтервалов, и обосновывается процедура нахождения таких гнпериитервалов для их последующего возможного разбиения (теорема 3.5).

Новый метод нацелен (в отличие от популярных в зарубежной литературе алгоритмов DIRECT и его локально-ориентированной модификации DIRECT/, которые также используют в своей работе множественные оценки константы Липшица) на решение сложных многомерных задач с большим числом локальных минимумов. Для достижения этой цели предлагается двухфазная схема поиска глобального минимума, в которой выделяются глобальная и локальная фазы. Как известно, алгоритм DIRECT также балансирует глобальную и локальную информацию в ходе работы. Однако в нем явное преимущество отдается локальной фазе. Предлагаемая двухфазная схема алгоритма НДАМО при достижении достаточного уровня разбиений гиперинтервалов около точки текущего минимального значения функции переключает работу метода на исследование больших гиперинтервалов, которые могут содержать лучшее решение. Такое решение обосновано тем, что около текущей лучшей точки проводится большое число разбиений, поэтому ее окрестность содержит лишь малые гиперинтервалы, в то время как большие гипериитервалы могут находиться только далеко от текущего решения. Таким образом, НДАМО балансирует глобальную н локальную информацию более совершенным образом с целью обеспечения более быстрой сходимости метода к точкам глобального минимума сложных многоэкстремальных функций.

Исследуются условия сходимости предложенного алгоритма, в частности, устанавливается (теорема 3.6) его так называемая "всюду плотная" сходимость (то есть сходимость бесконечной последовательности точек испытаний к любой точке области поиска). Описываются и интерпрети-

руюгся результаты численных экспериментов, проведенных на более чем 1600 многоэкстремальных функциях из 16 тестовых классов размерностей Лт = 2,3,4 и 5 с использованием предлагаемого в работе набора пяти критериев сравнения методов. Результаты проведенных экспериментов демонстрируют, что применение алгоритма НДАМО для решения сложных многомерных задач ведет к значительным улучшениям (в терминах рассматриваемых критериев) по сравнению с использованием алгоритма DIRECT и его модификации DIRECT/. Так как метод НДАМО ориентирован на решение сложных многомерных многоэкстремальных задач, то чем более сложные задачи содержатся в тестовом классе, тем заметнее преимущество нового алгоритма.

В заключении сформулированы основные результаты диссертационной работы.

В Приложен»» А - "GKLS-геиератор классов тестовых функций" -обсуждается вопрос численного тестирования алгоритмов глобальной оптимизации п детально описывается предлагаемый в работе генератор (GKLS-reкератор) трех классов (недифференцируемых, непрерывно дифференцируемых и дважды непрерывно дифференцируемых) многомерных многоэкстремальных тестовых функций. Процедура генерирования состоит в переопределении выпуклой квадратичной функции (параболоида) при помощи полиномов. Каждый тестовый класс содержит 100 функций и задастся лишь пятью интуитивными параметрами: (I) размерностью задачи, (2) числом локальных минимумов, (3) значением глобального минимума, (4) радиусом области притяжения точки глобального минимума, (5) расстоянием между точкой глобального минимума и вершиной параболоида. Изменяя указанные параметры, пользователь может создавать тестовые классы с различными свойствами и исследовать различные аспекты интересующего его алгоритма глобального поиска. Большинство других параметров выбирается генератором при помощи датчика случайных чисел, обеспечивая при этом однородность свойств функций одного класса и повторяемость численных экспериментов на тестовых классах GКLS-генератора. Необходимое согласование многочисленных парамет-

ров каждой функции (например, уже для одной двумерной функции с десятью локальными минимумами их. больше 40) осуществляется автоматически. Для всех тестовых функций генератор предоставляет подробную информацию о расположении точек минимумов и о размерах их областей притяжения. Также генерируются частные производные дифференцируемых функций. Генератор использовался в диссертационной работе при проведении численных экспериментов. С момента, создания (2003 г.) он уже был запрошен компаниями и исследовательскими организациями из более чем 20 стран мира.

Наконец, в Приложении В предлагается ряд критериев сравнения методов глобального поиска с использованием классов тестовых функций.

Основные результаты работы

1. Показано, как техника локальной настройки на поведение целевой функции, позволяющая получить значительное ускорение сходимости ряда методов липшицевой глобальной оптимизации, может быть применена при построении диагональных алгоритмов. В частности, предложены два геометрических метода с локальной настройкой, использующие в работе традиционные диагональные стратегии разбиения области поиска.

2. Изучены свойства безызбыточной диагональной стратегии разбиения гиперинтервалов и показано, что она может быть полажена в основу новой диагональной схемы построения быстрых алгоритмов глобальной оптимизации. Разработана специализированная база данных для храпения поисковой информации и организации работы предложенной диагональной схемы, а также реализована программная система на ее основе. Эффективность работы системы объясняется тем, что целевая функция вычисляется в каждой точке только один раз, результат вычислений сохраняется в базе данных и считываете» при необходимости, заменяя трудоемкую операцию многократного (до 2Л', где N есть размерность задачи) вычисления функции значительно более простой операцией считывания информации из базы данных.

3. Предложен многомерный информационно-статистический метод, расширяющий одномерный информационно-статистический алгоритм Р. Г. Стронгина на многомерный случай при помощи диагональной схемы с безызбыточиой стратегией разбиения. Результаты обширных численных экспериментов показали, что новый метод существенно превосходит традиционные диагональные методы.

4. Предложен геометрический диагональный алгоритм решения сложных многомерных задач, использующий как новую схему разбиения, так и новый подход к получению оценок константы Липшица из множества возможных значений. Предложена и реализована новая техника балансирования локальной и глобальной информации в ходе поиска глобального минимума. Результаты многочисленных экспериментов показали значительное преимущество нового метода по сравнению с ранее используемыми схемами.

5. Для всех предложенных алгоритмов установлены достаточные условия сходимости к глобальному минимуму.

6. Предложен генератор* классов многомерных многоэкстремальных случайных тестовых функций с известным расположением локальных и глобальных минимумов. Он позволяет генерировать тестовые классы, состоящие из 100 функций с близкой структурой, путем задания пяти простых параметров и предоставляет полное описание всех сгенерированных функций. Предложен набор критериев для сравнения различных методов глобальной оптимизации на классах случайных тестовых функций.

"Генератор хранится » Гипс лл.пп.и алгоритмов CALGO, туудержипасмоП Международной ассоциацией вычислительной пехннкн (Astociaiion for Coiaputo*£ Machincry, ACMK a пкж: находится н свобод-ним доступе но WWW-адрссу: h*t[i./7ww\i. info Jeis.unk'i)l.jt,''-y>iraGK.LSty.ml С моыекта соилшя (20Û3 i.) он уже бил запрошен коммльимми н исследовательскими оу> пн>гчми и i более чем 20 стрдч мира.

Публикации по теме диссертационной работы

1. Сергеев}!. Д., Квасов Д. Е. Адаптивные диагональные кривые и их программная реализация // Вестник ННГУ: Математическое моделирование и оптимальное управление. - 2001. - Вып. 2, № 24. - С. 300-317.

2. Квасов Д. Е. Структуры данных для реализации адаптивных диагональных кривых It Материалы Международного научно-практического семинара "Высокопроизводительные параллельные вычисления на кластерных системах" / Под ред. Р, Г. Сгронгина, - Н. Новгород; Изд-во ННГУ, 2001.-С 76-80.

3. Сергеев Я, Д., Квасов Д. Е. Новый диагональный алгоритм глобальной минимизации // Материалы второго Международного научно-практического се Miraapa "'Высокопроизводительные параллельные вычисления на кластерных системах" / Под ред. Р. Г. Сгронгина. - Н. Новгород: Изд-во ННГУ, 2002. - С. 265-267.

4. Квасов Д. Е„ Сергеев Я. Д. Многомерный алгоритм глобальной оптимизации л.1 Wiiobç адаптивных диагональных кривых П Журнал вычислительной математики jt математической физики. - 2003. — Т. 43, № 1. -С. 42-59.

5. Гришагин В. А., Квасов Д. Е., Сергеев Я. Д. Сравнительная оценка эффективности синхронных и асинхронных рекурсивных алгоритмов глобальной оптимизации // Материалы третьего Международного научно-практического семинара "Высокопроизводительные параллельные вычисления на кластерных системах"/ Под ред. Р. Г. Сгронгина. - Н. Новгород: Изд-во ННГУ, 2003. - С. 243-246.

6. Квасов Д. Е., Сергеев Я. Д. Исследование методов глобальной оптимизации при помощи генератора классов тестовых функций: Методическая разработка. - Н. Новгород: Иза-во ННГУ, 2006. - 48 с.

7. Kvasov D. Е.. Pizzuti С., Sergeyev }'а. D. Comparison of two partition strategies in diagonal global optimization algorithms: Tech. Rep. 9. - Institute of Systems and Informatics, Rende (CS), Italy: ISI-CNR, 2001. - 16 p.

8. Gaviano M, Kvasov D. E., Lera D., Sergeyev Ya. D. Software per la generazione di classi di funzioni test nelPottiniizzazione globale it Atti del Convegno Nazionale Italiano "Analisi Numérica: Stato dell"Arte" / A cura di F. Costabile. - Pubblicazioni de) Laboratorio di Analisi Numérica. -Dipartimento di Matematica, Universitá dclla Calabria, Rende (CS), Italy; 2002, - P. 24.

9. Kvasov D. E., Sergeyev Ya. D. Information global optimization algorithms // Atti del Convegno Nazionale Italiano "Analisi Numérica: Stato deirArte" / A cura di F. Costabile. - Pubblicazioni del Laboratorio di Analisi Numérica. - Dipartimento di Matematica, Universitá della Calabria, Rende (CS), Italy: 2002. - R 32-33. 1

10. Sergeyev Ya. D.. Kvasov D. E. A new optimization algorithm using adaptive diagonal curves and its numerical testing: Tech. Rep. 1. - Institute of Systems and Informatics, Rende (CS), Italy: 1SI-CNR, 2002. - 13 p.

11. Kvasov D. E., Pizzuti C., Sergeyev Ya. D. Local tuning and partition strategies for diagonal GO methods 7/ Numerische Mathematik. - 2003. -Vol. 94, no. 1,-P. 93-106.

12. Gaviano M., Kvasov D. E„ Lera D., Sergeyev Ya. D. Algorithm 829; Software for generation of classes of test functions with known local and global minima for global optimization // ACM Transactions on Mathematical Software. - 2003. - Vol. 29, no. 4. - P. 469-480.

13. Kvasov D. E„ Gaviano M„ Lera D.. Sergeyev Ya. D. Generator of classes of test functions for global optimization algorithms // Proc. of the 4th International Conference on Frontiers in Global Optimization / Ed. by C, A, Floudas, P. M. Pardalos. - Vol, 10 of Aegean Conferences Series. -Santorini, Greece: 2003. - P. 55.

14. Sergeyev Ya. D„ Kvasov D. E. Diagonal Lipschitz global optimization algorithm working with a set of Lipschitz constants: Tech. Rep. RT-ICAR-CS-04-15. - Institute of High Performance Computing and Networking, Rende (CS), Italy: ICAR-CNR, 2004. - 33 p.

15. Kvasov D. E., Sergeyev Ya. D. Global optimization methods and classes of test functions // Proc. of the 1st International Conference on Continuous

Optimization JCCOPT-I / Ed. by J.-S. Pang. - Troy (NY), USA: 2004. -P. 38-39.

16. Sergeyev Ya. D., Kvasov D. E. Lipschitzian global optimization without the Lipschitz constant based on adaptive diagonal curves // Proc. of the 6th International Congress on Mathematical Modeling. - Nizhni Novgorod: NNGU Press, 2004. - P. 121.

17. Sergeyev Ya. D., Kvasov D. E. Diagonal global search based on a set of possible Lipschitz constants // Proc. of the International Workshop on Global Optimization GO051 Ed. by I. Garcia, L. G. Casado, E. M, T. Hendrix, B. T6th. - Almeria, Spain: University of Almeria, 2005. - P. 219-224.

18. Khalaf F M. H., Kvasov D. E. One-dimensional constrained Lipschitzian global optimization algorithms // Proc. of the International Conference "Numerical Analysis: The State of the Art" / Ed. by F. Costabile et al. - Pubblicazioni del Laboratorio di Analisi Numerica. - Diparttmento di Matematica, Universita della Calabria, Rende (CS), Italy: 2005. - P. 43.

19. Kvasov D. E., Sergeyev Ya. D. Global search based on efficient diagonal partitions and several techniques for obtaining the Lipschitz information // Proc. of the 3rd International Conference of Applied Mathematics TICAM / Ed. byD. Bainov, S. Nenov.-Vol. 2. - Plovdiv, Bulgaria: 2006.-P. 164-165.

20. Khalaf F. M. H., Kvasov D. E„ Sergeyev Ya. D. One-dimensional global optimization problems with multiextremal constraints // Proc. of the VIII Congress of the Italian Society for Applied and Industrial Mathematics SIMAl 2006 / Ed. by L. Puccio, P. Rughetti. - Universita degli Studi di Messina, Italy; 2006.-P. 184.

21 .Sergeyev Ya. D., Kvasov D. E. Global search based on efficient diagonal partitions and a set of Lipschitz constants // SIAM Journal on Optimization. -2006. - Vol. 16, no. 3. - P. 910-937.

Подписано в печать 12.1 ОД006 г. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Гарнитура «Тайме». Усл. п. л, 1. Заказ № 1453. Тираж 100 экз.

Отпечатано с готового оригинал-макета в типографии Нижегородского госуниверситета им, Н.И. Лобачевского. Лиц. ПД№ 18-0099 от 4.05.01. 603000, г. Н. Новгород, ул. Б. Покровская, 37

ВВЕДЕНИЕ

ГЛАВА 1. Безусловная липшицева глобальная оптимизация

1.1. Постановка задачи.

1.2. Способы оценивания константы Липшица.

1.3. Подходы к решению многомерных задач.

ГЛАВА 2. Диагональный подход к решению задач глобальной оптимизации

2.1. Общая схема диагональных алгоритмов.

2.2. Диагональные алгоритмы с локальной настройкой

2.2.1. Предварительные замечания.

2.2.2. Вычислительная схема алгоритмов

2.2.3. Условия сходимости.

2.2.4. Численные эксперименты.

2.3. Избыточность традиционных диагональных стратегий разбиения.

2.4. Безызбыточная стратегия разбиения и ее реализация.

ГЛАВА 3. Методы глобальной оптимизации на основе безызбыточной диагональной стратегии разбиения 83 3.1. Диагональный информационно-статистический алгоритм на основе безызбыточных разбиений.

3.1.1. Предварительные замечания.

3.1.2. Вычислительная схема алгоритма.

3.1.3. Условия сходимости.

3.1.4. Численные эксперименты.

3.2. Диагональный алгоритм на основе безызбыточных разбиений и множественных оценок константы Липшица.

3.2.1. Предварительные замечания.

3.2.2. Оценивание нижних границ значений функции

3.2.3. Нахождение недоминируемых гиперинтервалов.

3.2.4. Вычислительная схема алгоритма и анализ сходимости

3.2.5. Численные эксперименты.

Актуальность темы диссертационной работы. Многие задачи принятия оптимальных решений, возникающие в различных областях науки и техники, могут быть сформулированы как задачи оптимизации. Сложность математических моделей проектируемых систем, являющаяся натуральным следствием возрастающей сложности этих систем, значительно затрудняет процедуру поиска наилучшей комбинации управляемых параметров. Трудности численного решения подобных задач во многом связаны с их размерностью и видом оптимизируемой целевой функции, которая в общем случае может быть многоэкстремальной, недифференци-руемой и, более того, задана в форме так называемого "черного ящика", на вход которого подается аргумент, а на выходе наблюдается соответствующее значение функции. При этом может быть недоступна дополнительная информация о функции, такая как, например, ее градиент, и лишь значения целевой функции могут быть использованы в ходе решения задачи. Кроме того, каждое испытание функции (то есть, ее вычисление в некоторой точке допустимой области) может потребовать значительных вычислительных ресурсов.

Увеличение числа прикладных задач, описываемых функциями подобного типа, а также бурное развитие вычислительной техники привели к росту интереса к указанным задачам оптимизации и к развитию глобальной оптимизации как области математического программирования, занимающейся разработкой методов решения многоэкстремальных оптимизационных задач. Подходы глобальной оптимизации существенно отличаются от техники стандартных методов поиска локальных оптимумов функции (часто неспособных найти глобальное решение рассматриваемых многоэкстремальных задач) и характеризуются высокой вычислительной трудоемкостью. Вопросам численного решения таких задач посвящена обширная литература (см., например, работы Д. И. Батищева,

B. П. Булатова, Ф. П. Васильева, В. П. Гергеля, А. И. Голикова, С. 10. Городецкого, В. А. Гришагина, В. Ф. Демьянова, Ю. Г. Евтушенко, В. Г. Жа-дана, А. А. Жиглявского, А. Г. Жилинскаса, В. Г. Карманова, А. Г. Корот-ченко, В. Н. Малоземова, Н. Н. Моисеева, Й. Б. Моцкуса, Ю. И. Неймарка,

C. А. Пиявского, Э. Полака, JL А. Растригина, Я. Д. Сергеева, А. С. Стре-каловского, Р. Г. Стронгина, А. Г. Сухарева, П. Пардалоса, Я. Пинтера, X. Туя, Д. Уайлда, К. Флудаса, Д. Химмельблау, Р. Хорста, Д. Б. Юдина и других). При этом техники решения задач одномерной глобальной оптимизации исследованы достаточно глубоко, в то время как построение эффективных алгоритмов многомерной оптимизации, имеющих большое практическое значение, продолжает привлекать большое внимание исследователей.

Возможность построения адаптивных схем поиска наилучшего, то есть глобального, решения многоэкстремальных многомерных задач, отличных от переборных схем, предполагает наличие неких априорных предположений о свойствах задачи. Такие предположения служат математическим инструментом для получения оценок глобального решения задачи на основе проведенных испытаний целевой функции и играют существенную роль при построении эффективных алгоритмов глобального поиска. Для многих практических задач (таких как, например, решение нелинейных уравнений и неравенств; регулирование сложных нелинейных систем; оптимизация иерархических моделей, связанных с задачами размещения, системами обслуживания и т.п.) типичным является предположение о липшицевости функций, поскольку относительные вариации функций, характеризующих моделируемую систему, обычно не могут превышать некоторый порог, определяемый ограниченной энергией изменений в системе. Разработкой теории и методов численного решения задач подобного типа занимается липшицева глобальная оптимизация. Важность данной подобласти глобальной оптимизации объясняется как наличием большого числа прикладных задач, моделируемых при помощи липшицевых функций, так и обширностью класса таких функций.

Учитывая практическую важность задач многомерной липшицевой глобальной оптимизации и существующие сложности на пути их решения, представляются актуальными исследования по разработке эффективных алгоритмов решения подобных задач, чему и посвящена данная диссертационная работа.

Цель работы. В диссертации рассматривается вопрос построения численных методов поиска глобального минимума в задачах многомерной оптимизации, где целевая функция определена на гиперинтервале и удовлетворяет на нем условию Липшица. При этом функция предполагается многоэкстремальной, недифференцируемой, заданной в виде "черного ящика", и вычисление функции даже в одной точке допустимой области требует значительных затрат (времени, машинной памяти и т.п.). Учитывая высокую вычислительную сложность рассматриваемых задач, целью работы является разработка быстрых методов решения таких задач. Основное внимание уделяется использованию новой безызбыточной диагональной стратегии адаптивного разбиения гиперинтервалов, предложенной Я. Д. Сергеевым, которая успешно объединяет в себе идеи кривых, заполняющих пространство, и диагональных алгоритмов.

Научная новизна.

1. Предложена схема построения диагональных алгоритмов глобальной оптимизации, основанная на новой диагональной стратегии разбиения гиперинтервалов, которая позволяет избежать генерирования избыточных точек испытаний целевой функции, характерного для традиционных диагональных стратегий разбиения.

2. В рамках введенной схемы предложены новые многомерные диагональные алгоритмы глобальной оптимизации: информационностатистический метод с адаптивной оценкой глобальной константы Липшица и геометрический метод, работающий со множеством оценок константы Липшица.

3. Предложена новая схема балансирования локальной и глобальной информации в ходе поиска глобального минимума. Показано, что техника локальной настройки на поведение целевой функции может быть успешно применена для построения многомерных геометрических диагональных алгоритмов глобальной оптимизации.

4. Для всех построенных алгоритмов установлены достаточные условия сходимости к глобальному минимуму.

5. Для проверки работоспособности алгоритмов глобального поиска предложены генератор классов многомерных многоэкстремальных случайных тестовых функций, предоставляющий информацию о расположении всех точек минимумов и размерах их областей притяжения, и ряд критериев проверки эффективности методов поиска глобального минимума на основе классов тестовых функций.

Практическая ценность работы. Исследования по теме диссертационной работы выполнялись при финансовой поддержке Российского фонда фундаментальных исследований (проекты 01-01-00587 и 04-01-00455-а), Итальянского фонда фундаментальных исследований (проекты FIRB RBNE01WBBB и RBAU01JYPN), а также гранта Калабрийско-го университета (Козенца, Италия) для молодых ученых (проект Giovani Ricercatori, 2006 г.). Результаты работы используются также в следующих курсах факультета вычислительной математики и кибернетики Нижегородского государственного университета им. Н. И. Лобачевского, посвященных вопросам оптимизации: "Модели и методы принятия решений" (общий курс по специальности "Прикладная информатика"), "Методы принятия решений" (спецкурс магистратуры по специальности "Прикладная математика и информатика"), "Системы поддержки принятия решений" (спецкурс кафедры математического обеспечения ЭВМ по специальности "Прикладная математика и информатика"), "Параллельные вычисления и методы глобальной оптимизации" (спецкурс кафедры математического обеспечения ЭВМ по специальности "Прикладная математика и информатика").

Апробация работы. Результаты работы были представлены на международных научно-практических семинарах "Высокопроизводительные параллельные вычисления на кластерных системах" (Нижний Новгород,

2001, 2002, 2003), VI международном конгрессе "Математическое моделирование" (Нижний Новгород, 2004), итальянских национальных конгрессах "Современная вычислительная математика" (Козенца, Италия,

2002, 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]

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, двух приложений и списка литературы.

Результаты работы внедрены в учебный процесс в Нижегородском государственном университете им. Н.И. Лобачевского.

Основное содержание диссертационной работы отражено в 21 публикации, в частности, в статьях в журналах Журнал вычислительной математики и математической физики [39], Вестник Нижегородского университета им. Н. И. Лобачевского: Математическое моделирование и оптимальное управление [64], SIAM Journal on Optimization [223], ACM Transactions on Mathematical Software [89], Numerische Mathematik [164], а также в работах [22,38,40,65,129,158,159,163,165-167,219-222,228].

Генератор хранится в базе данных алгоритмов CALGO, поддерживаемой Международной ассоциацией вычислительной техники (Association for Computing Machinery, ACM), а также находится в свободном доступе по WWW-адрссу: http://wwwinfo.deis.unical.it/~yaro/GKLS.html. С момента создания (2003 г.) он уже был запрошен компаниями и исследовательскими организациями из более чем 20 стран мира.

1. Алгоритмы. Построение и анализ / Т. X. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн.- 2 изд. СПб.: "Вильяме", 2005.

2. Баркалов К. А., Стронгин Р. Г. Метод глобальной оптимизации с адаптивным порядком проверки ограничений // Ж. вычисл. матем. и матем. физ. 2002. - Т. 42, № 9. - С. 1338-1350.

3. Батищев Д. И. Методы оптимального проектирования. —М.: Радио и связь, 1984.

4. Батищев Д. И., Львович Я. Е„ Фролов В. Н. Оптимизация в САПР. — Воронеж: Изд-во ВГУ, 1997.

5. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. Учебное пособие. — 3 изд. — М.: БИНОМ, Лаборатория знаний, 2004.

6. Бертсекас Д. П. Условная оптимизация и методы множителей Лагранжа. — М.: Радио и связь, 1987.

7. Булавский В. А., Звягина Р. А., Яковлева М. А. Численные методы линейного программирования. —М.: Наука, 1977.

8. Булатов В. П. Методы погружений в задачах оптимизации. — Новосибирск: Наука, 1977.

9. Васильев Ф. П. Численные методы решения экстремальных задач. — М.: Наука, 1988.

10. Гавурин М. К, Малоземов В. Н. Экстремальные задачи с линейными ограничениями. Учебное пособие. — Л.: Изд-во ЛГУ, 1984.

11. И. Гергель В. П. Алгоритм глобального поиска с использованием производных // Динамика систем: Межвуз. тематич. сб. науч. тр. / Под ред. Ю. И. Неймарка. Горький: ГГУ, 1992.- С. 161-178.

12. Гергелъ В. П., Стронгин Р. Г. АБСОЛЮТ. Программная система для исследований и изучения методов глобальной оптимизации. Учебное пособие. — Н. Новгород: Изд-во ННГУ, 1998.

13. Гермейер 10. Б. Введение в теорию исследования операций, — М.: Наука, 1971.

14. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация.— М.: Мир, 1985.

15. Голиков А. И., Евтушенко 10. Г. Теоремы об альтернативах и их применение в численных методах // Ж. вычисл. матем. и матем. физ. 2003. - Т. 43, № 3. - С. 354-375.

16. Городецкий С. Ю. Методы поиска глобального экстремума. Методическая разработка. — Горький: Изд-во ГГУ, 1990.

17. Городецкий С. 10. Многоэкстремальная оптимизация на основе триангуляции области // Вестник ННГУ: Математическое моделирование и оптимальное управление,— 1999.— Т. 2, № 21. — С. 249268.

18. Гришагин В. А. Операционные характеристики некоторых алгоритмов глобального поиска // Проблемы случайного поиска. Задачи адаптации в технических системах. — Рига: Зинатне, 1978. — Т. 7,— С. 198-206.

19. Гришагин В. А. Об условиях сходимости для одного класса алгоритмов глобального поиска // Численные методы нелинейного программирования. — Харьков: Изд-во ХГУ, 1979. — С. 82-84.

20. Гришагин В. А. Программная реализация многошаговых алгоритмов глобального поиска // Матем. обеспечение САПР. — Горький: Изд-во ГГУ, 1981.-С. 150-163.

21. Гришагин В. А. Исследование одного класса численных методов решения многоэкстремальных задач: Автореф. диссерт. на соисканиеуч. степ. канд. физ.-мат. наук: спец. 05.13.02 / Горьк. гос. ун-т.— Горький, 1983.

22. Даугавет В. А. Численные методы квадратичного программирования. Учебное пособие. — СПб.: Изд-во С.-Петерб. ун-та, 2004.

23. Дейт К Д. Введение в системы баз данных. — 8 изд. — СПб.: "Вильяме", 2005.

24. Демьянов В. Ф., Малоземов В. Н. Введение в минимакс. — М.: Наука, 1972.

25. Демьянов В. Ф., Рубинов А. М. Основы негладкого анализа и квазидифференциальное исчисление. — М.: Наука, 1990.

26. Евтушенко Ю. Р. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) // Ж. вычисл. матем и матем. фш.-1971.-Т. 11, №6.-С. 1390-1403.

27. Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. — М.: Наука, 1982.

28. Евтушенко 10. Р., Жадан В. Р. Об одном подходе к систематизации численных методов нелинейного программирования // Изв. АН СССР. Техническая кибернетика. — 1983. — Т. 1. — С. 47-59.

29. Евтушенко Ю. Г., Ратькин В. А. Метод половинных делений для глобальной оптимизации функций многих переменных // Техническая кибернетика. — 1987. — Т. 1. — С. 119-127.

30. Ермаков С. М., Жиглявский А. А. Математическая теория оптимального эксперимента. — М.: Наука, 1987.

31. Ермольев Ю. М., Норкип В. И. Методы решения невыпуклых негладких задач стохастической оптимизации // Кибернетика и системный анализ. — 2003. — Т. 5. — С. 89-106.

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

33. Жилинскас А. Г. Одношаговый байесовский метод поиска экстремума функции одной переменной // Кибернетика. — 1975.— Т. 1.— С. 139-144.

34. Жилинскас А. Г. Глобальная оптимизация. Аксиоматика статистических моделей, алгоритмы, применение. — Вильнюс: Мокслас, 1986.

35. Карманов В. Г. Математическое программирование. — 5 изд. — М.: Физматлит, 2004.

36. Карр Ч., Хоув Ч. Количественные методы принятия решений в управлении и экономике, — М.: Мир, 1964.

37. Квасов Д. Е., Сергеев Я. Д. Многомерный алгоритм глобальной оптимизации на основе адаптивных диагональных кривых // Ж. вы-числ. матем и матем. физ. — 2003. — Т. 43, № 1. — С. 42-59.

38. Квасов Д. Е., Сергеев Я. Д. Исследование методов глобальной оптимизации при помощи генератора классов тестовых функций. Методическая разработка. — Н. Новгород: Изд-во ННГУ, 2006.

39. Кнут Д. Искусство программирования, Том 2: Получисленные алгоритмы.— 3 изд. — М.: "Вильяме", 2000.

40. Коротченко А. Г. Об одном алгоритме поиска наибольшего значения одномерных функций // Ж. вычисл. матем. и матем. физ. — 1978.-Т. 18, №3.-С. 563-573.

41. Коротченко А. Г. Алгоритм поиска минимума функции двух переменных, не требующий вычисления производных // Техническая кибернетика. 1979. - Т. 4. - С. 68-78.

42. Коротченко А. Г. Приближенно-оптимальный алгоритм поиска экстремума для одного класса функций II Ж. вычисл. матем. и матем. физ. 1996. - Т. 36, № 5. - С. 30-39.

43. Малков В. П., Угодчиков А. Г. Оптимизация упругих систем. — М.: Наука, 1981.

44. Михалевич В. С., Волкович В. А. Вычислительные методы исследования и проектирования сложных систем, — М.: Наука, 1982.

45. Морозов А. Д. Введение в теорию фракталов. Современная математика. — М.-Иж.: Изд-во Института компьютерных исследований, 2002.

46. Моцкус Й. Б. Многоэкстремальные задачи в проектировании. — М.: Наука, 1967.

47. Неймарк Ю. И., Стронгин Р. Г. Информационный подход к задаче поиска экстремума функций // Изв. АН СССР. Техническая кибернетика.- 1966.-Т. 1.-С. 17-26.

48. Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации, — М.: Наука, 1979.

49. Нефедов В. Н. Некоторые вопросы решения липшицевых задач глобальной оптимизации с использованием метода ветвей и границ // Ж. вычисл. матем. и матем. физ. — 1992,— Т. 32, № 4.— С. 512529.

50. Норкип В. И. О методе Пиявского для решения общей задачи глобальной оптимизации // Ж. вычисл. матем. и матем. физ. — 1992. — Т. 32, №7. С. 992-1006.

51. Пайтген Х.-О., Рихтер П. X. Красота фракталов. Образы комплексных систем. — М.: Мир, 1993.

52. Перевозчиков А. Г. О сложности вычисления глобального экстремума в одном классе многоэкстремальных задач // Ж. вычисл. матем. и матем. физ. 1990. - Т. 30, № 3. - С. 379-387.

53. Пиявский С. А. Алгоритмы отыскания абсолютного минимума функций // Теория оптимальных решений. — Киев: Изд-во ИК АН УССР, 1967. Т. 2. - С. 13-24.

54. Пиявский С. А. Один алгоритм отыскания абсолютного экстремума функции II Ж. вычисл. матем. и матем. физ. — 1972. — Т. 12, № 4. — С. 888-896.

55. Поляк Б. Т. Введение в оптимизацию. — М.: Наука, 1983.

56. Препарата Ф. П., Шеймос М. И. Вычислительная геометрия. Введение.—М.: Мир, 1989.

57. Пшеничный Б. Н., Данилин 10. М. Численные методы в экстремальных задачах. — М.: Наука, 1975.

58. Растригин Л. А. Адаптация сложных систем. Методы и приложения.—Рига: Зипатне, 1981.

59. Рокафеллар Р. Т. Выпуклый анализ. — М.: Мир, 1973.

60. Самарский А. А., Попов 10. П. Вычислительный эксперимент. — М.: Знание, 1983.

61. Сергеев Я. Д. Одномерный детерминированный алгоритм глобальной оптимизации // Ж. вычисл. матем и матем. физ.— 1995.— Т. 35, №5.-С. 705-717.

62. Сергеев Я. Д., Квасов Д. Е. Адаптивные диагональные кривые и их программная реализация // Вестник ННГУ: Математическое моделирование и оптимальное управление.— 2001.— Т. 2, № 24.— С. 300-317.

63. Сергеев Я. Д., Стронгип Р. Г., Рришагин В. А. Введение в параллельную глобальную оптимизацию. Учебное пособие. — Н. Новгород: Изд-во ННГУ, 1998.

64. Современные методы принятия оптимальных решений. Учебник / Р. Г. Стронгин, В. П. Гергель, С. 10. Городецкий и др. — Н. Новгород: Изд-во ННГУ, 2002.

65. Стрекаловский А. С. К проблеме глобального экстремума // Докл. АН СССР. 1987.-Т. 282, №5.-С. 1062-1066.

66. Стрекаловский А. С. Элементы невыпуклой оптимизации. — Новосибирск: Наука, 2003.

67. Стригулъ О. И. Поиск глобального экстремума в некотором подклассе функций с условием Липшица // Кибернетика.— 1985. — Т. 6.-С. 72-76.

68. Стронгин Р. Г. Информационный метод многоэкстремальной минимизации при измерениях с помехами // Изв. АН СССР. Техническая кибернетика. — 1969. — Т. 6. — С. 118-126.

69. Стронгин Р. Г. О сходимости одного алгоритма поиска глобального экстремума // Изв. АН СССР. Техническая кибернетика.— 1973.— Т. 4.-С. 10-16.

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

71. Стронгин Р. Г. Поиск глобального минимума. — М.: Знание, 1990. — Т. 2 из Математика и кибернетика.

72. Стронгин Р. Г., Баркалов К. А. О сходимости индексного алгоритма в задачах условной оптимизации с ег-резервированными решениями // Математические вопросы кибернетики. — М.: Наука, 1999.— Т. 8. С. 273-278.

73. Стронгин Р. Г., Гергель В. П. О реализации на ЭВМ многомерного обобщенного алгоритма глобального поиска // Вопросы кибернетики. Случайный поиск в задачах оптимизации.— М.: АН СССР, 1978.-С. 59-66.

74. Стронгин Р. Г., Маркин Д. Л. Минимизация многоэкстремальных функций при невыпуклых ограничениях II Кибернетика,— 1986.— Т. 4.-С. 63-69.

75. Сухарев А. Р. Минимаксные алгоритмы в задачах численного анализа. — М.: Наука, 1989.

76. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации.—М.: Наука, 1986.

77. Тимонов Л. Н. Алгоритм поиска глобального экстремума // Изв. АН СССР. Техническая кибернетика. — 1977. — Т. 3. — С. 53-60.

78. Уайлд Д. Оптимальное проектирование. — М.: Мир, 1981.

79. Хамисов О. В. Глобальная оптимизация функций с вогнутой опорной минорантой // Ж. вычисл. матем. и матем. физ. — 2004. — Т. 44, №9.-С. 1552-1563.

80. Химмельблау Д. Прикладное нелинейное программирование. — М.: Мир, 1975.

81. Черноусько Ф. Л. Об оптимальном поиске экстремума унимодальных функций II Ж. вычисл. матем. и матем. физ.— 1970,— Т. 19, №4.-С. 922-933.

82. Чичинадзе В. К. Решение невыпуклых нелинейных задач оптимизации.—М.: Наука, 1983.

83. Шалтяпис В. Р., Варнайте А. Вопросы структуры многоэкстремальных задач оптимизации. — Вильнюс: АН Лит. ССР, 1976. — Т. 2 из Теория оптимальных решений.

84. Шор Н. 3. Методы минимизации недифференцируемых функций и их приложения. — Киев: Наукова думка, 1979.

85. Algorithms for noisy problems in gas transmission pipeline optimization / R. G. Carter, J. M. Gablonsky, A. Patrick et al. // Optim. Eng. 2001.- Vol. 2, no. 2.- Pp. 139-157.

86. Algorithm 829: Software for generation of classes of test functions with known local and global minima for global optimization / M. Gaviano, D. E. Kvasov, D. Lera, Y. D. Sergeyev // ACM Trans. Math. Software. — 2003. Vol. 29, no. 4. - Pp. 469^80.

87. An algorithm for finding the zero-crossing of time signals with lipschitzean derivatives / P. Daponte, D. Grimaldi, A. Molinaro, Y. D. Sergeyev II Measurement.— 1995.— Vol. 16, no. 1.— Pp. 3749.

88. Andramonov M. Y., Rubinov A. M., Glover В. M. Cutting angle methods in global optimization // Appl. Math. Lett. — 1999,— Vol. 12, no. 3.— Pp. 95-100.

89. Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems / Ed. by P. M. Pardalos.— Dordrecht: Kluwer Academic Publishers, 2000.

90. Archetti E, Schoen F. A survey on the global optimization problem: General theory and computational approaches // Ann. Oper. Res.— 1984.-Vol. 1, no. 2,-Pp. 87-110.

91. Baritompa W. Customizing methods for global optimization A geometric viewpoint // J. Global Optim.— 1993,— Vol. 3, no. 2.— Pp. 193-212.

92. Baritompa W., Cutler A. Accelerations for global optimization covering methods using second derivatives II J. Global Optim. — 1994. — Vol. 4, no. 3.-Pp. 329-341.

93. Bartholomew-Biggs M. C., Parkhurst S. C., Wilson S. P. Using DIRECT to solve an aircraft routing problem 11 Comput. Optim. Appl. — 2002. — Vol. 21, no. 3.-Pp. 311-323.

94. Bartholomew-Biggs M. C., Ulanowski Z. J., Zakovic S. Using global optimization for a microparticle identification problem with noisy data // J. Global Optim. 2005. - Vol. 32, no. 3. - Pp. 325-347.

95. Basso P. Iterative methods for the localization of the global maximum // SIAMJ. Numer. Anal. 1982.- Vol. 19, no. 4.- Pp. 781-792.

96. Beliakov G. Cutting angle method A tool for constrained global optimization // Optim. Methods Softw.— 2004.— Vol. 19, no. 2.— Pp. 137-151.

97. Bertsimas D., Tsitsiklis J. N. Introduction to Linear Optimization.— Belmont, Massachusetts: Athena Scientific, 1997.

98. Branin F. H. Widely convergent method for finding multiple solutions of simultaneous nonlinear equations // IBM J. Res. Dev. — 1972. — Vol. 16, no. 5.-Pp. 504—522.

99. Breiman L., Cutler A. A deterministic algorithm for global optimization // Math. Program. — 1993.— Vol. 58, no. 1-3. — Pp. 179199.

100. ButzA. R. Space filling curves and mathematical programming // Inform. Control.- 1968.- Vol. 12, no. 4,- Pp. 314-330.

101. Casado L. G., Garcia I., Csendes T. A new multisection technique in interval methods for global optimization computing // Computing.— 2000. Vol. 65, no. 3. - Pp. 263-269.

102. Casado L. G., Garcia L, Sergeyev Y. D. Interval branch and bound algorithm for finding the first-zero-crossing-point in onedimensional functions // Reliab. Comput. 2000. - Vol. 6, no. 2. - Pp. 179-191.

103. Casado L. G., Garcia I., Sergeyev Y. D. Interval algorithms for finding the minimal root in a set of multiextremal nondifferentiable one-dimensional functions // SIAM J. Sci. Comput. — 2002. — Vol. 24, no. 2.-Pp. 359-376.

104. Clausen J., Zilinskas A. Subdivision, sampling, and initialization strategies for simplical branch and bound in global optimization // Comput. Math. Appl. 2002. - Vol. 44, no. 7. - Pp. 943-955.

105. A comparison of global optimization methods for the design of a highspeed civil transport / S. E. Cox, R. T. Haftka, C. A. Baker et al. // J. Global Optim. 2001. - Vol. 21, no. 4. - Pp. 415-433.

106. Csallner A. E., Csendes Т., Markot M. C. Multisection in interval branch-and-bound methods for global optimization I. Theoretical results // J. Global Optim. - 2000. - Vol. 16, no. 4. - Pp. 371-392.

107. Csendes Т., Ratz D. Subdivision direction selection in interval methods for global optimization // SIAM J. Numer. Anal— 1997.— Vol. 34, no. 3.-Pp. 922-938.

108. Developments in Global Optimization / Ed. by I. M. Bomze, T. Csendes, R. Horst, P. M. Pardalos. — Dordrecht: Kluwer Academic Publishers, 1997.

109. Dixon L. C. W. Global optima without convexity: Tech. rep. — Hatfield Polytechnic, Hatfield, England: Numerical Optimization Centre, 1978.

110. Dynamic data structures for a direct search algorithm / J. He, L. T. Watson, N. Ramakrishnan et al. // Comput. Optim. Appl. — 2002. — Vol. 23, no. l.-Pp. 5-25.

111. Encyclopedia of Optimization (6 Volumes) / Ed. by C. A. Floudas, P. M. Pardalos. — Kluwer Academic Publishers, 2001.

112. Essays and Surveys in Global Optimization / Ed. by C. Audet, P. Hansen, G. Savard. GERAD 25th Anniversary. — New York: Springer-Verlag, 2005.

113. Evtushenko Y G. Numerical Optimization Techniques. Translations Series in Mathematics and Engineering.— Berlin: Springer-Verlag, 1985.

114. Famularo D., Pugliese P., Sergeyev YD. A global optimization technique for checking parametric robustness // Automatica.— 1999. — Vol. 35, no. 9.-Pp. 1605-1611.

115. Fast detection of the first zero-crossing in a measurement signal set / P. Daponte, D. Grimaldi, A. Molinaro, Y. D. Sergeyev II Measurement. — 1996.-Vol. 19, no. l.-Pp. 29-39.

116. Finkel D. E., Kelley С. T. An adaptive restart implementation of DIRECT: Tech. Rep. CRSC-TR04-30.- North Carolina State University, Raleigh, NC, USA: Center for Research in Scientific Computation, 2004. — August.

117. Finkel D. E., Kelley С. T. Convergence analysis of the DIRECT algorithm: Tech. Rep. CRSC-TR04-28. North Carolina State University, Raleigh, NC, USA: Center for Research in Scientific Computation, 2004. — July.

118. Fletcher R. Practical Methods of Optimization. — New York: John Wiley & Sons, 2000.

119. Floudas C. A. Deterministic Global Optimization: Theory, Algorithms, and Applications. — Dordrecht: Kluwer Academic Publishers, 2000.

120. Gablonsky J. M. An implementation of the DIRECT algorithm: Tech. Rep. CRSC-TR98-29. North Carolina State University, Raleigh, NC, USA: Center for Research in Scientific Computation, 1998, —August.

121. Gablonsky J. M. Modifications of the DIRECT algorithm: Ph.D. thesis / North Carolina State University. Raleigh, NC, USA, 2001.

122. Gablonsky J. M., Kelley С. T. A locally-biased form of the DIRECT algorithm I I J. Global Optim. 2001. - Vol. 21, no. 1. - Pp. 27-37.

123. Galperin E. A. The cubic algorithm // J. Math. Anal. Appl.— 1985. — Vol. 112, no. 2.-Pp. 635-640.

124. Galperin E. A. Precision, complexity, and computational schemes of the cubic algorithm II J. Optim. Theory Appl. — 1988.— Vol. 57, no. 2.— Pp. 223-238.

125. Gaviano M., Lera D. Test functions with variable attraction regions for global optimization problems II J. Global Optim.— 1998.— Vol. 13, no. 2.-Pp. 207-223.

126. Gergel V. P. A global optimization algorithm for multivariate function with Lipschitzian first derivatives // J. Global Optim. — 1997. — Vol. 10, no. 3.-Pp. 257—281.

127. Gergel V. P., Sergeyev Y. D. Sequential and parallel algorithms for global minimizing functions with Lipschitzian derivatives // Comput. Math. Appl. 1999.- Vol. 37, no. 4-5.- Pp. 163—179.

128. Global Optimization: From Theory to Implementation / Ed. by L. Liberti, N. Maculan. — Berlin: Springer-Verlag, 2006. — Vol. 84 of Nonconvex Optimization and Its Applications.

129. Global Optimization in Engineering Design / Ed. by I. E. Grossmann.— Dordrecht: Kluwer Academic Publishers, 1996.

130. Global Optimization: Scientific and Engineering Case Studies / Ed. by J. D. Pinter. — Berlin: Springer-Vcrlag, 2006. — Vol. 85 of Nonconvex Optimization and Its Applications.

131. Global Optimization Using Interval Analysis / Ed. by E. R. Hansen.— New York: M. Dekker, 1992.- Vol. 165 of Pure and Applied Mathematics.

132. Goldstein A. A., Price J. P. On descent from local minima // Math. Сотр. 1971.- Vol. 25, no. 115.- Pp. 569-574.

133. Gourdin E., Jaumard В., Ellaia R. Global optimization of Holder functions // J. Global Optim. 1996. - Vol. 8, no. 4. - Pp. 323—348.

134. Grishagin V. A., Sergeyev Y. D., Strongin R. G. Parallel characteristic algorithms for solving problems of global optimization // J. Global Optim. 1997.- Vol. 10, no. 2.- Pp. 185—206.

135. Handbook of Applied Optimization / Ed. by P. M. Pardalos, M. G. C. Resende. New York: Oxford University Press, 2002.

136. Handbook of Global Optimization / Ed. by R. Horst, P. M. Pardalos. -Dordrecht: Kluwer Acadcmic Publishers, 1995. —Vol. 1.

137. Handbook of Global Optimization / Ed. by P. M. Pardalos, H. E. Romeijn. — Dordrecht: Kluwer Academic Publishers, 2002.— Vol. 2.

138. Handbook of Test Problems in Local and Global Optimization / C. A. Floudas, P. M. Pardalos, C. Adjiman et al. — Dordrecht: Kluwer Academic Publishers, 1999.

139. Hansen P., Jaumard B. Lipschitz optimization // Handbook of Global Optimization / Ed. by R. Horst, P. M. Pardalos. — Dordrecht: Kluwer Academic Publishers, 1995. Vol. 1. - Pp. 407-493.

140. Hartman J. К. Some experiments in global optimization // Nav. Res. Logist. 1973. - Vol. 20. - Pp. 569-576.

141. Hiriart-Urruty J.-B., Lemarechal C. Convex Analysis and Minimization Algorithms (Parts I and II). — Berlin: Springer-Verlag, 1996.

142. Horst R. On generalized bisection of ./V-simplices // Math. Сотр. — 1997.- Vol. 66, no. 218.- Pp. 691-698.

143. Horst R., Pardalos P. M., Thoai N. V. Introduction to Global Optimization. — Dordrecht: Kluwcr Academic Publishers, 1995, — (The 2nd edition: Kluwer Academic Publishers, 2001).

144. Horst R., Tuy H. On the convcrgencc of global methods in multiextremal optimization // J. Optim. Theory Appl.— 1987,— Vol. 54, no. 2.— Pp. 253-271.

145. Horst R., Tuy H. Global Optimization Deterministic Approaches.— Berlin: Springer-Verlag, 1996.

146. Huyer W., Neumaier A. Global optimization by multilevel coordinate search // J. Global Optim. 1999. - Vol. 14, no. 4. - Pp. 331-355.

147. Jones D. R. The DIRECT global optimization algorithm // Encyclopedia of Optimization / Ed. by C. A. Floudas, P. M. Pardalos. — Dordrecht: Kluwer Academic Publishers, 2001.- Vol. l.-Pp. 431-440.

148. Jones D. R., Perttunen C. D., Stuckman В. E. Lipschitzian optimization without the Lipschitz constant // J. Optim. Theory Appl— 1993. — Vol. 79, no. l.-Pp. 157-181.

149. Jones D. R., Schonlau M., Welch W. J. Efficient global optimization of expensive black-box functions // J. Global Optim.— 1998.— Vol. 13, no. 4. Pp. 455-492.

150. Kearfott R. B. Rigorous Global Search: Continuous Problems.— Dordrecht: Kluwer Academic Publishers, 1996.

151. Kelley С. T. Iterative Methods for Optimization. — Philadelphia: SIAM Publications, 1999. — Vol. 18 of Frontiers in Applied Mathematics.

152. Khompatraporn C., Pinter J. D., ZabinskyZ. B. Comparative assessment of algorithms and software for global optimization // J. Global Optim. — 2005.-Vol. 31,no. 4. — Pp. 613-633.

153. Kiseleva E. M., Stepanchuk T. On the efficiency of a global non-differentiable optimization algorithm based on the method of optimal set partitioning // J. Global Optim. 2003. - Vol. 25, no. 2. - Pp. 209235.

154. Korotkich V. V. Multilevel dichotomy algorithm in global optimization // Proc. of the 14th IFIP Conference on System Modelling and

155. Optimization / Ed. by I I.-J. Sebastian, K. Tammer. — Vol. 143 of Lecture Notes in Control and Information Sciences. — Leipzig: Springer-Verlag, 1989.-Pp. 161-169.

156. Kvasov D. E., Pizzuti C., Sergeyev Y. D. Comparison of two partition strategies in diagonal global optimization algorithms: Tech. Rep. 9.— Institute of Systems and Informatics, Rende(CS), Italy: ISI-CNR, 2001.

157. Kvasov D. E., Pizzuti C., Sergeyev Y. D. Local tuning and partition strategies for diagonal GO methods // Numer. Math. — 2003, — Vol. 94, no. l.-Pp. 93-106.

158. Kvasov D. E., Sergeyev Y. D. Global optimization methods and classes of test functions // Proc. of the 1st International Conference on Continuous Optimization ICCOPT-I / Ed. by J.-S. Pang. Troy (NY), USA: 2004. -Pp. 38-39.

159. Lera D., Sergeyev Y. D. Global minimization algorithms for Holder functions // BIT. — 2002. — Vol. 42, no. l.-Pp. 119—133.

160. Levy A. V., Montalvo A. The tunnelling algorithm for the global minimization of functions // SIAMJ. Sci. Stat. Comput. — 1985. — Vol. 6, no. l.-Pp. 15—29.

161. Ljungberg К., Holmgren S., Carlborg 6. Simultaneous search for multiple QTL using the global optimization algorithm DIRECT // Bioinformatics. 2004. - Vol. 20, no. 12.- Pp. 1887-1895.

162. Locatelli M. On the multilevel structure of global optimization problems // Comput. Optim. Appl. 2005. - Vol. 30, no. 1. - Pp. 5-22.

163. Lucidi S., Piccioni M. Random tunneling by means of acceptance-rejection sampling for global optimization // J. Optim. Theory Appl. — 1989. Vol. 62, no. 2. - Pp. 255-277.

164. A magnetic resonance device designed via global optimization techniques / G. Liuzzi, S. Lucidi, V. Piccialli, A. Sotgiu // Math. Program. 2004.- Vol. 101, no. 2. - Pp. 339—364.

165. Mangasarian O. L. Nonlinear Programming. — New York: McGraw-Hill, 1969.- Reprinted by SIAM Publications, 1994.

166. Mayne D. Q., Polak E. Outer approximation algorithm for nondifferentiable optimization problems // J. Optim. Theory Appl — 1984,-Vol. 42, no. l.-Pp. 19-30.

167. Meewella С. C., Mayne D. Q. An algorithm for global optimization of Lipschitz continuous functions // J. Optim. Theory Appl — 1988.— Vol. 57, no. 2.-Pp. 307-322.

168. Meewella С. C., Mayne D. Q. Efficient domain partitioning algorithms for global optimization of rational and Lipschitz continuous functions // J. Optim. Theory Appl 1989.- Vol. 61, no. 2.- Pp. 247-270.

169. Mladineo R. H. An algorithm for finding the global maximum of a multimodal multivariate function // Math. Program. — 1986.— Vol. 34, no. 2.-Pp. 188-200.

170. Mladineo R. H. Convergence rates of a global optimization algorithm // Math. Program. 1992.- Vol. 54, no. 1-3.- Pp. 223-232.

171. Mladineo R. H. Stochastic minimization of Lipschitz functions // Recent Advances in Global Optimization / Ed. by C. A. Floudas, R M. Pardalos. — Princcton, NJ, USA: Princeton University Press, 1992.-Pp. 369-383.

172. Mockus J. Bayesian Approach to Global Optimization.— Dordrecht: Kluwer Academic Publishers, 1989.

173. Mockus J. A Set of Examples of Global and Discrete Optimization: Applications of Bayesian Hcuristic Approach.— Dordrecht: Kluwer Academic Publishers, 2000.

174. Moles C. G., Mendes P, Banga J. R. Parameter estimation in biochemical pathways: A comparison of global optimization methods // Genome Res. 2003. - Vol. 13, no. 11. - Pp. 2467-2474.

175. Molinaro A., Pizzuti C., Sergeyev Y. D. Acceleration tools for diagonal information global optimization algorithms // Comput. Optim. Appl. — 2001.-Vol. 18, no. l.-Pp. 5-26.

176. Molinaro A., Sergeyev Y. D. An efficient algorithm for the zero-crossing detection in digitized measurement signal // Measurement.— 2001. — Vol. 30, no. 3.-Pp. 187-196.

177. Molinaro A., Sergeyev Y. D. Finding the minimal root of an equation with the multiextremal and nondiffercntiable left-hand part // Numer. Algorithms.- 2001.- Vol. 28, no. 1-4,- Pp. 255-272.

178. Nocedal J., Wright S. J. Numerical Optimization.— Dordrecht: Springer-Verlag, 1999.

179. Nonlinear Optimization and Related Topics / Ed. by G. Di Pillo, F. Giannessi. — Dordrecht: Kluwer Academic Publishers, 2000.

180. Numerical Techniques for Stochastic Optimization Problems / Ed. by Y. M. Ermoliev, R. J.-B. Wets. Berlin: Springer-Verlag, 1988.

181. Optimization and Industry: New Frontiers / Ed. by P. M. Pardalos, V. V. Korotkikh. — Dordrecht: Kluwer Academic Publishers, 2003.

182. Optimization in Computational Chemistry and Molecular Biology: Local and Global Approaches / Ed. by C. A. Floudas, P. M. Pardalos. — Kluwer Academic Publishers, 2000.

183. Pardalos P. M., Romeijn H. E., Tuy H. Recent developments and trends in global optimization // J. Comput. Appl. Math. — 2000. — Vol. 124, no. 1-2.-Pp. 209-228.

184. Pardalos P. M., Rosen J. B. Constrained Global Optimization: Algorithms and Applications.— New York: Springer-Verlag, 1987.— Vol. 268 of Springer Lecture Notes In Computer Science.

185. Pinter J. D. Extended univariate algorithms for A^-dimensional global optimization // Computing. 1986. - Vol. 36, no. 1-2. - Pp. 91-103.

186. Pinter J. D. Globally convergent methods for N-dimensional multiextremal optimization // Optimization.— 1986,— Vol. 17.— Pp. 187-202.

187. Pinter J. D. Convergence qualification of adaptive partition algorithms in global optimization // Math. Program. — 1992.— Vol. 56, no. 1-3.— Pp. 343-360.

188. Pinter J. D. Global Optimization in Action (Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications).— Dordrecht: Kluwer Academic Publishers, 1996.

189. Ratschek Я, Rockne J. New Computer Methods for Global Optimization. Mathematics and Its Applications. — Chichester, England: Ellis Horwood Ltd, 1988.

190. RatzD., Csendes T. On the selection of subdivision directions in interval branch-and-bound methods for global optimization II J. Global Optim. — 1995.-Vol. 7, no. 2.-Pp. 183-207.

191. Recent Advances in Global Optimization / Ed. by C. A. Floudas, P. M. Pardalos. — Princeton, NJ, USA: Princeton University Press, 1992.

192. Rinnooy Кап A. II. G., Timmer G. T. Global optimization // Handbook of Operations Research, Volume 1: Optimization / Ed. by G. L. Nemhauser, A. H. G. Rinnooy Kan, M. J. Todd.— Amsterdam: North-Holland, 1989.-Pp. 631-662.

193. Saez-Landete J., Alonso J., Bernabeu E. Design of zero reference codes by means of a global optimization method // Optics Express. — 2005.— Vol. 13, no. l.-Pp. 195-201.

194. Sagan H. Space-Filling Curves. — New York: Springer-Verlag, 1994.

195. Schittkowski K. Nonlinear Programming Codes.— Berlin: Springer-Verlag, 1980,— Vol. 183 of Lecture Notes in Economics and Mathematical Systems.

196. Schittkowski K. More Test Examples for Nonlinear Programming Codes. — Berlin: Springer-Verlag, 1987.— Vol. 282 of Lecture Notes in Economics and Mathematical Systems.

197. Schoen F. Stochastic techniques for global optimization: A survey of recent advances // J. Global Optim. 1991. - Vol. 1, no. 1. - Pp. 207228.

198. Schwefel H.-P. Evolution and Optimum Seeking.— New York: John Wiley & Sons, 1995.

199. Sergeyev Y. D. A onc-dimcnsional global minimization algorithm using local estimation of Lipschitz constant: Tcch. Rep. 28. — University of Calabria, Rende(CS), Italy: DEIS, Department of Electronics, Computer Science, and Systems, 1992.

200. Sergeyev Y. D. An information global optimization algorithm with local tuning // SIAMJ. Optim. 1995. - Vol. 5, no. 4. - Pp. 858-870.

201. Sergeyev Y. D. A two-points-three-intcrvals partition of the N-dimensional hyperinterval: Tcch. Rep. 10.— Institute of Systems and Informatics, Rende(CS), Italy: ISI-CNR, 1995.

202. Sergeyev Y. D. Global one-dimensional optimization using smooth auxiliary functions // Math. Program.— 1998.— Vol. 81, no. l.-Pp. 127-146.

203. Sergeyev Y. D. On convergcncc of "Divide the Best" global optimization algorithms // Optimization. 1998. - Vol. 44, no. 3. - Pp. 303-325.

204. Sergeyev Y. D. Multidimensional global optimization using the first derivatives // Comput. Math. Math. Phys.— 1999.— Vol. 39, no. 5.— Pp. 711-720.

205. Sergeyev Y. D. Parallel information algorithm with local tuning for solving multidimensional GO problems // J. Global Optim.— 1999. — Vol. 15, no. 2.-Pp. 157-167.

206. Sergeyev Y. D. An efficient strategy for adaptive partition of N-dimensional intervals in the framework of diagonal algorithms // J. Optim. Theory Appl. 2000. - Vol. 107, no. 1. - Pp. 145-168.

207. Sergeyev Y. D. Univariate global optimization with multiextremal non-differentiable constraints without penalty functions // Comput. Optim. Appl. 2006. - Vol. 34, no. 2. - Pp. 229-248.

208. Sergeyev Y. D., Grishagin V. A. Parallel asynchronous global search and the nested optimization scheme // J. Comput. Anal. Appl — 2001.— Vol. 3, no. 2.-Pp. 123-145.

209. Sergeyev Y. D., Kvasov D. E. A new optimization algorithm using adaptive diagonal curves and its numerical testing: Tech. Rep. 1.— Institute of Systems and Informatics, Rende(CS), Italy: ISI-CNR, 2002.

210. Sergeyev Y. D., Kvasov D. E. Diagonal Lipschitz global optimization algorithm working with a set of Lipschitz constants: Tech. Rep. RT-ICAR-CS-04-15.- Institute of High Performance Computing and Networking, Rende(CS), Italy: ICAR-CNR, 2004.

211. Sergeyev Y. D., Kvasov D. E. Lipschitzian global optimization without the Lipschitz constant based on adaptive diagonal curves // Proc. of the 6th International Congress on Mathematical Modeling.— Nizhni Novgorod: NNGU Press, 2004.- P. 121.

212. Sergeyev Y. D., Kvasov D. E. Global search based on efficient diagonal partitions and a set of Lipschitz constants // SIAM J. Optim. — 2006. — Vol. 16, no. 3.-Pp. 910-937.

213. Sergeyev Y. D., Markin D. L. An algorithm for solving global optimization problems with nonlinear constraints // J. Global Optim. — 1995.- Vol. 7, no. 4.- Pp. 407-419.

214. Sergeyev Y. D., Pugliese P., Famularo D. Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints // Math. Program. — 2003. — Vol. 96, no. 3.-Pp. 489-512.

215. Shen Z, Zhu Y. An interval version of Shubert's iterative method for the localization of the global maximum // Computing.— 1987.— Vol. 38, no. 3.-Pp. 275-280.

216. Shubert В. О. A sequential method seeking the global maximum of a function // SIAMJ. Numer. Anal. 1972.- Vol. 9, no. 3.- Pp. 379388.

217. State of The Art in Global Optimization: Computational Methods and Applications / Ed. by C. A. Floudas, P. M. Pardalos.— Dordrecht: Kluwer Academic Publishers, 1996.

218. Stephens C. P., Baritompa W. Global optimization requires global information // J. Optim. Theory Appl.— 1998.— Vol. 96, no. 3.— Pp. 575-588.

219. Stochastic and Global Optimization / Ed. by G. Dzemyda, V. Saltenis,V

220. A. Zilinskas. — Dordrecht: Kluwer Academic Publishers, 2002.

221. Strekalovsky A. S. Global optimality conditions for nonconvex optimization II J. Global Optim.- 1998.- Vol. 12, no. 4,- Pp. 415434.

222. Strongin R. G. Algorithms for multi-extremal mathematical programming problems employing the set of joint space-filling curves // J. Global Optim. 1992. - Vol. 2, no. 4. - Pp. 357-378.

223. Strongin R. G., Sergeyev Y. D. Global multidimensional optimization on parallel computer // Parallel Comput.— 1992.— Vol. 18, no. 11.— Pp. 1259-1273.

224. Strongin R. G., Sergeyev Y. D. Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms.— Dordrecht: Kluwer Academic Publishers, 2000.

225. Strongin R. G., Sergeyev Y. D. Global optimization: Fractal approach and non-redundant parallelism // J. Global Optim. — 2003.— Vol. 27, no. l.-Pp. 25-50.

226. Tawarmalani M., Sahinidis N. V. Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications.— Dordrecht: Kluwer Academic Publishers, 2002.

227. Torn A., Ali M. M., Viitanen S. Stochastic global optimization: Problem classes and solution techniques // J. Global Optim. — 1999.— Vol. 14, no. 4.-Pp. 437-447.

228. Torn A., Zilinskas A. Global Optimization. — Berlin: Springer-Verlag, 1989. — Vol. 350 of Lecture Notes in Computer Science.

229. Towards Global Optimization (Volumes 1 and 2) / Ed. by L. C. W. Dixon, G. P. Szego. Amsterdam: North-Holland, 1975,1978.

230. Two methods for solving optimization problems arising in electronic measurements and electrical engineering / Y. D. Sergeyev, P. Daponte, D. Grimaldi, A. Molinaro // SIAMJ. Optim. 1999. - Vol. 10, no. 1. -Pp. 1-21.

231. Vanderbei R. J. Extension of Piyavskii's algorithm to continuous global optimization I I J. Global Optim. 1999. - Vol. 14, no. 2. - Pp. 205— 216.

232. Vasile M., Summerer /,., De Pascale P. Design of Earth-Mars transfer trajectories using evolutionary-branching technique // Acta Astronautica. 2005. - Vol. 56, no. 8. - Pp. 705-720.

233. Walster G., Hansen E., Sengupta S. Test results for global optimization algorithm // Numerical Optimization 1984 / Ed. by P. T. Boggs, R. H. Byrd, R. B. Schnabel. — Philadelphia: SIAM, 1985.- Pp. 272287.

234. Watson L. Т., Baker С. A fully-distributed parallel global search algorithm // Engineering Computations. — 2001,— Vol. 18, no. 1-2.— Pp. 155-169.

235. Wood G. R. Multidimensional bisection applied to global optimisation // Comput. Math. Appl. 1991.-Vol. 21, no. 6-7.-Pp. 161-172.

236. Wood G. R. The bisection method in higher dimensions // Math. Program. 1992. - Vol. 55, no. 1-3. - Pp. 319-337.

237. Yao Y. Dynamic tunnelling algorithm for global optimization // IEEE Trans. Syst., Man, Cybem. 1989.- Vol. 19, no. 5.- Pp. 1222-1230.

238. Zhang Baoping, Wood G. R., Baritompa W. Multidimensional bisection: The performance and the contcxt // J. Global Optim. — 1993.— Vol. 3, no. 3.-Pp. 337-358.

239. Zhigljavsky A. A. Theory of Global Random Search.— Dordrecht: Kluwer Academic Publishers, 1991.