Барьерно-проективные методы для задач дополнительности

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

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

1 Барьерно-проективный метод для линейных задач дополнительности

1.1 Устойчивый вариант барьерно-проективного метода

1.2 Допустимый вариант метода

1.3 Нелокальное поведение допустимого варианта метода

2 Барьерно-проективный метод с наискорейшим спуском для линейных задач дополнительности

2.1 Дискретные варианты барьерно-проективного метода

2.2 Метод наискорейшего спуска

2.3 Конечная локальная сходимость

2.4 Правые части в особых парах

2.5 Модифицированный барьерно-проективный метод с наискорейшим спуском

2.6 Конечная нелокальная сходимость метода
3 Барьерно-проективный метод для нелинейной задачи дополнительности
3.1 Нелинейная задача дополнительности

3.2 Первый вариант метода
3.3 Второй вариант метода
3.4 Итеративные процессы
4 Вычислительные эксперименты
4.1 Задача распределенного равновесия
4.2 Реализация устойчивого варианта барьерно-проективного
метода
4.3 Численная реализация допустимого варианта барьернопроективного метода и метода с наискорейшим спуском
4.4 Вычислительные эксперименты с модифицированным методом наискорейшего спуска
Заключение
Список использованных источников
А Тестовые задачи
А.1 Задачи для тестирования методов
А.2 Задачи для тестирования модифицированного метода с
наискорейшим спуском
В своей основной постановке задача дополнительности состоит в нахождении пары точек в п-мерном пространстве, связанных определенной функциональной зависимостью. При этом координаты искомых точек должны быть неотрицательны, и в каждой паре соответствующих координат не более чем одна величина может быть отлична от нуля.
Задачи дополнительности тесно связаны с двумя другими задачами математического программирования: решением вариационных неравенств и нахождением неподвижных точек. Теоремы существования и методы решения двух последних задач используются в теории задач дополнительности. И наоборот, идеи и специальные методы, разработанные для задач дополнительности, применяются для решения вариационных неравенств и для нахождения неподвижных точек [36, 41, 52, 64]. Обычно в литературе вариационные неравенства и задачи дополнительности рассматривают вместе. Это связано главным образом с тем обстоятельством, что задачи дополнительности являются важным частным случаем вариационных неравенств.
Вариационные неравенства стали изучаться в 1960-х годах, начиная с работы Дж. Стампаккьи. В эти же годы были опубликованы первые труды в этой области [59, 73, 74, 91]. Родоначальником теории вариационных неравенств стало вариационное исчисление. Исследования конечноБарьерно-проективный метод с наискорейшим спуском для ЛЗД

Тогда барьерно-проективный метод (2.2) можно переписать в виде
Хк+1 = Хк - акАхк, ук+1 =ук- акАук, (2.4)

Ахк = Р^хк, ук), Аук = Р£хк, ук). (2.5)
Рассмотрим поведение функции V(х, у) = (х, у) вдоль направлений, обратных Ахк и Аук, выпущенных из произвольной допустимой пары хк,Ук- Взяв а > 0, получаем
ф[а) = V{хк - аАхк, ук - аАук) = V(хк, ук) - сДж*, ук)а + с2(хк, ук)а2,
(2.6)

с(х,у) = (Ах, у) + (А у,х), с2(х,у) = (Ах,Ау).
Имеем х% = 0, хк = 0, ук = 0 и ук = 0. Кроме того, согласно (2.5),
Ахк = 0, Ахк = 0, Агук = 0, Ау1 = 0.
Поэтому выражения для коэффициентов С и с2 упрощаются
С1(хк,ук) = <Дж£,у£) + (Ау£,х%), с2(хк,ук) = (Ах{,Ау{),
т.е. фактически они зависят только от компонент с индексами из множества Jp{xk,yk).
Как было установлено, для сильно невырожденной ЛЗД Ахк — 0, Аук = 0 в том и только том случае, когда пара [хк, ук] является угловой точкой множества Z+. Поэтому, если пара [хк, ук] является угловой точкой множества Z+, то с(хк,ук) = с2(хк,ук) = 0. Покажем, что для неособых пар [хк,ук] коэффициенты С(хк, ук) и с2(хк, у к) обязательно ненулевые.