Комбинированные релаксационные методы для решения равновесных задач и вариационных неравенств тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

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

КОННОВ Игорь Васильевич

КОМБИНИРОВАННЫЕ РЕЛАКСАЦИОННЫЕ МЕТОДЫ ДЛЯ РЕШЕНИЯ РАВНОВЕСНЫХ ЗАДАЧ И ВАРИАЦИОННЫХ НЕРАВЕНСТВ

01.01.07 -вычислительная математика

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

КАЗАНЬ - 1997

Работа выполнена на кафедре ^прикладной математики Казан ского государственного университета.

Официальные оппоненты: доктор физико-математических

наук, ст. научн. сотр. A.C. Антипин; доктор физико-математических -- наук, член-корр. РАН В.В. Васин; доктор физико-математических наук, профессор A.B. Лапин.

Ведущая организация: Уральский государственный универси-

тет.

Защита состоится " " О^Л^Я- 1997 года в часов на заседании диссертационного совета Д 053.29.10 в Казанском государственном университете по адресу: 420008. г.Казань, ул. Университетская, 17, НИИММ, ауд. 324

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

Автореферат разослан " " Се^сЛЯщА^ 1997 г.

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

Е.М. Федотов

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

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

Развитие теории и методов для различных классов равновес-Е1ых задач длительное время шло независимыми друг от друга, параллельными путями, главным образом вследствие различных источников их возникновения и наличия различных формулировок принципов равновесия. Так, различные равновесные задачи физики рассматривали еще И. Бернулли, Л. Эйлер. Ж. Лагранж, Ж.Б. Фурье. В дапьнейшем, вслед за работами Г. Фикеры. Ф. Браузера, Ж.-Л. Лионса и Г. Стампаккьи стала развива ться теория вариационных неравенств применительно к задачам физики. Теория жономического равновесия была инициирована работами Л. Валь-эаса, А. Вальда, К. Эрроу и Ж. Дебре: принцип равновесного речения, сформулированный Дж. Нэшем. стая одним из осповопо-хагающих в теории игр. Общая теория равновесных задач стала эазвиваться сравнительно недавно, значительное продвижение в »той области связано с работами Ки Фана. X. Ннкнндо. Ж.-П. Обе-ja, а также Е. Блюма, В. Эттли и др. Различные методы решения завновесных задач предлагали* ь в {заботах К. Эрроу, Л. Гурви-

ца. X. Уд чаны, К. Ломке, В.Ф. Демьянова, Е.Г. Гольштейна, Ж.-Л. Лиопса. Р. Коттла, С.И. Зуховидкого, P.A. Поляка, М.Е. Примака. Й.-Ш. Паига и других авторов. При этом отсутствие свойства потенциальности (симметричности), характерное для равновесных задач и отличающее их от задач оптимизации, приводит, как правило. к необходимости введения дополнительных предположений пшя устойчивости множества решений, строгой монотонности и т.ч.. которые обеспечивают сходимость итерационных методов. Существуют различные подходы к построению методов, сходящихся при более слабых предположениях. Значительное продвижение в 1 oii области связано с работами A.C. Антипина, A.B. Бакушинско-го. Дж. Брауна, Р. Брука, В.В. Васина, В.А. Волконского, Ю.Г. Евтушенко, Б. Ивза, Г.М. Корпелевич, Б. Мартине, A.C. Немировско-го. Б.Т. Поляка. Р.Т. Рокафеллара, X. Скарфа, Н.З. Шора и других авторов. Наиболее разработанными являются методы поиска седло пых точек выпукло-вогнутой функции и методы решения вариационных неравенств с однозначным монотонным отображением при простом в смысле реализации операции проектирования допус тимом множестве. В то же время в этой области остается значительное число проблем, одной из главных среди них является проблема построения эффективных методов для достаточно общих равновесных задач, т.е. методов, с одной стороны, прос тых в вычислительном отношении и конструктивных, пригодных как для гладких, так и для негладких равновесных задач и вариационных неравенств, для задач со сложными нелинейными ограничениями, а с другой стороны, достигающих достаточно высокой .линейной скорости сходимости. Значительной проблемой является разработка методов для решения равновесных задач с более слабыми свойствами, чем выпуклость (монотонное!ь). В теории уже достаточно хороню изучены вопросы существования и <• шнствепности решения для таких задач. В то же время отмечено (С. Биллупс, М. Феррпс), что многие известные методы решении монотонных вариационных неравенств теряют работоспособность па простейших задачах с псевдомонотонным отображением.

Цель работы. Основная цель работы состоит в построении эффективных методов для решения достаточно широких классов рав-ювесных задач. Эта проблема включает в себя:

1) разработку общих схем построения методов и получение оценок точности последовательных приближений;

2) построение на базе общих схем простых и конструктивных методов решения равновесных задач и вариационных неравенств, сходящихся при достаточно слабых предположениях, в том числе а условиях обобщенной монотонности (вогнуто -выпуклости);

3) построение методов, пригодных для решения негладких равновесных задач и многозначных вариационных неравенств, а также для задач с нелинейными ограничениями;

4) получение оценок скорости сходимости и трудоемкости для построенных методов, в том числе оценок, соответствующих линейной скорости сходимости.

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

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

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

2) Построены простые и конструктивные варианты комбинированных релаксационных методов дня решения равновесном задачи :: гладкой вогнуто-выпуклой функцией и для решения вариационных неравенств с однозначным отоГфажепием. удов. 1еч норяюпшм условиям тина обобщенной монотонности. Методы применимы нрп

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

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

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

5) Предложены комбинированные релаксационные методы для решения равновесных задач и вариационных неравенств с декомпозиционной структурой, позволяющие либо сократить объем используемой памяти ЭВМ, либо выполнять части метода параллельно и ускорить вычислительный процесс.

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

7) Установлены условия существования решения для многозначного векторного вариационного неравенства в банаховом пространство при ослабленных свойствах монотонности основного ото-

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

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

