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

На правах рукописи УДК 519.6

Пинягина Ольга Владиславовна

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

01.01.07 — вычислительная математика

АВТОРЕФЕРАТ

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

КАЗАНЬ - 2006

Работа выполнена на кафедре экономической кибернетики Государственного образовательного учреждения высшего профессионального образования "Казанский государственный университет им. В.И. Ульянова-Ленина",

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

профессор Коннов Игорь Васильевич

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

профессор Лапин Александр Васильевич

доктор технических наук,

профессор Галиев Шамиль Ибрагимович

Ведущая организация: Вычислительный центр РАН, г.Москва

Защита диссертации состоится 26 октября 2006 г. в 14 30, на заседании диссертационного совета К 212.081.07 по защите диссертаций на соискание ученой степени кандидата физико-математических наук при Казанском государственном университете (420008, г. Казань, ул. Кремлевская, 18, корпус 2, ауд. 217).

С диссертацией можно ознакомиться в научной библиотеке им. Н.И. Лобачевского Казанского государственного университета.

Автореферат разослан 14 сентября 2006 г.

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

Агачев Ю.Р.

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

Актуальность темы. Равновесные задачи и вариационные неравенства позволяют единым образом формулировать и исследовать разнообразные сложные проблемы, возникающие в математической физике, экономике, исследовании операций и других областях. Значительный вклад в общую теорию равновесных задач внесли работы Х.Никайдо и К.Исоды, Фань Цзы, Л.Ниренберга, К.Байокки и А.Капело, Е.Блюма и

B.Эттли, Дж. Розена. Для решения равновесных задач различные методы предлагались в работах С.И. Зуховицкого, P.A. Поляка, М.Е. Примака, В.З. Беленького, В.А. Волконского, A.C. Антипина, И.В. Коннова,

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

Один из распространенных подходов к решению вариационных неравенств состоит в сведении их к оптимизационной задаче с помощью так называемых интервальных (или оценочных) функций и построении методов спуска, не использующих априорных сведений о задаче.

Интересный класс интервальных функций — D-интервальные функции — был предложен Дж. Пенгом. D-интервальные функции позволяют преобразовать вариационное неравенство в задачу безусловной дифференцируемой оптимизации без локальных минимумов, если отображение в вариационном неравенстве является сильно монотонным и дифференцируемым. И.В, Коннов распространил этот подход на смешанные ваг риационные неравенства, включающие негладкие выпуклые функции, и показал, что D-интервальные функции для негладких смешанных вариационных неравенств являются гладкими. Затем И.В. Коннов и О. Кум обобщили этот подход на случай гильбертовых пространств.

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

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

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

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

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

Научная новизна. Для негладких равновесных задач и смешанных вариационных неравенств построены методы спуска на основе интервальных функций при условиях сильной монотонности. Разработанные методы не требуют вычисления производных для интервальных функций. Построены сильно сходящиеся методы спуска по £)-интервальной функции для негладких равновесных задач в гильбертовом пространстве. Установлено мажорирующее свойство интервальных функций для расстояния до множества решений, что позволило построить конструктивные методы решения монотонных равновесных задач в конечномерных и бесконечномерных пространствах.

Таким образом, на защиту выносятся следующие, полученные автором результаты:

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

номерном пространстве, доказана его сходимость при сильной монотонности задачи.

На базе £>-интервальных функций построен и обоснован сильно сходящийся метод спуска без вычисления производных для негладких сильно монотонных равновесных задач в гильбертовом пространстве.

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

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

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

Теоретическая и практическая значимость. На основе интервальных и В-интервальных функций для негладких равновесных задач и смешанных вариационных неравенств построены методы спуска при условиях сильной монотонности, не требующие вычисления производных интервальных функций. Комбинированное применение технологии регуляризации и аппарата интервальных функций позволило построить для не строго монотонных негладких равновесных задач и смешанных вариационных неравенств конструктивные итеративные методы в конечномерных пространствах. Показано, что в гильбертовом пространстве эти методы являются сильно сходящимися. Разработанные в диссертационной работе методы могут быть использованы для практического решения негладких равновесных задач и вариационных неравенств, возникающих

в различных областях.

Апробация работы. Результаты диссертационной работы докладывались и обсуждались: на Всероссийской конференции "Математическое программирование и приложения-2003" (г. Екатеринбург, 24-28 февраля 2003 г.), на "18 Международном симпозиуме по математическому программированию"^. Копенгаген, Дания, 18-22 августа 2003 г.), на Пятом и Шестом Всероссийских семинарах "Сеточные методы для краевых задач и приложения" (г. Казань, 17-21 сентября 2004 г. и 30 сентября-2 октября 2005 г.), на итоговых научных конференциях Казанского государственного университета в 2002-2005 гг., на семинарах кафедры экономической кибернетики Казанского государственного университета.

Публикации. Результаты диссертации изложены в 11 работах.

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения. Библиография включает 90 наименований. Работа изложена на 111 страницах и содержит 19 таблиц и 4 рисунка.

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

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

В первой главе диссертации приводятся общие сведения из теории вариационных неравенств и равновесных задач.

Пусть U — непустое замкнутое выпуклое множество в вещественном гильбертовом пространстве Я, ф : H х H -ï R — равновесная функция, т.е. ф{щи) ~ 0 для любого и € Н. Предполагается также, что ф — дифференцируемая функция, ф{щ •) — выпуклая функция для любого u Е Я, / : H R — выпуклая непрерывная, но необязательно дифференцируемая функция, G : Я -> Я — дифференцируемое отображение. В качестве основных рассматривается класс негладких равновесных задач следующего вида: найти точку и* eU такую, что

ф(и\у) + f(v) - /(и*) >0 W € U, (1)

а также класс смешанных вариационных неравенств вида: найти точку и* € U такую, что

(С?(к*), и - и*) + f{u) - /(и*) >0 V« 6 U. (2)

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

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

Интервальная функция для задачи (1) строится в виде

ß(u) — supL(u,u) — ¿(u,v(u)),

где L(it,u) = — ф(иуу) — f{v) -f f{u) — 0.5аЦи — u||2. Доказано, что она обладает следующими свойствами:

(i) р(и) > 0 \/и е U;

(ii) ß(u) = 0, и G U > и € и*> где U* — множество решений задачи

Отсюда) в частности, следует, что исходная задача (1) эквивалентна задаче условной минимизации

min —> и(и).

