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

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

Основные обозначения

1 Оценки расстояния до решения и идентификация активных индексов

1.1 Смешанные комплементарные задачи

1.2 Связь с другими задачами

1.3 Переформулировки МСР в виде систем уравнений

1.4 Оценки расстояния до решения и условия регулярности

1.5 Идентификация активных индексов

% 2 Ньютоновские методы

2.1 Локальные методы активного множества

2.2 Глобализация сходимости

2.3 Сравнение с другими методами ньютоновского типа

3 Системы Каруша-Куна-Таккера
3.1 Постановка задачи
3.2 Оценки расстояния до решения
3.3 Идентификация активных индексов и ньютоновские методы
3.4 Сравнение с. другими методами
А Вычислительные эксперименты с идентификацией
Б Вычислительные эксперименты с ньютоновскими методами
Б.1 Локальные численные эксперименты
Б.2 Численные эксперименты с глобальной схемой
Заключение
Литература

В работе рассматривается новая постановка задачи, лишь недавно получившая распространение в оптимизационной литературе, а именно, смешанная комплементарная задача (Mixed Complementarity Problem, МСР), которая представляет из себя вариационное неравенство на параллелепипеде. А именно, пусть задан параллелепи-
^ < щ, г = 1,2 п, и отображение F : К" —> К", которое в дальнейшем будет предполагаться достаточно гладким. Требуется
Эквивалентным образом МСР формулируется в виде
0, если Х{
= 0, если Хі Є (2)
^ 0, ЄСЛИ Xt = Uj.
Многие задачи, связанные с отысканием разного рода равновесий, могут быть записаны в формате МСР (см. [40, 32, 29]). Кроме того, этот формат объединяет в
себе целый ряд важнейших постановок, возникающих в теории оптимизации, вариационном исчислении и других областях математики. Перечислим некоторые из таких постановок.
1. Система нелинейных уравнений
где F : R" —> Rn — заданное отображение.
2. Комплементарная задача (Nonlinear Complementarity Problem, NCP), состоящая в отыскании элемента х Є Rn такого, что
найти х Є [£, и] такой, что (F(x), у — ж) ^ 0 Vy Є [£, ы].
F(z) = 0,
(3)
х ^ 0, F(x) ^ 0, (ж, F(x)) = 0,
(4)

где F : Rn —> Rn — заданное отображение.
3. Система Каруша-Куна-Таккера (ККТ)
g{x) - (G'{x))Tn = 0, (5)
/О О, G(z) > 0, (ti,G(z))= О,
относительно (х, /j) £ Р х Rm, где д : Rp —> Rp и G : Rp —> Rm — заданные отображения. Переменную х еШР принято называть прямой, а ц G Еш — двойственной.
Если для некоторой функции / : Rp —> R выполнено
g{z) = f(z), z е Rp,
то при выполнении определенных условий регулярности ограничений система ККТ дает необходимые условия первого порядка локальной оптимальности в задаче оптимизации
f(z) —> min, г 6 D = {z € Rp | G(z) ^ 0}.
Приведем обзор основных известных подходов к построению ньютоновских методов для решения задач вышеперечисленных классов.
Различным методам решения гладких систем уравнений посвящены монографии [12, 9], причем особое внимание там уделено методу Ньютона и квазиньютоновским методам. Роль ньютоновских методов в современном численном нелинейном анализе и оптимизации трудно переоценить. Согласно теореме Денниса-Морэ, в соответствующих предположениях ньютоновский характер итерационного процесса является не только достаточным, но и необходимым для высокой скорости его сходимости. Именно поэтому наиболее эффективные и практически востребованные алгоритмы для различных классов нелинейных задач имеют в своей основе соответствующим образом понимаемую и адаптированную ньютоновскую итерацию.
Что касается NCP, то можно выделить следующие известные подходы к численному решению таких задач. В начале 90-х большое внимание уделялось сведению NCP к гладким задачам оптимизации с последующим применением к последним традиционных численных методов оптимизации [2, 36, 59, 60, 76], например, метода последовательного квадратичного программирования (Sequential Quadratic Programming, SQP) [65]. В последнее время все более популярным становится другой подход, основанный на переформулировках NCP в виде негладких систем нелинейных уравнений, которые можно решать с помощью специальных неглаких (так
Глава 1. Оценки расстояния до решения и идентификация активных индексов
в то время как невозможно получить элементы В-дифференциала такого вида. Это связано с тем, что значения и иг, соответствующие второй и третьей строке матрицы, не могут выбираться независимо.
Разумеется, регулярность максимального В-дифференциала
влечет В D-регулярность соответствующего отображения; обратное, вообще говоря, неверно, что иллюстрирует следующий пример.
Пример 1.7. Рассмотрим NCP при п = 2, F(x) = ((ац +х2)/2, (xj + х2)/2). Точка х = 0 является решением этой задачи, причем, как нетрудно видеть, максимальные S-дифференциалы Ф^я и d точке х содержат единственную вырожденную матно эта матрица не принадлежит ни ЗдФдгя(х), ни <9дФдд(й).
В [25, пример 2.1] показано, что регулярность максимального В-дифференциала Фдгя не влечет не только аналогичное свойство для Фдд, но даже SD-регулярность Фре- Вместе с тем, очевидно, что регулярность максимального В-дифференциала ФFO влечет аналогичное свойство для Флгд.
Напомним еще одно важнейшее понятие регулярности, введенное в [71]: решение х МСР сильно регулярно (по Робинсону), если для всякого у Е R”, достаточно близкого к нулю, возмущенная линеаризованная МСР:
найти х Є [І, и] такой, что {F(x) + F'(x)(x — х) — у, х — х) > 0, Vx Є [І, и]
имеет в некоторой окрестности точки х единственное решение, причем это решение зависит от у липшицевым образом. Сильная регулярность влечет регулярность максимального S-дифференциала Фhr и Фдд- Для Ф^д в случае ККТ это установлено в [55], а в случае NCP — в [25, теорема 2.5], причем приводимое там доказательство без изменений проходит и для МСР. Отсутствие обратной импликаций для Фдгд демонстрируется в [25, пример 2.1]. Для Фfb нужная импликация установлена в [31, теорема 1], отсутствие обратной импликации демонстрируется следующим примером.
Пример 1.8. Рассмотрим NCP при п = 1, F(x) = —х. Непосредственными вычислениями получается, решение 2 = 0 обладает BD-регулярностью, но не сильной