Введение к работе
Актуальность темы. Равновесные модели в Настоящее время находят свое применение в самых различных областях науки и техники, позволяя единым образом формулировать и анализировать возникающие при этом разнообразные задачи. К этим областям можно отнести прежде всего физику (в особенности, механику я термодинамику), экономику, биологию, экологию. Многие равновесные модели приводят к необходимости решения вариационных неравенств, составляющих специальный, но весьма обширный класс равновесных задач. Кроме того, равновесные задачи тесно связаны с другими общими математическими задачами, такими как задачи оптимизации, дополнительности, поиска неподвижной точки и др. Поэтому разработка методов решения равновесных за-цач позволяет не только находить решения сложных прикладных задач, но и выработать общие подходы для многих общих задач нелинейного анализа.
Развитие теории и методов для различных классов равновес-еіьіх задач длительное время шло независимыми друг от друга, параллельными путями, главным образом вследствие различных источников их возникновения и наличия различных формул иро-зок принципов равновесия. Так, различные равновесные задачи ризики рассматривали еще И. Бернулли, Л. Эйлер. Ж. Лагранж. Ж.Б. Фурье. В дальнейшем, вслед за работами Г. Фиксры. Ф. Браузера, Ж.-Л. Лионса и Г. Стампаккьи стала развиваться теория вариационных неравенств применительно к задачам физики. Теория жономического равновесия была инициирована работами Л. Валь-эаса, А. Вальда, К. Эрроу и Ж. Дебре: принцип равновесного речения, сформулированный Дж. Нэшем. стая одним из осповопо-хагающих в теории игр. Общая теория равновесных задач стала эазвиваться сравнительно недавно, значительное продвижение в )той области связано с работами Ки Фана. X. Нпкандо. Ж.-П. Обе-їл, а также Е. Блюма, В. Эттли и др. Различные методы решения завновееных задач предлагались в (заботах К. Эрроу, Л. Гурнн-
ца. X. Уд чаны, К. Ломко, В.Ф. Демьянова, Е.Г. Гольштейна, Ж.-Л. Лнопса. Р. Коттла, СИ. Зуховицкого, Р.А. Поляка, М.Е. Примака. Й.-Ш. Панга и других авторов. При этом отсутствие свойства потенциальности (симметричности), характерное для равновесных задач и отличающее их от задач оптимизации, приводит, как правило, к необходимости введения дополнительных предположений типа устойчивости множества решений, строгой монотонности и т.н.. которые обеспечивают сходимость итерационных методов. Существуют различные подходы к построению методов, сходящихся при более слабых предположениях. Значительное продвижение в этой области связано с работами А.С. Антипина, А.Б. Бакушинско-го. Дж. Брауна, Р. Брука, В.В. Васина, В.А. Волконского, Ю.Г. Евтушенко, Б. Ивза, Г.М. Корпелевич, Б. Мартине, А.С. Немировеко-го. Б.Т. Поляка. Р.Т. Рокафеллара, X. Скарфа, Н.З. Шора и других авторов. Наиболее разработанными являются методы поиска седлоиых точек выпукло-вогнутой функции и методы решения вариационных неравенств с однозначным монотонным отображением при простом в смысле реализации операции проектирования допустимом множестве. В то же время в этой области остается значительное число проблем, одной из главных среди них является проблема построения эффективных методов для достаточно общих равновесных задач, т.е. методов, с одной стороны, простых и вычислительном отношении и конструктивных, пригодных как для гладких, так и для негладких равновесных задач и вариационных неравенств, для задач со сложными нелинейными ограничениями, а с другой стороны, достигающих достаточно высокой линейной скорости сходимости. Значительной проблемой является разработка методов для решения равновесных задач с более слабыми свойствами, чем выпуклость (монотонность). В теории уже достаточно хорошо изучены вопросы существования и < инк і 'ценности решения для таких задач. В то же время отмечено (С. Биллупс, М. Феррпс). что многие известные методы решении МОНОТОННЫХ вариационных неравенств теряют работоспособность па простейших задачах с псевдомонотонным отображением.
Цель работы. Основная цель работы состоит в построении эффективных методов для решения достаточно широких классов рав-ювссных задач. Эта проблема включает в себя:
-
разработку общих схем построения методов и получение оценок точности последовательных приближений;
-
построение на базе общих схем простых и конструктивных методов решения равновесных задач и вариационных неравенств, сходящихся при достаточно слабых предположениях, в том числе з условиях обобщенной монотонности (вогнуто -выпуклости);
-
построение методов, пригодных для решения негладких равновесных задач и многозначных вариационных неравенств, а также для задач с нелинейными ограничениями;
-
получение оценок скорости сходимости и трудоемкости для построенных методов, в том числе оценок, соответствующих лишенной скорости сходимости.
Методика исследования. В работе используются методы нелинейного функционального анализа, выпуклого ли. .за. аппарат теории и методов решения экстремальных задач.
Научная новизна и практическая значимость. В работе получены следующие новые результаты:
-
Предложен новый общий подход к построению релаксационных методов решения равновесных задач, который основан па обь-здинешш в общей схеме, составленной по модульному принципу, элементов различных итерационных процессов и па использовании допустимых квазинерастягивающих операторов. Эю позволило привлечь широкие классы простых и конструктивных процедур релаксационного тина для определения параметров шага в пекущей итерационной точке основного процесса и обеспечить сходн-viocTb методов при достаточно слабых иредпо, южсипях.
-
Построены простые и конструктивные варианты комбинированных релаксационных методов дня решения равновесном задачи : гладкой вогнуто-выпуклой функцией и для решения вариационных неравенств с однозначным опюражеписм. удовлетворяющим условиям тина обобщенной монотонности. Методы применимы при
различных способах задания допустимого множества, в том числе при наличии нелинейных выпуклых ограничений. Указаны варианты методов, достигающие линейной скорости сходимости.
-
Построены простые и конструктивные варианты комбинированных релаксационных методов для равновесных задач с вогнуто-выпуклой и квазивогнуто - квазивыпуклой негладкой функцией при наличии линейных и нелинейных выпуклых ограничений, а также для вариационных неравенств с многозначным отображением, удовлетворяющим условиям типа обобщенной монотонности, при наличии нелинейных выпуклых ограничений. Указаны условия, при которых построенные методы имеют оценку трудоемкости, соответствующую линейной скорости сходимости.
-
Предложен новый подход к решению вариационных неравенств с нелинейными ограничениями, основанный на сведении исходной задачи к задаче поиска стационарной точки многозначного немонотонного отображения, для решения которой предложено применить один из комбинированных релаксационных методов, сходящийся при условии существования решения дуального вариационного неравенства.
-
Предложены комбинированные релаксационные методы для решения равновесных задач и вариационных неравенств с декомпозиционной структурой, позволяющие либо сократить объем используемой памяти ЭВМ, либо выполнять части метода параллельно и ускорить вычислительный процесс.
С) Построены реализации комбинированных релаксационных методов для задач математической физики, сводящихся к вариационному неравенству с непотенциальным некоэрцитивным отображением, для задач экономического равновесия (линейной модели обмена), сводящихся к задаче дополнительности с многозначным немонотонным отображением, а также для задач транспортного равновесия.
7) Установлены условия существования решения для многозначного векторного вариационного неравенства в банаховом пространство при ослабленных свойствах монотонности основного ото-
бражения и приведены условия преобразования исходной задачи к скалярному вариационному неравенству с псевдомонотонным отображением. Получены конструктивные условия существования решения дуальной равновесной задачи, при которых гарантируется сходимость комбинированных релаксационных методов.
Полученные результаты носят как теоретический, так и практический характер. Они могут быть использованы, в частности, при поиске седловых точек функции Лагранжа, поиске игрового равновесия, решении задач оптимизации по скалярному невыпуклому и векторному критерию, а также по бинарному отношению, решении вариационных неравенств с одно- и многозначным, не строго монотонным отображением, возникающих в механике и других областях физики, в экономике, при решении задач потокового равновесия, а также при решении векторных вариационных неравенств. Апробация работы. Основные результаты работы докладывались на семинаре Вычислительного центра Российской академии наук (1996 г.), на семинаре Института математики и механики Уральского Отделения РАН (1997 г.), на семинаре кафедры вычислительной математики Казанского государственного университета (1995 г.), на семинаре кафедры экономической кибернетики КГУ (1996 г.), на семинаре НИИ математики и механики при КГУ (1994, 1996 гг.), на семинаре кафедры прикладной математики КГУ и на итоговых научных конференциях КГУ (1992-1996 гг.), па Международной школе- семинаре "Методы оптимизации и их приложения" (Иркутск, 1989 г.), на Всероссийских конференциях "Математическое программирование и приложения" (Екатеринбург, 1993, 1995 гг.), на Всероссийском семинаре "Теория сеточных методов для краевых задач" (Казань, 1996 г.), на Четвертом Международном семинаре "Многокритериальные и игровые про_-блемы при неопределенности" (Орехово-Зуево, 1996 г.), на конференции^" Алгебра и анализ", посвященной 100-летию Б.М. Гагаева (Казань, 1997 г.). Результаты работы представлялись на Международном симпозиуме по математическому программированию (Анн Арбор, 1994 г.), на Международном симпозиуме по исследованию
операций (Пассау, 1995 г.).
Публикации. Основными публикациями по теме диссертации являются работы [1]—[26]. Все результаты диссертации получены автором самостоятельно, за исключением результатов 3 главы I о существовании решений многозначных векторных вариационных неравенств, полученных совместно с Д.Ч. Яо.
Структура работы. Диссертация изложена на 235 страницах, состоит из введения, четырех глав, заключения и списка литературы, содержащего 255 наименований. Нумерация формул, теорем, лемм и других структурных элементов в каждом параграфе диссертации самостоятельная, причем первое число - номер параграфа, а второе - номер соответствующего структурного элемента. При ссылках на формулу, теорему, лемму и т.д. из другой главы слева добавляется также и номер главы.
