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

• Будак, Борис Александрович
• кандидат физико-математических наук
• 2003

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

Введение

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].

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

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

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.