Ньютоновские методы для задач оптимизации с распадающимися ограничениями

• Автор: Погосян, Артур Левонович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 149 с. : ил.

Оглавление
Введение

Список основных обозначений

Глава 1. Задачи оптимизации с распадающимися ограничениями: элементы теории

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

1.1.1. Предварительные сведения

1.1.2. Поднятая задача

1.2. Задачи оптимизации с исчезающими ограничениями

1.2.1. Регулярность, стационарность и условия оптимальности

1.2.2. Поднятая задача

Глава 2. Обобщенные методы Ньютона для поднятых задач

2.1. Полу гладкий метод Ньютона для поднятых задач оптимизации
с комплементарными ограничениями
2.1.1. Локальный метод
2.1.2. Глобализация сходимости
2.2. Полугладкий метод последовательного квадратичного программирования для поднятых задач оптимизации
с комплементарными ограничениями
2.2.1. Локальный метод
2.2.2. Глобализация сходимости
2.3. Полугладкий метод последовательного квадратичного программирования для поднятых задач оптимизации
с исчезающими ограничениями
2.3.1. Локальный метод
2.3.2. Глобализация сходимости

Глава 3. Ньютоновские методы активного множества для задан оптимизации с исчезающими ограничениями
3.1. Локальные методы
3.1.1. Кусочный метод последовательного квадратичного программирования
3.1.2. Методы активного множества
3.2. Гибридная глобализация сходимости методов активного множества
3.2.1. Стратегия глобализации с возвратами
3.2.2. Стратегия глобализации с рекордами
3.2.3. Гибридные алгоритмы
Приложение А. Вычислительный эксперимент с поднятыми задачами оптимизации с комплементарными ограничениями
А.1. Полугладкий метод Ньютона
А.2. Полугладкий метод последовательного квадратичного
программирования
Приложение Б. Вычислительный эксперимент с задачами
оптимизации с исчезающими ограничениями
Б.1. Поднятые задачи
Б.2. Методы активного множества
Б.2.1. Гибридные полугладкие методы Ньютона
Б.2.2. Гибридные методы последовательного квадратичного
программирования
Заключение
Список литературы

Введение
Теория и численные методы оптимизации — относительно недавно сформировавшаяся самостоятельная область математической науки, бурный рост которой наблюдается со второй половины XIX века. За это время в оптимизации сформировались свои подобласти, появился свой язык, обнаружилось множество приложений; ей посвящено огромное количество работ (см., например, [1, 9] и цитированную там литературу). Процесс развития данной области знаний интенсивно продолжается и по сей день.
Эта работа посвящена изучению двух классов трудных оптимизационных задач, относящихся к объемлющему их классу условных задач оптимизации с распадающимися ограничениями. А именно, изучаются задачи оптимизации с комплементарными ограничениями и задачи оптимизации с исчезающими ограничениями. Термин «распадающиеся ограничения» возник в связи с тем, что допустимое множество задачи этого класса состоит из частей (кусков или ветвей), каждая из которых задается «обычными» (в некотором смысле) ограничениями. Задачи рассматриваемого класса трудны для анализа и численного решения, поскольку их ограничения обычно оказываются нерегулярными в традиционном смысле, в отличие от ограничений, задающих каждую ветвь.
Задача оптимизации с комплементарными ограничениями (ЗОКО) в общей форме имеет вид
f(x) -» min, h(x) = 0, g(x) < О,
G(х) > О, Н(х) ^ 0, (G{x), Н(х)) = О, а задача оптимизации с исчезающими ограничениями (ЗОИО) имеет вид
f(x) -> min, h(x) = 0, g(x) ä$ О,
H,(x) 0, Gl(x)IIl(x) ^ 0, г = 1, ..., s,
где f:Rn -» К - гладкая функция, а h: Rn -> IR', <7: R" -► IRm, G, H: Rn -> Rs -
гладкие отображения.
ЗОКО является относительно хорошо изученным классом задач, для которого все принципиальные трудности связаны именно с комплементарными ограничениями, составляющими вторую строку в (1) [59, 63]. Поэтому в данной работе для простоты
Пример 2. Рассмотрим задачу с ограничениями из примера 1 и с целевой функцией /(х) = —Х{ + х. Единственным (глобальным и локальным) решением такой задачи по-прежнему является точка х = 0. Поскольку /оо = 0, единственная отвечающая 5 = 0 кусочная задача совпадает с СЗМП
—XI + х • тт, Х ^0, дц ^ 0.
Ограничения этой задачи удовлетворяют условию регулярности Мангасариана-Фро-мовица, что дает выполнение кусочного условия регулярности Мангасариана-Фромо-вица в точке 5 = 0. Вместе с тем, отвечающие 5 = 0 множители Лагранжа СЗМП характеризуются системой
Д? + Д2? = 1> ДЯ = 0, дс ^ О,
решение которой не единственно. Значит, ЗОИО-строгое условие регулярности Мангасариана-Фромовица (23), (24) ни с каким множителем Д этой задачи выполняться не может.
Следующая теорема содержит необходимые условия первого порядка оптимальности для ЗОИО (12); она улучшает результат из (51, теорема 2.1] в том смысле, что в ее утверждении 2) предполагается выполнение ЗОИО-строгого условия регулярности Мангасариана-Фромовица вместо более сильного ЗОИО-условия линейной независимости.
Теорема 1. Пусть функция / и отображения д и С? дифференцируемы в точке I £ К", а отображения Н и Н дифференцируемы в некоторой окрестности этой точки, причелъ их производные непрерывны в точке х.
Тогда'.
1) если х — локальное решение задачи (12), и в этом решении выполнено кусочное условие регулярности Мангасариана-Фромовица, то х — В-стационарная точка задачи (12), а значит, и слабо стационарная точка этой задачи;
2) если в слабо стационарной точке х задачи (12) выполнено ЗОИО-строгое условие регулярности Мангасариана-Фромовица (23), (24) для отвечающего х множителя Лагранжа Д СЗМП (16) (т.е. для Д = (Дл, Д9, Дя, Дс) удовлетворяющего (18), (19)), то х является сильно стационарной точкой задачи (12), причем Д — единственный отвечающий х ЗОИ 0-множитель, а также единственный множитель Лагранжа СЗМП (16) и кусочной задачи (21) для любого разбиения (1, /г) 6 Т.