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

\

с-

I

\

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

ШПИРКО Сергей Валерьевич

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

Специальность 01.01.09 Математическая кибернетика

АВТОРЕФЕРАТ

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

МОСКВА - 2ООО

Работа выполнена в отделе прикладных проблем оптимизации ВЦ РАН

Научный руководитель:

докх-ор физико-математических наук Антипин А.С.

Официальные оппоненты:

доктор физико-математических наук, профессор Васильев Ф.П. доктор физико-математических наук Смольяков Э.Р.

Ведущая организация:

Центральный Экономико-Математический Институт РАН.

Защита диссертации состоится 2000 г. в 1.1.. ч.

на заседании дисеертационнного совета К002.32.01 при Вычислительном Центре РАН по адресу: 117967, Москва ГСП-1, ул. Вавилова, 40, конференц-зал

С диссертацией можно ознадомитьсяв библиотеке ВЦ РАН. Автореферат разослан " ..71..." 2000 г.

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

чл.-кор. РАН, доктор физико-математических наук

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

Актуальность темы диссертации.

Равновесное программирование является интенсивно развивающейся областью математического программирования. Задачу равновесного программирования можно сформулировать в следующей форме. Найти точку v" е V, удовлетворяющую неравенству

$(«*, V*) < Ф(v*, w) ~iw е V,

где целевая функция Ф (?;.?/;) задана на произведении подмножеств конечномерного метрического пространства V х V. Здесь переменная v играет роль параметра, а» - переменная оптимизации.

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

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

Значительным стимулом к дальнейшему развитию теории равновесных задач послужило доказательство теоремы Какутани о существовании равновесного решения, которую можно считать обобщением известной теоремы Брауэра о неподвижной точке. Позднее в работах Обепа, Ки Фаня, Лионса, Эттли и др. были получепы и другие формулировки теоремы существования.

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

Несмотря на достигнутые результаты, разработка равновесных методов по-прежнему остается актуальной и перспективной областью исследований.

Также необходимо остановиться еще на одном аспекте, связанном с равновесными задачами, а именно их неустойчивостью (некорректностью) к возму-

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

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

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

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

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

Научная новизна работы.

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

Теоретическая и практическая ценность работы.

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

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

- научном семинаре ВЦ РАН под руководством проф. Евтушенко Ю.Г.;

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

- научном семинаре ЦЭМИ РАН под руководством проф. Голыптейна Е.Г.;

- XI Всероссийской конференции "Математическое программирование и при-ложения"в Екатеринбурге ( февраль 1999 );

- VI Конференции "Обратные и некорректно поставленные задачи"« Москве (19-22 топя 2000).

Публикации. Основные результаты опубликованы в работах [1], [2], [3], перечисленных в конце автореферата.

Структура и объем работы. Диссертация состоит из введепия, трех глав и списка литературы, включающего "//' наименований. Объем работы составляет страниц машинописного текста.

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

В диссертации рассматривается следующая постановка равновесной задачи. Найти точку V* 6 V, удовлетворяющую неравенству:

Ф(г)*,«*) < Ф(г)*,то) Уш £ V. (1)

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

Таким образом, данная задача описывает ситуацию равновесия, при которой всем участникам не выгодно уклоняться от точки равновесия у', что в противном случае приведет к увеличению функции издержек Ф(г>*,ги).

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

Заметим, что если Ф(и, и) не зависит от V, то исходная задача превращается в классическую задачу оптимизации.

Принципиальный вопрос о существовании равновесного решения разрешает теорема Какутани. Действительно, с функцией Ф(?;, т) можно связать точечно-множественное отображение, которое ставит в соответствие каждой точке V из допустимого множества V выпуклое, замкнутое подмножество

М(у) = Агдтгп{Ф(у,и) | ы е V}.

Тогда согласно теореме Какутани, если множество V - выпуклый компакт, а функция Ф(и,щ) непрерывна по совокупности переменных, и выпукла по ю при

фиксированной v, то существует точка v', которая содержится в своем образе M(v*), т.е. является равновесным решением задачи (1).

