Задачи о дополнительности и обобщенные модели олигополии тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

_ __ /-х <"

Р I и Ь-..

ЦЕНТРАЛЬНЫЙ ЭКОНОМI1КО-МАТЕМАТ11ЧЕС'КIIII ИНСТИТУТ РОССИЙСКОЙ АКАДЕМИИ НАУК

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

КАЛАШНИКОВ Вячеслав Витальевич

ЗАДАЧИ О ДОПОЛНИТЕЛЬНОСТИ И ОБОБЩЕННЫЕ МОДЕЛИ ОЛИГОПОЛИИ

01.01.09 - Математическая кибернетика

Автореферат

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

Москва - 1995

Работа выполнена в Центральном экономико-математическом ш ституте Российской Академии наук

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

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

доктор физико-математических наук Беленький В.З. доктор физико-математических наук Березнев В.А. доктор физико-математических наук Мороз А.И.

Ведущая организация Вычислительный центр Российской Акадс мии наук

Защита состоится «? 4 /?7С /«=> " на заседании

диссертационного совета Д 002.27.02 в ЦЭМИ РАН по адресу: 117418, Москва, ул. Красикова, д. 32, комн. 520

С диссертацией можно ознакомиться в библиотеке ЦЭМИ РАН

Автореферат разослан / т2 «^З/С? /У^<Г

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

Скоков В.А.

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

Актуальность темы. Многие чадами, возникающие к различных властях математики, таких как теория игр, математическое про-раммирование, математическая экономика, могут быть сформули-юваны и следующем унифицированном виде: для заданного отображения / : /?" —> Пп найти вектор х £ такой, что

/(■?') € /?+ и хт/(х) = 0. (1)

Задачу (1) обычно называют задачей о дополнительности, и ее возможным источником явилась теорема Куна-Таккера для пелиней-юго 11]юграммпрона1111я, которая дает необходимые условия оптимальности при выполнении определенных требовании о дифферен-шруемостн целевой функции и ограничений.

За последние 30 лет задача о дополнительности выделилась и самостоятельную ветвь теории оптимизации, находящуюся на пере-ечепни нескольких областей фундаментальной математики (таких сак теория неподвижных точек, теория топологической степени отображения, вариационных неравенств, линейного и нелинейного анализа и др.) и некоторых разделов прикладной математики (теория п р, математическая экономика, механика, оптимальное управление I т.д.). В основном, теория дополнительности ассоциируется с изучением состояний равновесия, возникающих в физических, инже-Н'рмых п экономических моделях. В настоящее время изучаются »азличные типы задач о дополнительности: явная, неявная, общая «адачн на конусе, задача на решетке и т.д. Каждая из этих задач рассматривается в различных аспектах, начиная с вопросов существования и единственности решения и кончая численными методами нахождения решений.

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

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

Научная новизна. Все основные результаты диссертации являют ся новыми и заключаются в следующем:

- предложен и обоснован новый подход к получению достаточ ных условий существования решения в задачах о дополнительност] различных типов;

- в качестве техники в этом подходе использована теория то по логической степени непрерывного отображения;

- с помощью указанного подхода получены новые достаточ ные условия существования решения в задачах о дополнительности

- обосновано новое направление формирования однопродук товых моделей олигополии с использованием гипотез участников о( изменении общего объема рынка в зависимости от изменения вы пуска самого участника. Эти гипотезы названы коэффициентам 1 влияния участников;

- доказаны теоремы существования и единственности состояния равновесия в обобщенной таким образом модели Курно;

- осуществлено сравнение равновесных объемов рынка в моделях Курно и Штакельберга в случае, когда один из участников модели Курно становится лидером рынка;

- путем построения подходящих коэффициентов влияния для участников-лидеров на уровне условий первого порядка осуществлено вложение обобщенной модели Штакельберга с несколькими лидерами в рамки обобщенной же модели Курно;

- для численного нахождения состояния равновесия в обобщенной модели Курно предложен и обоснован численный метод, сочетающий шаги ньютоновского типа с делением пополам;

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

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

Апробация работы. Материалы диссертационной работы регулярно докладывались и обсуждались в Центральном экономико-математическом институте РАН на семинарах лаборатории теории

I

и численных методов для задач оптимизации, а также на семинарах лабораторий Вычислительного центра РАН (г. Москва), Института математики Сибирского отделения РАН (г. Новосибирск), Линчёпипгского университета (г. Линчёпинг, Швеция). Кроме того, основные результаты диссертации докладывались на XIV и XV Международных симпозиумах по математическому программированию (Амстердам, 1991, и Анн Арбор, США, 1994), Днях Оптимизации в Монреале, Канада, в 1994 и 1995 гг., 10, 11 и 12 Симпозиумах "Системы программного обеспечения решения задач оптимального планирования" (г. Нарва-Йыэсуу, 1988 и 1992 гг., г. Кострома, 1990 г.), VI научной конференции "Методы математического программирования и программное обеспечение" (Свердловск, 1989 г.), конференциях "Математическое программирование и приложения" (Екатеринбург, 1991, 1993 и 1995 гг.), симпозиуме "Вопросы оптимизации вычислений" (Киев, 1993 г.), Сибирской конференции по прикладной и промышленной математике (Новосибирск, 1994 г.).

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

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

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

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

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

Так, в п. 1.2.1 рассматривается общая задача о дополнительности. Пусть К С Rn — заостренный выпуклый замкнутый конус с вершиной в начале координат (при этом является частным случаем такого конуса). Следовательно, общая задача о дополнительности для отображения / : К —» R" состоит в нахождении вектора х £ К такого, что

f(x)eic и xTJ(x) = 0; (2)

здесь К* ={i6 Rn | хту >0 Vy 6 К} — двойственный конус множества К. Сначала вводится понятие исключительного семейства точек.

Определение 1. Множество точек {zr}r>0 С К называется исключительным семейством (ИС) относительно конуса К для отображения /, если ||zr|| —» +оо при г —► +оо,' и для всякого г > 0 найдется число цг > 0 такое, что вектор sr = f(zr) + /trzr является нормалью опорной гиперплоскости к конусу К в точке zr. Последнее, как известно, означает, что

Sjfz >0 Vz <= К, s^Zr = 0.

Теорема 1. Для всякого непрерывного отображения, / : А' —> 7?" существует либо решение задачи (2), либо исключительное семейство точек.

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

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

Теорема 2. Пусть f : К R" — непрерывное отображение, С С К ограниченное подмножество такое, что уТf(y) > 0 Vy 6 К\С. Тогда задача{2) имеет решение. Если для каждого у £ К \С имеет место строгое неравенство уТf{y) > 0, то осе решения задачи (2) лежат в множестве С.

Следствие 1. Пусть / : К —» R" — непрерывное отображение, С С К — ограниченное подмножество такое, что f(y) £ К* My £ К\С. Тогда задача (2) имеет решение. Если для каждого у £ К\С имеет место более сильное включение f(y) £ int. К* и 0 £ С, то все решения, задачи (2) лежат в множестве С.

Рассмотрим компактное подмножество С С К, звездное относительно нуля, т.р. с каждой точкой х оно содержит о трезок [0, .г]. Тогда корректно определена функция г/(.т), которая каждому х £ К, х ф 0 ставит в соотвествие наиболее удаленную от начала координат точку множества С, лежащую на луче, проходящем через 0 и точку х. Границу множества С относительно К обозначим символом Г.

Теорема 3. Пусть / : К —► Rn — непрерывное отображение, а непустое множество С С К компактно и звездно относительно нуля. Если при этом функция т](х) непрерывна, т](х) ф 0 и утf (у) > О для любых у = т](х), х £ К \ {0}, то задача (2) имеет решение в множестве С.

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

