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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.ЛОМОНОСОВА

На правах рукописи

Стукалов Алексей Сергеевич

АППРОКСИМАЦИЯ И РЕГУЛЯРИЗАЦИЯ ЗАДАЧ РАВНОВЕСНОГО ПРОГРАММИРОВАНИЯ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва — 2006

Работа выполнена на кафедре оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова

Научные руководители: доктор физико-математических наук,

профессор ф-та ВМиК МГУ им. М.В. Ломоносова ВАСИЛЬЕВ Федор Павлович

доктор физико-математических наук, профессор, ведущий научный сотрудник ВЦ РАН АНТИПИН Анатолий Сергеевич

Официальные оппоненты: доктор физико-математических наук, профессор,

гл. научный сотрудник Института системного анализа РАН БАКУШИНСКИЙ Анатолий Борисович

кандидат физико-математических наук, доцент ф-та экономики Государственного университета - Высшей школы экономики МОЛОСТВОВ Виталий Серафимович

Ведущая организация: Институт проблем управления РАН, г. Москва

Защита диссертации состоится «8» декабря 2006 г. в 11.00 на заседании диссертационного совета Д 501.001.44 при Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ. С текстом автореферата можно ознакомиться на портале ВМиК МГУ им М.В. Ломоносова http://cs.msu.su в разделе "Наука" - "Работа диссертационных советов" - "Д 501.001.44".

Автореферат диссертации разослан «30» октября 2006 г.

Ученый секретарь диссертационного совета профессор

Н.П. Трифонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Математическое программирование предлагает инструменты для выбора наилучшего управления в тех случаях, когда принимающий решение субъект — единственный. Однако многие актуальные сегодня проблемы естествознания, экономики и социологии связаны с поиском стратегий, согласовывающих полностью или частично противоречивые интересы нескольких сторон1. Разработка общей теории и методов решения подобных задач является целью равновесного программирования2. Это интенсивно развивающееся направление прикладной математики охватывает такие важные проблемы теории оптимизации и теории игр, как поиск экономического равновесия, многокритериальное принятие решений в условиях неопределённости, обратные задачи оптимизации, вариационные неравенства, отыскание седловых точек функции Лагранжа и т.д.

В данной работе в основном будет рассматриваться следующая постановка равновесной задачи. Пусть X — пространство стратегий, II 6 X — множество допустимых стратегий. Пусть для всех пар (и, у), и е I/, V € и определена целевая функция Ф(и, у). Требуется найти такую точку и = и* € £7, для которой

ф(«„«,)^ф(и„») Чиеи. (1)

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

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

