Аппроксимация и регуляризация задач равновесного программирования тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Стукалов, Алексей Сергеевич

• Стукалов, Алексей Сергеевич
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Стукалов, Алексей Сергеевич

Введение

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 — пространство стратегий, U G X — множество допустимых стратегий. Пусть для всех пар (u,v), и € U, v Е U определена целевая функция Ф (u,v). Требуется найти такую точку и = и* EU, для которой

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

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

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

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

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

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

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

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

Ф"(гЛ u") ^ Фм(им, vN) \fvN е UN, N = 1,2,., (3PN) где пространство XN — некоторое приближение пространства X, XJN С XN, Фм(им, vN) — приближения множества U и функции Ф(u,v) соответственно. Здесь N = 1,2,. — дискретный параметр аппроксимации; предполагается, что с ростом N растёт точность аппроксимации.

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

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

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

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

Ф(«,«) = <«, 17), *;) = («,*>)^{«eR1: |u|<l}.

Здесь точка и* = 0 — единственное решение равновесной задачи, аппроксимации целевой функции удовлетворяют соотношению фм(и,у)-ф(и,у)\^^ 4u,veU, N = 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 е и, где функционал Тихонова определяется с помощью классического стабилизатора

Ta(u,v) =f Ф(и, v) + a ||и||2 или положительно определённого

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

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

5.* (J ««.«•»- U {тН"?5

1ТГ1"11 u,€U. u.eut L

Поэтому аппроксимацию по функционалу как стремление решений приближенных задач к решению исходной следует понимать в смысле пределов множеств, а именно как выполнение включений ф.сыФйсьвФ^сФ', где Ф* — множество равновесных значений задачи (ЗР), Ф* — расширенное множество равновесных значений задачи (ЗР)

Ф* = |ф 6 R: Ve > 0 3u е U, |Ф(«,и) - Ф| < е, Ф(«,и) < inf Ф(и,и) + е\ , ^ veu j

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

Ф^ |ф(ц", u"): u* 6 U^, Ф"(хЛ u") ^ mf N Ф^и", v") + Ц .

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

Ф, = ПтФ^=Ф\

Для формулировки необходимых и достаточных условий аппроксимации по значению функционала, а также других результатов настоящей работы, в соответствии с общим подходом к аппроксимации [27] вводятся отображения, связывающие между собой точки исходного и аппроксимированного пространств:

• отображение «проектирования» Рдг X;

• отображение «квантования» Qn: X н» XN.

Теорема (6). Пусть U* Ф 0, существует такая константа С > 0, что < С,

УФ^ € Ф^, N = 1,2,. Для того, чтобы последовательность задач (3PN) е^-согласованно аппроксимировала задачу (ЗР) по значению функционала, необходимо и достаточно существование для каждого натурального числа N, начиная с некоторого N+, отображений

PN:UN^U, QN:U-> UN, PN:U xU" QN:UN xU для которых при всех N = JV«, iV* +1,. выполнены соотношения

Ф(PN (u"), PN Ю) - Ф(Р„ (u"), v))

- (Ф"(1Л и") - ФЛГ(иЛГ, Qn [u"J (v))) < eN Vu" £ U^, v € V, Jim - Ф (PN (u »),P„ (<))| = 0 Vuf„ € 1С и), Qn («)) - ФN(Qn («), v"))

- (Ф(«,«) - Ф(«, PN [ujv] (vN))) We U, vN G VN, Jim |Ф^((5лг(«•),<?*(«.))-$(«.»«*)! =0 Vu,

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

C(uV") = c&VV") + aNnN(vN), (1) где функционал flN(vN) определён на X.N и аппроксимирует некоторый т-стабилизатор Q(v), а^ > 0 — параметр метода. Предполагается, что для каждого N — 1,2,. существует ем-равновесная точка u^ €

С(и?,иП ^ + ^ Vv" € и",

V / s ^ 0, lim £n = 0. n-hx>

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

Теорема (8). Пусть выполнены следующие условия:

1) множество U т-секвенциально компактно;

2) множество решений исходной задачи U* ф 0;

3) функционал П(и) является т-стабилизатором и т-секвенциально полунепрерывен снизу на X;