Апробация работы. Основные результаты работы докладывались на семинаре Вычислительного центра Российской академии наук (1996 г.), на семинаре Института математики и механики Уральского Отделения РАН (1997 г.), на семинаре кафедры вычислительной математики Казанского государственного университета (1995 г.), на семинаре кафедры экономической кибернетики КГУ (1996 г.), на семинаре НИИ математики и механики при КРУ (1994, 1996 гг.), на семинаре кафедры прикладной математики КГУ и на итоговых научных конференциях КГУ (1992-1996 гг.), па Международной школе- семинаре "Методы оптимизации и их приложения" (Иркутск, 1989 г.), на Всероссийских конференциях "Математическое программирование и приложения" (Екатеринбург, 1993, 1995 гг.), на Всероссийском семинаре "Теория сеточных методов для краевых задач" (Казань, 1996 г.), на Четвертом Международном семинаре "Многокритериальные и игровые проблемы при неопределенности" (Орехово-Зуево, 1996 г.), на конференции^" Алгебра и анализ", посвященной 100-летию Б.М. Гагаева (Казань, 1997 г.). Результаты работы представлялись на Международном симпозиуме по математическому программированию (Анн Арбор, 1994 г.), на Международном симпозиуме по исследованию

операций (Пассау, 1995 г.).

Публикации. Основными публикациями по теме диссертации являются работы [1]-[26]. Все результаты диссертации получены автором самостоятельно, за исключением результатов §3 главы I о существовании решений многозначных векторных вариационных неравенств, полученных совместно с Д.Ч. Яо.

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

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

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

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

В §1 главы I рассматривается общая постановка равновесной задачи: найти элемент

€ и такой, что Ф(и0, у) > О V»£[/, (1)

где 17, V - выпуклые подмножества банахова пространства Е, [/СУ, 3> : V х V —у Л - функция такая, что Ф (и, и) = 0 для любого и 6 V, Я - расширенная вещественная числовая прямая. Равновесная задача в такой постановке изучалась в работах Ж.-П.Обена, Л.Ниренберга, Е.Блюма и В.Эттли и др. Множество решений задачи (1) обозначим 11°. Приведены примеры приложений задачи (1), в частности, отмечено, что задачи оптимизации, поиска седловой точки функции Лаграюка, игрового равновесия и оптимизации по нетранзитивному бинарному отношению записываются в виде (1). Приведены некоторые результаты о существовании решений равновесной задачи. Отмечается, что непустота множества и° связана, помимо свойств непрерывности Ф и (слабой) компактности и, также со свойствами (квази)выпуклости Ф(и, •), и либо (псевдо)монотонносш Ф, либо (квази)вогнутости Ф(-, и). Напомним, что функция Ф называется псевдомонотонной, если для любых и, V £17 выполняется

Ф(и, и) > 0 Ф(и,и) < 0.

Более слабым свойством является существование решения дуальной равновесной задачи: найти элемент

V0 в и такой, что Ф(и, и0) <0 Ум € 17. (2)

Множество решений задачи (2) обозначим IIе1.

Следующая теорема устанавливает связь между решениями задач (1) и (2).

Теорема 1. а) Если функция Ф псевдомонотонная, то 170 С

и".

Ь) Если функция Ф(-,у) полунепрерывна сверху для любого V £ 17, функция Ф(и, ■) явно квазивипукла для любого и £ 17, тпо V1 С ¡7°.

В §2 рассматривается вариационное неравенство: найти элемент

