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

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

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

I

Будак Борис Александрович

НЕПРЕРЫВНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ РАВНОВЕСНОГО ПРОГРАММИРОВАНИЯ

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

I

< АВТОРЕФЕРАТ

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

Москва - 2003

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

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

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

профессор ВАСИЛЬЕВ Ф.П.

доктор физико-математических наук, ведущий научный сотрудник АНТИПИН A.C.

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

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

профессор СМОЛЬЯКОВ Э.Р.

кандидат физико-математических наук МОЛОСТВОВ B.C.

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

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

С диссертацией можно ознакомиться в библиотеке факультета ВМиК

ЦЭМИ РАН.

МГУ.

Автореферат разослан "■К 2003 г.

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

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

1МТГ

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

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

Основную задачу равновесного программирования можно сформулировать следующим образом. Пусть имеется некоторая функция Ф(и,го), (г), и) £ № х ]¥, где \¥ — заданное множество из пространства Еп. Требуется найти точку V, £ И^, удовлетворяющую неравенству

Такую точку г>* называют неподвижной точкой или равновесной точкой задачи (1). Многие важные проблемы исследования операций, вычислительной математики и математической экономики могут быть сведены к задаче (1). Если функция Ф(«,«;) не зависит от переменной V, то задача (1) превращается в обычную задачу минимизации. Задачу (1) также можно трактовать как экономическую модель взаимодействия нескольких участников с совокупной стратегией ги из допустимого множества Ш и функцией издержек (целевой функцией) Ф(и,ш). Здесь первая переменная V играет роль параметра, а вторая ги - роль переменной оптимизации.

вования точек равновесия, равносильная проблеме существования неподвижных точек V 6 экстремального отображения ТУ (г;) функции Ф(г>, и>) на ЦТ, определяемого из условия

Экстремальное отображение, как правило, является многозначным и при доказательстве существования неподвижной точки обычно пользуются теоремами Какутани, Fan Ку, Oettli, обобщающими классические теоремы о неподвижных точках для многозначных отображений.

Что касается конструктивных методов точек равновесия, пригодных для использования на вычислительной тр*""*"* ™ чтп. чня.чиТельные

Ф(г>»,и«) ^ Ф(г),,го) Vw G W.

(1)

К настоящему времени достаточно хорошо изучена проблема сушест-

Ф(г>, W(t>)) = min Ф(г>, w), v € W, W{v) € W.

результаты получены лишь для отдельных классов задач (1), таких как задачи оптимизации, седловые задачи, вариационные неравенства. Однако эти методы разрабатывались и исследовались при значительных ограничениях на функцию Ф(я, w) (требования типа выпуклости по переменной w и вогнутости по переменной v, нулевой суммы игры, сильной монотонности оператора в вариационных неравенствах и т.п.). Между тем многие практически важные задачи математической экономики, теории игр не удовлетворяют этим ограничениям и ранее разработанные методы к этим задачам не вполне применимы. Поэтому можно считать, что разработка методов решения достаточно общих задач (1) практически только начинается, о чем свидетельствуют немногочисленные имеющиеся работы (Карпелевич Г.М., Антипин A.C., Шпирко C.B., Васин А.А, Делавархалафи А.)

При разработке методов решения задачи (1) следует еще учитывать, что эта задача, вообще говоря, неустойчива к возмущениям функции Ф(г>, w) и множества W, и для ее решения нужно использовать специальные методы, называемые методами регуляризации. Имеется относительно небольшое число работ, в которых предложены и исследованы методы регуляризации неустойчивых равновесных задач (Васильев Ф.П., Антипин A.C., Шпирко C.B., Делавархалафи А.).

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

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

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

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

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

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

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

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

— VII международной конференции "Обратные и некорректно поставленные задачи" (факультет ВМиК МГУ, Москва, 2001 г.)

— VIII международной конференции "Обратные и некорректно поставленные задачи" (факультет ВМиК МГУ, Москва, 2003 г.)

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

Структура и объем диссертации. Диссертация состоих из введения и трех глав. Общий объем диссертации 135 страниц. Список цитируемой литературы содержит 50 наименований.

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

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

В первой главе диссертации приводятся некоторые вспомогательные утверждения, используемые при доказательствах результатов диссертации (п. 1), предлагается непрерывный экстраградиентный метод с переменной метрикой (п. 2):

' v(t) + v(t) = 4«t)} [v(t) - 7(í)G-1(4í))Vw§(«(í),«(í))] ,

■ U(t) = 4W<» [v(t) - 7(í)G-1(4¿))V„$(<í),4¿))] , (2)

«(0) = г;0, t > 0,

где G(v) для каждого v — заданная симметричная положительно определенная матрица, [z] — так называемая G—проекция точки z на множество W, то есть точка тг^И'^ И является решением задачи минимизации

uq — любая фиксированная точка из Еп, Vw$(v,w) — градиент функции Ф(г>, w) по переменной w, 7(i) — параметр метода. Далее, в п. 3 излагается метод второго порядка, естественным образом обобщающий метод (2):

' Kt)Cr\v(t))v(t) + ß(t)v(t) + v{t) =

( = 4W<)) W - 7(Î)G-1(«(Î))V^(U(Î)îU(Î))] , ' <t) = 4(VW) KO - 7(*)G-1(«W)V.®(t;(i),«(i))] ,