4) функционал Ф(u,v) положительно полуопределён на U х U, т.е. выполнено неравенство (Ф^):

Ф(щ и) - Ф(и, v) - Ф(и, it) + Ф(и, v) ^ 0 Vu, v € U, функционал Ф(и, и) — Ф(и, v) является т-секвенциально полунепрерывным снизу по и на множестве U;

5) последовательность {uf} определена из условия (2);

6) для каждого N существуют такие отображения Рдг и Qn ■' что при каждом и £ v € U выполнены неравенства

Ф(PN (un), PN {un)) - Ф(PN (un), v)) - (ф"(и», un) - Qn (v))) < 6s,

ClN(QN (v)) - ОД < U(PN (uN)) - QN(uN) <

7) параметры аппроксимации и метода (1)-(2) удовлетворяют условиям: aN >0, eN> 0, SN £ 0, & ^ О, lim (aN + eN + Sn + = 0, lim + — o. n-+oo Af—> oo Ctjy

Тогда последовательность {Pjv (u^)} т-сходится ко множеству

U** = ArgminQ(u) иеи. нормальных решений задачи (ЗР), lim = lim Q(PN (uf)) = a = inf ВД- ■ n-> oo n-*oo u€u,

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

Ф"(гЛ u") + aNnN{uN) ^ Vs) + cxN£lN(vN) VvN е U", и если N достаточно велико, то полученную равновесную точку можно считать решением исходной задачи. Однако для обеспечения большой точности необходимо будет взять достаточно большой номер N, что скорее всего потребует большого объёма ресурсов, необходимых для работы численного метода, и замедлит скорость расчётов. Кроме того, при малых значениях параметра регуляризации адг свойства задачи (2), влияющие на скорость сходимости численных методов, также ухудшаются.

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

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

• экстраградиентного метода [2,5,12];

• экстрапроксимального метода [3,5];

• метода Ньютона [6,15].

Экстраградиентный метод решения задачи (ЗР) требует дифференцируемости функции Ф(и, v) по второму аргументу. Пусть при каждом N ^ 1 градиент У2Ф (и, и) целевого функционала по второй переменной при и = v аппроксимируется отображением \JN —> X.N, задано отображение pr^jv: Xw —> UN — приближение оператора проектирования на множество U, а также отображения X.N —► X и U —> U^. Кроме того, пусть известно начальное приближение точки равновесия — uj G U1.

Пусть известно текущее приближение £ U^ решения, один шаг экстраградиентного метода состоит из двух полушагов. Сначала делается прогнозный полушаг й£ = prgw К - К) - PNaNО, (3) на котором определяется направление для основного полушага х = prg* К - AvV2<&" К) - (3NaNaj), (4) после чего осуществляется переход к следующей аппроксимации uN+1 = PN (ujv+i), <х\ = QN+1 (tijv+i) ■ (5)

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

1. X — гильбертово пространство, U С X — выпуклое замкнутое множество.

2. Функция Ф(и, v): U х U hR непрерывна на отрезках по переменной и € U при каждом фиксированном v € U, слабо полунепрерывна снизу, выпукла и дифференцируема по переменной v 6 U при каждом фиксированном и EU, выполнено условие положительной полуопределенности (Фградиент Ф(и, v) по v при v = и удовлетворяет условию Липшица на U:

У2Ф(«,«) - У2Ф(и,17)|| < L\\u-v\\ Mv,ueU, L = const > О, u* — множество решений задачи (ЗР), непусто.

3. Линейные отображения РXN X, U U^ таковы, что для любого \xN € выполнено

Pn к) € ц