Будем в дальнейшем считать, что относительно задачи (1) выполнено Предположение 1: Допустимое множество V выпукло и замкнуто, функция Ф(г>, w) выпукла н дифференцируема по переменной w при фиксированной v, и удовлетворяет условию кососимметричности:

Ф(и,г)) - Ф(ь,то) - Ф(ад,и) + Ф(м,ги) > 0 е V. (2)

Предложенное Аптипиным A.C. понятие кососимметричности занимает важное место в теории равновесного программирования. Оно обобщает свойство "седловитости"функции Лагранжа и является достаточным для сходимости градиентных методов к равновесному решению. В связи с этим представляется важным получить необходимые и достаточные условия кососимметричности. Обозначим через УгФ(г>, w) градиент функции Ф(г;, ш) по второй переменной

w:

Справедлива следующая лемма.

Лемма 1 Пусть функция Ф(у,ги) кососимметрична (2) и выпукла по w при фиксированной v. Тогда справедливы неравенства

<V2$(ü, v) - Х/2Ф(щ w), v~w)> 0;

v) + V22$(t;, v) У 0 Vv,w£V,

где V21<P(v,v) и УгзФ^и) - якобианы векторной функции Vyi>(i>, w) по первой и второй переменной, взятые на диагонали квадрата w = v.

Достаточное условие кососимметричности изучено слабо. Однако часто оказывается полезным следующий факт. Если оператор A(v) : V —> Л" является монотонным на выпуклом множестве V, то функция Ф(ь,ш) -— (A(v),w) является кососимметричной.

Также необходимо отметить, что множество кососимметричных функций является выпуклым конусом: умножение кососимметричной функции на положительную константу оставляет функцию кососимметричной; сумма двух кососимметричных функций также является кососимметричной функцией.

Наряду с (2) рассмотрим важное условие сильной кососимметричности с константой ß > 0:

Ф(и,!/) - Ф(г>,ш) - Ф(го,ь) 4-Ф(ги,ги) > ß ||г> - u>||2 \/v,w £ V, (3)

которое гаралтирует не только сходимость к решению, но и получение оценок сходимости по аргументу.

В связи с условием (3) необходимо подчеркнуть, что в просто кососиммет-ричном случае мпожество V* равновесных решений имеет достаточно сложную структуру (например, оно может состоять из нескольких изолированных точек). Но если наша задача сильно кососимметричяа, то множество V* (если оно не пусто) всегда состоит из единственной точки.

С равновесной задачей (1) тесно связана следующая задача - найти й е V :

Ф(ги,и) < Ф(-ш,тя) е V. (4)

Справедлива следующая

Лемма 2 Если функция Ф («, ш) косоыишетрична (2), то любое решение задачи (1) является решением изадачи (4). Ив обратную сторону, если Ф(у,хи) выпукла и непрерывна по ш, то решение Ц) будет решением (1).

При этом заметим, что в случае выпуклости и непрерывности функции Ф(и,ги) по и) множество V решений задачи (4) выпукло и замкнуто.

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

Тогда решение д можно считать точкой притяжения этой игры. Находясь в точке V* 6 V*, игроки никогда не захотят изменить эту стратегию. Находясь же вне множества V, игроки всегда будут стремиться гуда придти. Интуитивно ясно, что условия для существования точек Ъ должны быть слабее, чем для точек V*.

Обоснованием данного утверждения служит следующая

Теорема 1 Если выполнено Предположение 1 и множество V ограничено, то задача (4) имеет хотя бы одно решение.

Если же фупкция Ф(и,ы?) сильно кососимметричяа, то существование решения удается доказать и без предположения об ограниченности допустимого множества V:

Теорема 2 Если выполнено Предположение 1 и функция Ф(г',ю) сильно косо-симметрична (3) с константой 0, то задача (4) имеет единственное решение V, причем удовлетворяющее неравенству

Ф(ю,€) +/3 Иг« - £[|2 < Ф(ю,т) Уш е V.

Таким образом, в сильно кососимметричном случает удается ослабить требование ограниченности множества V в теореме Какутани.

Заметим, что для существования решения (4) не требуется, в отличие от (1), непрерывность функции Ф(«, го) по V. Поэтому для некоторых важных классов

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

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

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

<УФ2(1>>*),И) - V*) > 0 Vw G V.

