Непрерывные методы решения задач равновесного программирования Будак Борис Александрович

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

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

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

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

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

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

Из вышесказанного следует, что тема диссертации, в которой разрабатываются и исследуются непрерывные методы решения задачи (1), является актуальной. А.С. Антипиным были предложены т. н. управляемые методы проекции градиента, или экстраградиентные методы, основанные на следующей идее: известно, что неподвижная точка v» задачи (1) является одновременно решением как вариационного неравенства так и операторного уравнения где 7riv(...) — оператор проектирования некоторого вектора на множество W. Оба соотношения эквивалентны и являются необходимым условием минимума функции Ф(г ,гу) на множестве W.

Преобразование кцг (v — 7V„, f(u, v)) — v можно трактовать как векторное поле скоростей, которое получается, если каждому вектору v поставить в соответствие образ этого преобразования. При этом точке и. будет соответствовать ноль, т.е. неподвижная точка имеет нулевую скорость. Во многих случаях, а именно в случае градиентных полей, порожденных задачами оптимизации, векторы поля направлены к неподвижной точке v», т.е. к точке с нулевой скоростью. Если приближаться к этой точке по некоторой траектории, то длины векторов скоростей будут уменьшаться до нуля. Поэтому ожидается, что если из некоторой стартовой точки v0 провести траекторию v(t) так, чтобы касательный вектор этой траектории совпадал с вектором поля в каждой точке этой траектории, то со временем траектория попадет в сколь угодно малую окрестность неподвижной точки. Эту ситуацию можно описать с помощью дифференциального уравнения правая часть которого удовлетворяет всем условиям теоремы существования и единственности, следовательно при любых VQ И всех t 0 существует траектория v(t). К сожалению, область применимости этого метода ограничена задачами оптимизации, поэтому был разработан аналог этого метода, использующий идею прогнозирования, а именно

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

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

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

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

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

Преобразование кцг (v — 7V„, f(u, v)) — v можно трактовать как векторное поле скоростей, которое получается, если каждому вектору v поставить в соответствие образ этого преобразования. При этом точке и. будет соответствовать ноль, т.е. неподвижная точка имеет нулевую скорость. Во многих случаях, а именно в случае градиентных полей, порожденных задачами оптимизации, векторы поля направлены к неподвижной точке v», т.е. к точке с нулевой скоростью. Если приближаться к этой точке по некоторой траектории, то длины векторов скоростей будут уменьшаться до нуля. Поэтому ожидается, что если из некоторой стартовой точки v0 провести траекторию v(t) так, чтобы касательный вектор этой траектории совпадал с вектором поля в каждой точке этой траектории, то со временем траектория попадет в сколь угодно малую окрестность неподвижной точки. Эту ситуацию можно описать с помощью дифференциального уравнения правая часть которого удовлетворяет всем условиям теоремы существования и единственности, следовательно при любых VQ И всех t 0 существует траектория v(t). К сожалению, область применимости этого метода ограничена задачами оптимизации, поэтому был разработан аналог этого метода, использующий идею прогнозирования, а именно

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

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

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