Pjm (Qiv+i (Рлг К))) - Pn К)|| < ^(1 + ||P* Ю||).

4. При каждом N = 1,2,. для отображения рг^лг : выполнено

Р„ (prgw u") - prи PN (uN) || ^ 5n Vun e XN, (6) где pry — оператор проектирования на множество U в пространстве X.

5. При каждом N = 1,2,. для отображения УФ^: U^ XN выполнено

Р„ (У2Ф" Ю) - У2Ф (Ря К), Р* М)|| ^ е^а + ИРлгЮЦ) Vu^ € (7)

6. Параметры {адг}, {Pn}, {^v}, {£n}, {e^} удовлетворяют условиям aN ^ aN+1 > 0, > О, 5n ^ О, ^ ^ О, eN ^ О N = 1,2,. lira (aw + <*лг + + £лг) = О, lira pN < у,

N—юо ЛГ—>оо iy

N (XNPN J ~

Тогда последовательности {Рлг (u$)} и {ujv}, порождённые методом (3)-(5), при любом выборе начального приблиэюения u} 6 U1 таковы, что lira ||Р„ (и#) - щ|| = lim ||Ujv - и*|| = 0, (8)

ЛГ-+оо 11 4 11 АГ-»оо где и« — нормальное решение задачи (ЗР), определяемое условием:

U*€U„ ||и,||= inf ||и||. иби.

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

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

N + 1)-ое приближение 6 Uw+1 находится из соотношений Л» (9)

Й» + (Ю)

UN+1 = PN (ujv+i) 1 UK 1 = QN+I (UN+l) ■ (11)

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

Теорема (11). Пусть выполнены следующие условия:

1. X — гильбертово пространство, U С X — выпуклое замкнутое множество.

2. Функция Ф(и, v): U х U —* R выпукла и слабо полунепрерывна снизу по переменной v € U при каждом фиксированном и € U, непрерывна на отрезках по переменной и £ U при каждом фиксированном v Е U; положительно полуопределённа (Ф^); удовлетворяет условию Липшица в смысле неравенства

Ф(И1, Vi) - Ф(uuv2)) - (Ф(«2, vi) ~ Ф(«2, v2))\ ^ L ||ui - it2|| Ibi - щ\\ Vui,W2,fi,f2 G U, L = const > 0.

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

4■ Существуют множества Ux С U, N = 0,1,. такие, что

UNCUN+1, N = 0,1,., OeUo, U.C]haUrf, (12)

N-* oo vgimn(\\\uQ-vf + (ЗмТа„(иъу)) €Un V«0 € UN-u «1 € UN. (13) veu J

5. XN, N = 0,1,. — линейные нормированные пространства, UN ф 0, UN С X.N, N = 0,1,.;

6. Существуют линейные отображения Pn• ь-> X и Qц: U >-> UN, N = 0,1,. такие, что rJVMI2

VII €17*, yNeUN, где и^^реи N-.pN{vN)eUN}.

7. При каждом N задана функция Фы: XJN х UN —► R такая, что для всех u,v uN,vNevN

Ф (PN {uN),PN (И)) - Ф"(и", v") ^ M 1 + ||P* K)||2 + ||Pjv (v")||2), (14)

Ф(ti, P* (vN)) - Ф"®* (и), v") < Ml + Ikll2 + \\Pn (vN) 1Г), (15) *"(u",QN («)) - 4PN K) ,V) < ^(1 + ||PiV Mil2 + IMI2), (16) фN(QN (u) , QN (V)) - Ф(«, v) ^ Ml + INI* + IM|2)- (17)

Реализация шагов метода (9)-(ll) такова, что й» G UN, <+1 б UN, N= 1,2,.