и* £ и такой, что Зд* £ <3(и*), (</*, и - и*) > 0 V« € С/, (3)

-де 17, V - выпуклые подмножества Е, II С V, С : V —+ ЩЕ') )Тображение (в общем случае точечно-множественное (т.м.о.)), Е'

- сопряженное к Е пространство. Здесь и далее П(Х) обозначает совокупность всех подмножеств множества X. Множество решений задачи (3) обозначим U*. Приведены различные способы преобразования задач оптимизации, дополнительности, поиска неподвижной точки к задаче (3), а также условия взаимных эквивалентных преобразований задач (1) и (3). Хотя вариационное неравенство (3) может быть приведено к виду (1), но такое преобразование не всегда целесообразно, поскольку специальные свойства вариационных неравенств позволяют предложить для них более эффективные методы анализа и решения. Приведены некоторые результаты о существовании решений вариационных неравенств, которые используют свойства (псевдо)монотонности т.м.о. G. Напомним, что т.м.о. G : U —» П(-Е") называется псевдомонотонным, если для любых и', и" G U и любых g' £ G(u'), g" € G(u") выполняется

{</", «' - «") > 0 => (g\v! - и") > 0.

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

В §3 устанавливаются условия существования решения многозначного векторного вариационного неравенства: найти элемент

и* & U такой, что Vu е U, 3g*eG(u*), (g*,u-u*) £ -intC(u*), (4)

где U - выпуклое подмножество Е, G : U Н(С(Е, F)), С : U —> П (F), причем С (и) - выпуклый замкнутый заостренный конус в F, iut С (и) ф 0 для любого и £ U; Е и F - банаховы пространства. Эта задача является естественным обобщением скалярного вариационного неравенства (3). В теоремах 2—5 получены различные тины условий, при которых решение задачи (4) существует, а также условия сведения задачи (4) к скалярному вариационному неравенству с псевдомонотонным отображением.

Итак, объектом приложения итерационных методов, предлагаемых в работе, являются равновесные задачи со свойствами (ква-зи)вогиуто - выпуклости, либо со свойствами типа монотонности

Ф, а также вариационные неравенства с основными отображениями, обладающими свойствами типа монотонности. Эти свойства являются довольно слабыми и характерны для весьма широких классов прикладных задач.

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

Отметим, что монотонные процессы проективного типа для более простых задач решения систем линейных уравнений и неравенств предлагались С. Качмажем, С. Агмоном, Т. Моцкиным и И. Шенбергом и другими; для решения систем выпуклых неравенств и задач оптимизации разрабатывались И.И. Ереминым и его учениками, а также В.А. Вулавским, Б.Т. Поляком и др. Введение вспомогательных процедур выбора параметров позволяет построить сходящиеся монотонные процессы для существенно более сложных, равновесных задач.

Следует также отметить, что использование в той или иной форме дополнительной информации о задаче в текущей итерационной точке присуще таким хорошо известным методам, как методы проксимальной точки (Б. Мартине, Р.Т. Рокафеллар), метод фиктивного разыгрывания (Дж. Браун, В.А. Волконский), прогнозные (экстраполяционные) методы (A.C. Антипин. Г.М. Кор-пелевич). В этих методах в текущей итерационной точке используется точное решение вспомогательной задачи, (обычно задачи

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

Допустимость итерационной последовательности комбинированных релаксационных методов в общем случае обеспечивается за счет включения в схему допустимого квазинерастягивающего оператора, выбор которого зависит от класса решаемых задач. По определению, оператор Р : Яп —► Я" называется:

a) квазинерастпягивающим в отношении множества V, если для любого и £ Я" выполняется ||.Р(м) — и|| < — и|| для всех ?; £ V;

b) допустимым в отношении множества V. если Р(и) £ V для любого и £ Я".

Обозначим Т(У) - множество допустимых квазинерастягиваю-щих в отношении множества V С Я" операторов. Итерационные процессы, в которых шаг основного процесса дополняется применением квазинерастягивающего (но не обязательно допустимого) оператора, рассматривались В.В. Васиным.

Онишем общие схемы построения комбинированных релаксационных методов применительно к задаче нахождения элемента неявно заданного множества К С V.

Общая схема I. Выберем точку и0 £ V, последовательность {7*} такую, что

оо

Ук е [0,2]Д = 0,1,...; £ 7*(2 - 7*) = оо;

к=О

определим последовательность операторов {Рк} таких, что £

На к-й итерации, к = 0,1,..., имеем точку ик. Применяем процедуру Дь с входной точкой ик и выходными параметрами: вектором

дк и числом (Tjt, после чего полагаем uk+l = Рк{ик - Jk<^k9k)- Итерация завершена.

Процедура Djt общей схемы I предназначена для обеспечения выполнения условий вида

эЩ С к : (дк, ик - и*) > ок\\дк\\* > О Vu* 6 Щ, (5)

либо

зU£CV. : {gk,uk-u*)>ok\\tk\\2+(gk-tk,uk-uk+l) Vu* еЩ (6)

для некоторой последовательности {th}. Показано, что условия (5), (6) гарантируют релаксационность последовательности {и*}, и, при достаточно общих предположениях, сходимость к точке множества V*.

Общая схема II. Выберем точку и0 £ V, последовательность {jj} такую, что

оо

7j е [0,2], j = 0,1,...; £ 7,(2 - Ъ) = оо;

j=0

определим последовательность операторов {Рк} таких, что Рк £ Т(У). Полагаем А(0) = 1, j(0) = 0.

На к-й итерации, к = 0,1,..., имеем точку ик, числа А (к), j(k).

1. Полагаем I = А (к), применяем процедуру £>к с входными параметрами: точкой ик и числом I и выходными параметрами: вектором дк и числами crfc, А (к + 1).

2. Если А (к + 1) > I, то uk+l = у1 = uh, j(k -f 1) = j(k)\ итерация завершена. Иначе полагаем j(k + 1) = j(k) + 1, ик+< = Рк(ик — li(k)(Jkgk)^ итерация завершена.

Процедура Dk общей схемы II предназначена для обеспечения выполнения условия (5). Отличие общей схемы II от общей схемы I состоит в том, что в ней предусмотрена возможность нулевого шага в неоптимальной точке. Такая ситуация может возникну ть в негладком (многозначном) случае, в задачах с нелинейными ограничениями. В общей схеме II величины \{к) — 1 и j(k) указывают

количества соответственно нулевых и ненулевых шагов за к итераций.

Таким образом, процедуры Dk, Dk и оператор Рк представляют собой заменяемые модули общих схем I и II, а множество V является параметром этих схем. Для полного определения метода поэтому достаточно указать способ реализации этих элементов. Такие реализации строятся в главах II - IV для конкретных классов равновесных задач и вариационных неравенств. При этом, если множество V достаточно просто устроено (например, V — многогранник). в качестве Рк можно выбрать оператор проектирования на V". Если же V определяется выпуклыми нелинейными ограничениями. то оператор Рк может быть реализован с помощью конечных алгоритмов.

Во второй главе рассматриваются комбинированные релаксационные методы для решения задачи (1) при условиях, когда U - непустое выпуклое замкнутое подмножество Rn, Ф (квази) вогнуто-выпуклая непрерывная функция. Также предполагается, что

При построении методов этой главы полагается V = U, а процедуру Dk (Dk) предлагается выбирать на основе модифицированной итерации некоторого метода минимизации функции Ф(ик, •) па множестве U, т.е. решения задачи

min {Ф(и*, v) | v £ U}. (7)

После получения в результате итерации точки vk G U параметры главного процесса определяются по формулам

дк € - ¿W>u(u,t,*)|u=ut,<7t = -Ф(и1У)/|ИД (8)

В §§1-4 предлагаются методы для случая вогнуто-выпуклой функции Ф. В §1 рассматривается метод, в котором точка ик определяется как решение задачи (7) с заданной точностью. Также рассмотрены методы, где точка vk есть результат выполнения итерации проке - метода и итерации метода центров. В теоремах

6-8 обоснована сходимость этих методов при сделанных предположениях. Отмечается, что реализация описанных методов может вызвать затруднения при нелинейной функции •) и нелиней-

ных ограничениях. Поэтому возникает необходимость в методах с более простыми в вычислительном отношении вспомогательными процедурами. Такие методы рассматриваются в -4.

В §2 предлагается метод решения задачи (1) при дополнительном условии гладкости функции Ф. Обозначим G(u) = Ф',(и. i')|,,=„, Z+ - множество целых неотрицательных чисел.

Метод 1. Выберем числа 9 G (0,1], а G (0,1), ¡1 G (0.1). последовательность симметричных матриц {Л^} таких, что

к'1И2 < (Atp,p) < «"INI2 VpGiT, о < к' < к" < ос.

Метод состоит в применении общей схемы I главы I. в которой V = U, а процедура Д^ описывается следующим образом.

Вход: точка uk G U. Выход: вектор ук и число ст^.

Шаг 1. Найти zk = агр,нип{ФЛ:(г') | v G U}, где Ф*(г) = {G{uk), v - ак) + 0.5(At(« - ик), v - ик).

Шаг 2. Определить

(1 = min{/ е Z+ | Ф(ик, ик + iVÖ(zk - ик)) < а/Щв(и1'). zk - ,/)

положить в ¡. = fid0, tik = ик + 6k(:k — ик).

Шаг 3. Определить дк = — Ф',(», vk)\ t. если </ — 0. останов. Иначе определить а^ = — Ф(?/', iik)/\\gk^2.

Для метода 1 выполняется vk G U° в случае дк = 0. поэтому nj)ii обосновании рассматривается лишь случай дк ф 0. к = 0. 1....

Теорема 9. Пусть градиент функции Ф(и. ■) явлж тел локально липшицевым на U. последовательность { ик} построена методом 1. Тогда

lim uk — и* G С". (9)

Кроме того, при дополнительных предположениях в теореме 10 установлена линейная скорость сходимости метола 1. Отметим, что метод 1 но существу включает в себя целый класс м<чо-дов ввиду произвольности выбора матриц .4,;.. Так. выбор Л/ ~ /

соответствует итерации метода проекции градиента, а выбор Ак — Ф"у(ик, w)| t - итерации метода Ньютона для выбора точки zk. Кроме того, можно использовать различные квазиньютоновские формулы пересчета Ак■ Вариант метода 1 с Ак = I близок к экстраградиентному методу (A.C. Антипин, Г.М. Корпелевич), но в отличие от него, не требует знания априорных характеристик задачи и использует простую процедуру линейного поиска. Для нахождения точки zk могут быть использованы итерации других релаксационных методов, так в [10], где был предложен данный подход к решению гладких равновесных задач, для этой цели применялась также модифицированная итерация метода условного градиента, т.е. для нахождения zk решается задача минимизации линейной функции на множестве U, тогда как в методе 1 - квадратичной функции.

В §2 построен также метод, полностью реализуемый и в случае, когда U определяется выпуклыми нелинейными ограничениями. А именно, пусть

U = {u G Rn | Ы[и) < 0 г = 1,...,т}, (10)

где hi : Rn —► R, i = 1,... ,m - выпуклые функции. Дополнительно предполагается, что выполняется условие регулярности Слейтера, т.е. существует точка ü такая, что hi{ü) < 0 для всех i — 1,...' ,га; вектор-функции Ф'v(u, •) для любого и Е U и h'{ для г = 1,..., m удовлетворяют условию Липшица на любом ограниченном множестве. Обозначим 1е(и) = {г | 1 < г < т, hi(u) > —е}.

Метод 2. Выберем числа а 6 (0,1), ß G (0,1), 9 £ (0,1], а также fii > 0 для г = 1,...,ш; последовательности {е/} \ 0, {г//} \ 0. Метод состоит в применении общей схемы II главы I, в которой V = U, процедура Dt определяется следующим образом.

Вход: точка ик £ U, число I. Выход: вектор дк и числа er*, A(fc+1).

Шаг 1. Найти вектор рк и число т*., являющиеся решением задачи

min —> т

при ограничениях

(С(ик),р) < г,

Шик),р) > //,-г «€/*(«*),

Ы < 1 ¿ = 1,...,п.

Шаг 2. Если тк > то дк = 0,ак = О, Л(&+.1) = 1+1, процедура завершена.

Шаг 3. Найти

сI = тиф' е | Ф(ик,ик+рёрк) < арё(С(ик),рк),ик+Р9рк е С}, ПОЛОЖИТЬ вк = 0е1 о, Ук = ик +

Шаг 4. Определить дк = - Ф'0(и, ст* = -Ф(и', и*)/||д'||2,

процедура завершена.

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

В §3 для равновесной задачи (1) с вогнуто-выпуклой, но необязательно гладкой функцией и допустимым множеством С/, задаваемым с помощью ограничений в виде линейных неравенств, построен и обоснован комбинированный релаксационный метод на основе общей схемы II. В этом методе для поиска точки ьк используется модифицированная итерация метода типа линеаризации, примененного к решению задачи (7), а выбор дк и а к осуществляется по формулам (8). При реализации метода требуется на каждой и ге-рации решить две задачи квадратичного программирования, что может быть сделано конечными алгоритмами.

В §4 для решения равновесной задачи (1) с вогнуто-выпуклой недифференцируемой функцией Ф при дополнительном условии тШ ф 0 строится метод, использующий для выбора параметров итерацию разработанного автором релаксационного субградиент-

ног» метода. Для каждого к определим т.м.о. по формуле

п (,,) = 1 0ф:(и*< =)|-=в если г' е ' \ 5(0, р) П Щи, ч) если г> <£ Ьт,

где „* е и. Р > 0. 5(0,/>) = {(} Е Л» | ||д|| = р}, щи,ч) = {д € Л" | (д. - — '')< 0 V; Е I/} - нормальный конус к множеству ¿7 в ючке г.

Метод 3. Выберем число 9 Е (0,1), ограниченные последовательности положительных чисел {о/}, {'//}• Метод состоит в применении обшей схемы II главы I, в которой V = и. а процедура Д^. омреде. шется следующим образом.

Вхо.г точка ик Е I', число /. Выход: вектордк и числам, \{к+1). Шаг 1. Положить > = 0,1Р° = и*, выбрать д' 6 ЯкЬ^1), положить // =

Шит 2. Если 1| < 1Ц. то г/ = 0, ак = 0, \{к + 1) = / + 1, процедура завершена.

Шаг 3. Положить «>'+1 = - «/р''/1И|- Если Ф(«*,ги,'+1) < —Йа/Цу/Ц, 1Г/+1 е и, то г* = №г+1, А (к + 1) = /, выбрать дк Е — 0Ф„(ч. ',<")| положить оь = — Ф(и1,г!*:)/||(/*:||''г, процедура завершена.

Шаг 4. Выбрать </+| Е <Ул(«''+1). положить

р'+1 = Рг(0, сопу^А д!+1[),

/' = /'+ 1 и перейти к шагу 2.

Внутренним шагом метода 3 будем называть изменение индекса / в процедуре

Теорема 12. Пусть последовательность } построена методом ',{. выполняются соотношения

М\о,Ы\о. (11)

Тогде:

a) количество внутренних шагов на, любой итерации метода ■конечно:

b) чьи),олН.Я1ГИГЯ. (9).

В качестве меры трудоемкости метода 3 определим суммарное число внутренних шагов N(6), обеспечивающее нахождение точки й6 G U такой, что

dis(ûs, U°) = inf{||û4 -z\\\ze U°} < 6,

где S > 0 - заданное число.

Теорема 13. Пусть последовательность {ак} построена методом 3, последовательности {«{}, {i]i},. {7j} выбраны из условий

щ = и1п,гц = г/ > 0,Z = 0,1,...; п > 0, и G (0,1);

7i = 7G(0,2),j = 0,l,... ^ '

Предположим также, что существует точка и* G U° такая, что

Ф(«,«*) < -/¿||и - u*|| Vît G U, fi > 0.

Тогда существуют числа à > 0 и г/ > 0 такие, члю для всех ci G (0, а) и f] G-(0, Г]) справедливо

N(6)<Bl ln(B„/6),

где 0 < Во, В\ < оо.

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

В §5 для решения задачи (1) в случае, когда Ф квазивогнуто -квазивыпуклая функция, inti/ ф 0, предложен и обоснован метод

4. и котором п качестве процедуры О у используется модифицированная итерация разработанного автором релаксационного метода, примененного к минимизации квазивыпуклой функции Ф(ик,-). В процедуре Д[. метода вместо субградиентов используются элементы нормального конуса к лебеговым множествам функции Ф(ик\ •) (обобщенно -опорные векторы). Таким образом, метод 4 имеет весьма широкую область сходимости.

Третья глава посвящена комбинированным релаксационным методам решения вариационных неравенств, т.е. задачи (3) при следующих общих предположениях: 17, V - выпуклые подмножества Я". V С V. б £ 2(Т/), где 2(У) - множество полунепрерывных сверху г.м.о., заданных на множестве V, с непустыми выпуклыми компактными образами в Еп.

В §1 главы III рассматривается следующее дополнительное условие. гарантирующее сходимость комбинированных релаксационных методов: существует множество 17^ ф 0 такое, что

V» 6 и. Уд е (а, и - и*) > о V«* е (аз;

Таким образом, 17^ - множество решений дуального вариационного неравенства. Из определения следует, что 17^ С Г/*. Показано что условие (13) выполняется для весьма широких классов задач в частности, если С (псевдо)монотонно, то 17^ = 17*, т.е. дл* выполнения (13) достаточно, чтобы исходная задача (3) имела решение. Таким образом, свойство (13) может рассматриваться ш некоторое обобщение свойства монотонности т.м.о. С.

Также установлено, что для общей равновесной задачи (1) выполняется С 0 С £ если положить

од = ЗФ,.(«.г)и„,

где функция Ф(и. ■) полунепрерывная снизу, регулярная и квачи выпуклая для любого и 6 17. функция Ф(-, г) - явно квазивогпуы} для любого с € V. Отметим, что эти условия выполняются, ес.'п выполнены предположения 4 главы II, более того, при энп

и0 = ил = и* = Поэтому итерационные методы решения вариационного неравенства (3), сходящиеся при выполнении условия (13), позволяют получить решение задачи (1) с вогнуто -выпуклой функцией Ф. Однако методы данной главы используют отличающиеся от (8) способы выбора направления движения дк. Более того, поскольку при решении вариационного неравенства (3) можно использовать только значения т.м.о. (9, го будут отличаться и способы построения вспомогательных процедур и Дь В §1 получены также условия выполнения соотношения (13) для ряда других классов равновесных задач, а также для некоторых задач невыпуклой оптимизации [10, 18].

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

и* £ 17 такой, что {¿(и*), и - и*) >0 Уи е II. (14)

Определим семейство отображений {Т*}, Т* : V х V —> Л", удовлетворяющих следующим условиям:

(a) Тк{и, •) сильно монотонно с константой т'к > 0 для любого и еУ;

(b) Тк(и, •) удовлетворяет условию Липшица с константой т[! для любого и ЕУ;

(c) Тк(и, и) = 0 для любого и Е V;

((1) Тк непрерывно на V х V.

Отметим, что перечисленные условия не являются ограничительными. Например, они выполняются, если определить

Тк{и,г) = Ак(2-и), (15)

где Ак - положительно определенная матрица порядка'гг.

Метод 5. Выберем числа а Е (0,1), /3 е (0,1), в > 0. Метод состоит в применении общей схемы I главы I, в которой V = и. а процедура Д& определяется следующим образом.

Вход: точка ик Е и. Выход: вектор дк и число ег*.

Шаг 1. Найти точку

i € U такую, что (G(uk) + Тк{ч\:), и - г) > О V?/ 6 U (16)

и положить :к = 5, рк = zk — ик. Шаг 2. Определить

<1 = min{j £ Z+ | u* + ?ёрк £ U, (G{uk + ßr9p%Pk) < n{G{uk),pk)},

положить вк = ftdÖ, vk = uk + 0kpk.

Шаг 3. Если G(vk) = 0, останов. Иначе определить qk = G(vk), а, = (G(vk),ttk - vk)/\\gkW2.

Отмстим, что на каждой итерации метода 5 решается вспомогательное вариационное неравенство (16) с сильно монотонным отображением. В случае представления (15) это отображение линейно. а значит, для многих классов допустимых множеств (например, когда U — R'l или U - многогранник) решение (16) можно найти эффективными конечными алгоритмами. При обосновании метода считается, что останова не происходит, поскольку иначе vk £ С*.

Теорема 14. Предположим, что семейство отображении {1\ } удовлетворяет условиям (a)-(d), отображение G локально лип-шицево на U. выполняются соотношения

4 > т' > 0, к = 0,1,..., limsup < т" < ос.

Jb—»oo

Если последовательность {и*} построена методом 5, то она имеет предельную точку в U*. Если же, дополнительно,

= (17)

то

lim uk = и* £ U*. (18)

>оо

Установлены оценки скорости сходимости метода 5 при различных предположениях о задаче (14). В частности, при выполнении предположений теоремы 14 и дополнительных предположении:

\\uk - 2fc|'| > р disi^M*), к = 0.1,...; (19)

Jk = У £ (0,2), Tk определяется соотношением (15), где ||Ль|| < г" < оо, U = Rn; установлена линейная скорость сходимости метода 5.

Отметим, что метод 5 по существу содержит целый класс методов, отвечающих различным способам выбора отображений Т*. Например, простейший выбор (15) с = I соответствует обобщению итерационного метода типа проекции градиента и в этом случае метод 5 является близким к экстраградиентному методу, однако, в отличие от него, процедура линейного поиска в методе 5 не требует знания априорных характеристик задачи. Выбор Ак — VG(uk) соответствует в (16) итерации метода Ньютона. Также возможны различные промежуточные варианты выбора матриц Ак по квазиныотоновским формулам. В отличие от методов, использующих оценочную функцию (П. Маркотте, Д. Чжу), метод 5 сходится при предположении, более слабом, чем монотонность G, ne требует компактности множества U, а также является более простым в вычислительной реализации, поскольку не требует дополнительного масштабирования отображений Тк для обеспечения сходимости.

В том случае, когда допустимое множество имеет вид (10). где hj : В" R, i — 1,..., m - выпуклые, но необязательно линейные функции, решение задачи (16) не может быть найдено точно. Поэтому в §2 построен и обоснован метод, в котором процедура D/. основана на модифицированной итерации метода возможных направлений, как в методе 2. Такой метод полностью реализуем при нелинейных ограничениях.

В §2 также описаны модификации методов, позволяющие ускорить вычислительный процесс за счет увеличения длины шага при сохранении свойства монотонного приближения к множеству решений. Идея модификаций состоит в использовании проекции вектора G(vk) на подпространство, параллельное касательному многообразию к множеству U. вместо вектора G(vk). в частности, при определении направления //' на шаге 3 процедуры D/..

В §3 для решения задачи (14) построен и обоснован метод 6. основное отличие которого от метода 5 заключается в одновремеи-

ном выполнении операций выбора длины шага и решения вспомогательного вариационного неравенства (16), т.е. основанный на использовании другой модификации метода типа проекции градиента для определения вспомогательной точки г>к. Для метода 6 установлены оценки скорости сходимости, аналогичные полученным для метода 5. В §3 предложены также модификации метода 6, связанные с иным способом выбора длины шага в процедуре Дь и позволяющие расширить класс задач, для которых гарантируется линейная скорость сходимости.

Метод 7. Выберем числа а 6 (0,1), ¡3 € (0,1), в > 0, семейство отображений {Тк}, удовлетворяющее условиям (а)-(с1) §2.

¡Ме тод состоит в применении общей схемы I главы I, в которой V = V. Рк(и) = Рг(?г,II), а процедура Бк определяется следующим образом.

Вход: точка ик £ II. Выход: вектор дк и число ак.

Шаг 1. Определить й как наименьшее число в ¿Г+ такое, что

(С(ик) - <?(*'), ик - < (1 - а){Тк(ик,- ик)/(9Р), (20)

где Р - решение вариационного неравенства: найти г 6 II такой, что

№*) + 0Р)~1Тк(ик,г), и - г) > 0 У и £ V. (21)

Шаг 2. Положить 9к = ук = Если ик — ик, останов. Иначе определить = в(ак) - <?(«*) + б£1Тк(ик, ьк) и

дк = <?(«*), ак = авк1(Тк{ик, г,к\ик - г,к)/\\^\\2.

Показано, что ик £ I/*, если ик = ьк, поэтому при обосновании метода рассматривается лишь случай, когда останова не происходит.

Сходимость метода 7 установлена в теореме 15 при тех же предположениях, что и для метода 5. Отметим, что Д. Саном был предложен близкий метод, использующий правило Тк(и,и) = и — а.

Предположение (П1). Выполняются соотношения 0 < т' < тк, тк < г" < ос. Если ик - произвольная точка из II, гк - любое

решение задачи

(G(uk) + 6-1Тк(ик,гк), и - zk) > О Vu е 17,

где 0 < в' < в < в" < оо, то найдется число 6 > 0 и константа р > 0, зависящая возможно от 6, в', в", г', т", такая что

(Tk(uk,zk),zk-uk)>pdis(uk,U*f,

как только (Тк(ик, zk), zk — ик) < <5.

Вторая часть предположения (П1) является некоторым вариантом условия (19), и, в случае представления (15), выполняется для довольно широких классов задач, включающих, в частности, задачу (14) с сильно монотонным отображением G, либо с произвольным линейным отображением G и многогранным множеством U.

Теорема 16. Пусть последовательность {«*} построена методом 7, jk =. 7 £ (0, 2) для к = 0,1,..., выполняется предположение (П1). Тогда последовательность {dis(w*, U*)} сходится к О линейно.

Таким образом, метод 7 достигает линейной скорости сходимости и в случае U ф Rn, более того, при этом отображение G може т быть немонотонным.

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

Метод 8. Выберем числа а £ (0,1), ¡S £ (0,1), в > 0. семейство отображений {Тк}, удовлетворяющее условиям (а) (<1) ¡¡2. Метод состоит в применении общей схемы I главы I, в которой процедура Dk описывается следующим образом.

Вход: точка ик £ V. Выход: вектор дк и число ак.

Шаг 1. Определить d как наименьшее число в Z+ такое, ч то выполняется (20), где Р - решение вариационного неравенства (21).

Шаг 2. Положить вк = /1нв, vk - zd. Если ик = гк. ос танов. Иначе

определить

дк = G(vk)-G(uk)~e^Tk(uk,i,k),ak = (дк,ик - vk)/\\gkf.

Заметим, что в случае, когда I/ С V, итерационная последовательность {и*} метода может содержать и недопустимые точки. М.В. Солодовым и П. Ценгом, а также Д. Саном при условиях V = Л" (V = II) предлагались близкие методы, которые используют правило Тк(и,у) = V— и. Следует отметить, что в методе 8, также в отличие от этих методов и методов 5 -7, оператор Рк зависит лишь от области определения V отображения С, что позволяет довольно просто реализовать его в случае и С V С В.'1, который часто встречается в приложениях. Если же V = Л", то Рк = I и тогда основной процесс выполняется без учета допустимого множества II. В то же время в теоремах 17, 18 для метода 8 получены такие же результаты сходимости и скорости сходимости, что и для метода 7. Таким образом, предложенный метод 8 существенно расширяет возможности комбинированных релаксационных методов, не снижая при этом скорости сходимости. При дополнительном условии типа острого минимума

где и*(и) = Pr(u, U*), в теореме 19 установлено, что методы 7 и 8 позволяют получить в этом случае решение за конечное число итераций.

В §4 предлагается комбинированный релаксационный метод для задачи (3), в котором для выбора параметров используется обобщение и модификация итерации релаксационного субградиентного метода, подобно методу 3. В дополнение к общим предположениям главы III, включающим (13), предполагается, что mtU ф 0.

Пусть р > 0 - произвольное число. Определим

Метод 9. Выберем число 9 е (0,1), ограниченные последовательности положительных чисел {а/}, {т//}. Метод состоит в при-

Vu 6 U, (G(u),u-u*(u))>0i||u-u*(u)ll. 0i > 0,

G(u) если и Е U,

5(0, р) П N(U, и) если и $ U.

менении общей схемы II главы I, в которой V = 17, а процедура Г)к определяется следующим образом.

Вход: точка и* 6 II, число Выход: вектор <7* и числа сг^, А(&+1).

Шаг 1. Положить г = 0,ги° = ик, выбрать д' £ (¿(тл1), положить р{ = д1'.

Шаг 2. Если ||р''|| < гц, то дк = О, <тк = 0, \{к + 1) = / + 1, процедура завершена.

Шаг 3. Положить ги,+1 = го° — «/р!/||р'||, определить д,+1 £ £К'+1). Если (?,'+1,р*') > 0|И|2, то ьк = го*+\ дк = д,+1, <тк = (дк, ик — vk)|\\gk\\'l, \(к + 1) = I. Процедура завершена.

Шаг 4. Положить р,+1 = Рг(0, сопу{р', д,+1}), г = г + 1 и перейти к шагу 2.

Внутренним шагом называется далее изменение индекса г в процедуре Ьк.

Теорема 20. Пусть последовательность {и*} построена методом 9, выполняются соотношения (11). Тогда:

a) количество внутренних шагов на к - Й итерации конечно;

b) существует предельная точка для {ик}, которая находится

в и*;

c) если выполняется (17), то справедливо (18).

Отметим, что реализация метода 9 не требует решения вспомогательных задач линейного или квадратичного программирования, а также линейного поиска. Мера трудоемкости метода 9, обозначаемая N(6), определяется так же, как и для метода 3, только расстояние измеряется до множества II*.

Теорема 21. Предположим, что т.м.о. С монотонно, выполняется (17), а также

Чи £ и, Уд е С(и), (д,ц-и*) >01||и-«*||, в\ > 0. (22)

для некоторого и* £ и*. Если параметры метода 9 выбраны и.1 условий (12), то найдутся числа а > 0 и г/ > 0 такие, что для всех а £ (0, и т) £ (0, г)) выполняется

Щ6)<В11п(В0/6), (23)

где. О < В0, В, < оо.

Таким образом, метод 9, по вычислительным затратам примерно эквивалентный методам усреднения (Р. Брук, A.C. Немиров-ский, Д.Б. Юдин), в отличие от них достигает оценки; соответствующей линейной скорости сходимости. Рассмотрим также случай, когда допустимое множество U задается с помощью выпуклой функции Л, т.е. U = {и £ Rn | h(n) < 0}. В этих условиях достаточно определить

и все результаты, полученные для метода 9, останутся справедли-

В §5 рассматривается задача поиска стационарной точки т.м.о. М, т.е. точки множества

при условии, что М £ 2(Нп), а также существует множество ф 0 такое, что для любого и £ Я" выполняется

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

где 8р(и) = 5(0, р)Г)М(и, и), и выполняются предположения §4. Более того, в этом случае II* = 5*. Таким образом, в §5 предлагается вместо вариационного неравенства (3) решать задачу поиска стационарной точки многозначного и в общем случае немонотонного

G(u) если h(u) < 0, dh(u) если h(u) > 0;

выми.

S* = {и* £ Rn | 0 G M(и*)}.

Vi G M (и), (t, и - и*) > 0 Vu* G S(*

отображения М. Для этой цели предлагается использовать комбинированный релаксационный метод, иДейно близкий к методу £).

Метод 10. Выберем число в £ (0,1), ограниченные последовательности положительных чисел {а/}, {/7/}. Метод состоит в применении общей схемы II главы I, в которой Рк = I, V = Яп, а процедура £>к аналогична процедуре в методе 9, с заменой т.м.о. ф на т.м.о. М.

Отметим, что итерационная последовательность {?<*'} в методе 10, в отличие от метода 9, может содержать недопустимые точки, а поскольку Рк = /, то в методе 10 нет необходимости в использовании допустимых квазинерастягивающих операторов в отношении и, но в то же время он полностью реализуем и в случае, когда допустимое множество имеет вид (10), где /г,- : Я" —► Я, г = 1,..., гп -зыпуклые, но необязательно линейные функции.

Теорема 22. Пусть последовательность {ик} построена методом 10, выполняются соотношения (11). Тогда:

a) количество внутренних шагов на к - й итерации конечно;

b) существует предельная точка для {и*}, которая находится

з 51*;

c) если 5*^ = 5*, то Шць-юо ик = и* £ 5*.

При дополнительных предположениях вида (22) для метода 10 установлена оценка трудоемкости (23), соответствующая линейной жорости сходимости.

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

В §1 главы IV описывается метод решения задачи нахождения шемента и* Е II такого, что

гп

]д* £ в,(и*), з = 1,..., т; £ {д*я, ».,-<) > 0 V», € Г,. * = 1.....ш:

•4=1

где и = («i,. ..,wm)T,

m

и= П Us\Gs : и -+n{Rs),us <= /Г, а = 1,...,т;

•S— 1

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

Для решения этой задачи предлагается комбинированный релаксационный метод, который строится на основе метода 9. Установлена сходимость метода при предположениях, подобных предположениям §4 главы III. В отличие от метода 9, допускается последовательное или параллельное выполнение частей метода, что позволяет соответственно либо сократить затраты машинной памяти, либо ускорить вычислительный процесс. Подобный метод был построен в [16] для равновесной задачи (1) с декомпозиционной структурой на основе метода 3. Отмечается, что в однозначном (гладком) случае данный подход может быть реализован на основе методов 5-7 (1) вместо метода 9 (3), соответственно.

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

В §3 описывается применение метода 9 для решения одной из наиболее известных задач экономического равновесия - линейной

модели обмена, которая сводится к решению вариационного неравенства вида (3) с многозначным отображением. Поскольку для данной задачи не гарантируется строгой монотонности G, а только выполнение условия типа (13), то используемые наиболее часто при решении подобных задач методы градиентного типа здесь не гарантируют сходимости к вектору равновесных цен. В то же время сходимость обеспечивает метод 9, не отличающийся существенно по объему вычислительных затрат, что демонстрируется на числовых примерах.

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

В §5 представлены результаты решения ряда тестовых зада1! методами, описанными в главах II и III. Результаты расчетов, а также их сравнение с результатами для других методов, показали достаточно стабильную и быструю сходимость комбинированных релаксационных методов, их пригодность для решения задач высокой размерности, а также более широкую область сходимости по сравнению с другими методами. Кроме того, по сравнению с большинством методов с аналогичным объемом вычислительных затрат на итерации методы имеют более быструю сходимость.

В заключении кратко описаны основные результаты настоящей работы.

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ

1. Коннов И.В. Применение метода сопряженных с\бградиеш он к минимизации квазивыпуклых функционалов // Исслед. по прикл. матем,- Казань, 1984.-Вып.12.-С.46-58.

2. Концов II.В. Метод типа сопряженных субградиентов для минимизации функционатов // Там же.-С.59-62.

3. Коннов И.В. Применение метода последовательной релаксации к решению экстремальных задач с полугладкими функциями // Исслед. по прикл. матем. - Казань, 1988.-Вып.15.-С.24-30.

4. Коннов И.В. Оценки эффективности релаксационных субградиентных методов// Межд. школа-семинар "Методы оптимизации и их приложения" : Тез. докл., Иркутск, 10 - 19 сентября 1989 г.- Иркутск,1989.- С.108-109.

5. Коннов И.В. О свойствах опорных и квазиопорных. векторов // Исслед. по прикл. матем.- Казань, 1990.-Вып.17.-С.50-57.

6. Коннов И.В. Сходимость релаксационных методов решения задач недифференцируемой оптимизации с ограничениями // Там же.-С.57-71.

7. Коннов И.В. Оценки трудоемкости для методов последовательной релаксации// Исслед. по прикл. матем.- Казань, 1992.-Вып. 19.-С.34-51.

8. Коннов И.В. Комбинированные субградиентные методы поиска седловых точек // Изв. вузов.Математика.- 1992.-№10.-С.30-33.

9. Коннов И.В. Двухуровневый субградиентный метод для поиска седловых точек выпукло-вогнутой функции // Ж. вычисл. мат. и мат. физ.- 1993.-Т.33,№4.-С.495~502.

10. Коннов И.В. Комбинированные релаксационные методы для поиска точек равновесия и решения смежных задач // Изв. вузов.Математика,- 1993.-№2.-С.46-53.

11. Коннов И.В. Комбинированный метод для вариационных неравенств // Информ. бюллетень АМП.- Екатеринбург,1993.-Вып.4.-С.64.

.2. Кошюв И.В. Методы недифференцируемой оптимизации.- Казань: Казанск. ун-т, 1993.-100 с.

.3. Коннов И.В. О скорости сходимости комбинированных релаксационных методов // Изв.вузов.Математика.- 1993.-№12.-С.89-92.

.4. Кошюв И.В. Применение комбинированного релаксационного метода для поиска точек равновесия квазивыпукло-вогнутой функции // Изв. вузов. Математика.- 1994.- №12.-С.70-75.

.5. Коннов И.В. Об одном общем подходе к решению равновесных задач // Информ. бюллетень АМП.- Екатеринбург, 1995.-Вып.5.-С. 123-124.

.6. Коннов И.В. Комбинированный релаксационный метод, использующий декомпозицию, для поиска точек равновесия // Ж. вычисл. мат. и мат. физ,- 1995.-Т.35, №3.-С.352-359.

.7. Коннов И.В. Комбинированный релаксационный метод для поиска векторного равновесия // Изв. вузов.Математика.-1995.-№12.-С.54-62.

.8. Коннов И.В. Один общий подход к нахождению стационарных точек и решению смежных задач // Ж. вычисл. мат. и маг. физ,- 1996.-Т.36, №5.-С.40-50.

9. Кошюв И.В. О существовании решений дуального вариационного неравенства при квазимонотонном отображении// М-лы Всероссийского семинара "Теория сеточных методов для нелинейных краевых задач". Казань, 24 - 28 июня 1996 г.- Казань. 1996.- С.61-62.

0. Коннов И.В. О применении проективных преобразований в комбинированных релаксационных методах // Там же.- С.63 65.

21. Концов И.В. Применение метода типа линеаризации при решении негладких равновесных задач // Изв. вузов.Математика.-

1996.-№12.-С.54-62.

22. Концов И.В. Комбинированные релаксационные методы с линейной скоростью сходимости // Информ. бюллетень АМП.-Екатерипбург,1997.-Вып.7.-С. 135-137.

23. Koimov I.V. Combined relaxation methods and their complexity estimates // 15tli Intern. Symp. on Math. Programming : Abstracts, Ann Arbor, USA, 15-19 August 1994.- Ann.Arbor, 1994.-P.121.

24. Konnov I.V. Vec tor variational inequalities and inverse vector optimization problems//4tli Intern. Workshop "Multiple Criteria and Game Problems under Uncertainty": Abstracts, Orekhovo-Zuevo, 8-14 Sept. 1996.- Moscow, 1996.-P.44.

25. Konnov I.V. A combined method for smooth equilibrium problems with nonlinear constraints // Optimiz. Methods and Software. -

1997,- V.7.№3.-P.311 324.

26. Konnov I.V., Yao J.C. On the generalized vector variational inequality problem// J. Math. Anal, and Appl.-1997.- V.206,№1.-