Для задачи (1) также доказано условие оптимальности в форме неподвижной точки отображения и t>(u): и* = v(u") и* £ U*.

Во втором разделе рассматривается задача (1) в пространстве /2й. Вводится следующее предположение.

(AI) Для частного градиента Vvtp(*,v) выполняется условие Липшица с константой для любого v £ U.

Функция fi по построению является недифференцируемой. Доказано, что при выполнении предположения (AI) функция р имеет производную в любой точке и € U по любому направлению d е Я™, причем

d) = f'{u]d) — (Vuip(u,v(u)) + а(и — v(u)),d).

Следующее предположение представляет собой вариант свойства сильной монотонности функции ф. (А2) Для любых щ V € и выполняется неравенство:

где к > 0.

Получено необходимое и достаточное условие оптимальности для задачи (1).

Теорема 2.1 (Условие стационарности). Пусть выполняются условия (А1) и (А2% Тогда у!(щи- й) > 0 V« € и й € и*.

Доказано, что если некоторая точка и € II не является решением задачи (1), то вектор й — у(и) — и представляет собой направление убывания для функции /х в точке и.

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

Метод 1

Шаг 0. Выберем точку € V и параметр а > 0. Положим к = 0. Шаг 1. Вычислим ц{ик) и ь(ик) по формуле

Если ц(ик) — 0, то ик является решением задачи, процесс решения останавливается.

Шаг В. Вычислим гу(и*) = ик+1к(1к, где в,к — у{ик)—ик, а представляет собой решение задачи одномерной минимизации

положим — гу(щ*), заменим к на к + 1 и перейдем к шагу 1.

Вводится дополнительное предположение. (АЗ) Для любого V 6 XI отображение является сильно льоно-

тонным па множестве и с константой т > 0.

+ — и) > #е||и — и||2,

р{ик) = тахДгДи) = £(«\г>(и*)).

тт 0<К1

Тогда интервальная функция представляет собой мажоранту квадрата расстояния до множества решений задачи (1). Теорема 2.2 Пусть выполняется предположение (A3). Тогда найдется •число <т > 0 такое, что — и*||2 < ¡л(и) Vu € U> где и* € U*. Вводится обозначение:

S(ti) = {v G U | fi(v) < д(и)} Vu € U,

Доказано, что при выполнении предположения (A3) лебегово множество S(u) функции ¡л для любого и € U является ограниченным, а задача (1) имеет единственное решение.

На этой основе доказана сходимость метода спуска по интервальной функции.

Теорема 2.3 Пусть выполняются предположения (Al), (А2) и (A3). Тогда итерационная последовательность {и*}, построенная методом 1, сходится к единственному решению задачи (1).

В третьем разделе рассматриваются свойства ¿»-интервальной функции : Н R} определенной как разность (difference) двух интервальных функций: = ца(и) — где 0 < а < /3, Здесь

¿¿«(w) = sup £q(u,v) = Ьа(и,г>Л(и)),

v£U

L*{uyv) = - f(v) + f(u) - 0.5a||v - u\\2.

Доказано, что D-интервальная функция обладает следующими свойствами:

(i) > 0 для любых и € #.

(и) ФО0(«*) = 0 и* еи\

Таким образом, исходная равновесная задача (1) эквивалентна задаче безусловной минимизации

min —►

«ея р 4 '

В дальнейшем используются дополнительные предположения. (В1) При любом v 6 Ну для отображения v) выполняется усло-

вие Липшица на любом ограниченном подмножестве Н. (В2) Отображение •) непрерывно.

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

Теорема 2.4 Пусть выполняются предположения (В1) и (В2). Тогда функция непрерывно дифференцируема и ее градиент определяется по формуле:

= — V„^(ti, vQ(u)) +0{и — Vff(u)) - — va(it)).

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

Вводится предположение: (С1) Отображение *Vuift(ut *) является сильно монотонным с константой к для любого фиксированного и 6 Н.

Для задачи (1) доказано достаточное условие оптимальности в форме условия стационарности задачи безусловной минимизации: Теорема 2.5 Пусть выполняются предположения (Bl), (В2) u (С1). Тогда из = 0 следует, что и* € V*.

Обозначим F(u) = v)|v=u. В дальнейшем используются сле-

дующие предположения относительно частных производных функции ф: (С2) Отображение Р : Н Н сильно монотонно с константой т. (СЗ) Для отображения V^f*» *) выполняется условие Липшица на каждом ограниченном подмножестве Н X Н.

(С4) Для отображения VvV('> •) выполняется условие Липшица с константой

В этих условиях задача (1) имеет единственное решение. Для задачи (1) доказана следующая оценка.

Теорема 2.6 Пусть выполняются предполоокения (С2) и (С4)- Тогда существует константа у > 0 такая, что у\\и—и*\\2 < V« € U,

где и* является решением задачи (1).

Определяются вспомогательные отображения г : H—t #, s : Н Я, где г(u) — va{u) ~ vp(u), s(u) = a[u — vQ{u)) — fi[u — vp{u)}. Доказано, что если выполняются предположения (С1)-{С4), то найдется такое р >

О, что для любой точки и € 5(и°) и любого числа р е (0, р), выполняется следующее неравенство

+ /»(«)) < -(к/2)(\\г{и)\\+р\\з(и)\\)2,

где и0 - произвольная точка из Н, Метод решения задачи (1) использует направление спуска г (и) + рэ{и) в точке и, т.е. также не связан с вычислением производных.

Метод 2.

Шаг 0: Выберем произвольную начальную точку и0 е Н н параметры О < а < /3, р > 0, $ е (0,1), у > 0. Положим номер итерации к = 0. Шаг 1: Вычислим Если = 0, останов, ик является ре-

шением задачи (1). Шаг 2: Положим йк — г(ик) + рэ(ик).

Шаг 3: Вычислим т как наименьшее неотрицательное целое число, такое что + - Ф^и*) < -0т7{Цг(и*)|| + р!Н«*)||)2.

Шаг Положим Л* = вт,ик+1 = ик+Х^к, заменим к на к+1 и перейдем к шагу 1.

Теорема 2.7 Пусть выполняются предположения (С1)~(С4)• Тогда последовательность {и*}, построенная методом 2 при р € (0 , р) и 7 ^ «/2, сильно сходится к единственному решению задачи (1).

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

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

В первом разделе рассматривается монотонная равновесная задача в конечномерном пространстве Я": найти точку и* такую, что

Г(и*,и)>0 Vv<=U. (3)

Здесь и — непустое замкнутое выпуклое множество вЛ",Г : Нпх Пп Я — равновесная функция, т.е. Г(и, и) = 0 для любого и 6 Я". Будем