Теорема 4. Пусть / : К —» Я" — непрерывное отображение непустое множество С С К компактно и звездно относительт начала координат, и 0 ^ Г. Если при этом уТ/(у) > 0 для любыз, точек относительной границы Г, то задача (2) имеет решение < множестве С.

В пункте 1.3 все аналогичные теоремы об альтернативе и достаточные признаки существования решения сформулированы для стандартной задачи о Дополнительности (1), в которой К = Я". Заметим, что в данном случае К* совпадает с Л" и условие /(х) 6 К* означает просто, что /(.т) > 0, а условие нормальности к опорной гиперплоскости легко расшифровывается в следующем определении исключительного семейства.

Определение 2. Семейство точек {жг}г>о С Л" называется исключительным, если ||:гг|| —» +оо при г —► +оо, и для всех г > О справедливы соотношения:

здесь Аг > 0 — некоторый скаляр.

Следующие две теоремы являются следствиями теорем 1 и 2, соответственно.

Теорема 5. Для всякого непрерывного отображения / : Л'^ —> Л" существует либо решение задачи (1), либо исключительное семейство точек.

Теорема 6. Пусть / : Я" —> Лп — непрерывное отображение, С С Я" — ограниченное подмножество такое, что хТ/(х) > 0 Ух 6 Л" \С. Тогда задача (1) имеет решение. Если для каждого х (Е Л" \ С имеет место строгое неравенство хТ/(х) > 0, то все решения задачи (1), лежат в множестве С.

если х\ > 0; если хг; = 0:

Следствие 1 влечет следующее утверждение.

Следствие 2. Пусть / : Я" —► Я" — непрерывное отображение, С С Я" - ограниченное подмножество такое, что /(.г) > 0 У.г € 7?" \С. Тогда задача (1) имеет решение. Если для каждого х 6 Я" \С имеет место строгое неравенство /(х) > О и О £ С, то все решения задачи (1) лежат в множестве С.

Из определения 2 исключительного семейства вытекает, что выполнение неравенства > 0 хотя бы для одного индекса г = 1,...,г? несовместимо с принадлежностью вектора х к такому семейству. Следовательно, теорема б может быть усилена следующим образом.

Теорема 7. Пусть / : Я" Д" — непрерывное отображение, а С С Я" - - непустое ограниченное подмножество такое, что для всякого х £ 1?'_1 \ С выполнено неравенство л:,•/,•(ж) > 0 хотя бы для одного индекса г = 1,..., п. Тогда существует решение задачи (3), и все решения содержатся в множестве С.

Пример 1. Пусть отображение / : Я2 —> Я2 имеет компоненты

/\{Х1,Х2) = Х1+Х2-1, Ь(х\,Х2) = 1 - Х\х2.

Выбрав в качестве множества С единичный квадрат {(ж^зтг) | 0 < .г, <1, г = 1,2}, убеждаемся в силу теоремы 7 в существовании решения задачи (3), лежащего в множестве С (таким решением, в частности, является точка х* = (1; 0)). В то же время теорема 6 не может в данном случае гарантировать существование решения. Действительно, нетрудно убедиться, что скалярное произведение (у—х)Т/(х) может принимать положительные значения на достаточно больших по норме векторах х, каковы бы ни были векторы у из произвольного ограниченного подмножества С С Я™.

Рассмотрим снова компактное подмножество С С Я", звездное относительно нуля. Из теоремы 7 вытекает следующее утверждение.

Следствие 3. Пусть / : Я" —► Я" - непрерывное отображение, а непустое множество С С Я!? компактно и звездно относительно

нуля. Если при этом функция Т}{х) непрерывна, т](х) ф 0 и yifi(y) > С хотя бы для одного i = 1,..., п для каждого у = г](х), х £ RJ\_ \ {0}. то задача (1) имеет решение в множестве С.

С помощью теоремы 4 предыдущий результат распространяется на случай разрывной функции Т].

Следствие 4. Пусть f : i?" —» Rn — непрерывное отображение, а непустое множество С С R+ компактно, звездно относительно нуля и 0 £ Г. Если при этом ytfi(y) > 0 хотя бы для одного i = 1,...,п для каждого у = т}(х), х 6 Я" \ {0}, то задача (1) имеет решение в множестве С.

В п. 1.4 рассматривается неявная задача о дополнительности, и для нее также вводится понятие исключительного семейства. Пусть К — выпуклый замкнутый острый конус в Rn с вершиной в начале координат, a f,g : R" -г> R" — непрерывные отображения. Рассмотрим неявную задачу о дополнительности на конусе: найти вектор х Е R" такой, что

9(®)eJf, f(x)Tg(x)= 0. (3)

Ясно, что в случае, когда функция / определена на неотрицательном ортанте Я", а функция g совпадает с тождественным отображением, т.е. д(х) = х Vx £ i?", задача (3) представляет собой стандартную задачу о дополнительности.

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

Определение 3. Назовем множество точек {яг}г>0 С R" исключительным семейством (ИС) для пары / и д относительно конуса К, если во-первых, ||хг|| —+ -foo при г —+ +оо, а во-вторых, для всякого г > 0 выполнено д(хг) € К и найдется скаляр \ir > 0 такой что вектор sr = f(xr) + /irg(xr) является нормалью к опорной гиперплоскости к конусу К в точке д(хг).

Теорема 8. Пусть отображения f,g : R" —> Rn непрерывны, а точка h £ Rn является единственным решением уравнения д(х) = 0. Кроме того, пусть g гомеоморфно отображает некоторую окрестность (в евклидовой топологии) точки Ь на некоторую окрестность нуля. Тогда существует либо решение задачи (3), либо исключительное семейство для пары fug.

Далее мы ограничимся рассмотрением частного случая гзадачи (3), когда в качестве конуса К выбран неотрицательный ортант R". Неявная задача о дополнительности тогда принимает вид: для заданных отображений f,g:Rn—+R" найти точку х G R" такую, что

д{.г)>0, /(*)> 0, f(x)Tg(x) = 0. (4)

Определение исключительного семейства точек тогда принимает следующую форму.

Определение 4. Назовем множество точек {хг}г>0 С Rn исключительным семейством (ИС) для пары / и д, если во-первых, ||:гг|| —* -foo при г —► +оо, а во-вторых, для всякого г > 0 выполнено д(хг) > 0 и найдется скаляр fir > 0 такой что для i = 1,..., п

f( r)i= если > 0; ТЛ ' 1 > 0, если д{(хг) = 0.