t»(0) = v0) v(0) = vu t > 0.

Для методов (2), (3) доказаны теоремы сходимости траекторий vit) к множеству решений исходной задачи при определенных требованиях на задачу (1) и параметры методов 7(t),fi(t),ß(t). Приведем теорему сходимости для метода (3).

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

1.W С Еп — выпуклое замкнутое множество, множество решений задачи (1) W* непусто;

2. Функция Ф(и, w) выпукла, непрерывно дифференцируема по w при любом V из Еп; удовлетворяет условию кососимметричности на W:

- $(v,w) - + ^ 0 4v,w EW; (4)

сужение ее частного градиента по второй переменной на диагональ множества Еп X Еп удовлетворяет условию Липшица

||Vw®(ti,u) - ^Ф(«,1>)|| < Lw\\u-v\\, Vu,г» Е Еп\

3. G{y) — симметричная положительно определенная матрица при любом V из Еп; существуют сильно выпуклая дважды дифференцируемая функция Ф(г)) и положительные константы то, M, m ^ M, такие что

G(i>) = Ф"(®); m||u>||2<№)u;,w)<M||u)||2 Vv,w е ET; 4- Параметры ß(t), ß(t),j(t) удовлетворяют следующим условиям:

lit) > 0; lim 7(t) = 70; 0 < 70 < min { J2L, ;

fi(t) Е С2[0;+оо); ß{t) Е C^Oj+oo); p(t) £ й) > 0; mß2(t) > 4/t(t); ß"{t) > 0, fi'(t) < 0, ß'(t) < 0, lim ß(t) = ßx > 0, Hm ¡j!{t) = /4,.

Тогда существует такая точка у' из множества решений Ш* задачи (1), что

<-ЮО

11т |К*) — г/11 = 0; Ит ||г,(*)|| = 0; Кт \\Щ\\ = 0.

t-¥00

Как известно, задача (1) неустойчива к возмущениям исходных данных Ф(«, ад), и для ее решения необходимо применять методы регуляризации. В диссертации проведена регуляризация методов (2), (3) с помощью модификации классической функции Тихонова в сочетании с методом штрафных функций (п. 4,5). Рассмотрен случай, когда множество У/ задано следующим образом:

УУ = {и,€\¥0 |&Н<0, * = !,...,/, <7,-И = 0, 1 = 1 + 1,...,8}, (5)

где И^о С Еп — заданное выпуклое замкнутое множество, функция Ф(г',ад) определена на произведении евклидовых пространств Еп х Еп и дифференцируема по ги, функции ^¿(ги), г = определены и

дифференцируемы на Еп. Для учета ограничений типа равенств и неравенств из (5) использована простейшая штрафная функция

где дЦш) -- тах{&(ад);0} при г = 1,...,/, д?(и)) = при г =

I + 1,... ,з. Предполагается, что вместо точных значений градиентов (г;, ад), Р'(ад) нам известны их приближения Уг0Ф(«, ад, ¿), Р'(ад,£), удовлетворяющие условиям:

Регуляризованные варианты методов (2) и (3) соответственно имеют

(6)

||У„Ф(ад,ад,г) - У„,Ф(ад,ад)|| < ¿(¿)(1 + ||ад||) Уад € Еп-||Р'(<М) - ^»11 ^ *(*)(! + 1М1) V™ 6 Е».

(7)

вид:

+А(1)Р'(и(г),Ь) + а(1)и(Щ

«(«) = "Й^К*) - тМ^М^^ФКО,"(*),*)+ (8)

«(0) = «о, 0,

ТУо

-тЮ^МЖ^Ф«*), «(«), г) + А{1)Р'{и{ь), г) +

' «(*) = -тюа-^тъ*(9)

-Ь4(«)Р'(г,(*),*) + а(*М*))].

г,(0)=г>0, ¿(0) = г/ь £ > О,

где г/о, «1 — любые фиксированные точки из Еп, а(£), 7(4), /3(4) — параметры методов.

Для методов (8), (9) указаны условия согласования параметров и требования на задачу (1), обеспечивающие сходимость траектории г»(£) каждого из методов к нормальному решению исходной задачи, сформулированы правила останова, построены регуляризующие операторы. Приведем теорему сходимости для регуляризованного метода второго порядка.

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

1. \¥а — выпуклое замкнутое множество из Еп; множество Ш* решений задачи (1) непусто; функция Ф(и, го) непрерывна по переменной и на И*о при каждом фиксированном го из выпукла и непрерывно дифференцируема по переменной и) на при каждом фиксированном V из №0, удовлетворяет условию кососимметричности (4) на ]¥(), функции г = 1,...,1 выпуклы и непрерывно дифференцируемы на \¥о, функции д{(и>), г = I + 1,... ,з аффинны, то есть ф(ги) = (а,-,ш) — Ь;, а,- Е Еп, £>,• — действительные числа.

2. Существуют положительные постоянные т],с,-, г = такие, что

I

Ф(у„ »,) < Ф(|>„ т) + £ СЫН)" V™ 6 ¡=1

где г/» — нормальное решение задачи (1), параметр р штрафной функции (6) удовлетворяет условиям р > 1 ,р ^ 17/

