Непрерывные методы решения задач равновесного программирования

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

Содержание
Введение

1 Непрерывные экстраградиентные методы с переменной метрикой

1.1 Вспомогательные утверждения

1.2 Непрерывный экстраградиентный метод первого порядка с переменной метрикой

1.3 Регуляризованный непрерывный экстраградиентный метод первого порядка с переменной метрикой

1.4 Непрерывный экстраградиентный метод второго порядка с переменной метрикой

1.5 Регуляризованный непрерывный экстраградиентный метод второго порядка с переменной метрикой

2 Непрерывные методы линеаризации с переменной метрикой

2.1 Непрерывный метод линеаризации первого порядка прогнозного типа

с переменной метрикой

2.2 Регуляризованный непрерывный метод линеаризации первого порядка прогнозного типа с переменной метрикой
2.3 Непрерывный метод линеаризации второго порядка прогнозного типа
с переменной метрикой
2.4 Регуляризованный непрерывный метод линеаризации второго порядка прогнозного типа с переменной метрикой
3 Непрерывные проксимальные методы с переменной метрикой
3.1 Непрерывный проксимальный метод первого порядка прогнозного типа
с переменной метрикой
3.2 Регуляризованный непрерывный проксимальный метод первого порядка прогнозного типа с переменной метрикой
3.3 Непрерывный проксимальный метод второго порядка прогнозного типа
с переменной метрикой
3.4 Регуляризованный непрерывный проксимальный метод второго порядка прогнозного типа с переменной метрикой
Литература

Введение
Исследование математических моделей многих сложных явлений экономики, естествознания, связанных с поиском компромисса и согласования частично (или полностью) противоположных интересов сторон конфликта, составляет содержание области математики, которую называют равновесным программированием. Эта область также охватывает ряд важных задач теории игр и экономического равновесия [34, 39], многокритериального принятия решений в условиях неопределенности [32], обратных задач оптимизации [1], вариационных неравенств [33], седловых задач функции Лагранжа [30].
Основную задачу равновесного программирования можно сформулировать следующим образом. Пусть имеется некоторая функция Ф(ц,ю), (v,w) £ W X W, где W — заданное множество из пространства Еп. Требуется найти точку v. £ W, удовлетворяющую неравенству
Ф(г>», v.) ^ Ф(г., w) Ww £ W. (1)
Такую точку v, называют неподвижной точкой или равновесной точкой задачи (1). Многие важные проблемы исследования операций, вычислительной математики и математической экономики могут быть сведены к задаче (1). Если функция Ф(г>,гг) не зависит от переменной V, то задача (1) превращается в обычную задачу минимизации. Также задачу (1) можно трактовать как экономическую модель взаимодействия нескольких участников с совокупной стратегией w из допустимого множества W и функцией издержек (целевой функцией) Ф(д,и;). Здесь первая переменная v играет роль параметра, а вторая w - роль переменной оптимизации. Таким образом, данная задача описывает ситуацию равновесия, при которой всем участникам невыгодно уклоняться от точки равновесия Vчто в противном случае приведет к увеличению значения функции издержек Ф(ц,и>).
К настоящему времени достаточно хорошо изучена проблема существования точек равновесия, равносильная проблеме существования неподвижных точек v £ W(v) экстремального отображения W(v) функции Ф(г, w) на W, определяемого из условия
Ф(г, W(v)) = min Ф(г>, w), v £ W, W(y) £ W.

Экстремальное отображение, как правило, является многозначным и при доказательстве существования неподвижной точки обычно пользуются теоремами Какутани [21], Fan Ку [31], Oettli [25], обобщающими классические теоремы о неподвижных точках для многозначных отображений.
Что касается конструктивных методов точек равновесия, пригодных для использования на вычислительной технике, то здесь значительные результаты получены лишь для отдельных классов задач (1), таких, как задачи оптимизации, седловые задачи, вариационные неравенства. Однако эти методы разрабатывались и исследовались при значительных ограничениях на функцию Ф(ц, w) (требования типа выпуклости по переменной w и вогнутости по переменной V, нулевой суммы игры, сильной монотонности оператора в вариационных неравенствах и т.п.). Между тем, многие практически важные задачи математической экономики, теории игр не удовлетворяют этим ограничениям и ранее разработанные методы к этим задачам не вполне применимы. Поэтому можно считать, что разработка методов решения достаточно

