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

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

Оглавление
Введение
Список основных обозначений
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]. Родоначальником теории вариационных неравенств стало вариационное исчисление. Исследования конечно-

Глава 1. Барьерно-проективный метод для линейных задач дополнительности
1.2 Допустимый вариант метода
Введем обозначение
г = {[х,у е Ш2" : Мх - у + = 0„}
и положим Z+ = Z О Ш2.'1. На основании (1.6) заключаем, что множество
Z является положительно инвариантным относительно системы (1.11),
т.е. из условия го & Z следует, что [х(£, го),у(Ь, г)] € Z для всех П> 0.
Поэтому, если относительно начальной пары го = [хо,Уо] потребовать,
чтобы г0 € Z, то систему (1.11) можно переписать в более простом виде:

— = -П(х)[1п + С2(х,у)(1п- М)0(х)]у,
& (1-28) = -П{у)[1п-С-х,у){1п-М)П{у)]х.
Систему (1.28) назовем допустимым вариантом барьерно-проективного метода (1-11).
Теорема 2. Пусть [а- невырожденное решение задачи (1-1). Тогда решения системы (1.28) локально сходятся к [ж*, у*] на Z+.
Доказательство. Поскольку [х*,у*] - невырожденное решение задачи (1.1), то по теореме 1 пара л* = [а:*, у*] есть экспоненциально устойчивое положение равновесия для системы (1.11) для любого т > 0. Согласно определению экспоненциальной устойчивости существует такая окрестность Д(г*) пары г*, что для любой начальной пары го = [аго, 2/о] из этой окрестности траектория г(Ъ, гй) = [х(1, го), у И, г0)] сходится к г*, причем справедлива оценка
\zit, г0) - 2*|| < Се',
где С ит/- некоторые положительные константы. Но траектории системы (1.28) и траектории системы (1.11) совпадают, если в качестве