9. Параметры {a*}, {/?jv}> {£лг}> {£лг}> {<5/v} удовлетворяют условиям aN^aN+1>0, pN> О, £лг ^ О, ^ О, 6N> 0, iV = l,2,. lira (a* + eN + + M = 0, ton 0NL <

N-* oo ЛГ->оо у 2

ЙЯ. (-5РГ + aMt ) - £ = +»■

ЛГ

Тогда последовательность {ипорождённая методом (9)-(11), при любом выборе начального приближения щ € t/o такова, что

Ига Цидг — = 0, (18)

N->oo где и* — нормальное решение задачи (ЗР), определяемое условием: и* G U*, |Ы| = inf ||ti||. иеи*

Сходимость в (18) является равномерной относительно выбора последовательности {Un,$n, Pn,Qn}n=i> компоненты которой удовлетворяют (12)—(17). ш

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

ГЧ 1 Q о ) QQ , U, V £ U, ОУ OVz OUOV строится регуляризованный метод Ньютона. Обозначим,

19) т-7 л./ \<ief 9Ф, . У2Ф {и, и) = jj(u,v)

I—I * , Ч def д2Ф . . дч. .

Для функционала Тихонова со стабилизатором (и, у) соответствующие операторы имеют вид:

V2Ta„ (и, и) = У2Ф (и, и) + aNu, □ TaN (и, и) - ОТ (и, и) + aNI.

Пусть вместо точных значений У2Ф (и, и), ОФ (и, и) известны их приближения V2$N (и) € XN, ПФ» (и) G C{XN XN) такие, что VuN е UN, hN € XN

У2Ф (.PN (mn),Pn (un)) - PN (ЪФ» (u"))|| < Ml + IIPn K)||) (20) \\ПФ (PN {un),Pn (un)) Pn (h") - PN (ПФЫ (uN) hN) || ^ fa ||PN (h") ||. (21)

Для приближения операторов V2Tqjv (и, и) и □ TaN (и, и) естественно использовать V2t^ (ti) d= ЪФ" (и) + aNu", Dt»N (и) ПФ* (и) + aNlN. На каждом шаге метода Ньютона решается вариационное неравенство относительно

V2C К) + dt^ К) (и" - <), v" - и") * 0 Vv" € UN,

22) где = Qn (им), uN в U — предыдущее приближение решения задачи (ЗР). Приближенное решение и$+1 неравенства (22) должно удовлетворять соотношению

Ps К+1) - PN K+i) И ^ eN(l + ||Р„ (uj) ||),

23) где й#+1 e \JN — точное решение (22). В качестве (N+1)-го приближения решения задачи (ЗР) берётся точка un+1 = PN (U#+1) е и

24) 14

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

Теорема (13). Пусть

1) U — замкнутое выпуклое множество из гильбертова пространства X;

2) функцияФ(и,у) определена, непрерывна, обладает непрерывными производными (19), выпукла по переменной v на U при любом фиксированном и £ U, отображение □Ф {и, и) является монотонным, т.е. m{u,u)h,h)>$ Vueu,hex и удовлетворяет условию Липшица:

ЦШФ (и,и) — ПФ (v,u)|| <L||u-u|| Vu,veU, L = const > 0;

3) множество U* решений задачи (ЗР) непусто, и* — нормальное решение задачи, т.е. щеи„ |Н| = inf |Н|;

4) XN — гильбертовы пространства, UN — непустые выпуклые замкнутые множества при каждом N = 1,2,. .;

5) существует последовательность Ы ^ 0 и линейные отображения Рдг: X.N н-> X и Qn : U ь-* U^, N = 1,2,. такие, что

I(Рн Ю ,v + PN (v")> - (uN,Qn (v) + v") J <

ЦРлгЮЦЦи + РлгЮЦ VuV^X", г; 6X,

PN+1 (.Qn+1 (Pn (u*))) - Pn K)|| ^ ^(1 + ||Pjv K)||) Vu" € Xя;

6) приближения V2$N (uN) G XN, ПФ" (uN) e C(XN -» XN) операторов У2Ф (w,«) и [ИФ(и,и) удовлетворяют условиям (20), (21);