В дальнейшем ограничимся анализом двух классов функций Ф(г>, w): с липши-цевым градиентом V2$'(v, v):

||Va$(«;,v)- V2$(u),w)|i < L ||ü-HI Vu,zueV, (5)

и равномерно ограниченным градиентом:

||У2Ф(«,ш)|| < 1 V»,weK (6)

Прежде всего, для решения задачи (1) рассматривается метод проекции градиента. В нем очередное приближение находится как проекция из точки, полученной из предыдущего приближения смещением в направлении антиградиента —УФ2(г>, w), взятого на диагонали квадрата w — v:

vk+1 = iry(vk — QfcVaiif*,«4)). (7)

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

В основе предлагаемого метода усреднений лежит идея модификации метода проекции градиента, а именно вместо последовательности (г)*} из (7) рассматривается последовательность их средпих значений:

^ = ¿7,^', ¿7,* = 1, (8)

г=0 ¿=о

Ük+1 = 7Tv(wfc - akV2$(üh,ük)), (9)

т.е. рассматривается суммирование по Чезаро. Поскольку непосредственное применение формул (8)-(9) затруднительно, то предлагается пересчет точек vk по определенным рекуррентным формулам. В данной диссертации для метода усреднений устанавливается сходимость к слабому решению (4) на классе функций с равномерно ограниченным градиентом. При этом требование убывания к нулю длины шага at является существенным для сходимости. Необходимо подчеркнуть, что в отличие от метода проекции градиента, сходимость (по функционалу) данпого метода гарантируется и в просто кососимметричном случае.

В основе экстраградиентного метода, разработанного Корпелевич Г.М. и Антипиным A.C. для класса функций с лшгашцевым градиептом, лежит идея предварительного вычислепия прогнозной точки, идея замены обычной итерации градиентного метода сдвоенной итерацией:

йк = ny(vk - aV2i(t)fc, vk)),

Vм = тгу(г/ - QV2$(ük,öfc)).

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

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

Теорема 3 Пусть выполнено Предположение 1 и следующие условия:

- функция Ф(г), tu) сильно кососимметрична (3) с константой ß > 0;

- градиент V2$(f,u) ограничен (6) с константой I > 0;

- длина шага а* выбирается как а* = С/{к + 1), где С = l/(ß - 7).

Тогда метод (8)-(9) сходится к слабому решению ii 6 V, причем справедлива оценка

711 11 - (fc+l)(fc + 2) G0-7)(fc + 2)' Jt:(U'Ph

Рассмотрим еще один аспект, связанный с равновесной задачей (1). А именно ее неустойчивость (некорректность) к возмущениям. Поэтому для ее решения приходится привлекать методы решения некорректных задач, в частности методы регуляризации. До сих пор исследователи развивали для этой цели классический метод Тихонова А.Н. с сильно выпуклым стабилизатором. Здесь стоит упомянуть работы Антипина A.C., Бакушинского A.B., Васильева Ф.П., Гончарского A.B.

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

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

П(у,ш) = {у, и)), v,weV,

и перейти к рассмотрению параметрического семейства регуляризованных задач - найти ур е V:

Ф/зО^Чз) < ад) V«) е V, (10)

где

Фр(и, ш) = Ф(г>, ю) + ¡3 П(г>, ги).

Поскольку регуляризованная функция Фр{и, эд) является уже сильно косо-симметричной, то решение ур единственно. Таким образом, семейство задач (10) порождает однозначную траекторию {ид}-

Необходимо подчеркнуть, что данная функция П(у,т) не удовлетворяет стандартным требованиям, предъявляемым к стабилизатору. Например, она не является неотрицательной. Однако кососимметричная регуляризация также обеспечивает устойчивость и сходимость траектории {ьр} к нормальпому решению исходной задачи (1).