также предполагать, что Г монотонна, т.е. для всех u, v G Rnt выполняется

Г(и, v) + r(v, и) <0,

Г(ад, ■) выпукла для любого и G Rn и Г(-, ад) полунепрерывна сверху для любого v € Я".

В качестве вспомогательной функции выбирается любая равновесная функция <р : Rn X Rn R , удовлетворяющая следующим условиям:

1) (р(и, -) выпукла для любых и € Rn n tp(-> v) полунепрерывна сверху для любых v € Я";

2) <р сильно монотонна с константой г > 0, т.е., для всех utv G Rn, выполняется

¥>(«, и) + <p{v, и) < -т||и — и(|2;

3) для любых и, v € Яп выполняется условие v) | < (¡u|| j|t> — uj|. Рассматривается возмущенная равновесная задача по отношению к

задаче (3): найти точку щ € U такую, что

Г(иг, v) + еу>{ие) v)>0 Vu G U, (4)

где £ — фиксированный положительный параметр.

Через U* обозначается множество решений задачи (3). Следующая теорема устанавливает базовое аппроксимирующее свойство задачи (4). Теорема 3.1 Если U* Ф 0, тогда {и£} —v ад* при е —0, где щ — решение задачи (4), а и£ — -такая точка из U*, что w) > 0 для всех w G U*.

Применим этот подход к негладкой монотонной равновесной задаче (1), где Г(и, v) = ад)+/(ад) — /(ад). Предполагается, что ф монотонна. В качестве вспомогательной функции <р выберем ее простейший вариант <p{u,v) = (u,t> — u). Возмущенная задача для задачи (1) выглядит следующим образом: найти точку ие G U такую, что

ф(ис, v) + f(v) ~ f(ue) + e{uet v -щ)> 0 Vv G U, (5)

где е > 0 — фиксированный параметр.

Согласно теореме о существовании и единственности из главы 1, задача (5) имеет единственное решение, а по теореме 3.1, если U* ф 0,

тогда последовательность решений {ие} возмущенных задач (5) при е О сходится к решению задачи (1) с наименьшей нормой.

Обозначим для краткости "фе(и) и) — ф(и, и) + е(и, и — и). Функция ф£ по построению является сильно монотонной с константой е.

Для решения задачи (5) используется интервальная функция, определенная в главе 2:

«вир =

ьеи

где а > 0 — фиксированный параметр, — вспомогательная функция, такая, что

«) = - /(«) + /{и) - 0.5а||и - и|[2.

Введены предположения, аналогичные (А2) и (АЗ). (А2') Для любых и,ьеи выполняется неравенство:

V) + ^^(и, и), V — и) > 0.

Из условия (А2') следует, что и) > гг||2.

(АЗ1) Для любого V €1/ отображение является монотонным

на множестве 17.

Из условия (АЗ') следует, что отображение является сильно

монотонным для любого V € и на множестве II с константой е.

Доказаны теоремы 3.2 и 3.3, являющиеся аналогами теорем 2.2 и 2.3 из главы 2. Комбинированный метод решения исходной монотонной задачи (1) выглядит следующим образом. Метод 3

Шаг 0. Выберем произвольное число в > 0, последовательность положительных чисел {б/} \ 0и точку € и. Положим 1 = 1. Шаг 1. Положим е — и и1 — г'-1 и выберем произвольное число а, 0 < а < е.

Шаг 2. Применим метод 1 из главы 2 для возмущенной сильно монотонной задачи (5) и найдем точку и1 6 {« € XI \ ¡1$ (и) < такую, что

№(и1)<е1+*. (6)

Шаг 3. Положим z* = и1 >1 = 1+1 и перейдем к шагу 1.

Условие (6) выполняется за конечное число шагов метода 1 в силу свойства сходимости к решению задачи (5), которое следует из теоремы 3.3.

Сходимость метода 3 доказывает следующая теорема.

Теорема 3.4 Пусть выполняются предположения (AI), (AB') и (AS')

uU* Тогда lim zl = <. ^ г-юо "

Таким образом, показано, что последовательность приближенных решений {г1} вспомогательных задач (5) сходится к решению исходной монотонной задачи (1).

Во втором разделе рассматривается монотонная равновесная задача в гильбертовом пространстве Н. Предполагается, что в задаче (3) Г монотонна, Г(-,г>) хеминепрерывна для любых и € Я и Г(и, •) выпукла и полунепрерывна снизу для любых и Е Н. Через U* обозначается множество решений задачи (3).

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

1) ip сильно монотонна с константой т > О,

2) для всех и, v € Я выполняется условие \<p{ut u)j < ]|u]|||v — u||;

3) <¿>(-,u) является хеминепрерывной для любого v € Я, а <р(и, •) выпукла и полунепрерывна снизу для любого и € Я.

Используя функцию (р> как и в конечномерном случае, определяем возмущенную задачу (4), которая в этих условиях имеет единственное решение, а также обладает базовым аппроксимирующим свойством по отношению к задаче (3) в гильбертовом пространстве Я. Теорема 3.5 Если U* ф 0, тогда —f tí* при £ —> 0, где и* — такая точка из U*} что <р(и*,ш) > 0 для всех ш 6 U*.

Далее рассматривается негладкая задача (1), т.е., полагаем Г(и, г») = ip{u,v) + f(v) — f(u) в задаче (3). Предполагаем, что ф монотонна. Используется простейший вариант регуляризирующей функции уз (u, v) — (ß(«),v — «), в качестве Б : Я —¥ Я выбирается линейный оператор, сильно монотонный с константой г > 0, удовлетворяющий условию

||В|| < 1. Тогда возмущенная задача имеет вид: найти точку щ € V такую, что

^(«е, V) + /(у) - /Ы + е(Вие, V - щ) > 0 \fveU, (7)

где е > 0 — заданный параметр.

