Исследование и разработка алгоритмов и комплекса программ для реализации модифицированного метода поиска глобального экстремума функции многих переменных

• Автор: Жадан, Игорь Витальевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 122 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

ГЛАВА 1. ОБЗОР МЕТОДОВ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ, НЕДОСТАТКИ И ПЕРСПЕКТИВЫ РАЗВИТИЯ

1.1 Задача глобальной оптимизации и практическая ценность

1.2 Обзор методов глобальной оптимизации. Преимущества и недостатки

1.3 Задача поиска глобального экстремума функции многих

переменных методов половинных делений и его недостатки

Выводы по главе

ГЛАВА 2. РАЗРАБОТКА И ТЕХНИКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ МОДИФИКАЦИЙ МЕТОДА ПОЛОВИННЫХ ДЕЛЕНИЙ ДЛЯ ПОИСКА ГЛОБАЛЬНОГО ЭКСТРЕМУМА

2.1 Модификация метода половинных делений (деление на 2ш параллелепипеда)

2.2 Модификация метода половинных делений - использование метода сопряженных градиентов в методе половинных делений .
2.3 Общая схема работы программного комплекса для поиска глобального экстремума функции многих переменных (для однопроцессорной ЭВМ)
2.4 Архитектура систем параллельной обработки данных
2.5 Алгоритм распараллеливания вычислительного процесса
реализованного метода
Выводы по главе
ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ПРОГРАММНОГО КОМПЛЕКСА И ЕГО ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ В АКУСТООПТИКЕ
3.1 Особенности работы программного комплекса в среде параллельных вычислений
3.2 Тестирование программного комплекса
3.3 Задача о минимизации функционала качества для обгонного
и обменного взаимодействия солитонов
Выводы по главе
ВЫВОДЫ ПО РАБОТЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ
Актуальность темы. В настоящее время одной из актуальных задач математического моделирования являются задачи рационального выбора, и в частности, задачи оптимизации [1-8]. Многоэкстремальная оптимизация и поиск глобального экстремума функции многих переменных занимает важное мето среди задач оптимизации [9-30].
Одной из особенностей решения такого рода задач является то, что лишь в редких случаях возможно получить их аналитическое решение. В связи с этим большую роль играют численные методы поиска оптимального решения. Основные трудности, возникающие при

решении задач поиска глобального экстремума связаны с большой размерностью задачи, многоэкстремальностью и негладкостью функции, а также наличием ограничений. Перечисленные проблемы привели к появлению большого числа вычислительных методов, учитывающих свойства входящих в постановку задачи функций.
На сегодняшний день существует значительное число различных подходов к решению задач глобальной оптимизации. Среди них можно отметить методы: случайного поиска; представления функций в виде суммы выпуклой и вогнутой составляющих; неравномерного покрытия; различные варианты метода ветвей и границ; методы, основанные на одномерной глобальной оптимизации и многие другие. Отечественные и зарубежные ученные, такие как Ю.Г. Евтушенко, С.Н. Пиявский, В.П. Булатов, Р.Г. Стронгин, Я.Д. Сергеев, А.Г. Жилинскас, A.C. Стрекаловский, Р. Хорст, X. Туй, А.М. Рубинов, И. Торн, П. Пардалос, К. Флоудас внесли значительный вклад в развитие теории и методов глобальной оптимизации.
Из-за многопеременности функций (количество переменных зачастую бывает более десятка), решения практических задач с помощью перечисленных выше методов обладают большой вычислительной трудоемкостью, что приводит к увеличению времени
расчетов. Таким образом, прежде чем приступить к решению подобных сложных вычислительных задач, необходимо сначала решить первостепенную задачу повышения эффективности методов поиска глобального экстремума.
Одним из наиболее плодотворных направлений глобальной оптимизации является идея неравномерных покрытий допустимого множества. В 1971 году опубликовал одну из первых научных работ Евтушенко Ю.Г. “Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке)” ЖВМ и МФ, 1971. 11 (6). С. 1390-1400, посвященную поиску глобального экстремума функций многих переменных с помощью неравномерных покрытий допустимого множества. Это направление в дальнейшем нашло плодотворное развитие. В статье Евтушенко Ю.Г. “Численный метод отыскания наилучших гарантированных оценок.” ЖВМ и МФ, 1972. 12 (1). С. 89— 104, метод был перенесен на нахождение гарантированных оценок в многошаговых играх, в статье Евтушенко Ю.Г., Потапов М. А. “Методы решения многокритериальных задач.”Доклады Академии наук СССР, 1986. Т. 291. N 1, С. 25-39.- на построение эпсилон-сети Паретовского множества. В статье Евтушенко Ю.Г., Ратькин В. А. “Метод половинных делений для глобальной оптимизации функции многих переменных.” Техническая кибернетика, 1987, (1). С. 119-127,
развивавшей метод неравномерных покрытий, был получен метод бисекций. Интерес к этому направлению значительно возрос в последнее время в связи с разработкой новых высокопроизводительных ЭВМ, основанных на параллельной и конвейерной организации расчётов.
В представленной диссертации для решения задач минимизации функции многих переменных при ограничениях предлагается модифицированный метод половинного деления, основанный на равномерном покрытии области ограничения на переменные функции.

4. Вычисляется антиградиент в этой точке
Г(! +1) — I ('Чг +ц).

5. Вычисляется А>+1> по формуле (23) или (24). Чтобы осуществить
рестарт алгоритма, то есть забыть последнее направление поиска и начать алгоритм заново в направлении скорейшего спуска, для
Переход на пункт 2.
Из приведенного алгоритма следует, что на шаге 2 осуществляется одномерная минимизация функции. Для этого, в частности, можно воспользоваться методом Фибоначчи, методом золотого сечения или методом бисекций. Более быструю сходимость обеспечивает метод Ньютона-Рафсона, но для этого необходимо иметь возможность вычисления матрицы Гессе. В последнем случае, переменная, по которой осуществляется оптимизация, вычисляется на каждом шаге итерации по формуле (31):
формулы Флетчера-Ривса ^(ччприсваивается 0 через каждые п + 1 шагов, для формулы Полака-Райбера — Ам - тах( Ды) >9).
6. Вычисляется новое сопряженное направление
°(г+1) - Г(М) + Р(1+1)^(0.

с_ ГГШ ЛтГ'(х^