7) число 7 и параметры {алт}, {<Sjv}> {<Wb {£лг} и {г/v} таковы, что aN

1 < 7 < 2, aN > 0, 1 <-< 7, lim aN = 0, ct^+l n-+oo $N ^ 0, S-2N ^ 0, ^ 0, £N ^ 0, lim (6N + 82N + £jv + eN) = 0,

N—*oo

-, , е \ ( ^N SN + 52N . ,Ьм (1 + &r) KJV + тг + bN-+ LCVN— 2 ax a bN^N . где aN

1(1 + ||«.||) (^^ + + QiVT+1) 1 < iV = 1,2,.,

V "iV a% orN JJ 7

N <*N ~ $2N — CON^N'

CON = ЦПФ (najv, wajv)|| + aN + 82N, 2

Cvn = (ti«w> «aw)|| + aN llti.ll + 5N( 1 + IHI) + (SN + 82N)?j- + 8) начальные u} € U1, ol\ таковы, что

Тогда последовательность {идг}, определяемая методом (22)-(24), существует и Ига Ф(uN,uN) = Ф(и*,и*), lim - и*|| = О,

N-*oo N—>oo причём сходимость является равномерной относительно выбора реализаций УгФ^ (uN), □Ф" (uw) из (20), (21). ■

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

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

Ф(«, v) % Гg(t, u(t), v(t), x(t, «(■),»(•))) di + G(x(T,«(•), v(-))), Jta

ГТ 'to где u,veU, множество допустимых стратегий