В первой главе диссертации приводятся некоторые свойства кососимметричных функций, свойства решений задачи равновесного программирования (1), а также утверждения, используемые при доказательствах полученных в диссертации результатов и предлагается непрерывный экстраградиентный метод с переменной метрикой, обобщающий метод (2): где Kw [...] — так называемая G—проекция точки на множество W [29, стр. 308], VQ — любая фиксированная точка из Еп, Vw$(v,w) — градиент функции Ф(г/, и ) по переменной w, 7(0 0 — параметр метода; G(v) для каждого v — заданная симметричная положительно определенная матрица. Заметим, что если G(v) = J — единичная матрица, то метод (3) превращается в метод (2). Далее на основе этого ме тода оказалось возможным получить метод второго порядка, естественным образом обобщающий метод (3):

Для методов (3), (4) доказаны теоремы сходимости траекторий v(t) к множеству решений исходной задачи при определенных требованиях на задачу (1) и параметры методов 7(0» МО»/ (О (теоремы 1.3 и 1.7). Как известно, задача (1) неустойчива к возмущениям исходных данных Ф(г , w), W, и для ее решения необходимо применять методы регуляризации. В диссертации проведена регуляризация вышеупомянутых методов с помощью модификации классической функции Тихонова в сочетании с методом штрафных функций. Рассмотрен случай, когда множество W задано следующим образом: где Wo С Еп — заданное выпуклое замкнутое множество, функция Ф(г , w) определена на произведении евклидовых пространств Еп х Еп и дифференцируема по гу, функции 7;(ги), г = 1,...,5 определены и дифференцируемы на Еп. Для учета ограничений типа равенств и неравенств из (5) использована простейшая штрафная функция где gt{w) = max{#(iu);0} при і = 1,...,/, gfip) = МИ І ПРИ « = /+ 1,...,л. Также предполагается, что вместо точных значений градиентов Vw$(v,w), P (w) нам известны их приближения V„,$(v,iu,),P (ty,), зависящие от параметра t 0. Регуляризованные варианты методов (3) и (4) соответственно имеют вид: где vo,t i — любые фиксированные точки из En,A(t) 0, a(t) 0,7(0 0, i(i), 3( ) — параметры методов.

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

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

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

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

Антисимметричные функции, то есть такие, что Функции, представимые в виде суммы: где /1( ),/2(10) — произвольные функции. 3. Матрично-скалярное произведение где а — фиксированная точка из W, G — симметричная положительно определенная матрица. Приведем одно из свойств кососимметричных функций [14]. Лемма 1.1 Пусть функция Ф(г ,го) выпукла и дифференцируема по w, удовлетворяет условию (18). Тогда справедливо неравенство Наряду с условием кососимметричности используется условие сильной кососимметричности: Примером сильно кососимметричной функции может служить матрично-скалярное произведение. Справедлива следующая лемма [43]: Лемма 1.2 Пусть функция Ф(г»,го) выпукла и дифференцируема по w, удовлетворяет условию (20). Тогда справедливо неравенство Далее будут приведены три утверждения [43], описывающие некоторые свойства множества решений задачи равновесного программирования (1). Отметим, что в случае компактности множества W функция Ф(г;, w) порождает непустое экстремальное отображение и исходная задача (1) эквивалентна задаче поиска неподвижной точки экстремального отображения ЇУ(и). Вопрос о существовании такой точки можно решить с помощью теоремы Какутани, а именно, если функция $(v,w) полунепрерывна снизу по v и выпукла по w, множество W — выпуклый компакт, то отображение W(v) всегда имеет неподвижную точку. Однако, условие (20) помогает ослабить требования, налагаемые на множество W, а именно, позволяет избавиться от требования ограниченности этого множества в пространстве Еп.

Пусть множество W выпукло и замкнуто, функция Ф(г,ги) выпукла и непрерывно дифференцируема по w при любом фиксированном v. Тогда задача (1) эквивалентна следующей задаче: найти v» EW : Лемма 1.4 Пусть множество W выпукло и замкнуто, функция Ф(-и,го) выпукла и дифференцируема по w при любом фиксированном v, непрерывна по v при любом фиксированном w, удовлетворяет условию (18), множество решений задачи (1) W непусто. Тогда оно выпукло и замкaнуто. Лемма 1.5 Пусть множество W выпукло и замкнуто, функция Ф(-и,го) выпукла и дифференцируема по w при любом фиксированном v, непрерывна по v при любом фиксированном w, удовлетворяет условию (20). Тогда задача (1) имеет, причем единственное, решение. Хорошо известно, что задача (1) неустойчива к возмущениям исходных данных, и для ее решения приходится привлекать методы решения некорректных задач, в том числе методы регуляризации. Для случая, когда неточно задана только функция Ф(г;,го), СВ. Шпирко [43] был разработан метод кососимметричной регуляризации, заключающийся в следующем: к исходной кососимметричной функции добавляется сильно кососимметричный стабилизатор и рассматривается параметрическое семейство регуляризованных задач: при каждом а 0 Отметим, что предложенный стабилизатор Q(v,w) не удовлетворяет стандартным требованиям, предъявляемым к стабилизаторам [28]. Тем не менее, кососимметрич-ная регуляризация позволяет получить решение равновесной задачи (1). Очевидно, что регуляризованная функция уже является сильно кососимметричной с параметром а. Поэтому, если потребовать непрерывность функции &(v,w) по каждой из переменных, ее выпуклость и дифференцируемость по переменной w, выпуклость и замкнутость множества W, то по лемме 1.5 получаем, что при каждом а решение va задачи (23) существует и единственно. Справедлива следующая теорема [43]: Теорема 1.1 Пусть множество W выпукло и замкнуто, множество решений W задачи (1) непусто, функция Ф(у,ш) непрерывна по совокупности переменных (v,w) на W, выпукла и непрерывно дифференцируема по w при любом фиксированном v из W, удовлетворяет условию кососимметричности (18) на W. Тогда Существование нормального решения следует из леммы 1.4 и теоремы о минимизации сильно выпуклой функции на выпуклом замкнутом множестве [29]. В случае, когда неточно задано само множество W, в диссертации применяется метод штрафов для кососимметричных задач. Рассмотрен такой случай: ищется точка v» из условий Справедлива следующая лемма Лемма 1.6 Пусть Wo — выпуклое замкнутое множество из Еп, функция Ф(г;,ги) непрерывна по переменной v на Wo при каждом фиксированном w из Wo, выпукла и дифференцируема по переменной w на Wo при каждом фиксированном v из Wo, удовлетворяет условию кососимметричности (18), функции 7;(ги), г = 1,...,1 выпуклы и дифференцируемы на Wo, функции gi(w), і = I + 1,..., s аффинны, то есть g%{w) = (a,-, w) — b а,- Є Еп, bi — действительные числа. Также пусть множество W решений задачи (24) непусто. Тогда W — выпуклое и замкнутое множество и задача (24) имеет единственное решение v» (нормальное решение), обладающее свойством г г/, v (Е W .

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

Рассматривается задача равновесного программирования: найти точку г . из условий Wo С En — заданное выпуклое замкнутое множество, функция Ф(г , W) определена на произведении евклидовых пространств Еп х Еп, дифференцируема по го на Еп, функции 7,(го), г = / + 1,... ,s определены и дифференцируемы на Еп. Предполагается, что множество решений W исходной задачи (55) непусто.

Для учета ограничений типа равенств и неравенств в (55) будем пользоваться простейшей штрафной функцией где gf{w) = max{0; gi{w)} при і = 1,...,1-, g?(w) = \g%{w)\ при і = I + 1,..., s. Введем функцию Тихонова где A(t) 0, a(t) 0 — некоторые заданные функции. Градиент функции (57) по переменной го равен где через Vw$(v, w), P (w) обозначены градиенты функций Ф(У, го), P(W) ПО W. Будем предполагать, что вместо точных значений градиентов Vw$(v,w),P (w) нам известны их приближения Vw$(v,w,t), P (w,t) такие, что для любого t О max{ \\V (w,w,t)-V (w,w)\\,\\P (w,t)-Pr(w)\\ } ( )(1 + MI) Vw є Еп, (59) где S(t) 0- некоторая заданная функция. Для решения задачи (55) предлагается следующий непрерывный экстраградиентный метод с переменной метрикой в сочетании с методом штрафов: — приближение точного градиента функции Тихонова, w = Кщ [...] — проекция точки на множество Wo в метрике, задаваемой скалярным произведением {G(v)x,y), G(v) — симметричная положительно определенная матрица, v0 — произвольная точка из Еп. Приведем условия согласования параметров a(t),f(t), S(t), A(t) метода (60) и сформулируем требования к задаче (55), обеспечивающие сходимость траектории v(t) процесса (60) при t — +00 к решению задачи (55). Теорема 1.4 Пусть выполнены следующие условия: 1. WQ — выпуклое замкнутое множество из Еп; множество W, решений задачи (55) непусто; функция Ф(г ,ги) непрерывна по v на Еп при каокдом w из Еп, выпукла и непрерывно дифференцируема по w на Еп при каждом v из Еп, удовлетворяет условию кососимметричности (18) на Wo, функции gi(w), і = 1,...,/ выпуклы и непрерывно дифференцируемы на Еп, функции gi(w), і = I + 1,... ,s аффинны, то есть gi(w) = (a,-,w) — Ь;, а,- Є Еп, 6,- — действительные числа. 2. Существуют положительные постоянные 77,с,-, г = 1,...,4 такие, что где г „ — нормальное решение задачи (55), параметр р штрафной функции (56) удовлетворяет условиям р 1, р п; S. Сужение градиента Vw$(v,w) на диагональ множества Еп х Еп и градиент Р (го) удовлетворяют условию Липшица 4. Вместо точных значений градиентов Vw fr(v,w) и P (w) известны их приближения V (v,w,t) и P (w,t), для которых выполнены условия (59); 5. G(v) — симметричная положительно определенная матрица при любом v из Еп; существуют сильно выпуклая дважды дифференцируемая функция Ф(г ) и положительные константы т, М, т М такие, что 6. Параметры a(t), y(t),8(t),A(t) метода (60) таковы, что aftMiMWeCMOj+oo); 5{t) Є С[0;+оо); a(t),1(t),A(t) 0; 8{t) 0; a(t) — выпуклая функция, a (t) 0; A{t) — вогнутая функция, A (t) 0; Y(t) 0; (при p = n последнее равенство не нужно) Тогда lim (0 + 7(0 + (0+ 7 )=05 lim A(t) = +00; - +oo у a[t) J t-++oo (63) Urn N0-». = 0; Ит 1И )П = 0 (64) где v» — нормальное решение задачи (55), причем сходимость в (64) равномерная относительно выбора Vw$(v,w,t) и P (w,t) из (59). В качестве параметров а(Ь),п((Ь) 8{Ь), A(t), удовлетворяющих условиям теоремы 1.4, можно взять, например, (при p = rj последнее условие не нужно) Доказательство. Воспользуемся характеристическим свойством G—проекции [29, стр. 308] для уравнений метода (60) с учетом определения функции VwTs(v,w, t): Подставим вместо w в первое из этих неравенств точку vT Є Wo — решение задачи (26) при t = т, а во второе — точку v(t) + v(t) Є Wo. Далее для краткости записи будем опускать аргумент t у функций v(t),v(t),u(t). Получим Сложим эти два неравенства: Поскольку vT является репіением задачи (26) при t = т, то, по лемме 1.3 (yw$(vT, vT) + A(T)P (VT) + a(r)vT, w-vT) 0 V Є W0. Подставим в это неравенство в качестве w точку u(t) Є Wo, умножив его на — 7(0 0. Будем иметь

Похожие диссертации на Непрерывные методы решения задач равновесного программирования

Методы решения задач квадратичного программирования в гильбертовых пространствах Ахмедов Фейзулла Гамидулла оглы

Итерационные методы решения задач математического программирования со специальной структуройПудова Марина Владимировна

Разработка и исследование некоторых методов решения задач целочисленного линейного программирования общего и специального видов Ситникова Ольга Дмитриевна

Методы решения двухуровневых задач дискретного монотонного программирования и их применение при оптимизации надежности непоследовательных систем Заславский Владимир Анатольевич

Разработка метода сведения общей задачи нелинейного программирования к задаче безусловной оптимизации и решение задачи оптимизации в нечетких условиях Егоров Юрий Анатольевич

Методы решения некоторых стохастических задач типа затраты-выпуск и линейного программирования Смирнова Валентина Викторовна

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

Исследование некоторых локальных алгоритмов решения квазиблочных задач дискретного программированияЩербина, Олег Александрович

Методы уменьшения размерности задачи бинарного программирования Ахмедов Фирудун Беюкага оглы

Задачи двухуровневого программирования, полиномиально разрешимые методом декомпозицииПлясунов Александр Владимирович