Аппроксимация и регуляризация задач равновесного программирования

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

1 Свойства равновесной задачи
1.1 Эквивалентные постановки задачи равновесия
1.2 Задачи, сводящиеся к равновесным
1.3 Существование и единственность решения
1.4 Регуляризация равновесной задачи
2 Аппроксимация равновесной задачи
2.1 Аппроксимация по значению функционала
2.2 Аппроксимация по аргументу
3 Регуляризованные методы решения равновесной задачи
3.1 Регуляризованный экстраградиентный метод
3.2 Регуляризованный экстрапроксимальный метод
3.3 Регуляризованный метод Ньютона
4 Аппроксимация динамической равновесной задачи
4.1 Постановка динамической равновесной задачи
4.2 Свойства целевой функции динамической задачи
4.3 Постановка аппроксимированной задачи
4.4 Оценки аппроксимации
4.5 Применение итеративных регуляризованных методов
4.6 Автономные линейно-квадратичные задачи
А Некоторые сведения из функционального анализа
Литература
Предметный указатель

Математическое программирование [27,43] предлагает инструменты для выбора наилучшего управления в тех случаях, когда принимающий решение субъект — единственный. Однако многие актуальные сегодня проблемы естествознания, экономики и социологии связаны с поиском стратегий, согласовывающих полностью или частично противоречивые интересы нескольких сторон [5,18,32,34,35,46,47,66]. Разработка общей теории и методов решения подобных задач является целью равновесного программирования (ЗР) [5,60,61]. Это интенсивно развивающееся направление прикладной математики охватывает такие важные проблемы теории оптимизации и теории игр, как поиск экономического равновесия, многокритериальное принятие решений в условиях неопределённое, обратные задачи оптимизации, вариационные неравенства, отыскание седловых точек функции Лагранжа и т.д.
В данной работе в основном будет рассматриваться следующая постановка равновесной задачи.
Задача Пусть X — пространство стратегий, и € X — множество допустимых стратегий. Пусть для всех пар (и, и), и £ II, V € II определена целевая функция Ф(и,г>). Требуется найти такую точку и = и, € {/, для которой
Ф(п,,и„) < Ф(и», и) Уиеи. (ЗР)
Точка и* называется точкой равновесия, а Ф(н,,и*) — равновесным значением задачи (ЗР).
В задаче (ЗР) можно выделить следующие два этапа:
1) оптимизация целевой функции по и при фиксированном значении параметра и €11, построение экстремального отобраэюения
и(и) Аг§тшФ(п,п), иби;
2) поиск неподвижной точки и» 6 «(и*) экстремального отображения. Необходимость решения этой подзадачи составляет принципиальное отличие равновесных задач от оптимизационных.

Задаче равновесия можно дать следующую интерпретацию экономического характера. Величина Ф(и»,г!) — это совокупные издержки, которые несут игроки при выборе совместной стратегии v 6 U. Неравенство (ЗР) описывает ситуацию равновесия, при котором отклонение игроков от стратегии и* может привести к увеличению этих издержек.
Равновесные задачи можно рассматривать как естественное обобщение вариационных неравенств, предложенных Ж.-Л. Лионсом, П. Хартманом и Г. Стампаккья [37,40,53]. Впервые равновесная задача в постановке (ЗР) приводится в [68], большой вклад в изучение вопросов существования и единственности решения этой задачи внесли Фань Цзы и Ж.-П. Обей [51]. Тем не менее до недавнего времени эффективные численные методы решения равновесных задач отсутствовали, что сдерживало практическое применение равновесного подхода. Ликвидации этого пробела способствовали, в частности, работы
A.C. Антипина, И.В. Коннова и др. [2-7,50,54,62-64,73].
Изложенные в этих работах конструктивные методы решения равновесных задач предполагают, что преобразованиям подвергаются непосредственно элементы пространства X. Однако во многих прикладных задачах X является бесконечномерным, поэтому практическая реализация шагов численных методов требует проведения аппроксимации. В общем случае аппроксимацию задачи (ЗР) можно представить как последовательность задач
®V,uw)<*V,vJV) Vv* GUW, N= 1,2 (3PN)
где пространство Хдг — некоторое приближение пространства X, UN С XN, Фл'(и^, v'v) — приближения множества U и функции Ф(и, v) соответственно. Здесь iV = 1,2,... — дискретный параметр аппроксимации; предполагается, что с ростом N растёт точность аппроксимации.
Заметим, что пространство XN может иметь отличную от X природу. Например, если X — пространство стратегий в динамической игре с непрерывным временем, то пространства XN аппроксимированных задач, полученных применением разностных схем к исходной — уже конечномерные пространства стратегий с дискретным временем.
Аппроксимации оптимизационных, максиминных и игровых задач, операторных уравнений исследовались, в частности, Б.М. Будаком [19-23], В.В. Васиным [29], Г.М. Вайник-ко [25], Ж.-П. Обеном и Р. Уэтсом [52], А. Дончевым, В. Хэйгером [56-58,65], Е.Р. Аваковым [1], A.C. Семовской [45] и др.
Проведение аппроксимации вносит возмущения во входные данные задачи. Руководствуясь наивным представлением об аппроксимации, можно в качестве искомого решения (ЗР) взять предел при N -* оо решений задач (3PN). Однако в общем случае такие действия не приведут к правильному результату, поскольку равновесным задачам свойственна неустойчивость (некорректность) по функции и по аргументу [28]: при сколь угодно малых погрешностях на входные данные решение возмущённой задачи может либо

2.2. Аппроксимация по аргументу
9) отображение Рдг для всех uN G U'v удовлетворяет условию
|Ф(Рдг Ю , PN (uN)) - Ф^гД uN) < 52N, (2.41)

&2N ^ 0, lim Ö2N = 0,
N-*
то из сходимости подпоследовательности Ф^ДиД uf*) следует сходимость подпоследовательности Ф{Рык (uf‘), Рцк (Д*)) и наоборот, причём
lim Ф"*(ч* 1Д) - lim Ф(PNk (и?*), PNk (гД)) G Ф.„ (2.42)
к—*оо I—»оо

Ф** = {Ф** €М: Эи„ € U„, Ф(и,.,и*,) = Ф„*}.
Доказательство. Рассмотрим точку тД удовлетворяющую условию (2.35). В силу произвольности vN е 1Д в неравенстве (2.35) можно положить vN = QN (v), где v - произвольный элемент из U:
Ф Д uf, uf) + алгПДД) < Ф^(Д,Qn (и)) + aNflN(QN (v)) + £дг Vv G U.
Соотношения (2.37)—(2.39) позволяют перейти в этом неравенстве к функционалам Ф(и, v) и П(п):
Ф(PN (Д), PN (Д)) + aNm (Д)) - Zn)
^ Ф(Рц (Д) ,v) + 5ц + ojv(fi(n) + £jv) + £jv Vt> G i/. (2.43)
Для произвольной точки равновесия исходной задачи u, G У* выполнено:
Ф(и„и.) < Ф(и»,и) Vu G U. (2.44)
В неравенстве (2.43) примем » = к„ а в неравенстве (2.44) возьмём v = Рдг (Д). Сложим оба неравенства:
Ф(Р„ (и"), PN (Д)) + <>ДП(Р„ (Д)) - Ы + Ф(а., и*) <
^ Ф(Д (Д),и,) + 6n + ajv(Ü(ut) + £n) + Sjv + Ф(н«, Рлг (Д))-
Привлекая свойство положительной полуопределенности (Ф^) функционала Ф(и, v), из