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

Содержание к диссертации

Введение

1 Свойства равновесной задачи 18

1.1 Эквивалентные постановки задачи равновесия 18

1.2 Задачи, сводящиеся к равновесным 21

1.3 Существование и единственность решения 22

1.4 Регуляризация равновесной задачи 27

2 Аппроксимация равновесной задачи 36

2.1 Аппроксимация по значению функционала 36

2.2 Аппроксимация по аргументу 47

3 Регуляризованные методы решения равновесной задачи 55

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

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

3.3 Регуляризованный метод Ньютона 75

4 Аппроксимация динамической равновесной задачи 88

4.1 Постановка динамической равновесной задачи 88

4.2 Свойства целевой функции динамической задачи 89

4.3 Постановка аппроксимированной задачи 94

4.4 Оценки аппроксимации 96

4.5 Применение итеративных регуляризованных методов 101

4.6 Автономные линейно-квадратичные задачи 118

Некоторые сведения из функционального анализа 122

Литература 125

Предметный указатель 131

• Существование и единственность решения
• Аппроксимация по аргументу
• Регуляризованный экстрапроксимальный метод
• Свойства целевой функции динамической задачи

Введение к работе

Математическое программирование [27,43] предлагает инструменты для выбора наилучшего управления в тех случаях, когда принимающий решение субъект — единственный. Однако многие актуальные сегодня проблемы естествознания, экономики и социологии связаны с поиском стратегий, согласовывающих полностью или частично противоречивые интересы нескольких сторон [5,18,32,34,35,46,47,66]. Разработка общей теории и методов решения подобных задач является целью равновесного программирования (ЗР) [5,60,61]. Это интенсивно развивающееся направление прикладной математики охватывает такие важные проблемы теории оптимизации и теории игр, как поиск экономического равновесия, многокритериальное принятие решений в условиях неопределённости, обратные задачи оптимизации, вариационные неравенства, отыскание седловых точек функции Лагранжа и т.д.

В данной работе в основном будет рассматриваться следующая постановка равновесной задачи.

Задача Пусть X — пространство стратегий, U Є X — множество допустимых стратегий. Пусть для всех пар (u,v), и Є U, v Є U определена целевая функция Ф(и,у). Требуется найти такую точку и = и* EU, для которой

Ф{и.,и*)^Ф(и.,у) VveU. (ЗР)

Точка и* называется точкой равновесия, а Ф(м*,и*) — равновесным значением задачи (ЗР).

В задаче (ЗР) можно выделить следующие два этапа:

1) оптимизация целевой функции по v при фиксированном значении параметра и Є U,построение экстремального отображения v(u) = Argmin<(u,u), и Є U;

2) поиск неподвижной точки и* Є v(u+) экстремального отображения. Необходимость решения этой подзадачи составляет принципиальное отличие равновесных задач от оптимизационных.

Введение

Задаче равновесия можно дать следующую интерпретацию экономического характера. Величина Ф(и*,у) — это совокупные издержки, которые несут игроки при выборе совместной стратегии v Є U. Неравенство (ЗР) описывает ситуацию равновесия, при котором отклонение игроков от стратегии и* может привести к увеличению этих издержек.

Равновесные задачи можно рассматривать как естественное обобщение вариационных неравенств, предложенных Ж.-Л. Лионсом, П. Хартманом и Г. Стампаккья [37,40,53]. Впервые равновесная задача в постановке (ЗР) приводится в [68], большой вклад в изучение вопросов существования и единственности решения этой задачи внесли Фань Цзы и Ж.-П. Обен [51]. Тем не менее до недавнего времени эффективные численные методы решения равновесных задач отсутствовали, что сдерживало практическое применение равновесного подхода. Ликвидации этого пробела способствовали, в частности, работы А.С.Антипина, И.В. Коннова и др. [2-7,50,54,62-64,73].

Изложенные в этих работах конструктивные методы решения равновесных задач предполагают, что преобразованиям подвергаются непосредственно элементы пространства X. Однако во многих прикладных задачах X является бесконечномерным, поэтому практическая реализация шагов численных методов требует проведения аппроксимации. В общем случае аппроксимацию задачи (ЗР) можно представить как последовательность задач ф"(гЛ и") ^ Ф"(іЛ w^N) \/v^N Є U^N, N = 1,2,..., (3P^N) где пространство X^N — некоторое приближение пространства X, XJ^N С Х^, Ф^и^, v^N) — приближения множества U и функции Ф(и,ь) соответственно. Здесь N = 1,2,... — дискретный параметр аппроксимации; предполагается, что с ростом N растёт точность аппроксимации.

Заметим, что пространство Х^ может иметь отличную от X природу. Например, если X — пространство стратегий в динамической игре с непрерывным временем, то пространства Х^ аппроксимированных задач, полученных применением разностных схем к исходной — уже конечномерные пространства стратегий с дискретным временем.

Аппроксимации оптимизационных, максиминных и игровых задач, операторных уравнений исследовались, в частности, Б.М.Будаком [19-23], В.В.Васиным [29], Г.М. Вайник-ко [25], Ж.-П.Обеном и Р.Уэтсом [52], А.Дончевым, В.Хэйгером [56-58,65], Е.Р. Авако-вым [1], А.С. Семовской [45] и др.