3. Сужение градиента Уц,Ф(г>,го) на диагональ множества Еп х Еп и градиент ^(ги) удовлетворяют условию Липшица

ПУ^ФС«,«) - У„Ф(«,«)|| < Ущи б Еп;

4. Вместо точных значений градиентов УшФ(г>,и>) и Р'(ги) известны их приближения У„,Ф(г;,ги,4) и ^(ги, для которых выполнено условие (1);

5. G(v) — симметричная положительно определенная матрица при любом V из Еп; существуют сильно выпуклая дважды дифференцируемая функция Ф(г/) и положительные константы то, M, m ^ М, такие что

G(v) = Ф"(«); to|H|2^(G(v)™,W)<M|H|2

6. Параметры a{t)^{t),S(t),A{t),ß(t),ii{t) метода (9) таковы, что

a(t),j(t),A{t) 6 С^+оо); S(t) 6 С[0;+оо);

a(t) — выпуклая функция, a(t) > 0, a'(i) ^ 0; 7(2) > 0,7'(f) ^ 0; A(t) — вогнутая функция, A(t) > 0, A'(t) ^ 0; S(t) ^ 0;

H{t) е С2[0; +оо], /3(i) € C^Oj+oo], //(i) ^ 0, ß'(t) < 0, ¡j,"{t) > 0; lim ßit) = ßx > 0, lim ß(t) = ßoo> 0, lim fi'(t) = fa >

t—>+oo с—>-f-oo t—>+oo 4

Hm A(t) = +oo; (a(t) + 7(t)A(t) + S(t) + ^Ä) = 0;

\ a5/2(i)73/2(t) ^ a(i)72(i) J ' i-yoo

(при p~ г) последнее равенство не нужно) Тогда

¿¿^ ||i/(i) - »»II = 0, ^ ||i(t)|| = 0, Jim, ||S(*)II = О, (Ю)

где V» — нормальное решение задачи (1), причем сходимость в (10) равномерная относительно выбора УШФ(v,w,t) и ,P(uî,î).

На практике реальнее можно ожидать, что известны приближения V%,$(v,w) и Pj(tu) удовлетворяющие условию:

IlV^Ctü,«») - V„«(«I, w)|| < i(l + ||w||) VwEB";

|IW-P>)||<*(I + IMI), VweF",

где S > 0 - фиксированное число. Тогда можем процесс (9) можно заменить таким процессом:

дфС-ЧКОЖ*) + ßmt) + v(t) = ^»И*)--7 + A(t)Fs(u(t)) + a(i)«(t))],

u(t) = *%:{t))[v(t) - -r(t)G-\v(t))(^(v(t),v(t))+ (12)

+ «(*>(*))],

ь t»(0) = «o, 0,

который получается из (9) при замене УшФ(г>, ад, i), P'(w, t) на V* Ф(г>, w) и Pg(w) соответственно.

При любом фиксированном 5 : О < S < ¿(0) процесс (12) будем продолжать до момента t = t(S), определяемого условием

t{6) = sup{i : i(s) > S ; 0 ^ s < t} (13)

Поскольку 5(t) -ï oo при t oo, ¿(0) > S, то t(5) конечен Vi > 0. Обоснованием сформулированного правила останова служит

Теорема 3 Пусть выполнены все условия теоремы 2, кроме пункта 4; v(t) : 0 < i ^ t(S) — траектория процесса (12), где момент t(5) определяется из (13); приближения Vsw$(v,w) и Pg(w) удовлетворяют (11). Тогда lim ||v(i(5)) - v„|| = 0.

S—f0

Из этой теоремы следует, что оператор Rg, ставящий в соответствие набору данных (V* Ф(г;, w), Pî{w), о, a(t), 7(i), 6(t)) точку v(Ä) = v(t(S)), определяемую (12), является регуляризующим.

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

v„£W, Ф(«*,г>„) < $(v„w) Vw G W\

(14)

W = {w€ Wo IsiKKÛ, ¿ = 1,...,/}.

где Wq С En — заданное выпуклое замкнутое множество, функция Ф(г>,ги) определена на произведении евклидовых пространств Еп X Еп, выпукла и дифференцируема по w на Еп, фукнкции <7,(ги), г == 1,..., I выпуклы и дифференцируемы на Еп. Непрерывные методы линеаризации, описываемые дифференциальными уравнениями первого и второго порядков, для задачи (14) соответственно имеют вид:

v(t) + v(t) = - 7(î)g-44î))v^(*Mî))L

«W = - 7(Î)G-1(4Î))V^(^(Î),i;(Î))], (15)

u(O) = -Uo, t > o,

рфСГЧьфЩЬ) +ß{t)v(t) +v(t) = = - 'i(t)G-\v(t))Vw*(u(t), «(*))],

%«) I

t»(0)=»o, ¿(0) = t>i, 0,

«(*) = »SM*) - 7(i)G-1(^W)V^(t;(i),1;(i))],

где

