Решение вариационного неравенства алгоритмами неподвижных точек

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

Оглавление

Глава 1. Введение

1.1. Задачи работы и методы их решения

1.2. Обзор развития симплициальных алгоритмов неподвижной точки

и их приложений

1.3. Структурная организация работы

1.4. Личный вклад диссертанта

Г лава 2. Предварительные результаты

2.1. Триангуляции

2.2. Примитивные множества

2.3. Векторные и целочисленные метки

2.4. Два. базовых симплициальных алгоритма неподвижной точки
Глава 3. Конструкция алгоритмов в отсутствии ограничений
3.1. Обшая схема алгоритма с целочисленными метками
3.2. Применение общей схемы для построения 2а алгоритма
3.3. Применение общей схемы для построения 3 1 алгоритма
3.4. Критерий существования алгоритма с заданным веером
Глава 4. Конструкция алгоритмов при линейных ограничениях
4.1. Обшая схема алгоритма с целочисленными метками
4.2. Алгоритм на симплициальном ограниченном многограннике
4.3. Алгоритм на несимплициальном ограниченном многограннике
4.4. Алгоритм на неограниченном многограннике
Глава 5. Численные эксперименты
5.1. Работа на сильно нелинейных задачах
5.2. Работа на слабо нелинейных задачах
5.3. Сравнение с градиентными методами
5.4. Опенки для алгоритмов при ограничениях
5.5. Сходимость процедуры нащупывания точки Нэша
Библиография


В совокупности со вторым условием, третье условие гарантирует что рано или поздно алгоритм найдет симплекс, соответствующий условию останова. Если необходимо найти стационарную точку функции д на ограниченном множестве С, задаваемом линейными ограничениями, то выполнимость третьего условия также не накладывает никаких дополнительных требований на функцию д. Действительно, множество С является в данном случае выпуклым ограниченным многогранником, разбиение которого на симплексы с любой наперед замкнутой мелкостью может быть выполнено конечным образом (см. Однако в том случае, если множество С не является ограниченным, тем более если нужно найти нулевую точку д или неподвижную точку / на К4*, для выполнимости третьего условия поведение функций д и / асимптотически, то есть в некоторой удаленности от начала координат, должно з'довлетворять некоторым специальным техническим требованиям. В основном эти требования были впервые сформулированы в [], однако они могут очень существенно различаться в силу того, что их главная задача - не столько характеристика функций, сколько обеспечение сходимости алгоритма. Существует, тем не менее, не совсем строгая, но достаточно устоявшаяся интерпретация этих требований по отношению к функции /, неподвижную точку которой необходимо найти. В соответствии с этой интерпретацией, при достаточно существенном удалении от начала координат в направлении х, вектор /(х) - х должен быть ‘направлен’ в сторону, противоположную х (см. Рис. Асимптотическое пове- Рис. Асимптотическое поведение функции /(х) - х = а. В общем случае условие (1. Поэтому для одного из алгоритмов, предложенных в работе сходимость доказывается при дополнительном предположении, согласно которому функция / отображает достаточно удаленные от начала координат точки в некоторое ограниченное множество - условие (1. В сочетании с тем, что сам этот алгоритм являются достаточно ‘многолучевыми’ (см. В следующем разделе данного параграфа показано, что в задаче нахождения равновесия по Нэшу в модели рыночного ценообразования оба предположения на функцию /, как слабое так и сильное, оказываются выполнеными. Нахождение равновесия по Нэшу в модели рыночного це-ноообразования. В качестве типовой задачи из области экономики, которая может быть решена построенными в работе алгоритмами, выбрана задача поиска равновесия по Нэшу в модели рыночного ценообразования, близкая к моделям, рассмотренным в []. Пусть есть один вид сырья, один вид продукции, рынок сырья, рынок продукции и несколько участников. Будем считать, что каждый участник характеризуется некоторой технологией переработки сырья в продукцию . Эту технологию мы будем описывать некоторым скалярным коэффициентом. К = const. Wi = (LiVi. Ui= pvi - cwi. В соответствии с (1. Vi 6 [0, +оо) и, следовательно, используя (1. Определение 1. Помимо нетривиальной точки Нэша в модели может существовать также тривиальная, равная 0. Однако в точке v = 0 величины р, е*, и Пг не определены, поэтому этот случай должен быть рассмотрен особо. Определение 1. TU (0,. Vi, 0,. Дифференцируя (1. Vi = 0, p-cOi^O. Определим компоненты gi(v)y. Vy. KE)-1 IM! V = (VI,. Переобозначив вектор у = (иь. X/), мы получим непрерывную фупкцию р(х), определенную на пространстве К7. Так как при р — са» >0 компоненты этой функции представляют собой левые части системы (1. КЕ)"1 \у\г~Е, то векторы модулей компонент нулевых точек функции д описывают обе (как нетривиальную, так и тривиальную) точки Нэша в рассмотренной выше модели. Пусть /(х) = д(х)--х, тогда д(х) — /(х) -х и нулевые точки д совпадают с неподвижными точками /. При этом для достаточно удаленных от нуля значений х мы, очевидно, имеем р—СЛ{ ^ 0 и, следовательно, /(х) = 0, что полностью соответствует рассмотренным ранее требованиям на /, при которых в данной работе доказывается сходимость алгоритмов в отсутствии ограничений. Таг ким образом, равновесие по Нэшу в описанной модели может быть вычислено одним из алгоритмов, построенных в данной работе для поиска стационарных точек в отсутствии ограничений.