Проведение аппроксимации вносит возмущения во входные данные задачи. Руководствуясь наивным представлением об аппроксимации, можно в качестве искомого решения (ЗР) взять предел при N — со решений задач (3P^N). Однако в общем случае такие действия не приведут к правильному результату, поскольку равновесным задачам свойственна неустойчивость (некорректность) по функции и по аргументу [28]: при сколь угодно малых погрешностях на входные данные решение возмущённой задачи может либо

Введение не существовать, либо значительно отличаться от решения точной задачи как в смысле равновесных стратегий, так и в смысле целевой функции.

Проиллюстрируем такое поведение простейшим примером [11]. Положим X.^N = X,

Ф(и,ь) = (и,ь), 3>^N(u,v) = (u,v)-±\\v\\\ U={uGR¹: |u|

Здесь точка u* = 0 — единственное решение равновесной задачи, аппроксимации целевой функции удовлетворяют соотношению \ф^м(и,у)-Ф(и,у)\^^ Vu,veU, ЛГ = 1,2,..., однако при любых N > 0 приближенная равновесная задача не имеет решения.

Как известно, эффективным средством решения многих некорректных задач, в т.ч. оптимизационных, является предложенный А.Н. Тихоновым метод регуляризации [26,27, 48,49]. В работах А.Б.Бакушинского [14-16], А.С.Антипина, Ф.П.Васильева [8-10,12,28] и др. методы и идеи регуляризации — метод стабилизации, невязки, квазирешений, итеративная регуляризация численных методов, построение регуляризующих операторов — были применены к решению задач оптимизации, вариационных неравенств и равновесных задач.

Из сказанного выше можно сделать вывод, что аппроксимацию равновесной задачи (ЗР) и построение эффективных численных методов в рамках аппроксимационного подхода, целесообразно проводить в сочетании с регуляризацией. Этой актуальной задаче и посвящена настоящая работа.

В первой главе обсуждается связь равновесной задачи в постановке (ЗР) с другими математическими проблемами — вариационными неравенствами [13,17,24,31,33,37,67,70], задачами поиска неподвижной точки [13,72], играми Нэша, седловыми и оптимизационными задачами и др. Там же формулируются условия существования и единственности решения равновесной задачи (ЗР) в действительном хаусдорфовом топологическом линейном пространстве.

Следует отметить, что ключевым свойством в результатах существования и единственности решения равновесной задачи, а также для проведения регуляризации является впервые предложенная А.С. Антипиным положительная полуопределёиностъ целевой функции [5]

Ф(и,и)-Ф(и,ь) -Ф(ь,и) + Ф(у,ь) ^ 0 Vu,veU, (Ф⁵*) и усиление этого свойства — сильная положительная определённость

Ф(и,и)-Ф(и,ь)-Ф(у,и) + Ф(у,ь) ^a\\u-v\\² Vu,veU, а > 0. (Ф>)

Введение

Рассматриваются условия существования и единственности решений регуляризованной равновесной задачи

Т_а (и_а ,и_а) ^Т_а (и_а ,v) Vu Є U, где функционал Тихонова определяется с помощью классического стабилизатора

Т_а(«,г;)^Ф(_и,і;) + а|Н|² или положительно определённого

Т_а(и,ь) = Ф(и,у) + а(и,ь).

В главе 2 вводится понятие аппроксимации равновесной задачи по значению целевой функции. Если в задачах оптимизации и седловых задачах оптимальное и седловое значения единственны (если они существуют), то в задаче (ЗР) равновесные значения могут образовывать произвольные множества на числовой прямой. Например, в равновесной задаче на множестве U = [—1,1] с целевой функцией и $(^w>^v) = 2 + (^u ~ ^v)² каждая точка отрезка U будет равновесной, т.е. [/* = [—1,1], и соответствующее множество равновесных значений есть

1 1 "2'2 .« и ((«..«.»- U{|} =

Поэтому аппроксимацию по функционалу как стремление решений приближенных задач к решению исходной следует понимать в смысле пределов множеств, а именно как выполнение включений

Ф.СІлФйСЬвФ^СФ', где Ф* — множество равновесных значений задачи (ЗР), Ф* — расширенное множество равновесных значений задачи (ЗР)

Ф* = (ф Є R: Ve > 0 Ви Є U, |Ф(«,и) - Ф| < є, Ф(«,и) < inf Ф(и,«) + Л , ^ vet/ J

ЬіФ^, Ls$^ — нижний и верхний топологические пределы множеств приближенных

Введение равновесных значений аппроксимированных задач

Ф^ t^f |ф(и", и"): и" 6 U", Ф"(іЛ и") ^ mf ^ Ф^и", v") + є A .

В тех случаях, когда множество Ф* и расширенное множество равновесных значений Ф* совпадают (как в приведённом выше примере), можно говорить о сильной аппроксимации по функционалу в смысле равенства ф\ = 1лтФ^=Ф*.

Для формулировки необходимых и достаточных условий аппроксимации по значению функционала, а также других результатов настоящей работы, в соответствии с общим подходом к аппроксимации [27] вводятся отображения, связывающие между собой точки исходного и аппроксимированного пространств: отображение «проектирования» Р^ ' X^N н+ X; отображение «квантования» Qn'. X н-> Х^.

Теорема (6). Пусть С/» Ф 0, существует такая константа С > 0, что |Ф^| < С, УФ^ Є Ф^, N = 1,2,.... Для того, чтобы последовательность задач (3P^N) є^-согла-сованпо аппроксимировала задачу (ЗР) по значению функционала, необходимо и достаточно существование для каждого натурального числа N, начиная с некоторого N*, отображений P_N:U^N^U, Q_N:U->U^N, P_N:UxU^N»U, Q_N:U^N xU»U^N, для которых при всех JV = JV«, iV* +1,... выполнены соотношения {Ф(Р„ (u"), P_N (и")) - Ф(Р„ К) _f v)) - - (Ф"(іЛ и") - Ф"(іЛ Q_N [u^N] (v))) < e_N Vu" eV^N,vG U, Jim |Ф"«,<) - Ф(Р„ (<) ,P„ «))| = 0 V< Є Uf„, (Ф^лг (и), Q„ («)) - $^N(Qn («), v")) - - (Ф(«,«) - Ф(«, P_N [u_N] (v^N))) ^e_N We U, v" є V^N, \im \ф^м(С}_м(щ),(Э_м(и*))-Ф(и*,и*)\=0 V«, ЄС/*.

Введение

Вторая половина главы 2 описывает применение метода стабилизации [27,28,48,49] к равновесной задаче (ЗР) на произвольном топологическом пространстве (X, г). При каждом N аппроксимирующей задаче (3P^N) ставится в соответствие новая равновесная задача с функционалом

СК/) = ф^іЛИ)+^"(v"), (і) где функционал Q^N(v^N) определён на X.^N и аппроксимирует некоторый т-стабилизатор Q(u), адг > 0 — параметр метода. Предполагается, что для каждого N — 1,2,... существует єn-Равновесная точка и+ Є U^N: C(uf ,uf) ^ C(uf,/) + ^ Vv" є U", En ^ 0, lim sn = 0.

Применение описанного метода стабилизации позволяет аппроксимировать равновесную задачу в смысле сходимости решений регуляризованных аппроксимированных задач к нормальному решению исходной задачи. В следующей теореме даются достаточные условия сходимости.

Теорема (8). Пусть выполнены следующие условия: множество U т-секвенциально компактно; множество решений исходной задачи U* ф 0; функционал Q(u) является т-стабилизатором и т-секвенциально полунепрерывен снизу на X; функционал Ф(ц, v) положительно полуопределёп на U х U, т.е. выполнено неравенство (Ф^):

Ф(и, и) - Ф(и, v) - Ф(у, и) + Ф(и, v) ^ 0 Уи, v Є U, функционал Ф(и, и) — Ф(и, v) является т-секвенциально полунепрерывным снизу по и на множестве U; последовательность {uf} определена из условия (2); для каждого N существуют такие отображения Р^ и Qn-' P_N:U^N»U, Q_N:U^U^N,

Введение что при каждом u^N Є U , v Є U выполнены неравенства (Ф(Р„ (u^N), P_N (u^N)) - Ф(Р„ (u^N), vj) - (Ф"(іЛ u^N) - Ф"(іЛ Qn Ш < 6s, n^N(Q_N (v)) - ОД < t_N, U(P_N (u^N)) - Q^N(u^N) < &,;

7) параметры аппроксимации и метода (1)-(2) удовлетворяют условиям: a_N > 0, e_N> О, S_N ^ О, &v ^ О, lim (алг + лг + &n + n) = 0, lim = О. N-+oo Af—>оо Q!JV

Тогда последовательность {Pn (u^)} т-сходится ко множеству U** = ArgminQ(u) нормальных решений задачи (ЗР), lim ft^N(u?) = lim Q(P_N (uf)) = a = inf ВД- N->oo N-*oo u(/.

Метод стабилизации обосновывает следующий к подход к решению исходной равновесной задачи (ЗР): при некотором N с помощью какого-либо численного метода приближённо решается задача

Ф"(гЛ u^N) + a_Nn^N{u^N) < Ф"(іЛ v") + a_NSl^N(v^N) \/v^N Є U", и если N достаточно велико, то полученную равновесную точку можно считать решением исходной задачи. Однако для обеспечения большой точности необходимо будет взять достаточно большой номер N, что скорее всего потребует большого объёма ресурсов, необходимых для работы численного метода, и замедлит скорость расчётов. Кроме того, при малых значениях параметра регуляризации а^ свойства задачи (2), влияющие на скорость сходимости численных методов, также ухудшаются.

Для того, чтобы увязать работу численного метода с регуляризацией некорректной задачи, используется итеративная регуляризация [14-16,27,30]: iV-ный шаг численного метода сопровождается сменой параметра регуляризации с а^ на алн-ь ^{а в} сочетании с аппроксимацией — ещё и переходом от JV-ой аппроксимации к (N + 1)-ой. В рамках этой схемы точность аппроксимации и необходимые для ее обеспечения ресурсы растут постепенно.

В главе 3 проводится итеративная регуляризация в сочетании с аппроксимацией трёх численных методов решения равновесной задачи:

Введение экстраградиентного метода [2,5,12]; экстрапроксимального метода [3,5]; метода Ньютона [6,15].

Экстраградиентный метод решения задачи (ЗР) требует дифференцируемости функции Ф(и, v) по второму аргументу. Пусть при каждом N ^ 1 градиент УгФ (и, и) целевого функционала по второй переменной при и = v аппроксимируется отображением УФ^Я: \J^N — Х^, задано отображение pr^jv : X.^N —> \J^N — приближение оператора проектирования на множество U, а также отображения Р^: X.^N -»Хи Q^\ U —> U^. Кроме того, пусть известно начальное приближение точки равновесия — и\ Є U¹.

Пусть известно текущее приближение ujy Є U^ решения, один шаг экстраградиентного метода состоит из двух полушагов. Сначала делается прогнозный полушаг U^N_N = prg_w К - fa V₂*^N К) - /W<), (3) на котором определяется направление для основного полушага <₊х = prg* К - /^_аФ" К) - /3_Na_Nu»), (4) после чего осуществляется переход к следующей аппроксимации u_N+i = P_N (ujv₊i), u#+} = Q_N+1 {u_N+1). (5)

Доказывается следующая теорема о сходимости метода (3)-(5). Теорема (9). Пусть выполнены следующие условия: X — гильбертово пространство, U С X — выпуклое замкнутое множество.

Функция Ф(и, v): U х U н-> R непрерывна на отрезках по переменной и Є U при каждом фиксированном v U, слабо полунепрерывна снизу, выпукла и дифференцируема по переменной v Є U при каждом фиксированном и EU, выполнено условие положительной полуопределенности (Ф**); градиент Ф(и, v) по v при v = и удовлетворяет условию Липшица па U: \\V2${u,u)-V₂${v,v)\\^L\\u-v\\ Mv,ueU, L = const > О, u* — множество решений задачи (ЗР), непусто.

Введение

3. Линейные отображения P/v: Х^ н-> X, Qn : U н+ U^ таковы, что для любого u^N Є выполнено Pn (uⁿ) Є U, \\Pn+i {Qn₊₁ {Pn К))) - P_N К)|| < ^(1 + \\P_N К) ||). ^. Дри каждом N = 1,2,... для отображения рг^лг : Х^ н-> и^я выполнено \\P_N{v4»xi^N)-_WuP_N(u^N)\\^5_N Уи^єХ", (6) где pry — оператор проектирования на множество U в пространстве X.

5. При каждом N = 1,2,... для отображения УФ^: U^ н+ X^N выполнено \\р„ (ъф* Ю) - у₂ф (Ря К), р„ Ю) || ^ ^(1 + ЦРлгЮЦ) Vu"eU". (7)

6. Параметры {o/v}, {Pn}, {^n}, {n}, {^n} удовлетворяют условиям a_N ^ a_N+i > О, /3jv > О, 5_N ^ О, ^ ^ О, e_N ^ О iV = 1,2,.-. lira (алг + <5лг + 6/ + лг) = О, lim p_N < -, N—юо N—»oo iy fa_N-a_N+i e_N n + Sn\ _n v^ д

Тогда последовательности {Рлг (u$)} и {им}, порождённые методом (3)-(5), при любом выборе начального приблиоюения и\ Є U¹ таковы, что lim ||P_W К) - щ|| = lim ||ujv - и*|| = 0, (8) N-00 " ^v " ЛГ-кэо где и* — нормальное решение задачи (ЗР), определяемое условием: и* Є U*, ||и,||= inf |М|.

Сходимость в (8) равномерная относительно выбора операторов рг^ и V<&^N, удовле творяющих (6) и (7).

Для случая, когда функция Ф(и,и) не является дифференцируемой по переменной v, предложен регуляризованный экстрапроксимальный метод. В рамках этого метода

Введение (N + 1)-ое приближение u$*{ Є U^w+1 находится из соотношений

ЛІ QlW-^vNH² + ^C«>v^)) +e_N, (9) <п- \ К-ий₊₁||'+^С(йг,и]ї₊₁) < *J&« (\\\<-^\\²⁺^М^)) + *"> (10) ujv+i = -Pn (ujv+i), ujvti ⁼ <5^+i (^MN+l) (11)

Доказывается следующий результат о сходимости метода (9)-(11) к равновесному решению задачи (ЗР).

Теорема (11). Пусть выполнены следующие условия: X — гильбертово пространство, U С X — выпуклое замкнутое множество.

Функция Ф(и, v): U х U —* R выпукла и слабо полунепрерывна снизу по переменной v Є U при каснсдом фиксированном и Є U, непрерывна па отрезках по переменной и U при каждом фиксированном v Є U; положительно полуопределёпна (Ф^); удовлетворяет условию Липшица в смысле неравенства \(Ф(щ, Vi) - (111,)) - (Ф(«₂, vi) ~ Ф(«2, %))| ^ ^ Ь\\щ — U2II ||ui — «21| Vui,w₂,vi,u₂ Є [/, L = const > 0.

3. U* — множество решений задачи (ЗР), непусто.

4- Существуют множества Ux С U, N = 0,1,... такие, что U_NCU_N+1, # = 0,1,..., 0є/₀, /,Climt^, (12) argrnin ( - ||u₀ - w||² + /№„(u_b v)) Є U_N W₀ Є U_N-u «і t/jv- (13) ret/ V )

5. X^N, N = 0,1,... — линейные нормированные пространства, U^N ф 0, U^N С X^я, ЛГ = 0,1,...;

Введение

6. Существуют линейные отображения Pn- Xⁿ і-» X и Q^: U >-> U^N, N = 0,1,., такие, что лмі² -Mv")|&-HN{l + \\u-P_N(v^N)\t_x) VueU_N, v^weU^w, U"^{v^NeV^N:P_N(v^N)eU_N}.

7. При каждом N задана функция Ф^м: XJ^N х U^N такая, что для всех u,v Є U^,

Ф(Р„ {u^N),P_N (v*)) - Ф"(и", v") ^ 5_N(l + \\P_N К)іГ + \\Pn ЮІГ), (14)

Ф(и, P_N (v^N)) - Ф»^ (и), v^N) N(1 + \\u\\² + \\P_N (И) ||²), $^N(v^N,Qn («)) - 4Pn K),«) < ^(1 + ||Piv K)||² + IMI²), *^N{Qn («), Qn И) - Ф(«,v) ^ ^(1 + ||n||² + IMI²). (16) (17)

8. Реализация шагов метода (9)-(11) такова, что а#єЇЇ", <₊₁GU^N, N =1,2,

9. Параметры {а^}, {Pn}> {^n}, {лг}> {$n} удовлетворяют условиям a_N^a_N+1>0, P_N>0, e_N^0, _N^0, 5_N^0, N = 1,2,... lira (a_N + e_N + _N + 5_N) = 0, lim 0_NL < -=, N->oo N-юо y2 fa_N-a_N+i e_N + p_N8_N + (²_N\ -A

Тогда последовательность {u^}, порождённая методом (9)-(11), при любом выборе начального приближения U\ Є Uq такова, что lim \\u_N -иЛ\ = О, TV—too где и* — нормальное решение задачи (ЗР), определяемое условием: и* Є І7», ||и*|| = inf ||п||

Введение

Сходимость в (18) является равномерной относительно выбора последовательности{[/jv,$^N,FjV)Qiv}?/=i> компоненты которой удовлетворяют (12)-(17). ш

Наконец, для функций Ф(и,г>), обладающих производными Фреше дФ(и,у) д²Ф(и,у) 84(u,v)

, u,v Є U, dv ' dv² ' dudv строится регуляризованный метод Ньютона. Обозначим

Г7 Л.Ґ \*f ^Ф, .

У₂Ф(и,и) = jj(u,v) д²ф, .

Для функционала Тихонова со стабилизатором (и, v) соответствующие операторы имеют V₂T_aN (и, и) = У₂Ф (и, и) + a_Nu, OT_aN (и, и) = ПФ (и, и) + a_NL

Пусть вместо точных значений У₂Ф (и, и), ПФ (и, и) известны их приближения У₂Ф^Я (и) Є X^N, ПФ" (и) Є (X^W -+X") такие, что Vu^N е U^N, h^N Є X" ||У₂Ф (P_N (n^N),P_N (u^N)) - P_N (У₂Ф* Ю)|| < ^(1 + \\P_N К |ПФ (P_N (u^N),P_N (u*)) P_N (h") - P_N (ПФ* (u^N) h^N)|| ^ 8_2N \\P_N (h (20) (21)

Для приближения операторов V₂T_QJV (u, и) и ПГ_алг (u, и) естественно использовать V₂C (ti) * У₂Ф" (u) + а*іЛ Dt_w („) H^f ПФ" («) + a_Nl^N.

На каждом шаге метода Ньютона решается вариационное неравенство относительно и" Є U" 2C (и» + ПС К) К - и», v" - и") ^ 0 W» є U", где и$ = Qyv («л0> u_N Є U — предыдущее приближение решения задачи (ЗР). Приближенное решение и$₊₁ неравенства (22) должно удовлетворять соотношению \\Pn К₊₁) - Pjv К₊₁) || ^ e_N(l + \\P_N (uj) ||), где й$₊₁ Є U" — точное решение (22). В качестве (iV+l)-ro приближения решения задачи (ЗР) берётся точка UN+l = Pn (^ujv+l) Є ^- (24) 14

Введение

Корректность метода (22)-(24) и его сходимость к нормальному решению задачи (ЗР) обосновывается в следующей теореме.

Теорема (13). Пусть U — замкнутое выпуклое множество из гильбертова пространства X; функцияФ(и,у) определена, непрерывна, обладает непрерывными производными (19), выпукла по переменной v на U при любом фиксированном и Є U, отображение ОФ(и,и) является монотонным, т.е. <ПФ(«,и)Л,Л)>0 Уиеи, heX и удовлетворяет условию Липшица: ||ПФ(м,«)-ПФ(«,г;)|| <||ц-и|| Vu,t;e/, L = const > 0;

3) множество [/* решений задачи (ЗР) непусто, и* — нормальное решение задачи, т.е.

ЩЄІІ*, Ы= inf |И|; X.^N — гильбертовы пространства, U^N — непустые выпуклые замкнутые множества при каждом N = 1,2,.. .; существует последовательность {n}> Ы ^ 0 и линейные отображения Рд/: Х^ н-> X и Qn : U ь-> U^, N = 1,2,... такие, что \(Pn{mⁿ) ,v + P_n(vⁿ)) - (u^N,Q_N(v) + v^N)_N\ < ^^ 11^ ЮН 11« + ^ Ю|| УїЛ^єХ", г; 6Х, \\Pn+i {Qn+i (Ps К))) - Pn ЮН ^ ^(1 + ||Fiv K)||) Vu" Є X^я; tfj приближения У₂Ф^ (u^N) Є X^я, ПФ* (u^N) Є (X^ -» X^w) операторов У₂Ф(и,и) и ПФ(и,и) удовлетворяют условиям (20), (21);

7) число 7 и параметры {а^}, {

1 < 7 < 2, a_N > 0, 1 < < 7) li^{m a}N = О» $N ^ 0, J₂N ^ 0, fAf ^ 0, Єд/ ^ 0, lim (2N + &v + e_N) = 0, JV—»oo

Введение (1 + Zn) \n + тг + on Н bGvN—о—f" V 2 алг aft +Д1 + Ції.») f^L±gL + ^ф + ^аіУ "^Л") < -, N = 1,2,...,

, <*n_ Con = РФ (u_aN,u_aN)\\ + a_N + S_2N, Cvn = ||У₂Ф (ti_ew> «_ew)|| + a_N |M + 5_N(1 + 1Ы1) + {8_N + ЗД ^ + ^-; 8) начальные u\ U¹, ai таковы, что

Тогда последовательность {un}, определяемая методом (22)-(24), существует и Ига Ф(uN, un) = Ф(«*, и»), lim \\u_N - «*|| = О, N-*oo N—юо причём сходимость является равномерной относительно выбора реализаций УгФ^ (u^N), ПФ^ (u^N) из (20), (21).

На основе каждого описанного в главе 3 численного метода строится регуляризующий оператор [15,27].

В главе 4 рассматривается динамическая равновесная задача со свободным правым концом. В общем виде её целевая функция имеет вид

Ф(и,») / g(t,u(t),v(t),x(t,u(-),v(-)))dt + G(x(T,u(-)M-m где u,v Є U, множество допустимых стратегий U = {и L² (t_Q, Т; М^г): u(t) Є V С W при п.в. t Є [t₀, Т]} , траектория системы x(t) = x(t,u(-),v(')) Є W²(to,T; Rⁿ) удовлетворяет дифференциальному уравнению x(t) = f(t,x(t),u(t), v{t)), при п.в. t Є [t_Q,T), x(t₀) = Xq.

Оглавление

При проведении аппроксимации U заменяется конечномерным множеством V^N ^ {u^N є X": и? Є V, і 0,п*-1}, дифференциальное уравнение — разностной схемой Эйлера [44]. Для предложенного способа аппроксимации проверяются условия, обеспечивающие применимость теорем б, 8, 9, И, 13.

Основные результаты диссертации предложено определение аппроксимации по функционалу равновесной задачи, доказан критерий аппроксимации равновесной задачи по функционалу; доказаны достаточные условия аппроксимации равновесной задачи в топологическом пространстве по аргументу (в смысле сходимости к нормальному решению); произведена итеративная регуляризация в сочетании с аппроксимацией трёх численных методов решения равновесной задачи: экстраградиентного, экстрапроксимального и метода Ньютона; доказана сходимость полученных методов, для каждого метода построен регуляризующий оператор; исследована динамическая задача равновесного программирования со свободным правым концом; установлены условия, обеспечивающие положительную полуопре-делённость и выпуклость по v целевой функции этой задачи; доказаны условия, при которых она допускает аппроксимацию по функционалу и по аргументу; доказана применимость к этой задаче упомянутых выше численных методов.

Автор искренне признателен своим научным руководителям, Федору Павловичу Васильеву и Анатолию Сергеевичу Антипину, за постановку задачи, постоянное внимание к работе, полезные обсуждения и советы.

Существование и единственность решения

Математическое программирование [27,43] предлагает инструменты для выбора наилучшего управления в тех случаях, когда принимающий решение субъект — единственный. Однако многие актуальные сегодня проблемы естествознания, экономики и социологии связаны с поиском стратегий, согласовывающих полностью или частично противоречивые интересы нескольких сторон [5,18,32,34,35,46,47,66]. Разработка общей теории и методов решения подобных задач является целью равновесного программирования (ЗР) [5,60,61]. Это интенсивно развивающееся направление прикладной математики охватывает такие важные проблемы теории оптимизации и теории игр, как поиск экономического равновесия, многокритериальное принятие решений в условиях неопределённости, обратные задачи оптимизации, вариационные неравенства, отыскание седловых точек функции Лагранжа и т.д.

Задаче равновесия можно дать следующую интерпретацию экономического характера. Величина Ф(и ,у) — это совокупные издержки, которые несут игроки при выборе совместной стратегии v Є U. Неравенство (ЗР) описывает ситуацию равновесия, при котором отклонение игроков от стратегии и может привести к увеличению этих издержек.

Равновесные задачи можно рассматривать как естественное обобщение вариационных неравенств, предложенных Ж.-Л. Лионсом, П. Хартманом и Г. Стампаккья [37,40,53]. Впервые равновесная задача в постановке (ЗР) приводится в [68], большой вклад в изучение вопросов существования и единственности решения этой задачи внесли Фань Цзы и Ж.-П. Обен [51]. Тем не менее до недавнего времени эффективные численные методы решения равновесных задач отсутствовали, что сдерживало практическое применение равновесного подхода. Ликвидации этого пробела способствовали, в частности, работы А.С.Антипина, И.В. Коннова и др. [2-7,50,54,62-64,73].

Изложенные в этих работах конструктивные методы решения равновесных задач предполагают, что преобразованиям подвергаются непосредственно элементы пространства X. Однако во многих прикладных задачах X является бесконечномерным, поэтому практическая реализация шагов численных методов требует проведения аппроксимации.

Заметим, что пространство Х может иметь отличную от X природу. Например, если X — пространство стратегий в динамической игре с непрерывным временем, то пространства Х аппроксимированных задач, полученных применением разностных схем к исходной — уже конечномерные пространства стратегий с дискретным временем.

Аппроксимации оптимизационных, максиминных и игровых задач, операторных уравнений исследовались, в частности, Б.М.Будаком [19-23], В.В.Васиным [29], Г.М. Вайник-ко [25], Ж.-П.Обеном и Р.Уэтсом [52], А.Дончевым, В.Хэйгером [56-58,65], Е.Р. Авако-вым [1], А.С. Семовской [45] и др.

Проведение аппроксимации вносит возмущения во входные данные задачи. Руководствуясь наивным представлением об аппроксимации, можно в качестве искомого решения (ЗР) взять предел при со решений задач (3PN). Однако в общем случае такие действия не приведут к правильному результату, поскольку равновесным задачам свойственна неустойчивость (некорректность) по функции и по аргументу [28]: при сколь угодно малых погрешностях на входные данные решение возмущённой задачи может либо ВВЕДЕНИЕ не существовать, либо значительно отличаться от решения точной задачи как в смысле равновесных стратегий, так и в смысле целевой функции. Проиллюстрируем такое поведение простейшим примером [11]. Положим X.N = X, Ф(и,ь) = (и,ь), 3 N(u,v) = (u,v)-±\\v\\\ U={uGR1: u l}. Здесь точка u = 0 — единственное решение равновесной задачи, аппроксимации целевой функции удовлетворяют соотношению \фм(и,у)-Ф(и,у)\ Vu,veU, ЛГ = 1,2,..., однако при любых N 0 приближенная равновесная задача не имеет решения. Как известно, эффективным средством решения многих некорректных задач, в т.ч. оптимизационных, является предложенный А.Н. Тихоновым метод регуляризации [26,27, 48,49]. В работах А.Б.Бакушинского [14-16], А.С.Антипина, Ф.П.Васильева [8-10,12,28] и др. методы и идеи регуляризации — метод стабилизации, невязки, квазирешений, итеративная регуляризация численных методов, построение регуляризующих операторов — были применены к решению задач оптимизации, вариационных неравенств и равновесных задач.

Аппроксимация по аргументу

Из сказанного выше можно сделать вывод, что аппроксимацию равновесной задачи (ЗР) и построение эффективных численных методов в рамках аппроксимационного подхода, целесообразно проводить в сочетании с регуляризацией. Этой актуальной задаче и посвящена настоящая работа. В первой главе обсуждается связь равновесной задачи в постановке (ЗР) с другими математическими проблемами — вариационными неравенствами [13,17,24,31,33,37,67,70], задачами поиска неподвижной точки [13,72], играми Нэша, седловыми и оптимизационными задачами и др. Там же формулируются условия существования и единственности решения равновесной задачи (ЗР) в действительном хаусдорфовом топологическом линейном пространстве. Следует отметить, что ключевым свойством в результатах существования и единственности решения равновесной задачи, а также для проведения регуляризации является впервые предложенная А.С. Антипиным положительная полуопределёиностъ целевой функции [5] Ф(и,и)-Ф(и,ь) -Ф(ь,и) + Ф(у,ь) 0 Vu,veU, (Ф5 ) и усиление этого свойства — сильная положительная определённость Ф(и,и)-Ф(и,ь)-Ф(у,и) + Ф(у,ь) a\\u-v\\2 Vu,veU, а 0. (Ф ) ВВЕДЕНИЕ Рассматриваются условия существования и единственности решений регуляризованной равновесной задачи Та (иа ,иа) Та (иа ,v) Vu Є U, где функционал Тихонова определяется с помощью классического стабилизатора Та(«,г;) Ф(и,і;) + аН2 или положительно определённого Та(и,ь) = Ф(и,у) + а(и,ь). Применение описанного метода стабилизации позволяет аппроксимировать равновесную задачу в смысле сходимости решений регуляризованных аппроксимированных задач к нормальному решению исходной задачи.

Однако для обеспечения большой точности необходимо будет взять достаточно большой номер N, что скорее всего потребует большого объёма ресурсов, необходимых для работы численного метода, и замедлит скорость расчётов. Кроме того, при малых значениях параметра регуляризации а свойства задачи (2), влияющие на скорость сходимости численных методов, также ухудшаются.

Для того, чтобы увязать работу численного метода с регуляризацией некорректной задачи, используется итеративная регуляризация [14-16,27,30]: iV-ный шаг численного метода сопровождается сменой параметра регуляризации с а на алн-ь а в сочетании с аппроксимацией — ещё и переходом от JV-ой аппроксимации к (N + 1)-ой. В рамках этой схемы точность аппроксимации и необходимые для ее обеспечения ресурсы растут постепенно. В главе 3 проводится итеративная регуляризация в сочетании с аппроксимацией трёх численных методов решения равновесной задачи: ВВЕДЕНИЕ экстраградиентного метода [2,5,12]; экстрапроксимального метода [3,5]; метода Ньютона [6,15]. Экстраградиентный метод решения задачи (ЗР) требует дифференцируемости функции Ф(и, v) по второму аргументу. Пусть при каждом N 1 градиент УгФ (и, и) целевого функционала по второй переменной при и = v аппроксимируется отображением УФЯ: \JN — Х , задано отображение pr jv : X.N — \JN — приближение оператора проектирования на множество U, а также отображения Р : X.N -»Хи Q \ U — U . Кроме того, пусть известно начальное приближение точки равновесия — и\ Є U1.

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

Пусть известно текущее приближение ujy Є U решения, один шаг экстраградиентного метода состоит из двух полушагов. Сначала делается прогнозный полушаг UNN = prgw К - fa V2 N К) - /W ), (3) на котором определяется направление для основного полушага +х = prg К - / аФ" К) - /3NaNu»), (4) после чего осуществляется переход к следующей аппроксимации uN+i = PN (ujv+i), u#+} = QN+1 {uN+1). (5)

1) предложено определение аппроксимации по функционалу равновесной задачи, доказан критерий аппроксимации равновесной задачи по функционалу; доказаны достаточные условия аппроксимации равновесной задачи в топологическом пространстве по аргументу (в смысле сходимости к нормальному решению);

2) произведена итеративная регуляризация в сочетании с аппроксимацией трёх численных методов решения равновесной задачи: экстраградиентного, экстрапроксимального и метода Ньютона; доказана сходимость полученных методов, для каждого метода построен регуляризующий оператор;

3) исследована динамическая задача равновесного программирования со свободным правым концом; установлены условия, обеспечивающие положительную полуопре-делённость и выпуклость по v целевой функции этой задачи; доказаны условия, при которых она допускает аппроксимацию по функционалу и по аргументу; доказана применимость к этой задаче упомянутых выше численных методов.

Автор искренне признателен своим научным руководителям, Федору Павловичу Васильеву и Анатолию Сергеевичу Антипину, за постановку задачи, постоянное внимание к работе, полезные обсуждения и советы.

Свойства целевой функции динамической задачи

Однако требования по переменной и, наоборот, усилены: вместо непрерывности на отрезках функции Ф(-,и) в пункте 4) требуется т-полунепрерыв-ность снизу функции Ф(-, ) — Ф(-,г;). Последнее требование может оказаться неприемлемым для некоторых приложений [13]. Однако с помощью леммы 1.3 нетрудно показать, что вместо условия 4) теоремы 8 можно потребовать следующего: 4) функционал Ф(и,у) положительно полуопределён на U х U, при каждом фиксированном и Є U функционал Ф(и, ) является выпуклым по г и г-полунепрерывным снизу, при каждом фиксированном v Є U функционал Ф(-, v) является непрерывным на отрезках. Возникает вопрос о взаимосвязи аппроксимации по функционалу и по аргументу, а именно: если задача допускает аппроксимацию по функционалу, будет ли она допускать аппроксимацию но аргументу и наоборот? Приведём примеры, показывающие, что на оба вопроса ответ, вообще говоря, отрицательный. Рассмотрим равновесную задачу на множестве U = [—1,1] с целевой функцией Ф(и, г;) = \и — v\ + и.

Пусть при каждом N 1 УгФ(и, и) (градиент целевого функционала по второй переменной при и = v) аппроксимируется отображением УгФ () : U н- Х . Пусть задано отображение ріцлг : Х ь- U — приближение оператора проектирования на множество U, а также отображения Р : Х і-» X и QN : [/ — U .

Таким образом, построен оператор RstS, который каждому набору входных данных V , Y rSvs,c из (3.30)-(3.31) ставит в соответствие точку и(8,є) = Р є Ыщ6еЛ, определяемую методом (3.29), (3.32). Равенство (3.33) означает, что любой оператор Щ,є является регуляризующим [48]. Подчеркнём, что в определении оператора RstS параметры {адг}, {PN}, {ЄЛГ}) {8N} ИЗ (3.9)-(3.11) и начальная точка щ Є U предполагаются фиксированными и не меняются при изменении 8 0 и є 0.

Последовательность Wjy = Цыдг — иалг , удовлетворяющая соотношению (3.62) с такими коэффициентами sN и d , сходится к нулю [27, лемма 2.6.6, стр. 90]. Сходимость будет равномерной относительно выбора последовательности {UN, &N, PN, Q;V}JV=I как SN И ЛГ зависят лишь от оценок погрешности (3.44)-(3.50).

Как и для экстраградиентного метода, мы можем указать правило останова метода (3.64), обеспечивающее при малых (,5,є) близость точки и(,5,є) = Р Ы (е$е)) к0 множеству U . Фиксируем какую-либо начальную точку щ Є U и последовательности {a./v}, {PN}, {N}, {8N}, { N}, удовлетворяющие условиям (3.52)-(3.54); будем считать, что 8i 8, i , Єї е. В контексте метода (3.64) 5 , дг є являются, вместе с а и Ду, параметрами метода, не связанными с какими-либо условиями вида (3.46)-(3.50). Предлагается следующее правило останова процесса (3.64): для каждого набора (, 5, є), 0 і Є, 0 5і 5, 0 Єї є, итерации (3.64) следует продолжать до такого наибольшего номера ./V = JV(, 5,є), при котором выполняются неравенства .

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

Решение задач квадратичного программирования с помощью эллипсоидальных аппроксимаций допустимого множестваНечаева Мария Станиславовна

Разработка метода сведения общей задачи нелинейного программирования к задаче безусловной оптимизации и решение задачи оптимизации в нечетких условиях Егоров Юрий Анатольевич

Методы отсечений с обновлением аппроксимирующих множеств для задач нелинейного программированияЯруллин Рашид Саматович

Задачи двухуровневого программирования, полиномиально разрешимые методом декомпозицииПлясунов Александр Владимирович

Итерационные методы решения задач математического программирования со специальной структуройПудова Марина Владимировна

Непрерывные методы решения задач равновесного программирования Будак Борис Александрович

Двойственные и прямо-двойственные методы аффинно-масштабирующего типа для линейных задач полуопределенного программированияОрлов, Александр Алексеевич

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

Методы уменьшения размерности задачи бинарного программирования Ахмедов Фирудун Беюкага оглы

Методы решения задач квадратичного программирования в гильбертовых пространствах Ахмедов Фейзулла Гамидулла оглы