S{v(t)) = {w € Wo | (g'Mt)),w - v(t)) + 9i(v(t)) < О, г = 1,... ,1},

V0,V! — любые фиксированные точки из Еп,7(i) > 0, fi(t),P(t) — параметры методов.

Заметим, что в методах (2), (3) в каждый момент времени, кроме выбора параметров 7(t), fj,(i),/3(t) еще необходимо проектировать точку на множество W, или, иначе говоря, решить задачу оптимизации, что не всегда просто для произвольного множества W. Поэтому градиентными методами пользуются в тех случаях, когда задача проектирования точки решается просто и в явном виде (например, когда , множество U представляет собой параллелепипед, гиперплоскость, по-

лупространство, ортант). В методах (15), (16) в случае, если Wo — многогранное множество, задача проектирования превращается в задачу квадратичного программирования, которая может быть решена за конечное число шагов.

Для методов (15), (16) доказаны теоремы сходимости траекторий v(t) к множеству решений задачи (14) при определенных требованиях на на параметры методов ^(t), fi(t),0(t) (п. 1,2).

В случае, когда вместо точных значений функций 9i{w) и градиентов нам известны их приближения gi(w,t), Vul$(v,w,t), g'i(w, t), зависящие от параметра t ^ 0, для решения задачи (14) можно использовать следующие регуляризованные варианты методов (2), (3):

' v{t) + vit) = - 7(î)G-Xî))(V^Kî),«(t), t) + a(t)u(t))],

• «W = - 7(î)G-1«î))(V^«î), vit), t) + a(iMi))],

fl(0) = t ^ 0,

