Метод кососимметричной регуляризации для решения равновесных задач

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

Оглавление
Введение
1 Кососимметричные функции и их свойства
§1.1 Кососимметричные функции и их свойства
§1.2 Задача равновесного программирования
§1.3 Слабая равновесная задача
§1.4 Слабое решение сильно кососимметричных задач
§1.5 Свойства оценочных функций
2 Методы решения сильно кососимметричной задачи
§2.1 Метод проекции градиента
§2.2 Метод усреднений
§2.3 Экстраградиентный метод с фиксированной длиной шага
§2.4 Экстраградиентный метод с переменной длиной шага
§2.5 Сравнительная характеристика методов
3 Метод кососимметричной регуляризации
§3.1 Метод непрерывной кососйммет^чнс^ регуляризации
§3.2 Метод итеративной регуляризации •#*•;-<*
§3.3 Регуляризация с постоянным пара^еяфой***
§3.4 Метод регуляризации с отслеживанием
Список литературы

Введение
Равновесное программирование [4, 8, 9] можно рассматривать как одно из обобщений таких устоявшихся областей знаний как математическое программирование и теория игр. Актуальность развития теории и методов решения равновесных задач очевидна, поскольку именно эти задачи описывают на модельном уровне сложные ситуации, связанные с поиском компромисса и согласования частично (или полностью) противоположных интересов сторон конфликта [22, 33, 35].
Рассмотрим одну из постановок равновесной задачи, предложенную Антипиным A.C. [4, 5], - найти точку v* £ V, удовлетворяющую неравенству:
Ф(г>*,и*) < Ф(ц*,ш) Vtü £ V. (1)
Эта задача представляет собой экономическую модель взаимодействия нескольких участников с совокупной стратегией w из допустимого множества V и функцией издержек (целевой функцией) Ф(щш). Здесь первая переменная v играет роль параметра, а вторая w - роль переменнной оптимизации. Таким образом, данная задача описывает ситуацию равновесия, при которой всем участникам не выгодно уклоняться от точки равновесия v', что в противном случае приведет К увеличению функции издержек Ф(у*, .
К конструкции (1) сводятся многие известные математические модели [2, 4]:
Седловые задачи
Пусть L(x,p) - непрерывная, выпуклая по х и вогнутая по у функция, заданная на произведении выпуклых множеств X х Q. Седловая точка (т*,р*) находится как решение системы неравенств
L{z*,p) < < Ц%,Р’) Vz G X, р б Q, (2)
что эквивалентно задаче - найти
Xя £ Argmin{L(z,p*) z £ X), р* £ Argrrnn{- Цхм, у) у £ Q}.
Введем переменные w = {z, у), V (х,р) и рассмотрим нормализованную функцию (свертку) [32]
Ф(v,w) = L(z,p) ~ L(x,y). (3)

Тогда не трудно показать, что исходную седловую задачу можно свести к виду (1) - найти Vя = (х*,р*):
Vх £ Агдтт{Ф(уш) = Ь{г,рх) - Ь{хх,у) и> = (г,у) £ X х <2]. Вариационные неравенства
Пусть задан непрерывный оператор А : V V. Задача вариационного неравенства заключается в нахождении точки и* £ V:
(Ли*, ю - Vх) > 0 Уги 6 V7.
Не трудно заметить, что такая задача сводится к (1), если положить Ф(г?,ш) = {/I -и, го).
Игры п-лиц с равновесием по Нэшу
Пусть на рынке действуют п-игроков, каждый из которых имеет свою непрерывную функцию затрат /,(и) — /»(и», Г-г), заданную на V = У х .. х V; х ... х Уп. Здесь - собственная стратегия, а и_; = (гц, ..,и;_ъ ун-ь ••, г^п) б х .. х
К-1 х 17+1 хх К - стратегии остальных участников. Задачей каждого игрока является минимизация своих затрат при условии, что остальные участники придерживаются своих стратегий, т.е. нужно найти (г>*,у*,Vх) £ V :
Ущ £ У{ г — 1, .-,п.
Если ввести свертку
Ф(и,ш) = 53 1=
то исходную игру также можно представить в виде (1).
Задачи выпуклой и гладкой оптимизации
Пусть задана выпуклая, дифференцируемая функция /(п), где V £ V. Задача оптимизации заключается в отыскании точки Vх £ V:
Г = 1Ю что в данном случае эквивалентно поиску Vх £ V:
(/'(ух),ш — Vх) > 0 /ш £ V.
Если положить Ф(гуш) — {/'(г;),ш), то эта задача также может быть сведена к
Преобразовывая далее неравенство и применяя формулу разности квадратов, окончательно получаем
Л Д(1 -ф- А/В)2( 1 + угт А/В)2 _ вр- 1 + А/В)2 11 ” “ (1 + ,/1-А/В)2 ~ [1 + ^/1-А/В)2'
откуда
, , ^ Л2 Л
/Ли) > ----------— > —.
В(1~^1-А/ВУ 4В
Лемма доказана.
Отметим, что даже если обе задачи (1) и (7) эквивалентны, скорость сходимости к решению по мере £(г>) и у{у) может быть разной.
Пример 1.3 Пусть Ф(и,ш) = (и,ш), ||д[| < 1, ||гу|| < 1.
Понятно, что решением будет единственная точка V* — 0. Возьмем малую константу 0 < с < 1. Тогда
£(г>) = тах{Ф(и, и) — Ф(г?,ш)} — тах{||гг|]2--.— (г>,и>)} = |[и||2 + ||г? {|.
Поэтому, £(г>) < с если 1И1 < е/2 < 1.
С другой стороны,
п(у) = шах |Ф(ш, и) — Ф(ш,и>)} = шахiw.v) — ||го||2}.
^ ’ 1И<1 1Н1<
Не трудно показать, что максимум правой части достигается при ю = у/2.
Следовательно,
*4?! = -1Н121 = М1У1 -1М12/4 = 1М12/41*>
если |ф|| < 2->/ё. Таким образом, применяя минимизацию по мере /л(у), мы попадем в б - окрестность решения на порядок медленнее, чем минимизируя по
Ограничимся в дальнейшем рассмотрением двух классов функций Ф(и,го). Первый класс состоит из функций Ф(-у,ш), у которых сужение градиента У2Ф(г;,гу) на диагональ хо = у удовлетворяет условию Липшица с константой
[у > 0:
||У2Ф(и, у) - У2Ф(ш, ю)\ < Ь\у- ш|| V«, го € V. (20)
Второй класс состоит из функций, у которых градиент У2Ф(и,ги) равномерно ограничен на V (но , вообще говоря, не непрерывен) с константой I > 0:
||72Ф(и,гу)|| < I (21)