общих задач (1) практически только начинается, о чем свидетельствуют немногочисленные имеющиеся работы (Карпелевич Г.М. [35], Антипин A.C. [3, б, 8], Шпирко С.В. [43], Васин А.А [23], Делавархалафи А. [19]).
При разработке методов решения задачи (1) следует еще учитывать, что эта задача, вообще говоря, неустойчива к возмущениям функции Ф(п,ш) и множества W, и для ее решения нужно использовать специальные методы, называемые методами регуляризации. Имеется относительно небольшое число работ, в которых предложены и исследованы методы регуляризации неустойчивых равновесных задач (Васильев Ф.П., Антипин A.C. [17, 18], Шпирко С.В. [43], Делавархалафи А. [20]).
Из вышесказанного следует, что тема диссертации, в которой разрабатываются и исследуются непрерывные методы решения задачи (1), является актуальной.
A.C. Антипиным были предложены т. н. управляемые методы проекции градиента, или экстраградиентные методы, основанные на следующей идее: известно, что неподвижная точка V. задачи (1) является одновременно решением как вариационного неравенства
где -kw(- • •) — оператор проектирования некоторого вектора на множество W■ Оба соотношения эквивалентны и являются необходимым условием минимума функции Ф(п„,гд) на множестве W.
Преобразование (г> — 7У„,Ф(п, v)) — v можно трактовать как векторное поле ско-
ростей, которое получается, если каждому вектору г) поставить в соответствие образ этого преобразования. При этом точке V, будет соответствовать ноль, т.е. неподвижная точка имеет нулевую скорость. Во многих случаях, а именно в случае градиентных полей, порожденных задачами оптимизации, векторы поля направлены к неподвижной точке V,, т.е. к точке с нулевой скоростью. Если приближаться к этой точке по некоторой траектории, то длины векторов скоростей будут уменьшаться до нуля. Поэтому ожидается, что если из некоторой стартовой точки vQ провести траекторию v(t) так, чтобы касательный вектор этой траектории совпадал с вектором поля в каждой точке этой траектории, то со временем траектория попадет в сколь угодно малую окрестность неподвижной точки. Эту ситуацию можно описать с помощью дифференциального уравнения
правая часть которого удовлетворяет всем условиям теоремы существования и единственности, следовательно при любых по и всех < ^ 0 существует траектория г(4). К сожалению, область применимости этого метода ограничена задачами оптимизации, поэтому был разработан аналог этого метода, использующий идею прогнозирования, а именно
('Уи,Ф(п.,п,), w — V,) ^ 0 Vin е W,
так и операторного уравнения
V, = 7Гw {v, - 7^,шФ(ц„, ц„)),
ù + у = nw(v — 7У„Ф(п,п)), i>(0)=vo,

Умножив неравенство (105) на h(t) > 0 и проинтегрировав его на отрезке [£,£], мы получим

fi(t)h(t)f(t,vt)^2C(Ç,v*) J h(s)ds + n(()h(Ç)f(Ç,vm) V£,<, t0^£
гои, »•) /*(»)* + межа/к, »•)
‘ wm v«,.,<.<{«•
Перейдем к пределу при t —)■ оо в последнем соотношении, воспользовавшись классическим правилом Лопиталя. Поскольку в силу (94) m/3(t) > 2ji’{i), тпрса > /i(i)
ограничена снизу, то lim Л(£) = -foo. Поэтому

lim /(*,!>•) < )- • (106)
t-K» лг/?оо - /1'«,
Таким образом, мы доказали ограниченность ||v(i) — ti*||2. Далее, из (104) вытекает
- ”*П2 + MWWIIWII* < C(f,t0,
поэтому
- V*> +/W(<)II2 ^
n(t) Но
Применяя неравенство 2(а,Ь) Jï —е||а||2 — е_1||Ь||2, получаем
m) - e)i и*)пг - ^ц«(<) - ^*н2 <
Возьмем t = 2^°о) тогда fl{t) — е > >0 Vi ^ t0. Значит,
о < 1И*)Н2 < ^г№ - *.ll2 + (107)
то есть ||г>||2 ограничена сверху. С учетом этого мы имеем и ограниченность снизу
— ||г/(£) — v*\2. Тогда из (104) следует dt

11Х?1№)112* + / (ÎÎÎÇ^-/*(*)-(/•(-)/»(*))') 1ЖП‘Л+

jIM«) -t)(e)||2rf« ^ Cî(£,i>*) V£,t,t0 <£