(17); +/*(*)«(*) + »(0 =

^ = «siïmW - iw-^m^w^ «w, о+

' «(*) = - l(t)G-\vit))iVw^ivit),vit),t) + a(t)v(t))\,

. ti(0) = Щ, ¿(0) = vlt t > 0,

где

S(v(t),t) = {w e Wo I gi(v(t),t) + - «(*)> <

^0(i)(l + |Ki)||2), ¿ = 1,...^}, 11

I

I

— любые фиксированные точки из Еп, A{t),a(t),-y(t),0(t) ^ О, fj,(t),ß(t) — параметры методов. '

Для методов (17), (18) указаны условия согласования параметров и требования на задачу (14), обеспечивающие сходимости траекторий v(t) к нормальному решению исходной задачи, сформулированы правила останова, построены регуляризующие операторы (п. 3, 4).

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

v(t) + v(t) = Атдтт |I||«, - t>(i)||2G(v(f)) + 7(i)*Mi),«)} , *

u[t) = Ar g mm {i||tu - i»(*)IIg(.W) + 7(*Ж«(*)>«0} , . v(0) = v0, t > 0,

' fi^G-^vit))^) +ß(t)v{t) + v(t) =

= Arg min |i||ii; - t;(i)||c(,W) + 7(*)ФМ*)>™)} .

< f

u(t) = Arg mm |I||«, - «(f)|ßWfl) + 7№(v(t),w)

. t»(0) = va, v(0) = vu t > 0,

где ||®||g(b) = {G(y)x,x), г>0, V\ — любые фиксированные точки из Еп, 7(i),/t(i), ß(t) — параметры методов.

Для методов (13), (20) сформулированы требования на задачу (1) и параметры методов j(t), fi(t),ß(t), гарантирующие сходимость траекторий v(t) к множеству решений исходной задачи (п. 1,2).

Для решения задачи (1) с неточно заданными данными предложены и исследованы регуляризованные варианты методов (19), (20) имеющие

(20)

вид:

v(t) + v(t) = Arg min{-||w - t»(i)|ß(,W)+

+7(*)(Ф М*)>щ> 0 + A(t)P{w, t) + a(t){u(t), to»}, « u(t) = Arg min {I||« - (21)

+y(t)($(v(t), w, t) + A(t)P(w, t) + or(t)<t»(t),«»»} k v(0) = «o, t > 0, ' ¡i{t)G-x(v{t))v{t) + ß{t)v(t) + v(t) =

= " "Wllcw«)) + 7(«)(Ф(«(0.».*)+

+i4(t)P(w>t) + o(i)(«(i)>ii»»}>

fl (22)

u(t) = Arg min |-||to - t>(i)||£(,{t))+

+7(t)(#(i>(t), v), t) + A(t)P(w, t) + a(t){v(t), w»},

v(0) = v0, v(0) -vu t > 0,

где vq, vi — любые фиксированные точки из Еп, A(t), a(t), 7(i), ¡j,(t),ß(t) — параметры методов. Указаны требования к параметрам и задаче (1), обеспечивающие сходимость методов к нормальному решению задачи (1), сформулированы правила останова и построены регуляризующие операторы (п. 3,4).

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

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

2. Проведена регуляризация всех предложенных методов и на их основе построены регуляризующие операторы.

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

1. Антипин A.C., Будак Б.А., Васильев Ф.П. Непрерывный экстраградиентный метод первого порядка с переменной метрикой для решения задач равновесного программирования. // Вестник Моск. Ун-та. Сер. 15. Вычисл матем. и киберн., 2003. №1. С. 37-41.

2. Антипин A.C., Будак Б.А., Васильев Ф.П. Регуляризованный непрерывный экстраградиентный метод первого порядка с переменной метрикой для решения задач равновесного программирования. // Дифференциальные уравнения, 2002. Т. 38. №12. С. 1587-1595.

3. Антипин A.C., Будак Б.А., Васильев Ф.П. Регуляризованный непрерывный экстраградиентный метод первого порядка с переменной метрикой для решения задач равновесного программирования с неточно заданным множеством. // Вычислительные методы и программирование, 2002. Т. 3. №2. С. 118-128.

4. Будак Б.А. Непрерывный экстраградиентный метод второго порядка с переменной метрикой для решения задач равновесного программирования. // Вестник Моск. Ун-та. Сер. 15. Вычисл матем. и киберн., 2003. №2. С. 27-32.

5. Будак Б.А. Непрерывные экстраградиентные методы с переменной метрикой для решения задач равновесного программирования. // Докл. VII конф. "Обратные и некорректно поставленные задачи", Тезисы докладов, 2001, С. 15.

6. Будак Б.А. Непрерывные экстрапроксимальные методы с переменной метрикой для решения задач равновесного программирования. // Докл. VIII конф. "Обратные и некорректно поставленные задачи", Тезисы докладов, 2003, С. 15.

7. Будак Б.А. Непрерывный метод линеаризации первого порядка с переменной метрикой для решения задач равновесного программирования. // Вестник Моск. Ун-та. Сер. 15. Вычисл матем. и киберн., 2003.

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

í t »,

Введение

1 Непрерывные экстраградиентные методы с переменной метрикой

1.1 Вспомогательные утверждения.

1.2 Непрерывный экстраградиентный метод первого порядка с переменной метрикой.

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

1.4 Непрерывный экстраградиентный метод второго порядка с переменной метрикой.

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

2 Непрерывные методы линеаризации с переменной метрикой

2.1 Непрерывный метод линеаризации первого порядка прогнозного типа с переменной метрикой.

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

2.3 Непрерывный метод линеаризации второго порядка прогнозного типа с переменной метрикой.

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

3 Непрерывные проксимальные методы с переменной метрикой

3.1 Непрерывный проксимальный метод первого порядка прогнозного типа с переменной метрикой.

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

3.3 Непрерывный проксимальный метод второго порядка прогнозного типа с переменной метрикой.

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

Исследование математических моделей многих сложных явлений экономики, естествознания, связанных с поиском компромисса и согласования частично (или полностью) противоположных интересов сторон конфликта, составляет содержание области математики, которую называют равновесным программированием. Эта область также охватывает ряд важных задач теории игр и экономического равновесия [34, 39], многокритериального принятия решений в условиях неопределенности [32], обратных задач оптимизации [1], вариационных неравенств [33], седловых задач функции Лагранжа [30].

Основную задачу равновесного программирования можно сформулировать следующим образом. Пусть имеется некоторая функция Ф(и, w), (v, w) G W x W, где W — заданное множество из пространства Еп. Требуется найти точку v„ Е W, удовлетворяющую неравенству Ф(г>„и>) V™ € W. (1)

Такую точку vm называют неподвижной точкой или равновесной точкой задачи (1). Многие важные проблемы исследования операций, вычислительной математики и математической экономики могут быть сведены к задаче (1). Если функция Ф(и, w) не зависит от переменной V, то задача (1) превращается в обычную задачу минимизации. Также задачу (1) можно трактовать как экономическую модель взаимодействия нескольких участников с совокупной стратегией w из допустимого множества W и функцией издержек (целевой функцией) Ф(и,го). Здесь первая переменная v играет роль параметра, а вторая w - роль переменной оптимизации. Таким образом, данная задача описывает ситуацию равновесия, при которой всем участникам невыгодно уклоняться от точки равновесия V», что в противном случае приведет к увеличению значения функции издержек Ф(г>, w).

К настоящему времени достаточно хорошо изучена проблема существования точек равновесия, равносильная проблеме существования неподвижных точек v G W(v) экстремального отображения W(v) функции Ф(и, го) на W, определяемого из условия

Ф(и, W(v)) = min Ф(и, w), v е W, W(v) € W. w£W

Экстремальное отображение, как правило, является многозначным и при доказательстве существования неподвижной точки обычно пользуются теоремами Какутани [21], Fan Ку [31], Oettli [25], обобщающими классические теоремы о неподвижных точках для многозначных отображений.

Что касается конструктивных методов точек равновесия, пригодных для использования на вычислительной технике, то здесь значительные результаты получены лишь для отдельных классов задач (1), таких, как задачи оптимизации, седловые задачи, вариационные неравенства. Однако эти методы разрабатывались и исследовались при значительных ограничениях на функцию Ф(г>, го) (требования типа выпуклости по переменной w и вогнутости по переменной v, нулевой суммы игры, сильной . монотонности оператора в вариационных неравенствах и т.п.). Между тем, многие практически важные задачи математической экономики, теории игр не удовлетворяют этим ограничениям и ранее разработанные методы к этим задачам не вполне применимы. Поэтому можно считать, что разработка методов решения достаточно общих задач (1) практически только начинается, о чем свидетельствуют немногочисленные имеющиеся работы (Карпелевич Г.М. [35], Антипин А.С. [3, б, 8], Шпирко С.В. [43], Васин А.А [23], Делавархалафи А. [19]).

При разработке методов решения задачи (1) следует еще учитывать, что эта задача, вообще говоря, неустойчива к возмущениям функции w) и множества W, и для ее решения нужно использовать специальные методы, называемые методами регуляризации. Имеется относительно небольшое число работ, в которых предложены и исследованы методы регуляризации неустойчивых равновесных задач (Васильев Ф.П., Антипин А.С. [17, 18], Шпирко С.В. [43], Делавархалафи А. [20]).

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

А.С. Антипиным были предложены т. н. управляемые методы проекции градиента, или экстраградиентные методы, основанные на следующей идее: известно, что неподвижная точка v» задачи (1) является одновременно решением как вариационного неравенства

Vu^v»,г>„), w — v*) ^ 0 Ww G W, так и операторного уравнения и, = 7\w (v* ~ v,)) , где 7riv(.) — оператор проектирования некоторого вектора на множество W. Оба соотношения эквивалентны и являются необходимым условием минимума функции Ф(г>*,го) на множестве W.

Преобразование itw (v — irVw$(v, v)) — v можно трактовать как векторное поле скоростей, которое получается, если каждому вектору v поставить в соответствие образ этого преобразования. При этом точке v, будет соответствовать ноль, т.е. неподвижная точка имеет нулевую скорость. Во многих случаях, а именно в случае градиентных полей, порожденных задачами оптимизации, векторы поля направлены к неподвижной точке v„, т.е. к точке с нулевой скоростью. Если приближаться к этой точке по некоторой траектории, то длины векторов скоростей будут уменьшаться до нуля. Поэтому ожидается, что если из некоторой стартовой точки г>о провести траекторию v(t) так, чтобы касательный вектор этой траектории совпадал с вектором поля в каждой точке этой траектории, то со временем траектория попадет в сколь угодно малую окрестность неподвижной точки. Эту ситуацию можно описать с помощью дифференциального уравнения

4-v = kw{v — l(Vw$(v,v)), v(0)=vo, правая часть которого удовлетворяет всем условиям теоремы существования и единственности, следовательно при любых v<j и всех t ^ 0 существует траектория v(t). К сожалению, область применимости этого метода ограничена задачами оптимизации, поэтому был разработан аналог этого метода, использующий идею прогнозирования, а именно t»(0 + v(t) = 7TW Иt) - 7ушФ(м(г), u(t))), и(*)=*гиг(г>(0--7^«,ФИ0,«(*)))» (2) k v(0) = v0.

Здесь нахождение точки u(t) можно толковать как прогноз, то есть значение градиента функции Ф(и,го) по переменной w в основном уравнении метода берется не в текущей точке v(t), а в некой спрогнозированной точке u(t). На основании этих идей также были предложены и исследованы методы линеаризации прогнозного типа и проксимальные методы прогнозного типа. Однако, теоретические и численные исследования подтверждают, что такие методы медленно сходятся в тех случаях, когда поверхности уровня функции Ф(и, v) сильно вытянуты и эта функция переменной v имеет так называемый овражный характер.

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

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

В первой главе диссертации приводятся некоторые свойства кососимметричных функций, свойства решений задачи равновесного программирования (1), а также утверждения, используемые при доказательствах полученных в диссертации результатов и предлагается непрерывный экстраградиентный метод с переменной метрикой, обобщающий метод (2): u(t) = тг^(е)> - -u(t))], (3) v(0) = v0, t ^ 0, где [.] — так называемая G—проекция точки на множество W [29, стр. 308], vq — любая фиксированная точка из Еп, УшФ(г;, w) — градиент функции ги) по переменной w, 7(t) ^ 0 — параметр метода; G(v) для каждого v — заданная симметричная положительно определенная матрица. Заметим, что если G(v) = I — единичная матрица, то метод (3) превращается в метод (2). Далее на основе этого метода оказалось возможным получить метод второго порядка, естественным образом обобщающий метод (3):

- rtt)G-i(v{t))v{t)+mm+Ht) = 4(v(t» \v(t) - 7(t)G'1 (v(t)) Vm9(u(t), u(t))l, r -1 (4) k v(0) = v0, v(0) = vlf t ^ 0.

Для методов (3), (4) доказаны теоремы сходимости траекторий v(t) к множеству решений исходной задачи при определенных требованиях на задачу (1) и параметры методов 7(t), fi(t),(3(t) (теоремы 1.3 и 1.7).

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

W = {weW0 » = 1,.,/, gi(w) = 0, i = l + l,.,s}, (5) где Wo С Еп — заданное выпуклое замкнутое множество, функция Ф(г>, w) определена на произведении евклидовых пространств ЕпхЕп и дифференцируема по гу, функции <7;(го), г = 1,.,5 определены и дифференцируемы на Еп. Для учета ограничений типа равенств и неравенств из (5) использована простейшая штрафная функция S рн = £ W»)', р > 1,»€ Еп, (6) 1 где gt{w) = max{#(iu);0} при i = 1,.,/, gfip) = | при г = /+

Также предполагается, что вместо точных значений градиентов УшФ(г>, w), P'(w) нам известны их приближения У„,Ф(г>,ги,£), P'(w,t), зависящие от параметра t ^ 0. Регуляризованные варианты методов (3) и (4) соответственно имеют вид: v(t) + v(t) = тгйи(<)) [«(*) - 7WGf-1(® W) u(t), t)+

A(t)P'(u(t),t) + a(t)u(tj)], u(t) = [v{t) - 1(t)G-\v(t)){y^(v(t),v(tU)+ W

A(t)P'(v(t),t) + a(t)v(t))], u(0) = vo, 0, MWG-Hvitmt)+mm+«w= v(0) = Vo, v(0) =vu t ^ o, где Vo,Vi — любые фиксированные точки из En,A(t) > 0, a(t) > 0,7(2) > 0,fi(t),(3(t) — параметры методов.

Для методов (7), (8) указаны условия согласования параметров и требования на задачу (1), обеспечивающие сходимости траекторий v(t) к нормальному решению исходной задачи, сформулированы правила останова, построены регуляризующие операторы (теоремы 1.4, 1.5, 1.8 и 1.9).

Во второй главе диссертации предлагаются и исследуются различные модификации непрерывных методов, основанные на идее линеаризации [6, 7]. Эти методы реализованы для такой задачи равновесного программирования: найти точку v. из условий

-у. 6 W, ^ $(v„,w>) VweW; W = {w е W0 U(«>K0, t = l,.,/}, (9) где Wo С En — заданное выпуклое замкнутое множество, функция Ф(и,ги) определена на произведении евклидовых пространств Еп х Еп, выпукла и дифференцируема по w на Еп, фукнкции gi{w), i = 1,.,/ выпуклы и дифференцируемы на Еп. Непрерывные методы линеаризации, описываемые дифференциальными уравнениями первого и второго порядков, для задачи (9) имеют вид: v(t) + v(t)= [v(t) - «(0)] > = -тСО^Ю^.ФИ*), *(«))], (10) v(0) = v0, t ^ 0, ' fi(t)G-l(v(t))v{t)+/3(t)v(t)+v{t) = = [«(0 " v(0) = t»0, v(0) =vu t^ 0, где

S(v(t)) = {w € Wo I (g'i(v(*)), w - v(t)) + gi{v{t)) < 0, г = 1,.,/},

Vo, Vi —любые фиксированные точки из En,nf(t) > 0,fi(t),fi(t) — параметры методов. Если положить G(v) = I, то метод (10) превращается в непрерывный вариант метода из [6].

Для методов (10), (11) доказаны теоремы сходимости траекторий v(t) к множеству решений исходной задачи при определенных требованиях на задачу (1) и параметры методов 7(t), fi(t),/3(t) (теоремы 2.1 и 2.4).

Заметим, что в методах (3), (4) в каждый момент времени, кроме выбора параметров 7(t),fi(t)i/3(t) еще необходимо проектировать точку на множество W, или, иначе говоря, решить задачу оптимизации, что совсем непросто для произвольного множества W. Поэтому градиентными методами пользуются в тех случаях, когда задача проектирования точки решается просто и в явном виде (например, когда множество W представляет собой параллелепипед, гиперплоскость, полупространство, ортант). В методах (10), (11) в случае, если Wo — многогранное множество, задача проектирования превращается в задачу квадратичного программирования, которая может быть решена за конечное число шагов.

В случае, когда вместо точных значений функций <7;(ги) и значений градиентов У^Ф(г;,ги), <7,'(го) нам известны их приближения <7,•(«;,£), V„,$(u,iu,f), зависящие от параметра t ^ 0, для решения задачи (9) можно использовать следующие регуляризованные варианты методов (3), (4): щ+V(t)=[«(«) - 7(OG-1 И*» (v.«(I.(O, «w, t)+а(*мо)], «w = [«(о - iw~4v(t)) (y^(v(t)Mt), t)+«(о® w)], v(0) = v0, « > 0,

H^G-^vitMt) + (3{t)v(t) + v(t) = f (0 - 7(0G-1(f W) w, «(0,0 + a(0«(0)]. w = w - w) «w, о+«(*м*))]> t»(0) = Vo, t>(0) = vu t^ 0,

12)

13) где

S(v{t),t) = {w e Wo \ 9i(v(t),t) + (gi(v(t),t),w-v(t)) < 9(t)( 1 + И01Г), i = 1,.,/}, voj^i —любые фиксированные точки из Еп, A(t), a(t),7(£) > O,0(i) ^ 0,n(t),/3(t) — параметры методов.

Для методов (12), (13) указаны условия согласования параметров и требования на задачу (1), обеспечивающие сходимости траекторий v(t) к нормальному решению исходной задачи, сформулированы правила останова, построены регуляризующие операторы (теоремы 2.2, 2.3, 2.5 и 2.6).

В третьей главе диссертации предлагаются алгоритмы, основанные на идее проксимальных методов [8, 9,10, 13,16]. Проксимальные методы первого и второго порядков предназначены для решения задачи (1) с выпуклой по w, но, возможно, недиффе-ренцируемой функцией Ф(и,го). Они описываются следующими дифференциальными уравнениями: v(t) + v(t) = Атдтт ji||u, - t>(*)|fcMt)) + 7(*)*Н0>™)} , u(t) = Argndn |i||ti; - t>(*)||o(v(t)) + , v(0) = v0, t > 0, i{t)G~1(v{t))i{t)+j3{t)v(t) + v{t) = Arg nun I |u; - t>(i)| lent)) + т(*)Ф(«(*), w) J, u(t) = Argmm ||||w - v(OIIgmo) + 7(*)*M*)>«o} , w(0) =v0, t>(0) =vu t^ 0, где ||ж||с(у) = (G(y)x,x), v0,v1 — любые фиксированные точки из En^[t) > 0,fi(t), fi(t) — параметры методов. Если G(v) = I, то метод (14) превращается в непрерывный аналог метода из [16].

14)

15)

Для методов (14), (15) сформулированы требования на задачу (1) и параметры методов 7(t),pi(t),l3(t), гарантирующие сходимость траекторий v(t) к множеству решений исходной задачи (теоремы 3.1 и 3.5).

Для решения задачи (1) с неточно заданными данными в диссертации предложены и исследованы регуляризованные варианты методов (14), (15) имеющие вид:

16)

17) 1 v (2)1 &(„(*))

7(t) (ф(u(t), w, t) + A(t)P(w, t) + «(*)(«(*), w)) }, u{t) = Arg min - v(f)|£(v(t))+

7(t) (ф(v(t),w,t) + A(t)P(w,t) + a(t)(v(t),w)) }, v(0) = v0, t^ 0,

G-4v(t))v(t) + 0(t)v(t) + t>(*) = Arg min{^||«; -+7(0 (ф(гф), w, t) + A(t)P(w, t) + a(t)(u(t),w>) }, u{t) = Arg min - f (О11о(„(0)+

7(0 (ф(г;(0, -ш, t) + A(t)P(w, t) + a(t)(v(t),«;)) }, v(0) = г;0, г>(0) = vu t ^ 0, где vq^vi —любые фиксированные точки из Еп, A{t),a{t),^{t) > 0,[i(t),/3(t) — параметры методов. Для этих методов указаны требования к их параметрам и задаче (1), обеспечивающие их сходимость к нормальному решению задачи (1), сформулированы правила останова и построены регуляризующие операторы (теоремы 3.2, 3.3, 3.6 и 3.7).

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

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

2. Проведена регуляризация всех предложенных методов и на их основе построены регуляризующие операторы.

Основные результаты диссертации опубликованы в [44, 45, 46, 47, 48, 49, 50].

Автор выражает глубокую и искреннюю благодарность своим научным руководителям АНАТОЛИЮ СЕРГЕЕВИЧУ АНТИПИНУ и ФЕДОРУ ПАВЛОВИЧУ ВАСИЛЬЕВУ за постановку задач, ценные советы, замечания и помощь в работе.

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

2. Гольштейн Е.Г., Третьяков Н.В. Модифицированные функции Лагранжа. Теория и методы оптимизации. М.: Наука, 1989.

3. Fan Ку. A minimax inequality and applications // Inequalities III. Acad. Press, 1973. P. 103-113.

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

5. Harker Р.Т., Pang J.-Sh. Finite-dimensional variational inequality and nonlinear complementary problems: a survey of theory, algorithms and applications. // Mathematical programming, 1990. V. 48. P. 161-220.

6. Карлин С. Математические методы в теории игр, программировании и экономике. М.: Мир, 1964.

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

8. Nash J.F. Jr. Equilibrium points in n-person games. // USA, Proc. nat. acad. science, 1950. V. 36, 48-49.

9. Nicaido H., Isoda K. Note on noncooperative convex game. // Pacific J. Math., 1955. V. 5. №1. P. 807-815.

10. Обен Ж.-П. Нелинейный анализ и его экономические приложения. М.: Мир, 1988.

11. Полтерович В.М. Экономическое равновесие и хозяйственный механизм. М.: Наука. 1990.

12. Смольяков Э.Р. Равновесные модели при несовпадающих интересах участников. М.: Наука, 1986.

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

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

15. Шпирко С.В. Метод кососимметричной регуляризации для решения равновесных задач. Кандид, диссертация. М.: ВЦ РАН, 2000.

16. Антипин А.С., Будак Б.А., Васильев Ф.П. Непрерывный экстраградиентный метод первого порядка с переменной метрикой для решения задач равновесного программирования. // Вестник Моск. Ун-та. Сер. 15. Вычисл матем. и киберн., 2003. №1. С. 37-41.

17. Антипин А.С., Будак Б.А., Васильев Ф.П. Регуляризованный непрерывный экстраградиентный метод первого порядка с переменной метрикой для решения задач равновесного программирования. // Дифференциальные уравнения, 2002. Т. 38. №12. С. 1587-1595.

18. Будак Б.А. Непрерывный экстраградиентный метод второго порядка с переменной метрикой для решения задач равновесного программирования. // Вестник Моск. Ун-та. Сер. 15. Вычисл матем. и киберн., 2003. №2. С. 27-32.

19. Будак Б.А. Непрерывные экстраградиентные методы с переменной метрикой для решения задач равновесного программирования. // Докл. VII конф. "Обратные и некорректно поставленные задачи", Тезисы докладов, 2001, С. 15.

20. Будак Б.А. Непрерывные экстрапроксимальные методы с переменной метрикой для решения задач равновесного программирования. // Докл. VIII конф. "Обратные и некорректно поставленные задачи", Тезисы докладов, 2003, С. 15.

21. Будак Б.А. Непрерывный метод линеаризации первого порядка с переменной метрикой для решения задач равновесного программирования. // Вестник Моск. Ун-та. Сер. 15. Вычисл матем. и киберн., 2003.