U = {и € L2 (t0, Т; Мг): u(t) е V С Мг при п.в. t € [f0, Т\) , траектория системы x(t) = x(t, u(-),v(-)) 6 IV2 (to, T; Rn) удовлетворяет дифференциальному уравнению x(t) = f(t,x(t),u(t), v(t)), при П.В. t e [tQ,T], x(t0) = x0.

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

Основные результаты диссертации

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Стукалов, Алексей Сергеевич, 2006 год

1. Аваков Е. Р. Об условиях аппроксимации максимшшых задач со связанными множествами // Ж. Вынисл. Мат. и Мат. Физ. — 1978. — Т. 18, Л» 3.- С. 603-613.

2. Антипин А. С. Равновесное программирование: методы градиентного типа // Автоматика и телемеханика. — 1997. — № 8. — С. 125-137.

3. Антипин А. С. Равновесное программирование: проксимальные методы // Ж. Вычисл. Мат. и Мат. Физ. 1997. - Т. 37, № 11. - С. 1327-1339.

4. Антипин А. С. Метод внутренней линеаризации для задач равновесного программирования // Ж. Вычисл. Мат. и Мат. Физ.- 2000.- Т. 40, № 8,- С. 1142-1162.

5. Антипин А. С. Градиентный и экстраградиентный подходы в билинейном равновесном программировании. — М.: Вычислительный Центр им. А. А. Дородницына РАН, 2002.

6. Антипин А. С. Метод Ньютона для решения равновесных и игровых задач // Сб. статей "Нелинейная динамика и управление". — Т. 3. — М.: ФизМатЛит, 2003. — С. 123-138.

7. Антипин А. С. Экстрапроксимальный метод решения равновесных и игровых задач // Ж. Вычисл. Мат. и Мат. Физ.- 2005.- Т. 45, № 11.- С. 1974-1995.

8. Антипин А. С., Васильев Ф. П. Метод стабилизации для решения задач равновесного программирования с неточно заданным множеством // Ж. Вычисл. Мат. и Мат. Физ. — 1999. — Т. 39, К0- 11.-С. 1779-1785.

9. Антипин А. С., Васильев Ф. П. Метод невязки для решения равновесных задач с неточно заданным множеством //Ж. Вычисл. Мат. и Мат. Физ. — 2001. — Т. 41, № 1.— С. 3-8.

10. Антипин А. С., Васильев Ф. П. Метод квазирешений для решения задачи равновесного программирования с неточно заданным множеством множества // Вестник Российского университета Дружбы народов. Серия математика. — 2002. — Т. 8, JY2 2. — С. 10-16.

11. Антипин А. С., Васильев Ф. П., Шпирко С. В. Регуляризованный экстраградиентный метод решения задач равновесного программирования // Ж. Вычисл. Мат. и Мат. Физ. — 2003. — Т. 43, № 10. С. 1451-1458.

12. Антипин А. С., Васильев Ф. П., Шпирко С. В. Регуляризованный экстраградиентный метод решения задач равновесного программирования с неточно заданным множеством // Ж. Вычисл. Мат. и Мат. Физ. 2005. - Т. 45, № 4. - С. 650-660.

13. Байокки К., Капело А. Вариационные и квазивариационные неравенства. Приложение к задачам со свободной границей. — М.: Наука, 1988.

14. Бакушипский А. Б., Гончарский А. В. Итеративные методы решения некорректных задач. — М.: Наука, 1989.

15. Бакушипский А. В., Гончарский А. В. Некорректные задачи. Численные методы и приложения. — М.: Изд-во Московского Ун-та, 1989.

16. Бакушипский А. Б., Кокурин М. Ю. Итерационные методы решения некорректных операторных уравнений с гладкими операторами. — М.: Едиториал УРСС, 2002.

17. Бакушипский А. Б., Поляк Б. Т. О решении вариационных неравенств // ДАН СССР.— 1974,- Т. 219, № 5.-С. 1038-1041.

18. Братусь А. С., Новожилов А. С. Математические модели экологии и динамические системы с непрерывным временем. — М.: Изд. МГУ ВМК, 2004.

19. Будак Б. М., Берковт Е. М. Об аппроксимации экстремальных задач, I, II // Ж. Вычисл. Мат. и Мат. Физ. 1971. - Т. И, № 3. - С. 580-596. - № 4 - С. 870-884.

20. Будак Б. М., Беркович Е. М., Соловьева Е. Н. О сходимости разностных аппроксимаций для задач оптимального управления // Ж. Вычисл. Мат. и Мат. Физ. — 1969. — Т. 9, JYS 3. — С. 522-547.

21. Будак Б. М., Васильев Ф. П. Некоторые вычислительные аспекты задач оптимального управления. — М.: Изд-во МГУ, 1975.

22. Будак Б. М., Иванов А. И. О разностных аппроксимациях для дифференциальных игр // Ж. Вычисл. Мат. и Мат. Физ.- 1970.- Т. 10, № 3.- С. 630-643.

23. Будак Б. М., Иванов А. И. О разностных аппроксимациях для дифференциальных игр с фазовыми ограничениями //Ж. Вычисл. Мат. и Мат. Физ. — 1970. — Т. 10, № 4.— С. 868884.

24. Вайнберг М. М. Вариационный метод и метод монотонных операторов. — М.: Наука, 1972.

25. Вайникко Г. М. Анализ дискретизационных методов. — Тарту: Изд-во Тартусск. ун-та, 1976.

26. Васильев Ф. П. Методы решения экстремальных задач. — М.: Наука, 1981.

27. Васильев Ф. П. Методы оптимизации. — М.: "Факториал Пресс", 2002.

28. Васильев Ф. П., Антипин А. С. Метод стабилизации для решения задач равновесного программирования с неточно заданными исходными данными // Ж. Вычисл. Мат. и Мат. Физ. 1999. - Т. 39, ДО 11. - С. 1707-1714.

29. Васин В. В. Дискретная аппроксимация и устойчивость в экстремальных задачах // Ж. Вычисл. Мат. и Мат. Физ.- 1982. Т. 22, № 4.- С. 824-839.

30. Васин В. В. Методы итеративной регуляризации для некорректных задач // Известия вузов. Математика. 1995.- Т. 402, № П. - С. 69-84.

31. Гловински Р., Лионе Ж.-JI., Тремолъер Р. Численное исследование вариационных неравенств. — М.: Мир, 1979.

32. Гольштейн Е. Г., Юдин Д. В. Новые направления в линейном программировании. — Изд-во "Советское радио", 1966.

33. Дюво Г., Лионе Ж.-Л. Неравенства в механике и физике. — М.: Наука, 1980.

34. Жуковский В. И., Молоствов В. С. Многокритериальная оптимизация систем в условиях неполной информации. — М.: МНИИПУ, 1990.

35. Жуковский В. И., Чикрий А. А. Линейно-квадратичные дифференциальные игры. — Киев: "Наукова Думка", 1994.

36. Канторович Л. В., Акилов Г. П. Функциональный анализ. — М.: Наука, 1977.

37. Кипдерлерер Д., Стампаккья Г. Введение в вариационные неравенства и их приложения. — М.: Мир, 1983.

38. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — М.: Наука, 1981.

39. Куратовский К. Топология. М.: Мир, 1966.- Т. 1.

40. Лионе Ж.-Л. Оптимальное управление системами, описываемыми уравнениями с частными производными. — М.: Мир, 1972.

41. Морозов В. В. Основы теории игр, — М.: Издательский отдел факультета ВМиК МГУ, 2002.

42. Половинкин Е. С., Балашов М. В. Элементы выпуклого и сильно выпуклого анализа. — М.: ФизМатЛит, 2004.

43. Поляк Б. Т. Введение в оптимизацию. — М.: Наука, 1983.

44. Самарский А. А. Теория разностных схем. — М.: Наука, 1989.

45. Семовская А. С. Аппроксимация множества неулучшаемых оценок вектора критериев в задаче динамического принятия решений в условиях неопределенности // Известия РАН, ТИСУ. 2005. - Vol. 3. - Pp. 12-23.

46. Смольяков Э. Р. Теория антагонизмов и дифференциальные игры. — М.: Едиториал УРСС, 2000.

47. Смольяков Э. Р. Теория конфликтных равновесий. — М.: Едиториал УРСС, 2005.

48. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. — М.: Наука, 1986.

49. Тихонов А. Н., Леонов А. С., Ягола А. Г. Нелинейные некорректные задачи. — М.: Наука, 1995.

50. Antipin A. S. Solution Methods for Variational Inequalities with Coupled Constraints // Сотр. Math. Math. Phys. 2000. - Vol. 40, no. 9. - Pp. 1239-1254.

51. Aubin J.-P., Frankowska H. Set-Valued Analysis. — Berlin: Birkhatiser, 1990.

52. Aubin J.-P., Wets R. J. B. Stable approximations of set-valued maps // Annales de I'Insitut Henri Poincare, Analyse поп lineaire.— 1988. — Vol. 5, no. 6. — Pp. 519-535. http://www.numdam.org/ item?id=AIHPC1988565190.

53. Blum E., Oettli W. From optimization and variational inequalities to equilibrium problems // Mathematics Student. 1994. - Vol. 66. - Pp. 123-145.

54. Chadli O., Konnov I. V., Yao J. Descent methods for equilibrum problems in a banach space // Computers and Mathematics with Applications. — 2004. — Vol. 48.— Pp. 609-616.

55. Dontchev A. L., Hager W. W. Lipschitzian stability in nonlinear control and optimization // SIAM J. Control and Optimization.- 1993.-May. Vol. 31, no. 5.- Pp. 569-603. http:// locus.siam.org/SIC0N/volume-31/art0331026.html.

56. Dontchev A. L.f Hager W. W. The Euler approximation in state constrained optimal control // Mathematics of Computation. — 2001. — Vol. 70, no. 233. —Pp. 173-203. http://www.math.ufl. edu/~hager/papers/discrete.ps.

57. Dontchev A. L., Hager W. W., Malanowski K. Error bounds for Euler approximation of a state and control contstrained optimal control problem // Numerical Functional Analysis and Optimization. 2000. - Vol. 21. - Pp. 653-682.

58. Emmrich E. Discrete versions of gronwall's lemma and their applications to the numerical analisys of parabolical problems // Preprint Reiche Mathematik. — 1999. — Vol. 637.

59. Equilibrium Models in Complex Systems, http://emics.ksu.ru.

60. Equilibrium Problems: Nonsmooth Optimization and Variational Inequality Models / Ed. by F. Giannessi, A. Maugeri, P. M. Pardalos. — Kluwer Academic Publishers, 2004.

61. Facchinei F., Kanzow C. Beyond monotonicity in regularization methods for nonlinear complementarity problems // SI AM J. Control Optim.- 1999.- Vol. 37.- Pp. 1150-1161.

62. Konnov I. V. Combined Relaxation Methods for Variational Inequalities.— First edition.— Springer, 2001.

63. Konnov I. V., Ali M. Descent methods for monotone equilibrium problems in banach spaces // Journal of Computational and Applied Mathematics. — 2006.— Vol. 188. — Pp. 165-179.

64. Malanowski K., Biiskens C., Maurer H. Convergence of approximations to nonlinear optimal control problems // Preprint!!! — 1998. — Vol. 3.

65. Murray J. D. Mathematical Biology. I. An introduction. — Third edition. — Springer, 2002.

66. Nagurney A. Variational inequalities.— 2002. http://supernet.som.umass.edu/ austrialectures/fvisli.pdf.

67. Nikaido H., Isoda K. Note on noncooperative convex games // Pacific Journal of Mathematics. — 1955. Vol. 5, no. 1. - Pp. 807-815.

68. Dontchev A. L., Hager W. W., Malanowski K., Veliov V. M. On Quantitative Stability in Optimization and Optimal Control.— 1999. http://www.math.ufl.edu/~hager/papers/set. ps.

69. Pang J.-S., Stewart D. Differential Variational Inequalities. — 2003.

70. Robinson S. M. Strongly regular generalized equations // Mathematics of Operations Research. — 1980.-no. 5.-Pp. 43-62.

71. Saveliev P. Fixed Points and Selections of Set-Valued Maps on Spaces with Convexity // Internat. J. Math. & Math. Sci.~ 2000.- Vol. 24, no. 9.- Pp. 595-612. http://www.hindawi.net/ access/get.aspx?journal=ijmms\&volume=24\&pii=S0161171200004403.

72. Васильев Ф. П., Стукалов А. С. Аппроксимация равновесной задачи по аргументу // Ж. Вычисл. Мат. и Мат. Физ. — 2004. — Т. 44, № П. С. 1972-1982.

73. Васильев Ф. П., Стукалов А. С. Условия аппроксимации равновесных задач по значению функционала // Ж. Вычисл. Мат. и Мат. Физ. 2004. — Т. 44, № 7.- С. 1195-1207.

74. Метод Ньютона для решения задач равновесного программирования / А. С. Антипин, Ф. П. Васильев, А. С. Стукалов, М. Ячимович // Выч. методы и программирование.— 2006.-Т. 7.-С. 202-210.

75. Стукалов А. С. Регуляризоваиный экстраградиентный метод решения задач равновесного программирования в гильбертовом пространстве // Ж. Бычисл. Мат. и Мат. Физ.— 2005.- Т. 45, № 9.- С. 1538-1554.

76. Стукалов А. С. Аппроксимация регуряризованного метода ньютона для решения задач равновесного программирования // "Тихонов и Современная Математика". — Секция 1. Функциональный анализ и дифференциальные уравнения. — М.: МГУ, 2006.— Июнь. — С. 266-267.