1) оптимизация целевой функции по г» при фиксированном значении параметра и € [/, построение экстремального отображения

у(и) = Аг|£птФ(и, у), и € [/;

«е(7

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

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

1 Антипин, А. С. Градиентный и экстраградиентный подходы в билинейном равновесном программировании. М.: Вычислительный Центр им. А. А. Дородницына РАН, 2002; Смольяков, Э. Р. Теория конфликтных равновесий. М.: Едиториал УРСС, 2005; Смольяков, Э. Р. Теория антагонизмов и дифференциальные игры. М.: Едиториал УРСС, 2000; Жуковский, В. И./Молоствов, В. С. Многокритериальная оптимизация систем в условиях неполной информации. М.: МИНИНУ, 1990; Жутсовский, В. И./ Чикрий, А. А. Линейно-квадратичные дифференциальные игры. Киев; "Наукова Думка*, 1994; Вратусъ, А. С./Новожилов, А. С. Математические модели экологии и динамические системы с непрерывным временем. М.: Изд. МГУ ВМК, 2004.

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

равновесия, при котором отклонение игроков от стратегии ut может привести к увеличению этих издержек.

Равновесные задачи можно рассматривать как естественное обобщение вариационных неравенств, предложенных Ж.-Л. Лионсом, П. Хартманом и Г. Стамп-аккья3. Впервые равновесная задача в постановке (1) приводится в работе X. Ни-кайдо и К. Исоды4, большой вклад в изучение вопросов существования и единственности решения этой задачи внесли Фапь Цзы и Ж.-П. Обен5. Тем не менее до недавнего времени эффективные численные методы решения равновесных задач отсутствовали, что сдерживало практическое применение равновесного подхода. Ликвидации этого пробела способствовали, в частности, работы A.C. Антипина, И.В. Коннова и др.6

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

&N{uN, uN) < wN) \fwN € U^, N = 1,2,..., (2)

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

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

Аппроксимации оптимизационных, максиминных и игровых задач, оператор-

iЛионе, Ж.'Л. Оптимальное управление системами, описываемыми уравнениями с частными производными. М.: Мир, 1972; Киндерлерер, Д./Стампаккья, Г. Введение в вариационные неравенства и их приложения. М.: Мир, 1983; Blum, E./Oettli, W. From optimization and variational inequalities to equilibrium problems. Mathematics Student, 66 1994.

*Nikaido, H./Isoda, K. Note on noncooperative convex games. Pacific Journal of Mathematics, 5 1955 № 1.

'Aubin, J.-P./Fmnkowska, H. Set-Valued AnalyBis. Berlin: Birkhaüser, 1990.

Mhitiujiw, А. С. Градиентный и экстраградиентный подходы в билинейном равновесном программировании. М.: Вычислительный Центр им. А. А. Дородницына РАН, 2002; Антипин, А. С./Василъев, Ф. П. Методы регуляризации для решения задачи равновесного программирования с неточными входными данными, основанные на расширении множества. Ж. Вычисл. Мат. и Мат. Физ. 42 2002 № 8; Антипин, А. С. Метод Ньютона для решения равновесных и игровых задач. В Сб. статей "Нелинейная динамика и управление".Том 3 М.: ФизМатЛит, 2003; Антипин, А. С. Экстрапроксимальный метод решения равновесных и игровых задач. Ж. Вычисл. Мат. я Мат. Физ. 45 2005 № 11; Antipin, A. S. Solution Methods for Variational Inequalities with Coupled Constraints. Comp. Math. Math. Phys. 40 2000 № 9; Konnov, I. V./Ali, M. Descent methods for monotone equilibrium problems in Banach spaces. Journal of Computational and Applied Mathematics, 188 2006.

ных уравнений исследовались, в частности, Б.М. Будаком7, В.В. Васиным8, Г.М. Вай-никко9, Ж.-П. Обеном и Р. Уэтсом10, А. Дончсвым, В. Хэйгером11, Е.Р. Аваковым12, A.C. Семовской13 и др.

Проведение аппроксимации вносит возмущения во входные данные задачи. Руководствуясь наивным представлением об аппроксимации, можно в качестве искомого решения (1) взять предел при ЛГ —► оо решений задач (2). Однако в общем случае такие действия не приведут к правильному результату, поскольку равновесным задачам свойственна неустойчивость (некорректность) по функции и по аргументу14: при сколь угодно малых погрешностях на входные данные решение возмущённой задачи может либо не существовать, либо значительно отличаться от решения точной задачи как в смысле равновесных стратегий, так и в смысле целевой функции.

Проиллюстрируем такое поведение простейшим примером. Положим liN = X, UN = U = {u е Ж1 : М<1},

Ф(и, и) = {и, v), ФЛГ(и, V) = (и, v> - ||г>||2.

Здесь точка и* = 0 — единственное решение равновесной задачи, аппроксимации целевой функции удовлетворяют соотношению

Vu,v eu, N= 1,2,...,

однако при любых N > 0 приближенная равновесная задача не имеет решения.

Как известно, эффективным средством решения многих некорректных задач, в т.ч. оптимизационных, является предложенный А.Н. Тихоновым метод регуляризации15. В работах А.Б.Бакушинского16, А.С.Антипина, Ф.П.Васильева17 и др. методы и идеи регуляризации — метод стабилизации, невязки, квазирешений,

7Будах, Б. М./Берхович, Е. М. Об аппроксимации экстремальных задач, I, II. Ж. Вычисл. Мат. и Мат. Физ. 111971 №3; Будак, Б. М./Васильев, Ф. Л. Некоторые вычислительные аспекты задач оптимального управления. М.: Изд-во МГУ, 1975.

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

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

10Aubin, J.-P.fWets, R. J. В. Stable approximations of set-valued maps. Annales de l'lnsitut Henri Poincaré, Analyse noil linéaire, 5 19S8 № 6 (URL: http : //www. numdam. org/itemTid-AIHPC_1988__5_6_519_0 ).

uDontchev, Л. L./Hager, IV. W. The Euler approximation in state constrained optimal control. Mathematics of Computation, 70 2001 № 233 (URL: http://vwH.math.uil.edu/~hager/paper3/diserete.ps).

12 Абаков, E. P. Об условиях аппроксимации максиминных задач со связанными множествами. Ж, Вычисл. Мат. и Мат. Физ. 18 1978 № 3.

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

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

15 Тихонов, А. Н./Леонов, А. С./Ягола, А. Г. Нелинейные некорректные задачи. М.: Наука, 1995; Васильев, Ф. П. Методы оптимизации. М.: "Факториал Пресс", 2002.

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

i7 Васильев, Ф. П./Антипин, А. С. Метод стабилизации дая решения задач равновесного программирования с неточно заданными исходными данными. Ж. Вычисл. Мат. и Мат. Физ. 39 1999 № 11; Антипин, А. С. J Васильев,

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

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

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

Научная новизна работы. В диссертации предлагаются определения и условия аппроксимации равновесной задачи (1) по значению функционала и аргументу, регуляризованные методы решения равновесной задачи в сочетании с ее ап-проксимациией: экстраградиентный метод, экстрапроксимальный метод и метод Ньютона.

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

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

Апробация работы. Результаты диссертации докладывались и обсуждались

на:

— семинаре кафедры оптимального управления факультета ВМиК МГУ (руководитель профессор Васильев Ф.П.);

— международной летней школе "INTAS Summer School on Equilibrium Programming and Applications to Economics, Electricity and Transportation", Бергамо, Италия, Университет Бергамо, 5-9 июня 2006 г.;

— международной конференции "Тихонов и современная математика", секция "Дифференциальные уравнения и функциональный анализ", Москва, МГУ, 19-24 июня 2006 г;

Ф. П. Метод невязки для решения равновесных задач с неточно заданным множеством. Ж. Вычисл. Мат. и Мат. Физ. 41 2001 № 1; Актипищ А. С./Васильев, Ф. П. Метод квазирешений для решения задачи равновесного программирования с неточно заданным множеством множества. Вестник Российского университета Дружбы парадов. Серия математика, 8 2002 № 2; Антипин, А. С./Васильев, Ф. П./Шпирко, С. В. Регулярнзованный экстраградиепгный метод решения задач равновесного программирования с неточно заданным множеством. Ж. Вычисл. Мат. и Мат. Физ. 45 2005 № 4.

— научном семинаре "Математическая теория оптимального управления и теория дифференциальных включений", Москва, МИ АН, 12-13 октября 2006 г.

Публикации. Основные результаты диссертации опубликованы в работах [1-6], список которых приводится в конце автореферата.

. Структура и объем диссертации. Диссертация состоит из введения, четырех глав и приложения. Общий объем диссертации 131 стр. Библиография содержит 79 наименования.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении раскрываются цели и задачи работы, ее актуальность, а также кратко описываются основные результаты, полученные в диссертации.

В первой главе обсуждается связь равновесной задачи в постановке (1) с другими математическими проблемами — вариационными неравенствами18, задачами поиска неподвижной точки19, играми Нэша, седловыми и оптимизационными задачами и др.

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

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

Ф(и,и) — Ф(и,у) — Ф(у,и) + Ф(г1,г>) ^ 0 Vu,vGU, (Ф5*)

и усиление этого свойства — сильная положительная определённость

Ф(и,и) — Ф(«,и) — Ф(у,и) + Ф(у,у) ^ o;||u — и||2 Vu,u€t/, а > 0. (Ф>)

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

1НВакугиинский, А. Б./Поляк, Б. Т. О решении вариационных неравенств. ДАН СССР, 219 1974 № 5; Nagurney, A. Variational Inequalities. 2002 {UKL: http://eupernet.eom.uinaas.edu/aiistria.lec-tureB/fvisli.pdi); Кин-дерлерер, Д./ Стампаккья, Г. Введение в вариационные неравенства и их приложения. М.: Мир, 1983; Байокки, К./Капело, А. Вариационные и квазивариационные неравенства. Приложение к задачам со свободной границей. М.: Наука, 1988; Гловински, Р./Лионе, Ж.-Л./Тремолъер, Р. Численное исследование вариационных неравенств. М.: Мир, 1979; Дюво, Г./Лионе, Ж.-Л. Неравенства в механике и физике. М.: Наука, 1980; Pang, J.-S./Stewart, D. Differential Variational Inequalities. 2003; Вайнберг, M. M. Вариационный метод и метод монотонных операторов. М.: Наука, 1972.

ldSaveliev, P. Fixed Points and Selections of Set-Valued Maps on Spaces with Convexity. Internat. J. Math. & Math. Sei, 24 2000 № 9 (URL: http: //ww .hindavl.net/access/get.aspx?journal-ijnms\&voluma>=24\tpil» S0161171200004403); Байокки, К./Капело, А. Вариационные и квазивариационные неравенства- Приложение к задачам со свободной границей. М.: Наука, 1988.

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

зованной равновесной задачи

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

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

TQ(u,v) Ф(u,v) 4- а (u,v).

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

Ф(и, v) — ^ + (и — v)2

каждая точка отрезка U будет равновесной, т.е. U* = [—1,1], и соответствующее множество равновесных значений есть

« и №.,«.)}= и {?}- [4 s

u.eU. u.eU. L J

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

ф. с 1ЛФ& С С Ф*,

где Ф» — множество равновесных значений задачи (1), Ф* — расширенное множество равновесных значений задачи (1)

Ф* Üf |ф е R: Ve > 0 3и е U, |Ф(и, г«) - Ф| < г, Ф(«,и) < inf Ф(и,у) + е|,

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

^ {ф(и", uN): uN е VN, uN) < v mf N Ф^и". v") + eN J .

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

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

• отображение «проектирования» Рм' X'v у-* X;

• отображение «квантования» Qj?: X 1—► XjV.

Теорема (7). ПустьJU* ф 0, существует такая константа С > 0, что

< С, € Ф^,, N = 1,2,____Для того, чтобы последовательность

задач (2) -согласованно аппроксимировала задачу (1) по значению функционала, необходимо и достаточно существование для каждого натурального числа N, начиная с некоторого N*, отображений

Pn\XJn~u, Qn- и —* xjn, Pn:UxUn~U, Qn:UnXU>-> U*

для которых при всех N = N*, N* + 1,... выполнены соотношения

(Ф(Рлг М , PN (иЛ')) - Ф(PN (uN) ,v))~

- uN) - ф^(илг, Qn [ил] (v))) < £JV Vu'v eu",^ U,

Um <) - Ф(PN «) , PN «))| = 0 V< €

(Ф"(<Э* (и), Qn («)) - Ы , vw)) -

- (Ф(и, и) - Ф(и, [UWJ (v"))) < eN Vu 6 17, v* € U* lim ^(Qjv-fa*),Qjv(u.)) -)| =0 Vit» € Ut.

JV—»oo 1

Вторая половина главы описывает применение метода стабилизации22 к равновесной задаче (1) на произвольном топологическом пространстве (Х,т). При каждом N аппроксимирующей задаче (2) ставится в соответствие новая равновесная задача с функционалом

t* (u", v") = vN) + (3)

где функционал iTv(vAT) определён на X.N и аппроксимирует некоторый т-ста-билизатор П(г>), адт > 0 — параметр метода. Предполагается, что для каждого N = 1,2,... существует е^-равновесная точка и^ € UA':

£n ^ 0, lim sn = 0. ^ '

S1 Васильев, Ф. П. Методы оптимизации. М.; "Факториал Пресс?*, 2002.

22 Тихонов, А. Н./Леонов, А. С./Ягола, А. Г. Нелинейные некорректные задачи. М.: Наука, 1995; Васильев, Ф. П./Антипин, А. С. Метод стабилизации для решения задач равновесного программирования с неточно заданными исходными данными. Ж. Вычисл. Мат. и Мат. Физ. 39 1999 № 11.

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

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

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

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

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

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

Ф(и, и) — Ф(и, V) — Ф(г>, и) + Ф(и, v) ^ О Vu, v €U,

функционал Ф(и, и) — Ф(u,v) является г -секвенциально полунепрерывным снизу по и на множестве U;

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

6) для каждого N существуют такие отображения Р2\- и Qm :

Pn-.Vn^U, Qn:U^XJn, что при каждом и € veU выполнены неравенства

(Ф(Р„ (и") , PN (uN)) - Ф(Р* К), V)) -

- (Ф"(|Д и") - Ф"(гЛ Qn («))) < <5jv,

UN(QN («)) - ОД < fr, П(PN Ю) - < fr;

7) параметры аппроксимации и метода (3)-(4) удовлетворяют условиям:

aN > 0, en > О, SN О,

lim (ajf + £n + än + €n) — 0, lim + — 0.

N-> oo jV—>oo OiN

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

Utt — Argminfi(u)

ueu.

нормальных решений задачи (1),

lim n^(uf) = lim H(Pjv (uf)) = П» = inf fi(tt).

n->oo v jv—oo v v * " neu. 4

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

О + < ФЛГ(и№, V*) + Ух" е и*

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

Для того, чтобы увязать работу численного метода с регуляризацией некорректной задачи, используется итеративная регуляризация23: Л7-ный шаг численного метода сопровождается сменой параметра регуляризации с ам на алг+ь а в сочетании с аппроксимацией — ещё и переходом от ТУ-ой аппроксимации к (И + 1)-ой. В рамках этой схемы точность аппроксимации и необходимые для ее обеспечения ресурсы растут постепеипо.

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

• экстраградиеитного метода24;

• экстрапроксимального метода25;

• метода Ньютона26.

Экстраградиентный метод решения задачи (1) требует дифференцируемости функции Ф(и, г>) по второму аргументу. Пусть при каждом N ^ 1 градиент УгФ (и, и) целевого функционала по второй переменной при и — у аппроксимируется отображением VФN : ХЗМ —+ Х^, задано отображение рг^лг: X* и" -приближение оператора проектирования на множество V, а также отображения Рдг: X" —> X и и —> . Кроме того, пусть известно начальное приближение точки равновесия — и^ 6 и1.

Пусть известно текущее приближение 6 и^ решения, один шаг экстраградиентного метода состоит из двух полушагов. Сначала делается прогнозный

23 Бакушинский, А. Б./Гопчарский, А. В. Итеративные методы решения некорректных задач. М.: Наука, 1989; Васильев, Ф. П. Методы оптимизации. М.: "Факториал Пресс", 2002.

24Антипин, А. С- Равновесное программирование: методы градиентного типа. Автоматика и телемеханика, 1997 № 8.

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

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

полушаг

Одг = ргулт « - (и$) - , (5)

на котором определяется направление для основного полушага

- РГи" « - (й#) - ¡3NaNu%), (6)

после чего осуществляется переход к следующей аппроксимации

uN+1 = Рм «+г) , u^+i = Qn+1 (Ujv+i) • (7)

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

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

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

||У2Ф(гг,и) - У2Ф(г>,г>)|| ^ L ||u-uj| Vv,u€U, L = const > О, и* — множество решений задачи (1), непусто.

3. Линейные отображения Pj?: ХЛ* >-* X, Qp?: U »—» U*v таковы, что для любого uN € UAr выполнено

Pn{un) € U,

(0ЛЧ1 (Pn К))) - PN (ил') || ^ 6/(1 + I\PN (uN) ||).

4- При каждом N = 1,2,... для отображения : ь-+ \JN выполнено ||PW (pr£* uw) - pry PN (xiN) || < 5n Vua' € Хл\ (8)

где ртц — оператор проектирования на множество U в пространстве X.

5. При каждом N = 1,2,... для отображения •. ил' ь-» Хл' выполнено

||Р* (Va4»" (u*)) - У2Ф (.PN (uN),PN (и")) || <

^е^(1 + ||РлгЮ||) Vu* € U^. (9)

6. Параметры {a.v}, {/За'}, {елг} удовлетворяют условиям

aN ^ aN+1 > 0, ßN > О, SN > О, & > О, eN > О JV = 1,2,... lim (an + ön + £jv 4- £jv) = 0, Jim Ду <

JV—+oo ЛГ-юо X/

(аы — ajv+i , £лг + 5лг\ ^

lim -5—--1---1---— =0, > aNßN = oo.

jv-oo V од ajvÄv ) ^

Тогда последовательности {Рдг ы {ujv}- , порождённые методом (5)-(7),

при любом выборе начального приближения и} е U1 таковы, что

lim |jPjv «) - и*|| = lim ||и/у - и*|| = 0, (10)

где и* — нормальное решение задачи (1), определяемое условием:

и* € U*, |М = inf ||и||.

Сходимость в (10) равномерная относительно выбора операторов рг^« и VФN, удовлетворяющих (8) и (9).

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

GiJriHu^-ü^+^CK.Ö^X

< QК -+V-)) + (11)

< JA* G - ^ll2+ßNt^' ^)+ (12)

un+1 = pn (ujv+l) , ^n+1 = qn+1 (m+l) ■ (13)

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

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

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

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

|(Ф(иь их) - Ф(иь v2)) - '(Ф(«а, vi) - Ф(«я, «г))| <

< L ||«1 — «21| ||i>i — va|| Vui, щ, vi,V2 €U, L — const > 0.

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

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

unqun+u ЛГ = 0,1,..., 0 € Г/0, i/*C limbr№ (14)

Л—»00 v '

argmin ( i ||uq - г>Ц2 + Д»Т0к(«ь«)) 6 UN Vw0 € UN-i, «1 € Us- (15)

v&J \<2 /

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

6. Существуют линейные отображения Р¡v: X.N X и Qn' U н-» \JN, N = 0,1,... такие, что

и«-мо iii-и

< + ||u - PN {vN) Hi) Vu uw,

где

U" AM (/eu": PN (vN) eUN}.

7. При каждом N задана функция Фм: TJN х —* R такая, что для всех u,v е UN, uN,vN € U^

Ф(PN (uN)yPN (vN)) - *N(uN,vN) <

^Mi^lMOlMlMv")!!2), (16)

Ф(г», PN (v")) - («), v") < + \\uf + ||P* (vw) II2), (17)

Qn («)) - Ф(р* Ю , v) < sjfo- + ||Рлт К) II2 + IIvf), (18)

*N(Qn («), Qn (v)) - Ф(«, v) ^ Ы1 + N|2 + \\vf). (19)

8. Реализация шагов метода (11)—(13) такова, что

€ <+1 € и*, ЛГ=1,2,...

9. Параметры {c*7\r}, {Pn}, , {£лг}> удовлетворяют условиям

otN > ajv+i >0, ßN> 0, eN > 0, > 0, 5n > О, N = 1,2,... lim (адг + Cn + 4- SN) = 0, lim ßxL < —7=,

N->00 ЛГ-юо -y/2

(oin-an+1 . £n + ßn^n + ^

Тогда последовательность {«/v}, порождённая методом (11)~(13), при любом выборе начального приближения щ е £7о такова, что

lim ||ujv — «,|| = 0, (20)

N—xxt

где и* — нормальное решение задачи (1), определяемое условием:

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

neu.

Сходимость в (20) является равномерной относительно выбора последовательности {Un, <&m>Pn, Qn}n=i, компоненты которой удовлетворяют (14)-(19).

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

дЧ(и,у) д2Ф(и,у) —dtf—' u'v&u> (21) строится регуляризованный метод Ньютона. Обозначим,

\ def ЭФ, л

У2Ф(и,и) = •^jK«)

г-1л t \ d(* ^2Ф I \

д2Ф, .

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

У2Т„„ (и, и) — У2Ф (и, и) + ами, ПГад, (и, и) — ОФ (и, и) + адг/.

Пусть вместо точных значений У2Ф (и, и), ЕЗФ (и, и) известны их приближения У2Ф^ (и) 6 X*, ПФМ (и) 6 £(Х№ — Хдг) такие, что Уи^ 6 € X*

||У2Ф (.РК (и*)) - Р* (ЪФ" Ю) || < 6М(1 + \\Р„ (и")||) (22)

||ПФ (Рк (и"), Р* Ю) РК (Ь") - Ря (ПФ" Ю Ь") || < 52М ||Ру (Ь") ||.

(23)

Для приближения операторов Т&2Таг, (и, и) и ПТал, (и, и) естественно использовать

(и) & У2ФЛГ (и) + а„Х1», П^ (и) ПФ» (и) + 15

На каждом шаге метода Ньютона решается вариационное неравенство относительно u^ е и*

<V2C (и#) + DC Ю (и" - О, v" - и№> > о (24)

где < = Qn(un), un € U — предыдущее приближение решения задачи (1), Приближенное решение и$+1 неравенства (24) должно удовлетворять соотношению

\\Pn«+1)-PNK+1)\\^^ + \\PN«)\\), (25)

где й#+1 € иЛ' — точное решение (24). В качестве (N + 1)-го приближения решения задачи (1) берётся точка

uN+1 = Pn (ujv+i) е U. (26)

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

Теорема (14)- Пусть

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

2) функция Ф(и, v) определена, непрерывна, обладает непрерывными производ-нъши (21), выпукла по переменной v на U при любом фиксированном и G U, отображение ШФ (и, и) является монотонным, т.е.

{□Ф(и,и)Л,А>>0 Vu£U,heX

и удовлетворяет условию Липшица:

||Ш> (и, и) - С)Ф (и, г>)|| ^ L ||u - u|| W, v € U, L = const > 0;

3) множество ГУ» решений задачи (1) непусто, и* — нормальное решение задачи, т.е.

и« € U*, ||ti,|| = inf ||v||;

veu,

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

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

I(PN (и") ,v + PN «)> - <и",(«) + V»)N\ <

^ ||Ря (u-v) || ||г, + PN (v") || WuN, vN eXN,ve X,

ll-P^+1 (Qn+1 (Pn (un))) - PN K)|| <

^(l + HMOID Vu^eX^;

6) приближения Ч2ФН (ил') 6 Xм, ПФМ (u") € £(XN -> Хл') операторов

и) и ШФ (и, и) удовлетворяют условиям (22), (23);

7) число 7 и параметры {a/v}, {5jv}j {<W}, fóv} и {елг} таковы, что

Cí V

1 < 7 < 2, aN> 0, 1 < —— < 7, hm aN = О,

ал'+i лг—<»

SN > 0, <52лг & > 0, > О,

lim (¿дг + S2n + €n + £n) = О,

JV—юо

/1 , , v/ ,bfir , , ¿iV + ¿27V , Ьлг&У ,

(1 + + -TT + ON--ь LCvn-2—f"

V, 2 ajv a¿N + .....

где

j ___алг_

<*лг — fev — Cfcw&v'

cfcw = ||оф (uan, «ал,)ii +адг + 62n,

CvN = ||У2Ф(иад,иаЛ| + aN Kll + Ml + IWD+

<Sj начальные uj EU1, ац таковы, что

IIMuD-^IHf.

Гог<9а последовательность {«лг}, определяемая методом (24)-(26), существует и

lim Ф(илт, uN) - Ф(и*, и,), lim ||ujV - «*|| = О, N—юо N—юо

причём сходимость равномерная относительно выбора реализаций УгФ^ (и^), □фМ (UJV) ш (22), (23).

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

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

Ф(и,г) Гg(t,u(t)Mt),x(tM-)M-)))dt+G(x(T,u(-),v(-))), Jto

где и, v £ u, множество допустимых стратегий

U = {u 6 L2 (t0,T; Rr) : u(t) бУсГ при п.в. t е [t0, Т]} ,

17

траектория системы х(<) = и(-), и(-)) е IV2 (<о,Т; Ж") удовлетворяет дифференциальному уравнению

= /(*> и(<))> ПРИ п-в- 4 ^ [¿о, Т\, х(Ь0) = х0.

При проведении аппроксимации V заменяется конечномерным множеством

и* = {И е X": иГ € V, г € 0,зд-1},

дифференциальное уравнение — разностной схемой Эйлера27. Для предложенного способа аппроксимации проверяются условия, обеспечивающие применимость теорем 7, 9, 10, 12, 14.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

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

4. Стукалов. А. С. Экстрапроксимальный метод решения равновесных задач в гильбертовом пространстве // Ж. Вычисл. Мат. и Мат. Физ. — 2006. — Т. 46, №. 5.-С. 781-798.

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

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

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 24.10.2006 г. Формат 60x90 1/16. Усл.печл. 1,25. Тираж 100 экз. Заказ 740. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение

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 целевой функции этой задачи; доказаны условия, при которых она допускает аппроксимацию по функционалу и по аргументу; доказана применимость к этой задаче упомянутых выше численных методов.

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

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.