Тео]>ема 8 позволяет получить новые признаки существования решения задачи (4). Рассмотрим случай обобщенной монотонности отображения / относительно д.

Теорема 9. Пусть отображения f,g : R" —> R" непрерывны и удовлетворяют условиям теоремы 8. Кроме того, пусть ||д(ж)|| —» -foo при ||:с|| —> -foo, и существует функция (р : [0,-foo) —► [0,-foo) с условием

t lin^ <p{t) = -foo, (fi{t) >0 Vt > 0,

и такая, что

Ш - g(y)]T[f(x) - f(y)] > \\g(x) - $(у)|И||ф) - g(y)||),

Уж, у € Rn. Тогда существует решение задачи (4) с отображениями fug.

Следующие утверждения аналогичны теоремам б и 7, соответ ственно.

Теорема 10. Пусть /, д : Я" —+ Я" удовлетворяют условиям теоремы 8, а С С Яп — ограниченное подмножество такое, чт> для любых х ^ С либо /(я)Тд(х) > 0, либо не выполнено неравенствI д(х) > 0. Тогда задача (4) имеет решение. Если же для любых х £ С либо Лх)Тд(х) > 0, либо не выполнено д{х) > 0, то все решени: задачи (4) лежат в множестве С.

Теорема 11. Пусть /, д : В," —► Я" удовлетворяют условиял теоремы 8, а С С Яп — непустое ограниченное подмножество та кое, что для любых х £ С либо <7,(ж)/,(я) > 0 хотя бы для одног( г = 1,... ,тг, либо не выполнено неравенство д(х) > 0. Тогда задаче (4) имеет решение, и при этом все решения лежат в множеств< С.

Напомним, что замкнутое множество С С Я" мы называем звезд ным относительно точки Ь, если оно обладает следующим свойством вместе со всякой точкой х оно содержит отрезок [Ь, х\. Снова можне корректно определить функцию г](х), которая каждой точке х ф I ставит в соответствие наиболее удаленную от Ь точку множества С на луче, проходящем через Ъ и х.

Теорема 12. Пусть /,<7 : Яп —+ Яп удовлетворяют условиям теоремы 8, а непустое компактное множество С С Я" является звездным относительно точки Ь. Если при этом для любого х £ Яп\ {6} и у — Т)(х) либо <Л'(у)/|(у) > 0 хотя бы для одного г = 1,..., п, либс не выполнено д(у) > 0, то задача (4) имеет решение в множестве С.

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

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

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

Пусть имеются п фирм-производителей однородного продукта, текущие объемы производства котоых будем обозначать через д,-, а функции затрат — через /,-(д,-), г = 1,...,п. Символом С обозначим общий объем сделок на рынке, а формулой — обратную функцию спроса, т.е. цену, складывающуюся на рынке при общем объеме сделок С. Мы будем допускать наличие постоянных внешних поставок в объеме <3- Таким образом, по определению для нашего рынка должно выполняться равенство (7 = + Ед;-

Предположим, что производители вместо стандартной гипотезы модели Курно пользуются гипотезами более общего вида:

где г/ — предполагаемый объем поставок г-го производителя, а С,(ту) — ожидаемый г-м производителем объем сделок в ответ на изменение его собственных поставок с д,- па г/. Стандартная модель Курно получается, если ш,г(С,д,) = «¿/"(С?, д,-) = 1 при любых г и (3. Здесь и в дальнейшем для сокращения записи опускается явное указание зависимости С,(г/) также и от С и q^. Поведение каждого участника определяется текущим состоянием (С, д,) и гипотезой (5). Именно, для его объема производства г/ предполагаемая прибыль выразится

1 > Чи

V < д.-,

(5)

формулой

т{г1) = т1р{сы)-т, (6)

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

В дальнейшем использованы следующие предположения о функциях /;, wf и р.

AI. Каждая из функций /,■((/,■) определена для д, > 0, непрерывно дифференцируемая, неубывающая и выпуклая.

А2. Обратная функция спроса p(G) непрерывно дифференцируемая, определена для положительных G, положительная, и p'(G) < О при всех G.

A3. При каждом i существует Я, > 0, для которого /-(Я,) = р(Н,).

A4. Для каждого г функции wf(G, qi) определены для G > д, > О, и произведения qiwf{G,qi) не убывают по д,-. Кроме того, в каждой точке (G,qi) > 0 функция wf(G, Qi) полунепрерывна сверху по G и непрерывна справа по qi, функция wJ~(G,qi) полунепрерывна снизу поСи непрерывна слева по д,, при этом имеют место соотношения

О < w;(G, qi) < w+(G, Qi), wf{G, G) = 1.

Определим функции

оЦС, 4i) = qiwf(G, gi)/G, ar(G, qx) = qiWr(G, q,)/G

и заметим, что ввиду монотонности по д,- и неотрицательности их можно доопределить в точках (G, 0) как предельные значения:

ot(G,0)= lim at(G,qi), <rr(G,0)= lim ar(G,g,).

Функции ot(G,qi) имеют ясный экономический смысл. Именно, af{G,qi) при гипотезе (5) дает предполагаемую г-м участником в состоянии (G, qi) эластичность объема рынка по собственному объему д,- при его возрастании. Аналогично трактуется af(G, д,) при убывании объема q{. В терминах эластичностей предположение A4 можно переформулировать в следующей форме.

А4'. Для каждого г функции гт^С, определены для б" > О, ^ > <И > 0 11 ие Убывают по д,. Кроме того, для д,- > 0 функция полунепрерывна сверху по С и непрерывна справа по <7,-, функция <7,Г(С, д,) полунепрерывна снизу по С и непрерывна слева но 17,, и при этом имеют место соотношения

О < < о?(С,д{) < о?(С, С) = 1.

А5 (принцип потенциального участия). Для некоторого к существуют такие Со > 0 и <70* > 0, что при (7 < выполнено неравенство

Р(С) + р'(С)С - Л(д0к) > 0.

А6. Функция вогнута по С?.

Принцип А5 означает, что при достаточно малых С > 0 (и следовательно, достаточно больших р) хотя бы один из участников стремится объем своего производства увеличить сверх доь

Используя теперь условия первого порядка для экстремума функции предполагаемой прибыли каждого участника, мы сформулируем задачу о поиске состояния равновесия следующим образом: при заданном ф > 0 найти неотрицательный набор = (С?, дь ■ • • -,Чп) такой, что (7 > 0, выполнено балансовое равенство

+ д = (7)

при каждом 1

/ДО, Чг) = р(С) + <ДО, (<?)<?.- Ш < 0, (8)

и если гц > 0, то

цг(в, яд = р(С) + аГ(С, д{)р'(С)С - Ш > 0. (9)

Отметим, что в случае <7+(С,д,-) = г/,-) для участника с д,- > 0

неравенства (8) и (9) эквивалентны одному равенству.

Чтобы иметь право решение задачи (8)-(9) трактовать как равновесие для участников с д,- > 0, показана вогнутость функции предполагаемой прибыли (6). Также доказано, что при выполнении условий (8)-(9) участник с нулевым объемом д, = 0 не стремится производить.

В пункте 2.2 доказана следующая теорема существования.

Теорема 13, Пусть ф > 0 и выполнены предположения А1 -А4. Тогда существует решение задачи (7)-(9). Если дополнительно выполнено условие А5, то решение существует и при <5 = 0.

Вопрос о единственности состояния равновесия, изученный в пункте 2.3, можно разделить на две части. Во-первых, с общемодельной точки зрения интересна единственность равновесного общего объема рынка С. В основном этому и посвящен раздел 2.3. Во-вторых, данный равновесный объем рынка в принципе может в состоянии равновесия по-разному распределяться между отдельными производителями. Это уже связано с единственностью решений локальных задач (7)-(9) и обсуждается кратко в конце раздела.

Для изучения вопроса о единственности решения задачи (7)-(9) мы сохраним предположения А1 - Аб и добавим следующее.

А7. Для каждого г при 0 < С\ < бг, 0 < 6 < 1 выполнено соотношение

(10)

— С

Кроме того, (С?,д,) < если 0 < д, < (7.

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

Определение 5. Состояние равновесия Z{Q) = [С(<Э),д1(<5),..., д„(ф)] назовем немонопольным, если д,- < (?, г = 1,..., п.

Теорема 14. При условиях А1 - А7 и любом >0 общий объем для немонопольного состояния равновесия определяется однозначно.

Если С} > 0. то любое состояние равновесия не монопольно. Следовательно. в этом случае равновесный объем С(б^), согласно теореме 14, определяется однозначно. Если же = 0, то вообще говоря, в одной задаче возможно существование и монопольного, и немопо-польного равновесий с разными объемами (например, такое возможно, если функции /,- и кусочно линейны).

Следствие 5. Если в условиях теоремы 14 предположить дополнительно, что для каждого г либо /,• строго выпукла, либо для всякого С > 0 из 0 < <7/ < <7? < С вытекает неравенство

етДОд/) <<тГ(С,д?),

то не только равновесный обяем но и весь равновесный набор

единствен.

В пункте 2.4 подробнее изучен частный случай, когда функции /, и р дважды непрерывно дифференцируемы, а функции «>/" и ?/>,г имеют вид

£

'"ПС, ?.•) = "ДО- ?,•) = в,- + а,—, о < <7, < в, (11)

И

ш-(С,С) = а, + а;, = 1. (12)

Здесь 0 < а, < 1, 0 < пг < 1 — а,-. Условие Аб в случае дважды дифференцируемой р сводится к выполнению неравенства

2;/(<?) + <0, УС > 0. (13)

Случай п,- = 0 соответствует постоянству эластичности прогнозируемого изменения общего объема С в зависимости от изменения ОБусловил, гарантирующие существование решения задачи (7)-(9), кото])ые приведены в разделах 2.1 и 2.2, допускают разрывы первого рода для функций и>{, а также не требуют определения функции р(С) в точке С = 0. В частности, значения функции р(С) могут неограниченно возрастать при стремлении С? к нулю. С другой стороны, в этих условиях оговорена выпуклость функций /,-. В пункте 2.6,

потребовав непрерывной дифференцируемости функции р вплоть до нуля, ее невозрастания, а также непрерывности функций мы применяем результаты главы 1 к задаче (7)-(9) и получаем достаточные условия существования решения в ней без требования выпуклости функций /,-.

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

В п. 3.1 обобщенная задача Штакельберга (для модели с несколькими лидерами) вкладывается в схему обобщенной модели Курно путем построения соответствующих коэффициентов влияния «/¿(С, д,) для лидеров. В классической модели Штакельберга один из субъектов учитывает реакцию остальных участников рынка на изменение его объема поставок и выбором этого объема максимизирует свою прибыль. Такой участник часто называется лидером рынка. Ниже рассматривается случай, когда таких лидеров несколько, а остальные (ведомые) субъекты ведут себя согласно модели раздела 2.4. Обобщенную модель Штакельберга мы вкладываем в общую схему на уровне условий первого порядка, т.е. ищем такое состояние, при котором функции прибыли лидеров имеют стационарную точку. К сожалению, в рамках данной работы исследовать эти стационарные точки на предмет выполнения условий второго порядка не удается. Поэтому мы будем говорить в дальнейшем не о состояниях равновесия обобщенной модели Штакельберга, а о стационарных состояниях.

Пусть первые в субъектов (1 < в < п) относятся к категории лидеров, т.е. в своем прогнозе учитывают реакцию остальных (п — «) участников на изменение их совокупного объема производ-

5

ства <5 = д,-, но друг относительно друга действуют как участники классической модели Курно, т.е. считают, что остальные лидеры не изменяют объем производства. Наконец, последние (п — в) субъектов применяют рассмотренную выше тактику с внешними поставками С}

и функциями + , j = .9 + 1,..., п, определенными формула-

ми (11) (12). Классическая модель Штакельберга получается, если .9 = 1, nj = 1, О) — 0, 2 = 2,..., п. В силу А1-А8 для любого р > О решение задачи (7)-(9) = [С?(<5), д8+1(<3),. .., <7„(<Э)] существует,

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

Для того чтобы вложить обобщенную модель Штакельберга в общую схему, нужно определить функции ги* и ш,г для г = Сделаем что следующим образом. Для 0 < д,- < С}{С) положим

«'Г(С,7,) =--= и~ (в),

,7=*-Н

«./■(С, <Ь) =-^-=

1- Е +

При этом в точках непрерывности функции и~ и и+ совпадают. В точках же разрыва функция и-(С?) непрерывна слева, а и+(С) — справа. Это обеспечивает выполнение условия А4. Для применения теоремы 13 нужно формально доопределить функции для

г = 1.....я при всех значениях (7 > О, 0 < <7, < ,(7 с соблюдением

условия А4. Это удается сделать в разделе 3.1, который завершается формулировкой следующей теоремы.

Теорема 15. Пусть выполнены условия А1-АЗ, А5, Аб, А8, и для участников с номерами j = я + 1,... ,п функции (¡¡) определе-

ны равенствами (11)-(12). Тогда обобщенная модель Штакельберга имеет стационарное состояние.

В п. 3.2 производится сравнение равновесных объемов производства для обобщенной модели Курно и классической модели Штакельберга (с одним лидером), т.е. модели с 5 = 1. В этом случае 71 = и лидер решает задачу максимизации своей ожидаемой прибыли

тах{т (<?) = р (ОД)) д - Л (Я) | <9 > 0}, (14)

располагая ценой p(G(Q)) как функцией своего объема поставок Q.

Здесь G(Q) = Q+ £ qj{Q), где ¡£ qj(Q) — равновесный совокупный j=2 j=2

объем производства участников с номерами j = 2,...,п, которые решают задачу (7)-(9) с внешними поставками Q и коэффициентами влияния wf, определенными равенствами (11)—(12).

В п. 3.2 установлены соотношения между Q* — решением задачи (14), и Q - равновесным объемом поставок в случае, если первый участник, как и остальные, пользуется гипотезами вида (11)—(12) для j — 1. Кроме того, интерес представляет сравнение этих величин с Q — объемом производства лидера в ситуации, когда он при максимизации своей прибыли игнорирует изменение цены товара, т.е. решает задачу о дополнительности: найти Q > 0 такое, что

ß\(Q) = f[{Q) ~ Р (G(Q)) >0, Q ■ ß\(Q) = 0.

Теорема 16. Пусть выполнены предположения А1-А8. Тогда

max {Q;Q* }<Q< #i, (15)

где Н\ >0 — величина из условия A3, т.е. такая, что f[(H\) = р(Нх).

Отметим, что операция взятия максимума из двух величин Q и Q* в оценке (15) существенна. Дело в том, что в отличие от работы,1 в которой установлена оценка Q < Q*, принятое здесь более слабое условие (13) на обратную функцию спроса p{G) не позволяет в общем случае получить эту оценку. Более того, возможны случаи, когда лидерство слабого (в некотором смысле) участника приведет к снижению его (а значит, и общего) объема выпуска продукта. Далее мы рассмотрим частный случай нашей задачи, в котором дополнительные предположения о функциях цены р и затрат /,• позволяют доказать строгую вогнутость функции прибыли лидера Ц\(Q). При этом становится возможным выяснить соотношение между Q и Q*, используя лишь локальную информацию.

'Sherali H.D., Soyster A.L. and Murphy F.H. Stackelberg -Nash- Cournot equilibria: characterizations and computations // Operations Research. - 1983.- Vol. 31, N. 2. - P. 253-276.

Именно, предположим, что функция р трижды дифференцируема

и удовлетворяет условиям

'>• ••

для любых С > 0. Кроме того, будем предполагать, что функции затрат участников линейны, т.е. /¿(ф) = г = 1,...,тг. Тогда классификация случаев становится полной и вытекает из локальных правил:

(0 если С(<?+0) > 1, аС'(Р-О) < 1, то С}* = <3, в (С}*) = = С;

(¿0 если С(<?+0) < 1, то <2* > <5, ОД*) > ОД) = 6; (Ш) если С(д-О) > 1, то С}* < <5, ОД*) < ОД) = д. Так, например, если п = 2 и ^(б) < 0, то <3* > п следовательно, ОД*) > Если же < 0, а ц'2{6) > 0, то ф* < <3, и значит,

С(<3*) < (т.е. если в ситуации равновесия по Курно второй

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

В п. 3.3 представлен численный метод для решения задачи (14), изученной в предыдущем параграфе. Для этого сначала фиксируется' <3 > 0 и рассматривается динамическая система, задаваемая дифференциальным уравнением

с = + £ д,(<з) = т(с), с(о) = д; (16)

тс.)

здесь д;(б) — решение задачи:

т > 0, ¥>,-(£, яд = ш - амрЧв) - о{Ср'{С) - р(С) > 0,

<И*р(<3, д,-) = о,

а 1{С) = {1 < г < п : д,(<?) > 0. Показано, что решение б = С((д) уравнения (7) является устойчивой стационарной точкой динамической системы (16). Интегрирование системы (16) может быть осуществлено в рамках итерационного процесса

( вм = С* - [С* - 3 - Е д,•(<?*)] , к = 0,1,2,..., ( . \с° = д, , 8ь > 0. 110

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

можно ожидать локальную линейную сходимость последовательности С*, порожденной процессом (17), к (5 = (*(<5) сверху.

Наконец, оптимальный объем производства С} внешнего поставщика (лидера) возможно определять с помощью методов одномерной максимизации его функции прибыли

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

Пусть X — непустое замкнутое выпуклое подмножество в Я", а С — непрерывное отображение из X в Я". Предположим, что С псевдомонотонно на X, т.е. для любых х, у (Е X

где т^ ) означает внутренность множества. Здесь 0+Х — рецессивный конус множества X, т.е. множество всех таких направлений в £ -К", что X + в С X, а С* — двойственный конус для С С Л", т.е.

Таким образом, условие (18) означает, что вектор С(аг°) лежит во внутренности двойственного конуса для рецессивного конуса множества X.

к = 0,1,...,

(х - y)TG{y) > 0 влечет (х - y)rG(x) > 0, и существует вектор х° 6 X такой что

G(x°) 6 int (0+JT)*,

(18)

С* = {у G Я" | угх >0 Ух € С}.

При выполнении жох указанных выше условии имеет место следующий результат.

Теорема 17. Вариационное неравенство, в котором требуется найти такоИ вектор л £ X, что

(х - >0 УхеХ^ (19)

имеет непустое компактное выпуклое множество решений.

Предположим далее, что множество 2 решений задачи (19) состоит более чем из одной точки, и рассмотрим следующее вариационное неравенсто: найти вектор такой, что

(л - г*)т^(г*) >0 V* 6 Я, (20)

где Р: ЛЛ —► Я" — непрерывное и строго монотонное на X отображение, т.е. (.г - у)Л[Р(х) — F(y)] > 0 Ух, у Е X, х ф у. В этом случае показанные выше выпуклость и компактность множества 2 гарантируют существование единственного (в силу строгой монотонности F) решения задачи (20).

Будем называть задачу (19), (20) двухуровневым вариационным неравенством (ДВН) и рассмотрим следующий алгоритм ее решения, не требующий явного описания множества 2. Именно, изучим одноуровневое вариационное неравенство с параметром: для фиксированного с > 0 найти х£ £ X, удовлетворяющее требованию

(х - .ге)т[С(:г£) + еПхе)} >0 V г е X. (21)

Оказывается, если предположение о псевдомонотонности оператора С заменить условием его монотонности, т.е.

(х-у)Т[С(х)-С(у)}> о Ух,уеХ,

а предположения о непрерывности ^ и С, строгой монотонности Г и условие (18) оставить без изменений, то имеет место следующее утверждение.

Теорема 18. Для всякого достаточно малого е > 0 задача (21) имеет единственное решение хе, и последние сходятся к решению г* задачи (19), (20) при е —► 0.

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

Наконец, в п. 3.6 представлена схема оптимального управления точностью в двухуровневом итерационном процессе. Многие численные методы сводятся к итерационному процессу вида

¿ = 0,1,..., (22)

хе,Х(+1 € /?т, обладающему скоростью сходимости порядка 1 + а, а 6 (0,1], где для практического построения в свою очередь, применяется итерационный процесс

г, = Ф(г8_1,а;г), 5=1,2,...,

го -

называемый внутренним. Процесс (23), вообще говоря, требует бесконечного числа итераций, т.е. х.(+\ = 1ипг8. Поэтому чаще всего задача отыскания Х(+\ по известному Х( решается неточно, и процесс

(23) заменяется на такой, в котором выполнены соотношения

||а*+1 - ФЫ|| < 7ь ,¿ = 0,1,... (24)

где л > 0 — некоторый управляющий параметр, определяющий точность выполнения (¿+1)-го шага. Как правило, эта величина должна уменьшаться по мере приближения к решению, но слишком медленное или слишком быстрое ее стремление к нулю нежелательны, гак как они влекут увеличение суммарной трудоемкости процесса. Отсюда естественным образом возникает важная задача оптимального (в некотором смысле) выбора значения управляющего параметра 7* на каждом шаге.

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

(24) глобально сходится с линейной скоростью, а в некоторой окрестности V точки х* — неподвижной точки отображения Ф, — эта сходимость имеет порядок 1 + ас0<а<1 (например, квадратичная при а = 1). Другими словами, найдутся числа 0<р<1иТ>>0,

зависящие, вообще говоря, от начального приближения .г", такие, что

||.г* - Ф(.г,)|| < min {р, V\\xt - х*\\"} • 11^ - ( = 0,1,...

Далее, предположим, что внутренний процесс сходится линейно, т.е. для всех £ имеет место оценка

где UJ Е (0,1). В этих условиях показано [6], что задача выбора последовательности параметров {7/}, определяющих в (24) точность выполнения внутреннего шага, может быть поставлена в форме

"¿(ln^L + ß)—> inf, (25)

1=0 \ 7» / Т6Г'

где i]о > 0 -- оценка начальной погрешности внешнего процесса (24), В > 1п(1 4- р) — некоторая константа, a Ti — совокупность последовательностей таких» Т1ТО) во-первых, 7/ —* 0 при I —► оо, и во-вторых, последовательность определяемая соотношениями

е < ц( = min {р, Vrft_,} • + уе_и ( = 1,2,..., п - 1, ?/„ = min{p;Vrft_x} • r/„_i + 7„_i < e, является убывающей. Здесь е > 0 — заранее заданная точность, при. достижении которой процесс закапчивается.

В работе автора [б] решается задача (25) минимизации суммарной трудоемкости, и на основе ее решения вырабатываются правила выбора оптимального значения уе на (( + 1)-м шаге процесса (22). Именно, если текущая погрешность тц > 0 удовлетворяет неравенству т]е > (p/V)1/", то в качестве j( следует взять число je = pfott, где ío > 0 — единственный положительный корень уравнения

' е1п£ = 1пр+(1 + 0Ц1+0 + Я*- (26)

Если же имеет место соотношение гц < (р/Т>)^а, то в качестве уе рекомендуется выбрать величину y¿ = ^Т>т}\+а, где > 0 — единственный положительный корень уравнения

In (V"'4l) +(lnp(() + (1 + f а)( = 0. (27)

Здесь функция р(£) определяется формулой

ОО 1

р( 0 = П 1 + + (28)

Важным свойством этой методики является тот факт, что величина управляющего параметра уе, £ — 0,1,..., зависит в явном виде лишь от величины щ погрешности (( + 1)-го шага итерационного процесса (24) и не зависит от того, какую точность е мы хотим достичь. Это обстоятельство обусловливает эффективность использования предложенного метода управления двухуровневым итерационным процессом в вычислительной практике.

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

В п. 4.1 представлен метод ньютоновского типа для расчета состояния равновесия в обобщенной модели Курно. Пусть имеются п фирм-производителей однородного продукта и один его внешний поставщик. Будем обозначать через q¡ объем выпуска г-й фирмы, а через <9 > 0 — объем внешних поставок. Тогда суммарный объем (7 продукта выразится формулой (3 = С? + Рассмо-

трим случай, в котором участники имеют линейные функции затрат /,•(?,■) = с,д,-, с,- > 0,г = 1 ,...,п, а обратная функция спроса р = р(С) дважды дифференцируема, имеет отрицательную первую и положительную вторую производную при всех С? > 0. Кроме того, предположим, что р(б) —► 0 при С? —* + оо, вторая производная р" удовлетворяет условию Липшица на всяком замкнутом отрезке [а, Ь], Ь > а > 0, а функция р{С)С вогнута по б.

В этом пункте, как и в 2.4, мы рассмотрим модель, в Которой функция 1и1(С,д{) линейна по (7 и </,-. Точнее, равновесием в этой модели может быть вектор ((3, ..., д„) с (3 > 0 такой, что выполнен баланс

с = я + (29)

и для всякого ? = 1,..., п число д,- > 0 решает задачу о дополнительности

т) = а - ам'(С) - о&р'(С) - Р(С) > о, (30)

и

= 0. (31)

Как было показано в п. 2.4, если выполнены все вышеуказанные условия на функцию р((т), а параметры а,-, ^ удовлетворяют соотношениям а,- >0, 0 < а, < 1, и «¿Ч-с,- < 1, то решение задачи (29)-(31) существует и единственно.

В этом пункте исследован численный метод, идея которого состоит в следующем. При каждом значении С > 0 участник г выбирает оптимальный (согласно его гипотезе о реакции рынка) объем производства щ — (¡¡{С) как единственное (в силу свойств функции р и положительности параметра «,) решение задачи (30)-(31). Это решение выр;>жается явной формулой

д^в) = тах|0,- , -—К г = 1 ,...,п.

I ещр (С) >

Тогда задача (29)-(31) сводится к нахождению неподвижной точки отображения Е <ц{С) 4- т.е. решения (7* скалярного уравнения

F(G) = G-Q- £ д{(С) = 0, (32)

<е/(С)

где 1(С) = {?' : д¡(С) > 0}. Условия на функцию р(С) обеспечивают существование первой производной и вогнутость функции д¡(С) в точках ограниченного интервала, где она принимает положительные значения. Однако невязка Р(СИ) не обладает выпуклостью, что не позволяет применять чистый метод Ньютона для решения уравнения (32).

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

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

Рассмотрим нелинейную задачу о дополнительности: найти вектор х Е Я" такой, что

f{x)> 0, xTf(x) = 0, (33)

где / : Я^, -) if — отображение из класса C1(jR" ). Метод Ньютона для решения задачи (33) состоит в следующем: имея текущее приближение хк, определяют хк+х как (точное) решение линейной задачи о дополнительности (ЛЗД):

х > 0, w = f(xk) + f'(xk){x - хк) > 0, xTw = 0. (34)

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

Я"+.

Определение 6. Квадратная матрица А Е С(Я") называется Z-матрицей, если ее внедиагональные элементы неположительны; она называется Р-матрицеЙ, если все ее главные миноры положительны; наконец, неособенная матрица А называется М-матрицсй, если (i{j < 0 при г ф j, и А"1 > 0.

Известно , что всякая Р-матрица является М-матрицей в том и только в том случае, когда она одновременно является Z-матрицей. Поэтому для того, чтобы положительно определенная матрица f'(x) была М-матрицей, достаточно того, чтобы она являлась Z-матрицей.

Теорема 19. Пусть отображение f : Я" —► Я" из класса С1(Яп) сильно монотонно, покомпонентно выпукло, и в любой точке х Е i?" матрица f'(x) является Z-матрицей. Тогда для любого начального приближения хо Е Яп последовательность {х*}, построенная с помощью метода Ньютона, сходится к х* — единственному решению задачи (33). Если, кроме того, производная f'(x) удовлетворяет условию Липшица на каждом ограниченном выпуклом подмножестве Я", то сходимость будет квадратичной, т.е. найдется

кпнстаитпп V > 0 такая, что справедливы оценки

- 1*|| < Щхк - х*\\2, А: = 0,1,.... (35)

Рассмотрим теперь другой класс отображений. Именно, будем считать, что / : Я" R" — строго монотонное отображение из класса C''(i?" ), и каждая его компонента /,• является вогнутой функцией. Кроме того, предположим, что допустимое множество отображения / не пусто, т.е. существует точка х £ R" такая, что f(x) > 0. Наконец, предположим, что матрица f'(x) в каждой точке х £ R" является Z-матрицей (/¡}(х) < 0 при г ф j).

Теорема 20. Пусть отображение f удовлетворяет всем выше-упомяпутым условиям. Тогда при произвольном начальном приближении х° £ последовательность {ж1}, порожденная методом Ньютона, сходится к х* £ i?" — решению задачи (33).

Теорема 21. Пусть отображение f : ii" —► Rn удовлетворяет условиям теоремы 20 и кроме того, производная f(x) удовлетворяет условию Липшица на всяком ограниченном выпуклом множестве V С i?" • Тогда последовательность приближений {ж*}, полученных методом Ньютона, сходится к х* — решению задачи (33), — с квадратичной скоростью.

Рассмотрим еще один класс отображений /, представляющий интерес для практических целей.

Теорема 22. Пусть отображение f : i?" —► R" задано в виде /(.г) = Л.г + <р(х), где А £ C(Rn) — положительно определенная матрица с параметром /г > 0 (т.е. иТАи > /¿||и||2 для всех и £ Rn), а отображение ip : —► R" является непрерывно дифференцируемым с ограниченной производной:

У{х)\\ <qn Vxe^

с некоторым параметром 0 < q < 1/3. Тогда для любого начального х° £ R1 последовательность {хк}, построенная по методу Ньютона, сходится к х* — единственному решению задачи (33). Если, кроме того, производная <р'(х) удовлетворяет условию Липшица на

каждом ограниченном выпуклом подмножестве R+, то сходимость будет квадратичной, т.е. выполнена оценка (35) с некоторой константой V.

В разделе 4.3 рассматривается применение техники, описанной в в пункте 3.6 предыдущей главы, к управлению точностью шага метода Ньютона, используемого для поиска решения нелинейной задачи о дополнительности (НЗД). Предварительно получены результаты о сходимости и скорости сходимости неточного метода Ньютона.

Для исследования поведения неточного метода Ньютона нам понадобятся некоторые оценки для меры ошибки |Щ:г)||, где h(x) — min{.-c, f{x)} — покомпонентный минимум векторов х и f(x).

Опишем теперь один из вариантов неточного метода Ньютона. Пусть xk е Rn — текущая итерация, к > 1. Построим xk+i в соответствии с правилом

1М**+1)11<7* = 6||М*')||, 6 > 0, (36)

где hk(x) = шт{ж, f(xk)+f'(xk)(x~xk)}, а{£ц.} — последовательность положительных чисел.

Теорема 23. Пусть х* £ R+ — (единственное) решение задачи (33) с отображением f(x) = Ах -)- >р(х), удовлетворяющим условиям теоремы 22. Тогда для любого начального приближения х° G Пп последовательность {хк}, построенная по правилу (36),

а) сходится к х*, если

6 (1 + \\А -f ч>'(хк) ||) (1 + ЦАЦ + qn) <V(1-q- ei)-

-(2-ei)|H*')ll, к = 0,1,..., (37)

для некоторого £j > 0 такого, что £i < ^

б) если к тому же ip £ C2(i?n) —» 0 при к —► оо, то сходимость будет сверхлинейной, т.е. справедливо соотношение

lim L-г^ = 0;

к-*оо X — X*

о) если, вдобавок, начиная'с некоторого к, выполнено соотноше-

ние

6 < «ИМ* )И>

то сходимость будет квадратичной, т.е. выполнено неравенство (35) с некоторой константой V > 0.

Применим схему оптимального управления точностью двухуровневого итерационного процесса, описанную в разделе 3.6 предыдущей главы, к неточному методу Ньютона. Сначала отметим, что в этом случае выражение Ф(х^) представляет собой вектор ?/+| — точное решение линейной задачи дополнительности (34) при к = С. В качестве непрерывной функции 6к(х), позволяющей оценивать величину отклонения вектора х от Ф(х^), можно выбрать норму вектора Нк(х) = тш{."г, /(хк) + /'(хк)(х — я*)}. Функция же ||Л(Ж)|| = || тт{х,/(.г)}|| может использоваться в качестве оценки близости итерации хк к решению х* задачи (33). В частности, если отображение /(;г) = Ах + <р(:г) удовлетворяет условиям теоремы 22,- то справедливы двусторонние оценки

в которых

В силу квадратичной скорости сходимости метода Ньютона, в рассматриваемом случае о = 1.

Тогда алгоритм управления точностью (& + 1)-го шага можно описать так. Пусть хк — текущая итерация. Как рекомендовано в п. З.б главы 3, вычислим величину щ = Т^РЦЛ^*)!! и сравним ее с величиной е = где е > О — заранее заданная конечная точность, а V — константа из квадратичной оценки (41). Если щ < е, то процесс окончен, хк — приближенное решение задачи (33); если же г/о > е, то сравниваем щ с величиной р и находим границу для погрешности выполнения шага по формуле

| о^о/Р, если 'По > ° I ^Ло/Р, если Щ < Р\

здесь £0 >0и(| >0 — корни уравнений

и

соответственно. Напомним, что функция р(£) определяется формулой

и определяем новое значение т;0. С найденными х1+1, щ описанная выше процедура повторяется.

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

В разделе в п. 4.4.1 доказывается существование решения нелинейной возмущенной задачи о дополнительности, зависящей от параметров: для произвольного набора параметров и = (щ,..., t¿m)т £ Я'" и вектора £ > 0 найти точку х £ В"1, для которой выполнены соотношения

здесь / : Я" х Ят —» Я" — отображение, определенное на парах переменных (х,и) £й" х Ят. В п. 4.4.2 показана сходимость решений возмущенной задачи к решению исходной и исследуется скорость сходимости при стремлении правых частей возмущенной задачи к нулю. Наконец, в п. 4.4.3 описан метод решения возмущенной задачи на каждом шаге и обосновывается его сходимость.

Х{^{х) =

г = 1,..., п.

(38)

х > 0, xifi{x, и) = ги г = 1,..., п;

Пусть зафиксирован вектор л £ + = {р 6 R" | р, > 0. i = 1,...,»} и рассматривается вспомогательная задача (38). Так как г > 0, чту задачу можно переформулировать так: найти положительное решение нелинейной системы уравнений

F(x) = 0, (39)

где ^

Fi(x) = fi(x) - —, г = 1,..., п. x¡

Нам удобно представить F в виде F(x) = f(x) 4- Н(х), где

2'

Щх) = —i=l,..., п.

Легко убедиться, что отоб])ажение Н : —> R" монотонно (по х). Поэтому если отображение / непрерывно и локально сильно монотонно на R", то для решения задачи (39) можно применить модифицированный метод Пнсмэна-Рэкфорда : по имеющемуся приближению хк сначала находится вектор хк+х^2 как положительное решение уравнения

Axt+1/'2 + H(xk+Xt2) = \хк — J(xk), (40)

а затем но найденному хк+x¡2 строится вектор хк+х — решение задачи

Xxk+l + f(xk+i) = \хк+]'2 - #(xfc+,/2). (41)

Здесь А > 0 фиксированный параметр.

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

Теорема 24. Пусть отображение f : R" —» R" локально сильно монотонно, а на каждом компактном множестве в R" непрерывно по Липшицу. Тогда для любых х° £ Rn, А > 0 последовательность {.т*1} корректно определена формулами (40)-(41) и сходится к х* = x*(z) — единственному решению задачи (33).

Заметим, что точка xk+l/2 из уравнения (40) легко вычисляется с помощью решения квадратных уравнений. Именно,

fi(xk) , sj[\xk - fi(xk)]2 + 4\Zi Xi ~ 2 2A + 2A ' г-1'"-'п-

Поэтому фактически на каждом шаге алгоритма остается решить нелинейную систему уравнений

Ая,- +/,■(* ---т+щ,

г — 1,..., п. Но отображение (ЛЕ + /) уже сильно монотонное, и для решения последней системы можно применять эффективные методы типа метода Ньютона.

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

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

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

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

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

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

5. Для определенного класса функций проведено сравнение равновесных общих объемов в моделях Курно и Штакельберга.

G. Построены и обоснованы алгоритмы ньютоновского тина ятя решения задачи о дополнительности и отыскания рашкшсспя н обобщенных моделях олигополии.

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

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

работах:

[1] Калашников В.В. Некоторые задачи лексикографической минимизации // Оптимизация. - 1978. - Вып. 21(48). - С. 109-120.

[2] Калашников В.В. Метод раздельных шагов для минимизации овражных функций // Оптимизация. - 1980. - Вып. 25(42). - С. 70 85.

[3] Калашников В.В. Метод минимизации овражных функций с помощью выделения сингулярных направлений // Оптимизация. - 1982. Вып. 30(47). - С. 35 - 49.

[4] Калашников В.В., Калашникова Н.И. Глобальная сходимость неточного метода Ньютона для решения задачи дополнительности // Оптимизация. - 1988.- Вып. 42(59). - С. 66-85.

[5] Калашников В.В., Калашникова Н.И. Управление точностью выполнения шага в методе Ньютона для решения нелинейной задачи дополнительности // Оптимизация. - 1988. - Вып. 43(60). - С. 27 - 40.

[6] Калашников В.В., Калашникова Н.И. Оптимальное управление внутренней точностью в двухуровневом итерационном процессе // Оптимизация. - 1988. - Вып. 44(61). - С. 27 - 55.

[7] Калашников В.В. Теорема существования решения нелинейной задачи дополнительности // Оптимизация. - 1989. - Вып. 45(62). - С. 26- 33.

[8] Калинников В.В., Калашникова Н.И. Управление точностью шага в методе нагруженного функционала // Оптимизация. 1989. Вып. 45(62). - С. 34-53.

[9] Калашников В.В., Калашникова Н.И. Метод декомпозиции для решения блочной задачи о дополнительности // Оптимизация. - 1989. - Вып. 46(63). - С. 67-85.

[10] Калашников В.В., Калашникова Н.И. Сходимость метода Ньютона для нелинейной задачи о дополнительности // Оптимизация. - 1991. - Вып. 49(65). - С. 69-79.

[11] Kalaslinikov V.V. On locally strongly monotone nonlinear complementarity problem // XIV International Symposium on Mathematical Programming. - Book of Abstracts. - Amsterdam, the Netherlands. - 1991. - P. 153.

[12] Калашников В.В., Калашникова Н.И. Один итерационный метод решения нелинейной задачи о дополнительности // Оптимизация. - 1993. - Вып. 52(69). - С. 42-54.

[13] Булавский В.А., Калашников В.В. Метод прогонки по параметру для изучения состояния равновесия // Экономика и мате. матические методы. - 1994 - Т. 30, N. 4 - С. 129-138.

[14] Калашников В.В., Калашникова Н.И. Решение двухуровневого вариационного неравенства // Кибернетика и системный анализ. - 1994. - Т. 30,N. 4. - С. 178-180.

[15] Bulavsky V.A., Kalashnikov V.V. Parameter driving method to compute equilibria // CORS'94 - Optimization Days.- Montreal, Canada - Book of Abstracts. - 1994. - P. 163.

[16] Bulavsky V.A., Kalashnikov V.V. Solving two-level variational inequality // XV International Symposium on Mathematical Programming.- Book of Abstracts. - Ann Arbor, USA.- 1994.-P. 178.

[17] Bulavsky V.A., Ivala-shnikov V.V. Parameter driving met hod to compute equilibrium // XV International Symposium 011 Mathematical Programming.- Book of Abstracts. Ann Arbor, USA. 1994. - P. 262.

[18] Kalashnikov V.V. Application of topological degree theory to complementarity problems // Труды Сибирской конференции no прикладной и индустриальной математике (памяти Л.В. Канторовича), ред. Л.А. Бокуть. - Институт математики СО РАН, Новосибирск. - 1995. Т.1. - С. 316-324.

[19] Bulavsky V.A., Kalashnikov V.V. Equilibria in generalized models of oligopolistic market // Труды Сибирской конференции по прикладной и индустриальной математике (памяти .П.В. Канторовича), ред. Л.А. Бокуть. - Институт математики СО РАН, Новосибирск. - 1995. Т.1. - С. 253-261.

[20] Булавский В.А., Калашников В.В. Равновесие в обобщенных моделях Курно и Штакельберга // Тез. докл. конф. "Математическое программирование и приложения". - 1995. - Екатеринбург: Институт математики и механики УрО РАН. - С. 48-48.

[21] Калашников В.В. Применение теории степени отображения в задачах о дополнительности. - Там же. - С. 112-113.

[22] Bulavsky V.A., Kalashnikov V.V. Equilibrium in generalized Cournot, and Stackelberg models // Optimization Days 1995. -Program and Abstract Book. - 1995. - Montreal, Canada. - P. 50.

[23] Булавский В.А., Калашников B.B. Равновесия в обобщенных моделях Курно и Штакельберга // Экономика и математические методы. - 1995. - Т. 31, N. 3. - С. 164-176.

[24] Калашников В.В. Теоремы существования неподвижной точки, основанные на топологической степени непрерывного отображения // Препринт ЦЭМИ РАН. - 1995. - 29 с.

• [25] Bulavskv V.A., Isac G., Kalashuikov V.V. Application of topological degree theory to complementarity problems / / International Conference on Industrial and Applied Mathematics (ICIAM95). - Book of Abstracts. - Hamburg, Germany, 1995. - P. 318.

[26] Bulavsky V.A., Kalashnikov V.V. Equilibria in Generalized Cournot and Stackelberg Models. - Там же. - P. 318.

[27] Bulavsky V.A., Kalashnikov V.V. A Newton-like approach for solving an equilibrium problem // International Symposium on Operations Research (OR'95).- Book of Abstracts. - Passau, Germany, 1995. - P. 134.