Теорема 4 Пусть выполнено Предположение 1, а функция Ф(у,ы) непрерывна по совокупности переменных (у,го). Тогда траектория {г^} ограничена и сильно сходится при 0 —> 0 тс проекции проксцентра (в данном случае это точка ноль) на множество решений исходной задачи (1):

V/} —► я у* 0.

Если целевая функция задана неточно, то сходимость траектории {г^} обеспечивается при классических условиях согласования параметров е(5) и 0(6):

И-

Здесь 6 > 0 - точность задания целевой функции:

|Ф4(1>,ш) — Ф(г>, ад)| < <5 (1 + |Н| ||гу||) Уу,юеУ, (11)

а £ > 0 - точность решения регуляризованной задачи.

Следуя работам Васильева Ф.П., в диссертации развивается метод итеративной кососимметричной регуляризации, в которой шаг итеративного метода

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

ük = TTyC^ - ак (у{;Ф(</У) + ßk ufc)), (12)

vk+1 = ny(vk - Qfc йк) + ßk fi*)), (13)

где У£Ф(г>, v) - вычисленное приближенно значение частного градиента V2i"(w, v).

Здесь необходимо подчеркнуть, что возможность применения экстраградиентного метода основана на том, что поиск регуляризованного решения Vß эквивалентен решению следующего вариационного неравенства:

Vß) + ß vß, w - Vß) > 0 Vtü 6 V.

Справедлива следующая

Теорема 5 Пусть выполнена Предположение 1; градиент V2$(u,i>) Липшицев с константой L > 0; приближение Vfä(v,v) задано с точностью ö > 0:

- Va«(t>,r»)l < it(l + ||w||) Vu e V; (14)

последовательности ak >0, ßk > 0, <5*. > 0 таковы, что

oo

lim ßk = lim Sk = 0, Y,01А = +oo, ь=о

ßk+1 < 0k, lim ——= 0, lim ~ = 0 при k-* oo. Qkßl ßk

Тогда последовательность {vfe}, построенная с помощью (12), (13), сильно сходится при к —> оо к

v* = х у* 0.

Необходимо заметить, что при выведении асимптотических оценок сходимости в классической регуляризации (по А.Н. Тихонову) существенно использует^ ся свойство неотрицательности стабилизатора. В нашем случае этого гарантировать мы не можем. Поэтому приходится опираться на другие идеи. А именно, кососимметричная регуляризация позволяет использовать развитый во второй главе математический аппарат для решения исходной кососиммегричной задачи (1).

Естественной мерой сходимости метода к решению является невязка по аргументу ||i>fc - d*||. Поскольку без дополнительного предположения о сильной

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

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

£(v) = sup{<3>(ü,u) v е V,

а для слабой задачи (4) - функция

ß(v) = sup{4?(w,u) — Ф(ш,«))}, v е V.

u)6V

Не ограничивая общности рассуждений, считаем, что £(и) и ¡i(v) заданы на ограниченном множестве (diamV — R). В противном случае (когда V неограни-чено) будем рассматривать сильную и слабую меры заданными на пересечении V с шаром достаточного большого радиуса R, содержащим соответствующую точку решения.

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

Также отметим, что из условия кососимметричности следует неравенство — £(v)> хс- 601,1 гочка v* - сильное решение, то она также будет и слабым решением. В обратную сторону это не так: слабое решение может существовать, а сильное - нет. Но даже если точка v* является сильным и слабым решением, то скорость сходимости мер £(vk) и ß(vk) к нулю может быть различной.

Развивая идеи Бахвалова Н.С., Немировского A.C., Нестерова Ю.Е. и Юдина Д.Б. на случай равновесных задач, в качестве оценки эффективности методов предлагается использовать показатель трудоемкости (iV£ для сильной, а N^ дня слабой задачи).

Он показывает сколько нужно сделать итераций метода, чтобы получающаяся при этом погрешность (£(?/) или ß{vk)) не превосходила заданного малого числа с.

Опираясь на развитый математический аппарат, в диссертации исследуются несколько вариантов кососимметричной регуляризации.

