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

• Автор: Куренной, Алексей Святославович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 134 с. : ил.

Оглавление
Введение
Список основных обозначений
Глава 1. Элементы вариационного и негладкого анализа
1.1. Условия регулярности для смешанных комплементарных задач
1.1.1. Смешанные комплементарные задачи
1.1.2. Системы Каруша-Куна-Таккера
1.2. Обобщенные дифференциалы
1.2.1. Общий случай
1.2.2. Отображения специального вида
1.3. Оценки расстояния до решений
Глава 2. Итерационные схемы для решения обобщенных уравнений
2.1. Абстрактные ньютоновские схемы
2.1.1. Сходимость к сильно метрически регулярным решениям
2.1.2. Сходимость к полуустойчивым решениям
2.1.3. Случай возможно неизолированных решений
2.2. Полугладкий метод Джозефи-Ныотона
Глава 3. Методы оптимизации для задач с липшицевыми производными
3.1. Метод модифицированных функций Лагранжа
3.1.1. Сходимость при достаточном условии второго порядка оптимальности
3.1.2. Сходимость при некритичности множителя
3.2. Метод множителей с линеаризованными ограничениями
3.3. Полугладкий метод последовательного квадратичного программирования
Заключение

Введение
Имеющийся в литературе локальный анализ наиболее эффективных численных методов оптимизации традиционно предполагает двукратную непрерывную дифференцируемость целевой функции и ограничений задачи. Настоящая работа посвящена распространению результатов о локальной сходимости этих методов на задачи с более слабыми свойствами гладкости и одновременно построению единой теории их локальной сходимости. Кроме того, целыо работы является изучение свойств локальной сходимости этих алгоритмов в различных предположениях о регулярности задачи, и, в частности, ослабление требований регулярности, па которые опираются существующие результаты об их локальной сходимости.
В работе рассматриваются задачи с липшицевыми производпьиш, т. е. задачи оптимизации, производные целевой функции и ограничений которых являются локально липшицевыми. Напомним, что отображение Ф: К'5 Нг называется локально липшицевыы в точке г 6 К“, если оно удовлетворяет условию Липшица в некоторой окрестности этой точки, т. е. если существует число I > 0 и окрестность [/СЕ5 точки г такие, что
||ф(21) - ф(г2)|| ^ £||«1 - гг|| V«1, г2 е и.
При этом отображение называется локально липшицевым, если оно локально липшицево в каждой точке своей области определения.
Приведем типичный пример возникновения задачи оптимизации с липшицевыми производными. Предположим, что фирма может производить п типов товаров, и ее выпуск задается вектором х € Ж", ^'-я компонента которого равна производимому количеству ^'-го товара. Пусть при производстве товаров может выделяться N различных вредных веществ. Объем г-го вредного вещества, выделяемый при производстве единицы у-го товара равен ау. Если выделенное количество г-го вредного вещества превышает установленный государством допустимый уровень то фирма должна понести затраты по утилизации излишка, равные его квадрату. Тогда, если р £ Ж" — вектор цен, а с: Ж" Ж — функция издержек, то

функция прибыли фирмы /: Л" ь4 IR. имеет вид
/(ж) = (р, х> - с(ж) - ^ ' atJTj - b,

Как легко проверить, функция / является дифференцируемой, и ее производная локально липшицева, но при этом функция /, вообще говоря, не является дважды дифференцируемой. Фирма может поставить перед собой задачу максимизации функции / при тех или иных ограничениях на выпуск. Если эти ограничения обладают соответствующими свойствами гладкости, то в результате возникает задача с лиишицевыми производными.
Другим важным примером задач оптимизации с лиишицевыми производными являются так называемые поднятые переформулировки задач оптимизации с комплементарными ограничениями. Задачей оптимизации с комплементарными ограничениями (см. [64, 71]) называется задача вида
где /: Лп ь-> И — заданная функция, а С, Я: Л" ы- Л"1 — заданные отображения. Один из подходов к решению таких задач оптимизации состоит в их переформулировке в виде задач с ограничениями равенствами (см. [49, 88]):
где у G Лт — дополнительная переменная, и операции взятия максимума/минимума и возведения в степень осуществляются покомпонентно. Такая переформулировка называется поднятой. Какими бы гладкими ни были отображения G и Я, ограничения поднятой переформулировки не являются дважды дифференцируемыми. В то же время, если функция / и отображения С и Я дифференцируемы, и их производные локально липшицевы, то переформулированная задача представляет собой задачу с лиишицевыми производными.
Еще одним источником возникновения задач оптимизации с лиишицевыми производными являются методы поиска обобщенного равновесия Нэша. Пусть имеется N агентов (игроков), и пусть стратегия г-го игрока представляет собой вектор размерности щ. Требуется найти набор стратегий ж = (xi, ж2, ..., хд?) £ И", п = щ +... + nN, ж, € Лп‘, такой, что для каждого г = 1, ..., N точка ж* является решением задачи оптимизации
fi(x 1, . . . , Ж;_Ь Ж;, Xi+U . . . , XN) -> lTlin, (хг , . . . , Хг _ I, Хг, Хг f-i, . . . , xN) G х,
где /,: IRTl Л — функция потерь г-го игрока, непрерывная по совокупности переменных и выпуклая по переменной ж,, а X С Л" — непустое замкнутое и выпуклое множество.
/(ж) —>■ min, G(ж) ^ О, Я(ж) ^ 0, (G(x), Я(ж)) = О,
/(ж) —> min, (min{0, у})2 — G{x) = 0, (max{0, г/})2 — Я(ж) = О
Далее, для любого к имеет место цепочка равенств

^ОФ . к г кдф, кг к

'Т+1 /ЯЛ

гр+1 гр+1
а,, 9Ф * *
ГР+1 /ял

= 1 гр+
+ £«: х=
'дФ, -ч ЗФ к й

ЭФ, к кч ^ к /^Ф, к г —(Ж ,у) + £о, (^г(^).г

у*)--П +
еднее равенство следует из второго равенства в (31) 'орого неравенства в (32) имеем
£+|+;.й-1 <*&.»*>). рз)
Х~1 ' ^
С учетом первого равенства в

< Да:

— (хк'* + ) - /*
^ гр+
1 Л /. 1 •ее«

>;(“(*. «*>-•? выводим оценку
9Ф , ь . _ч <9Ф , Ь „ , Л
ГР+1 ЯЛ

, с учетом леммы 4 <9Ф

< £а: г=
дФ, к,, _ч к

4г||у* - у|| £ аг = Му* - у|1. 1=
юнстанта Липшица для К на Ы. Отсюда следует, чг—~ч , (дФ. к , ЭФ, * , ьЛ