Через С/* обозначается множество решений задачи (1). В этих условиях задача (7) имеет единственное решение, а в силу теоремы 3.5, если I/* ф 0, то {и£} —^ и*, при е -—>■ 0, где и* — такая точка из и*, что {Ви*п, ад — -и*) > 0 для всех щ € и*.

Для краткости обозначим ф£(и, и) = ф{и, г?) + е{Ви, V — и). По построению, ф£ сильно монотонна, поэтому для решения задачи (7) с фиксированным значением е можно применять аппарат ^-интервальных функций, рассмотренный в главе 2. ^-интервальную функцию обозначим следующим образом:

где 0 < а < /?.

Формулируется аналог предположения (С1) из главы 2. (С1*) Отображение Чиф(и} •) монотонно для любого и€ Н.

Заметим, что из (С1') следует, что отображение ■) является силь-

но монотонным с константой ет для любого и 6 Я.

Обозначим Р(и) = Р£(и) = Чьф£(и, = +

еВи для любого и € Н.

Поскольку функция ф монотонна, то монотонным является и отображение Р. Более того, из определения следует, что равновесная функция фе является сильно монотонной с константой ет, так же, как и отображение Р£ : Н —► Н.

Для регуляризированной задачи доказаны теоремы 3.6 и 3.7, которые являются аналогами теорем 2.6 и 2.7 из главы 2. Комбинированный метод для решения исходной монотонной задачи (1) выглядит следующим образом. Метод 4

Шаг 0. Выберем произвольное число В > 0, последовательность положительных чисел {с*} \ 0 и начальную точку г° € Н. Положим I = 1.

Шаг 1. Положим е = и и0 = г'-1.

Шаг Применим метод 2 из главы 2 для сильно монотонной задачи (7) и найдем точку ик € {и € Н \ < такую, что

ФЙ(и*) < (8)

Шаг 3. Положим г1 — ик, 1 = 1+ 1 и перейдем к шагу 1.

Условие (8) выполняется за конечное число шагов метода 2 в силу сильной сходимости к решению задачи (7), которая следует из теоремы 3.7.

Теорема 3.8 Пусть выполняются предположения (С1'), (СЗ) и (С4), и V* ф 0. Тогда Нт г1 = и*

^ 1-*оо п

Таким образом, доказана сильная сходимость последовательности ■{У} приближенных решений вспомогательных задач (7) к решению исходной монотонной задачи (1) в гильбертовом пространстве.

Третий раздел посвящен рассмотрению смешанного вариационного неравенства (2) с монотонным основным отображением в конечномерном пространстве Нп. Вводятся предположения: (Б1) Множество (I* решений задачи (2) непусто. (В2) Отображение О монотонно.

Определяется вспомогательная равновесная функция : V х и Я, которая обладает следующими свойствами:

(Е1) <р равномерно монотонна с функцией в, т.е., для всех -и, и € /Г1, имеем

<р(щи)+(р(у,и) < -0(||и - «11)11« - И|>

где В : К -> К — некоторая непрерывно возрастающая функция такая, что 0(0) = 0, 9(г) +оо при г —>• +оо;

<р равномерно ограничена с функцией а, т.е., для всех и, и е выполняется неравенство

Ии,«)|<1г(М)||и-|;||.

где а : Я Я — неубывающая функция со свойствами сг(0) = 0 и

ст(т) > 0 для любого т > 0;

<р(и) •) выпукла для любого и € II.

(Е2) Функция <р : V х V Я дифференцируема.

Рассматривается возмущенная задача: пусть с — положительный параметр, найти точку щ такую, что

(С(и£), V - и.) + /(V) - /(«*)+€*>(«*, и) > О VI» е II. (9)

В теореме 3.9 показано, что решения задач (9) аппроксимируют решение задачи (2) при е -> 0.

Для возмущенной задачи (9) строится интервальная функция. Фиксируется число ос > 0 и выбирается произвольная вспомогательная функцию ф : и х и Я, которая обладает следующими свойствами: (П) ф — дифференцируемая равновесная функция такая, что ф(и, V) > 0 для всех и, V 6 и, и ф и; Ч„ф(и, ад) 6 N{1/, ад) = {д € Я" : (д, V — и) < 0 V« € и} для всех и € 17; и ф(и1 *) равномерно выпукла с функцией С для любого и £ и, т.е.

ф{и>т) — ф(и,и) > — г;) + С(||ги — и|))Цги — и|| Уг>, ш € и,

где £ : Я —> Я — некоторая непрерывно возрастающая функция такая, что £(0) = 0, С(т) пРи Т +оо.

Определяется функция

где = V — и) + /(г?) — /(и) + е(р(щь) + аф{и1 V), и дока-

зывается, что она является интервальной функцией для задачи (9).

Вводятся предположения: (ВЗ) Для отображения (7 выполняется условие Липшица на II. (ЕЗ) Для отображений •) и •) выполняется условие Лип-

шица на1/ х I/; и для любой пары точек и, и € С/, имеем {Vи<р(щу) + — и) > г;([|и - г>|[)|[и - г>|(, где г} : Я Я —

непрерывно возрастающая функция такая, что г)(0) к= 0, Г}(т) —>■ +оо при т —> +оо.

(Р2) Для отображений V•) « ') выполняется условие Лип-

шица на и X и; и для любой пары точек щ V € и, имеем {и, г>) 4-¥ьф(и, и), и — и) > 0.

В этих условиях отображение и г>£еЧи) непрерывно, а функция

имеет производную по любому направлению й € В? в любой точке и е £Л

Формулируется необходимое и достаточное условие оптимальности для задачи (9).

Теорема 3.10 (Условие стационарности). Пусть выполняются предположения (В2), (Е1)-(ЕЗ), (Е1) и (Р2). Тогда тонка й является решением задачи (9) в том и только в том случае, когда и — и) > О Уи € и.

Доказывается, что если некоторая точка и € 17 не является решением задачи (9), то вектор й = — и представляет собой направление убывания для функции ^ в точке и.

Для вспомогательной равномерно монотонной задачи (9) предложен метод 5, подобный методу 1 из главы 2.

Теорема 3.11 Пусть выполняются предположения (В2), (ВЗ), (Е1)~ (ЕЗ), (Р1) и (Р2). Тогда итерационная последовательность, сгенерированная методом 5, сходится к единственному решению задачи (9).

Для решения исходного монотонного смешанного вариационного неравенства разработан следующий метод:

Метод 6

Шаг 0. Выберем произвольную точку € V, число 5 > 0 и последовательность положительных чисел {е*} \ 0. Положим г = 1. Шаг 1. Применим метод 5 к вспомогательной равномерно монотонной задаче (9) при у0 = г1-1, г = г», и будем строить последовательность {у*} ДО тех пор, пока не выполнится условие

11/II (Ю)

Шаг В. Положим г% = ук, заменим г на г + 1 и перейдем к шагу 1. Теорема 3.12 Пусть выполняются предположения (В1)-(ВЗ), (Е1)~ (ЕЗ), (Р1) и (Р2) и последовательность {г*} построена методом 6. Тогда: (г) каждая 1-ая итерация метода является конечной; (И) последовательность -{У} сходится к точке и* € II* такой, что выполняется условие ь) > 0 Уи £ и*.

Четвертая глава диссертации посвящена численному исследованию

методов, изложенных во 2 и 3 главах. В первом разделе четвертой главы

1

рассмотрены примеры решения разнообразных тестовых задач. Размерность рассмотренных задач от 4 до 1000. Для построения части примеров использовался генератор тестовых задач. Результаты численных экспериментов показывают стабильную сходимость методов, при этом на скорость сходимости влияют многие факторы, такие как величина константы сильной монотонности, соотношение слагаемых гладкой и негладкой части и так далее.

Во втором разделе рассмотрен пример приложения вариационных неравенств к задаче потокового равновесия, приведены результаты численных экспериментов решения этой задачи на различных конфигурациях сети. Сравнение методов спуска по интервальной функции (метод 1) и по ^-интервальной функции (метод 2) показывает, что второй метод работает быстрее. Также рассмотрена задача потокового равновесия в динамической постановке, т. е., на временном интервале [0,Т], которая формулируется в виде вариационного неравенства в гильбертовом пространстве. Для ее решения применяется метод спуска по /^-интервальной функции (метод 2). Рассмотрены гладкий и негладкий вариант этой задачи, причем в негладком случае задача решается быстрее, т.е. здесь негладкость оказывает некоторый стабилизирующий эффект. В целом по итогам данной главы можно сделать вывод о работоспособности предложенных в работе методов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. На базе /^-интервальных функций построен и обоснован сильно сходящийся метод спуска без вычисления производных для негладких сильно монотонных равновесных задач в гильбертовом пространстве.

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

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

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

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

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

1. Коннов И.В. Применение D-интервальных функций для решения общих задач равновесия [Текст] / И.В. Коннов, О.В. Пинягина // Информационный бюллетень №10. Тезисы докладов XII Всероссийской конференции "Математическое программирование и приложения-2003" (Екатеринбург, 24-28 февраля 2003 г.) - Екатеринбург, 2003. - С.154.

2. Konnov I.V. £>-gap functions for a class of equilibrium problems in Banach spaces [Текст] / I.V. Konnov, O.V. Pinyagina // Computational Methods in Applied Mathematics. - 2003. - V.3, №2. - P.274-286.

3. Konnov I.V. Application of the £>-gap function approach to general equilibrium problems in Banach spaces [Текст] / I.V. Konnov, O.V. Pinyagina // 18th Intern. Symp. on Math. Programming : Abstracts (Copenhagen, Denmark, August 18-22, 2003) - Copenhagen, 2003. - P.53.

4. Коннов И.В. Метод спуска по интервальной функции для негладких задач равновесия [Текст] / И.В. Коннов, О.В. Пинягина // Изв.вузов. Математика. - 2003. - №12. - С.71-77.

5. Konnov I.V. £>-gap functions and descent methods for a class of monotone equilibrium problems [Электронный ресурс] / I.V. Konnov, O.V. Pinyagina // Lobachevskii Journal of Mathematics (http://Ijm.ksu.ru). -2003. - V.13. - P.57-65.

6. Кашина O.A. Применение регуляризации для монотонных задач равновесия и оптимизации [Текст] / О А. Кашина, И.В. Коннов, О.В. Пи-нягина // Тезисы Всероссийской конференции "Алгоритмический анализ неустойчивых задач" (Екатеринбург, 2-6 февраля 2004 г.) - Екатеринбург: Изд-во Уральского университета, 2004. - С. 278-279.

7. Пинягина О.В. Метод спуска по интервальной функции для негладких монотонных задач равновесия [Текст] / О.В. Пинягина // Вычислительные методы и программирование. - 2004. - Т.5. - С.154-160.

8. Пинягина О.В. Применение интервальных функций к негладким монотонным задачам равновесия [Текст] / О.В. Пинягина // Материалы Пятого Всероссийского семинара "Сеточные методы для краевых задач и приложения", посвященного 200-летию Казанского государственного университета (Казань, 17-21 сентября 2004 г.) - Казань, 2004. - С. 196199.

9. Пинягина О.В. Метод спуска для монотонных смешанных вариационных неравенств [Текст] / О.В. Пинягина // Труды Второй Всероссийской научной конференции "Математическое моделирование и краг евые задачи", Часть 3 (Самара, 1-3 июня 2005 г.) - Самара, 2005. -С. 193-194.

10. Коннов И.В. Метод спуска для монотонных задач равновесия [Текст] / И.В. Коннов, О.В. Пинягина // Материалы Седьмой международной Казанской летней научной школы-конференции "Теория функций, ее приложения и смежные вопросы"(Казань, 27 июня-4 июля 2005 г.) - Казань, 2005. - С. 86-87.

11. Пинягина О.В. Применение регуляризации и D-интервальных функций к монотонным задачам равновесия в банаховом пространстве [Текст] / О.В. Пинягина // Материалы Шестого Всероссийского семинара "Сеточные методы для краевых задач и приложения"(Казань, 30 сентября-2 октября 2005 г.) - Казань, 2005. - С. 182-184.

Подписано в печать 06.09.2006 г.

Заказ К-09/06. Уел, печ. л. 1,3. Тираж 100 экз. Бумага офсетная. Печать ризографическая. Отпечатано в копи-центре Казанского государственного университета

Введение

1 Равновесные задачи и вариационные неравенства. Общие сведения

1.1 Равновесные задачи, свойства монотонности, существование и единственность решения.

1.2 Вариационные неравенства и их свойства.

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

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

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

Формулировка равновесной задачи, которую сейчас считают классической, впервые была приведена в работе Х.Никайдо и К.Исоды (см. [45, 84]). Кроме вышеуказанных авторов, значительный вклад в общую теорию равновесных задач внесли работы Фань Цзы [71, 72], Ж.-П.Обена [48], Е.Блюма и В.Эттли [65, 66], Л. Ниренберга [46].

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

Для решения равновесных задач различных классов к настоящему времени предложено значительное число методов. Наиболее разработанными являются методы поиска седловых точек (строго) выпукло - вогнутой функции и методы решения вариационных неравенств с однозначным (строго) монотонным отображением. Методы такого типа предлагались К. Эрроу, JI. Гурвицем, X. Удзавой, В.Ф. Демьяновым, Е.Г. Голь-штейном, Ю.Г. Евтушенко, А.С. Антипиным, Г.М. Корпелевич, В.В. Васиным, И.В. Конновым, А.В. Лапиным, Е.А. Нурминским и П.И. Вер-ченко, Й.-Ш. Пангом и другими (см. [1, 2, 7, 13, 18, 19, 20, 21, 24, 25, 26, 34, 39, 40, 41, 42, 43, 47, 62, 73, 87] и др.). Методы решения игровых, в том числе минимаксных, и общих равновесных задач предлагались Дж. фон Нейманом, Н.Н. Воробьевым, Ю.Б. Гермейером, С.И. Зуховиц-ким, Р.А. Поляком, М.Е. Примаком, В.А. Волконским и В.З. Беленьким, В.П. Булатовым, Ю.Г. Евтушенко и В.Г. Жаданом, В.В. Федоровым, А.С. Антипиным, Ш.И. Галиевым, Ю.М. Ермольевым, С.П. Урясьевым и другими (см. [3, 4, 5,10,14,15,17,16, 26, 27, 29, 30, 44, 54, 55, 56, 57, 61] и др.).

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

Как известно, один из наиболее распространенных подходов к решению вариационных неравенств состоит в сведении их к соответствующей оптимизационной задаче с помощью так называемых интервальных (или оценочных) функций, (напр., [54, 55, 56, 57, 85, 86]). Хотя эти функции, как правило, являются невыпуклыми, они позволяют преодолеть многие трудности как в теории, так и при построении методов решения вариационных неравенств. При этом для сходимости обычно требуются дополнительные условия типа сильной монотонности. К тому же обычные интервальные функции не годятся для решения негладких задач в бесконечномерных пространствах.

Интересный класс интервальных функций — D-интервальные функции — был предложен Дж. Пенгом в [88] для обычных вариационных неравенств. Дж. Пенг показал, что D-интервальные функции позволяют преобразовать вариационное неравенство в задачу безусловной дифференцируемой оптимизации без локальных минимумов, если отображение в вариационном неравенстве является сильно монотонным и дифференцируемым. И.В. Коннов [34] распространил этот подход на смешанные вариационные неравенства, включающие негладкие выпуклые функции, и показал, что сами D-интервальные функции для негладких смешанных вариационных неравенств являются гладкими, затем И.В. Коннов и С. Кум [74] расширили этот подход на случай гильбертовых пространств.

С другой стороны, для решения монотонных вариационных неравенств широко используются регуляризирующие приемы (см. например, [74]), основанные на аппроксимациях Тихонова-Браудера [9, 60, 67, 68]. При этом для решения исходной монотонной задачи строится последовательность регуляризированных задач, обладающих усиленными свойствами монотонности, таким образом, что последовательность решений регуляризированных задач сходится в решению исходной задачи.

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

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

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

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

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

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

Основные результаты диссертации опубликованы в 11 работах: [31], [36]—[38], [50]—[53], [75]-[77]. Результаты докладывались на семинарах кафедры экономической кибернетики, на итоговых научных конференциях Казанского государственного университета (2002-2005); на Всероссийской конференции "Математическое программирование и приложения-2003", г.Екатеринбург, 24-28 февраля 2003 г., на "18 Международном симпозиуме по математическому программированию", г. Копенгаген, Дания, 18-22 августа 2003 г., на Пятом и Шестом Всероссийских семинарах "Сеточные методы для краевых задач и приложения", г. Казань, 17-21 сентября 2004 г. и 30 сентября-2 октября 2005 г.

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

Заключение

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

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

2. На базе D-интервальных функций построен и обоснован сильно сходящийся метод спуска без вычисления производных для негладких сильно монотонных равновесных задач в гильбертовом пространстве.

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

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

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

1. Антипин, А.С. Об одном методе отыскания седловой точки модифицированной функции Лагранжа Текст] / А.С. Антипин // Экон. и мат. методы. - 1977. - Т.13, №3. - С.560-565.

2. Антипин, А.С. Градиентные и проксимальные управляемые процессы Текст] / А.С. Антипин // Вопр. кибернетики. — М.,1992. — Вып. 178. С.32-67.

3. Антипин, А.С. О сходимости и оценках скорости сходимости проксимальных методов к неподвижным точкам экстремальных отображений Текст] / А.С. Антипин // Ж. вычисл. мат. и мат. физ. — 1995. Т.35, №5. - С.688-704.

4. Антипин, А.С. Итеративные методы прогнозного типа для вычисления неподвижных точек экстремальных отображений Текст] / А.С. Антипин // Изв. вузов. Математика. 1995. - №11. - С.17-27.

5. Антипин, А. С. Вычисление неподвижных точек экстремальных отображений при помощи методов градиентного типа Текст] / А.С. Антипин //Ж. вычисл. мат. и мат. физ. — 1997. — Т.37, №1. — С.42-53.

6. Бадриев, И.В., Итерационные методы решения вариационных неравенств в гильбертовых пространствах Текст]: учеб. пособие / И.Б. Бадриев, О.А. Задворнов. — Казань: Казанский государственный университет, 2003. — 132 с.

7. Бадриев, И.Б., Методы двойственности в прикладных задачах: Общая теория Текст]: учеб. пособие / И.Б. Бадриев, М.М. Карчевский.

8. Казань: Изд-во Казан, ун-та, 1987. — 146 с.

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

10. Бакушинский, А.Б. Итерационные методы решения некорректных задач Текст] / А.Б. Бакушинский, А.В. Гончарский. — М.: Наука, 1989. 128 с.

11. Беленький, В.З. Итеративные методы в теории игр и программировании Текст] / В.З. Беленький, В.А. Волконский, С.А. Иванков и др. М.: Наука, 1974. - 240 с.

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

13. Васильев, Ф.П. Численные методы решения экстремальных задач Текст] : учеб. пособие для вузов / Ф.П. Васильев. — М.: Наука, 1988. 522 с.

14. Васин, В.В., Некорректные задачи с априорной информацией Текст] / В.В. Васин, A.JI. Агеев. — Екатеринбург: Наука, 1993. — 263 с.

15. Воробьев, Н.Н. Основы теории игр. Бескоалиционные игры Текст] / Н.Н. Воробьев. М.: Наука, 1984. - 496 с.

16. Галиев, Ш.И. Направления убывания для минимаксиминных задач Текст] / Ш.И. Галиев //Ж. вычисл. мат. и мат. физ. — 1994. Т.34, №3. С.323-343.

17. Галиев, Ш.И. Нахождение приближенных решений минимаксных задач Текст] / Ш.И. Галиев //Ж. вычисл. мат. и мат. физ. — 1997.- Т.37, №12. С.1439-1448.

18. Гермейер, Ю.Б. Игры с непротивоположными интересами Текст] / Ю.Б. Гермейер. М.: Наука, 1976. - 327 с.

19. Голыптейн, Е.Г. Обобщенный градиентный метод отыскания седло-вых точек Текст] / Е.Г. Голыптейн // Экон. и мат.методы. — 1972. Т.8, №4. - С.569-579.

20. Голыптейн, Е.Г. Метод уровней, его обобщения и приложения Текст] / Е.Г. Голыптейн, А.С. Немировский, Ю.Е. Нестеров // Экон. и мат. методы. 1995. - Т.31, №3. - С.164-180.

21. Демьянов, В.Ф. Численные методы разыскания седловых точек Текст] / В.Ф. Демьянов, А.Б. Певный // Ж. вычисл. мат. и мат. физ. 1972. - Т. 12, №5. - С.1099-1127.

22. Демьянов, В.Ф. Приближенные методы решения экстремальных задач Текст] /В.Ф. Демьянов, A.M. Рубинов. — JL: Ленингр. ун-т, 1968. 180 с.

23. Демьянов, В.Ф. Основы негладкого анализа и квазидифференциальное исчисление Текст] /В.Ф. Демьянов, A.M. Рубинов. — М.: Наука, 1990. 432 с.

24. Дюво, Г. Неравенства в механике и физике Текст] : пер. с франц. / Г. Дюво, Ж.-Л. Лионе. М.: Наука, 1980. - 384 с.

25. Евтушенко, Ю.Г. Итеративные методы решения минимаксных задач Текст] / Ю.Г. Евтушенко //Ж. вычисл. мат. и мат. физ. — 1974. — Т. 14, №5. С.1138-1149.

26. Евтушенко, Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации Текст] / Ю.Г. Евтушенко. — М.: Наука, 1982. 432 с.

27. Евтушенко, Ю.Г. Численные методы решения некоторых задач исследования операций Текст] / Ю.Г. Евтушенко, В. Г. Жадан //Ж. вычисл. мат. и мат. физ. 1973. - Т.13, №3. - С.583-598.

28. Ермольев, Ю.М. О поиске равновесий по Нэшу в играх многих лиц Текст] / Ю.М. Ермольев, С.П. Урясьев // Кибернетика. — 1982. — №3. С.85-88.

29. Зангвилл, У. Нелинейное программирование. Единый подход Текст] : пер. с англ. / У. Зангвилл. — М.: Советское радио, 1973. — 312 с.

30. Зуховицкий, С.И. О вогнутой игре п лиц и одной модели производства Текст] / С.И. Зуховицкий, Р.А. Поляк, М.Е. Примак // Докл. АН СССР. 1970. - Т.191, М. - С.1220-1223.

31. Зуховицкий, С.И. Вогнутые игры многих лиц Текст] / С.И. Зуховицкий, Р.А. Поляк, М.Е. Примак // Экон. и мат.методы. — 1971. — Т.7, №6. С.888-900.

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

33. Коннов, И.В. Методы решения конечномерных вариационных неравенств. Курс лекций Текст] / И.В. Коннов. — Казань: Изд-во ДАС, 1998. 101 с.

34. Коннов, И.В. Об одном классе D-интервальных функций для смешанных вариационных неравенств Текст] / И.В. Коннов // Изв.вузов. Математика. — 1999. — №12. — С.60-64.

35. Коннов, И.В. Об одном классе моделей экономического равновесия Текст] / И.В. Коннов // Экон. и мат. методы. — 2004. Т.40, №3. - С.103-109.

36. Коннов, И.В. Метод спуска по интервальной функции для негладких задач равновесия Текст] / И.В. Коннов, О.В. Пинягина // Изв.вузов. Математика. 2003. - №12. - С.71-77.

37. Корпелевич, Г.М. Экстраградиентный метод для отыскания седло-вых точек и других задач Текст] / Г.М. Корпелевич // Экон. и мат.методы. 1976. - Т.12, №4. - С.747-756.

38. Корпелевич, Г.М. Экстраполяционные градиентные методы и их связь с модифицированными функциями Лагранжа Текст] / Г.М. Корпелевич // Экон. и мат.методы. — 1983. — Т.19, №4. — С.694-703.

39. Лапин, А.В. Введение в теорию вариационных неравенств Текст] / А.В. Лапин. — Казань: Изд-во Казанск. ун-та, 1981. — 125 с.

40. Лапин, А.В. Сеточные аппроксимации вариационных неравенств Текст] / А.В. Лапин. — Казань: Изд-во Казанск. ун-та, 1984. — 96 с.

41. Лапин, А.В. Методы релаксации для некоторых классов вариационных неравенств в Rn Текст] / А.В. Лапин // Сб. "Числ. анализ и мат. моделирование", М.: ОВМ АН СССР. 1989. - С.127-143.

42. Нейман, Дж. Теория игр и экономическое поведение Текст] : пер. с англ. / Дж. Нейман, О. Моргенштерн. — М.:Наука,1970. — 707 с.

43. Никайдо, X. Выпуклые структуры и математическая экономика Текст] : пер. с англ. / X. Никайдо. М.: Мир, 1972. - 520 с.

44. Ниренберг, Л. Лекции по нелинейному функциональному анализу Текст] : пер. с англ. / Л. Ниренберг. М.: Мир, 1977. - 232 с.

45. Нурминский, Е.А. О сходимости алгоритмов поиска седловых точек Текст] / Е.А. Нурминский, П.Е. Верченко // Кибернетика. — 1977. -т. С.112-116.

46. Обен, Ж.-П. Нелинейный анализ и его экономические приложения Текст] : пер. с франц. / Ж.-П. Обен. М.: Мир, 1988. - 264 с.

47. Панагиотопулос, П. Неравенства в механике и их приложения Текст] : пер. с англ. / П. Панагиотопулос. — М.: Мир, 1989. — 494 с.

48. Пинягина, О.В. Метод спуска по интервальной функции для негладких монотонных задач равновесия Текст] / О.В. Пинягина // Вычислительные методы и программирование. 2004. - Т.5. - С.154-160.

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

50. Примак, М.Е. Об одном вычислительном процессе отыскания точек равновесия Текст] / М.Е. Примак // Кибернетика. — 1973. — №1. — С.91-96.

51. Примак, М.Е. К вопросу об отыскании решения модели производства обмена Текст] / М.Е. Примак // Экон. и мат.методы. — 1979. - Т.15, №3. - С.559-571.

52. Примак, М.Е. Алгоритм отыскания решения линейной модели чистого обмена и линейной модели Эрроу-Дебре Текст] /М.Е. Примак // Кибернетика. 1984. - №5. - С.76-81.

53. Пшеничный, Б.Н. Необходимые условия экстремума Текст] / Б.Н. Пшеничный. М: Наука, 1969. - 152 с.

54. Сеа, Ж. Оптимизация Текст] / Ж. Сеа. М.: Мир, 1973. - 244 с.

55. Тихонов, А.Н. Методы решения некорректных задач Текст] : учеб. пособие для вузов / А.Н. Тихонов, В.Я. Арсенин. — М.: Наука, 1979.- 285 с.

56. Федоров, В.В. Численные методы максимина Текст] / В.В. Федоров.- М.: Наука, 1979. 280 с.

57. Эрроу, К. Дж., Исследования по линейному и нелинейному программированию Текст]: пер. с англ. / К.Дж. Эрроу, JI. Гурвиц, X. Удза-ва. М.: ИЛ, 1962. - 335 с.

58. Auslender, A. Optimisation: Methodes Numeriques Текст] / A. Auslender. — Paris: Masson, 1976. — 178 p.

59. Bertsekas, D. Projection methods for variational inequalities with application to the traffic assignment problem Текст] / D. Bertsekas, E. Gafni // Math. Progr. Study. Amsterdam. - 1982. - V.17. -P.139-159.

60. Blum, E. Variational principles for equilibrium problems Текст] / E. Blum, W. Oettli // Parametric Optimization and Related Topics III/ Edited by J. Guddat, H.Th. Jongen, B. Kummer, and F. Nozicka.- Frankfurt am Main: Peter Lang, 1993. P.79-88.

61. Blum, E. From optimization and variational inequalities to equilibrium problems Текст] / E. Blum, W. Oettli // The Mathem. Student. -1994. V.63, №1. — P. 123-145.

62. Browder, F.E. Nonlinear monotone operators and convex sets in Banach spaces Текст] / F.E. Browder // Bull, of the Amer. Math. Soc. — 1965.- V.71, №5. P.780-785.

63. Browder, F.E. Existence and approximation of solutions of nonlinear Variational inequalities Текст] / F.E. Browder // Proc. Nat. Acad. Sci. USA. 1966. - V.56. - P.1080-1086.

64. Chadli, 0. Descent method for equilibrium problems in a Banach space Текст] / О. Chadli, I.V. Konnov, J.C. Yao // Сотр. Mathem. Appl. -2004. V.48. - P.609-616.

65. Cojocaru, M.-C. Projected Dynamical Systems, Evolutionary Variational Inequality, Applications, and a Computational Procedure Текст] / M.-C. Cojocaru, P. Daniele, A. Nagurney //J. Optim. Theory Appl. 2005.-V.127, №3.-P.l-15.

66. Fan, K. A generalization of Tychonoff's fixed-point theorem Текст] / К. Fan // Math. Annalen. 1961. - V.142, №3. - P.305-310.

67. Fan, K. A minimax inequality and applications Текст] / К. Fan // Inequalities III / Edited by O. Shisha. — New York: Academic Press, 1972. P.103-113.

68. Konnov, I.V. Combined Relaxation Methods for Variational Inequalities Текст] / I.V. Konnov. — Berlin: Springer-Verlag, 2001. — 181 p.

69. Konnov, I.V. Descent methods for mixed variational inequalities in a Hilbert space Текст] / I.V. Konnov, S. Kum // Nonlinear Analysis: Theory, Methods and Applications. 2001. - V.47. - P.561-572.

70. Konnov, I.V. D-gap functions for a class of equilibrium problems in Banach spaces Текст] / I.V. Konnov, O.V. Pinyagina // Computational Methods in Applied Mathematics. 2003. - V.3, №2. - P.274-286.

71. Konnov, I.V. D-gap functions and descent methods for a class of monotone equilibrium problems Электронный ресурс] / I.V. Konnov, O.V. Pinyagina // Lobachevskii Journal of Mathematics (http://ljm.ksu.ru). 2003. - V.13. - P.57-65.

72. Larsson, Т., Ergodic, primal convergence in dual subgradient schemes for convex programming Текст] / Т. Larsson, M. Patriksson, A.-B. Stromberg // Math. Programming. 1999. - V.86. - P.283-312.

73. Lescarret, C. Cas d'Addition des Applications Monotones Maximale dans un Espace de Hilbert Текст] / С. Lescarret // Comptes Rendues Hebdomadaires des Seances de l'Academie des Sciences. — 1965. — V.261. P.1160-1163.

74. Lions, J.-L. Variational inequalities Текст] / J.-L. Lions, G. Stampacchia // Comm. Pure. Appl. Math. 1967. - V.20, N3. - P.493-519.

75. Nagurney, A. Network Economics: A Variational Inequality Approach Текст] / A. Nagurney. — Dordrecht, The Netherlands: Kluwer Academic Publishers, 1999. 444 p.

76. Nash, J. Non-cooperative games Текст] / J. Nash // Ann. of Mathematics. 1951. - V.54, №2. - P.286-295.

77. Nikaido, H. Note on noncooperative convex games Текст] / H. Nikaido, K. Isoda // Pacific J. Mathematics. 1955. - V.5, №1. - P.807-815.

78. Patriksson, M. Merit functions and descent algorithms for a class of variational inequality problems Текст] / M. Patriksson // Optimization.- 1997. V.41, M. - P.37-55.

79. Patriksson, M. Nonlinear Programming and Variational Inequality Problems: a unified approach Текст] / M. Patriksson. — Dordrecht, The Netherlands: Kluwer Academic Publishers, 1999. — 334 p.

80. Pang, J.-S. Iterative methods for variational and complementarity problems Текст] / J.-S. Pang, D. Chan // Math. Programming. — 1982,- V.24, №3. P.284-313.

81. Peng, J.-M. Equivalence of variational inequality problems to unconstrained minimization Текст] / J.-M. Peng / / Math. Programming. 1997. - V.78. - P. 347-355.

82. Rosen, J.B. Existence and uniqueness of equilibrium points for concave n-person games Текст] / J.B. Rosen // Econometrica. — 1965. — V.33, №3. P.520-534.

83. Yamashita, N. Unconstrained optimization formulations of variational inequality problems Текст] / N. Yamashita, K. Taji, M. Fukushima // J. Optim. Theory and Appl. 1997. - Y.92. - P.439-456.