В основе первого варианта лежит идея однократной регуляризации. А именно, пусть нам необходимо решить исходную задачу (1) с требуемой точностью с (по сильной и слабой мерам). Для этой цели выберем один раз параметр регуляризации ß и решим приближенно соответствующую регуляризованпую задачу (10). Тогда, если согласовать определенным образом параметр регуляризации и погрешность решения регуляризованной задачи с с, то полученная точка vk будет приближенным решением и исходпой задачи.

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

Теорема 6 Пусть последовательность {vk} строится по следующим рекуррентным формулам:

= —--vk + (15)

1 +- °iHl 1 + 1

где

йм = тгу(йк - ak (?,Ф(й\й*) +

Olk 1 + Ok ß0

Тогда, если выполнено Предположение 1 и следующие условия:

- градиент V2$(v,v) равномерно ограничен (6) с константой I > 0;

- длина шага ак — 2Я2/(е (к -f 1)),

то последовательность {vk}, построенная методом (15), сходится к v*, причем справедливы оценки

. t. ^ 2!2R2e2 ^ е

4 l2R2e2

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

На классе функций с равномерно ограниченным градиентом оптимальным является метод усреднений, реализующий неулучшаемуго оценку трудоемкости Л^ = 0(1/е2). Заметим, что метод проекции является наихудшим и на таком классе функций (А^ =■ 0(1 /с4)).

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

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

||v* - V/jJ <7 Рк, 7 = const > 0. (16)

Отсюда, в силу 0к —> 0, следует, что последовательность {г^} приближенных решений все ближе сходится к траектории {г^} точных регуляризованных решений.

Приведем формальное описание предложенного варианта регуляризации. Зафиксируем последовательности Д, а* и начальную точку v° € V.

Пусть к началу fc-oro этапа схемы имеется точка и*-1. Положим vk,° := vk~l и г := 0.

1) Вычислим очередную точку vk,,+1 с помощью экстраградиентного метода:

а" = - а*У2Ф&(г,*'\ (17)

V

V

vk= * («* - (18)

2) Если

||vfc'i+1 — V0k\\ > 7 = const > 0,

то полагаем t ;= t + 1 и возвращаемся к 1).

Иначе полагаем m(fc) := г-\ 1, vk — vk,m<-k^ и переходим к следующему (fc+L)-ому этапу.

Поскольку в явном виде критерий (16) останова не применим, то будем использовать его достаточное условие

ULR<^ (19)

N 7

+ Л ^ 7 А«, к = 0,1,...,

из которого и находятся требуемые параметры т(к) и 0к. Тогда справедлива следующая

Теорема 7 Пусть выполнено Предположение 1,

- множество V ограничено (НатУ = П),

- градиент УгФ(1;,г>) удовлетворяет условию (5) с константой Ь,

- длина тага ак = 1/(\/2 £)■

Тогда последовательность {г'*}, построенная с помощью (17), (18), сходится к решению исходной задачи (1):

V* —»V* = х у* 0.

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

Основные результаты, выпосимые па защиту.

1) проведено исследование основной задачи равновесного программирования, получены необходимые условия кососимметричности первого и второго порядков;

2) предложена слабая равновесная постановка и на ее основе доказана теорема существования для исходной задачи в кососимметрпчном и сильно ко-сосимметричном случае;

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

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

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

6) предложен метод отслеживания траектории с использованием экстраградиентного метода;

7) проведено сравнение предложенных методов по эффективности на основе сформированного математического аппарата.

Основные результаты диссертации опубликованы в следующих работах:

1. Шплрко C.B. Решение игр многих лиц с помощью градиентного метода прогнозного типа// Изв. ВУЗов. Математика.- 2000.-N 6.-С. 63-69.

2. Шпирко C.B. Решение игр многих лиц с помощью проксимального метода прогнозного типа// Докл. XI Всеросс. конф. "Математическое программирование и приложения", Тезисы докладов, 1999, С. 291-292.

3. Антипин A.C., Шпирко C.B. Метод кососимметричной регуляризации для поиска неустойчивых точек равновесия// Докл. VI конф. "Обратные и некорректно поставленные задачи", Тезисы докладов, 2000, С.7-8.