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

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

РЕШЕНИЕ БЕСКОНЕЧНЫХ СИСТЕМ ВЫПУКЛЫХ НЕРАВЕНСТВ ФЕЙЕРОВСКИМИ

МЕТОДАМИ

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

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Екатеринбург - 2005 г.

Работа выполнена в Институте математики и механики Уральского отделения РАН. Научный руководитель:

академик РАН И.И. Еремин

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

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

кандидат физико-математических наук, доцент Л.А.Истомин

Ведущая организация:

Челябинский государственный университет

Защита состоится .............. 2005 года в

часов на заседании диссертационного совета К 004.006.01 по защите диссертаций на соискание ученой степени кандидата наук в Институте математики и механики Уральского отделения РАН по адресу: 620219, г.Екатеринбург, ул.Софьи Ковалевской, 16.

С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН.

Автореферат разослан ................ 2005 г.

Учёный секретарь / ^^

диссертационного совета / //^

к.ф.-м.н., с.н.с. /пац/^^ В.Д. Скарин

Г"?* к

Актуальность темы.

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

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

Следующий шаг к обобщению систем неравенств - это континуальные системы, которым и посвящена диссертация.

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

1РОС. НАЦИОНАЛЬНАЯ

библиотека

с именами Моцкина 1 и Агмона 2 применительно к конечным системам линейных неравенств. В них были рассмотрены методы циклического проектирования и проектирования на наиболее удаленное полупространство из числа полупространств, определяемых неравенствами рассматриваемой системы.

Позже появились работы Мерзлякова3, Еремина4, 5, Брэг-мана6, Гурина-Райка 7 и др.

В серии работ И.И.Еремина 8, 9 были предложены принципиальные обобщения, введено понятие фейеровского оператора, расширена терминологическая и понятийная база

1 Motzhin T.S., Schömberg J.J. The Relaxation Method for Linear Inequalities // Cañad. J. Math. - 1954. ~ 6, N 3. - S. 393-Щ.

2Agmon S. The Relaxation Method for Linear Inequalities // Cañad. J. Math. - 1954- - 6, N3. - S. 382- 392.

3 Мерзляков Ю.И Об одном релаксационном методе решения систем линейных неравенств //Журнал выч.мат-ки и мат.физики. — 1962. - т. 2, № 3.

4Еремин И.И. Обобщение релаксационного метода Моцкина-Агмона // Успехи математических наук. — 1965. — т. XX, вып. 2 (122). — С. 183-187.

5 Еремин И.И. Релаксационный метод решения систем неравенств с выпуклыми функциями в левых частях // ДАН СССР. — 1965. — т. 160, X» 5.

вВрэгман JI.M. Нахождение общей точки выпуклых множеств методом последовательного проектирования //ДАН СССР. — 1965. — т. 162, № 3. - С. 487-490.

7Турин Л.Г., Поляк Б. Т., Райк Э.В. Методы проекций для отыскания общей точки выпуклых множеств // Журнал выч.мат-ки и мат.физики. - 1967. - т. 7, № 6. - С. 1211-1228

8Еремин И.И. К общей теории фейеровских отображений // Математические записки УрГУ. — 1969. — т. 7, № 2. — С. 50— 58.

9 Еремин И. И. Применение метода фейеровских приближений к решению задач выпуклого программирования с негладкими ограничениями // Журнал выч.мат-ки и мат.физики. — 1969. — т. 9, № 5. — С. 1153-1160.

MííO*r f J

; 1 ,

ь .......... 4

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

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

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

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

10 Черников С.Н. Линейные неравенства. // М., Наука. — 1968.

11 Еремин И. И. Противоречивые модели оптимального планирования. // М., Наука. - 1988, С. 93

Цель работы состоит в следующем:

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

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

3. Разработать методы синтеза фейеровских отображений с несовпадающими пространствами их образов.

4. Применить метод фейеровских отображений к решению вогнуто-выпуклых игр.

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

Научная новизна.

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

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

2. Исследованы бесконечные системы линейных и выпуклых неравенств, имеющие особенности в своей структуре. Приведен конкретный вид фейровских отображений, приводящих к решению таких однотипных систем неравенств.

3. Решен вопрос синтеза нескольких фейровских отобра-

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

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

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

Апробация работы. Результаты диссертации докладывались на региональной молодежных конференциях "Проблемы теоретической и прикладной математики" (1999, 2002, 2003 гг.), на Всероссийской конференции "Математическое программирование и приложения"(1999, 2003 гг.), семинарах отдела математического программирования ИММ УрО РАН, а также на ежегодных сессиях молодых ученых ИММ УрО РАН (1999-2004гг.).

Работа поддержана грантом НШ-792.2003.1.

Публикации. Основные результаты диссертации опуб-

ликованы в 8 работах, список которых приводится в конце автореферата.

Структура и объём работы. Диссертация состоит из введения и 4 глав, разбитых на 17 параграфов. Объём диссертации 78 страниц, набранных в текстовом редакторе LATEX. Библиографический список содержит 25 наименований.

Краткое содержание работы

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

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

В §§1.1 и 1.2 первой главы даются необходимые определения и свойства фейеровских отображений и порождаемых ими процессов, которые используются в дальнейшем. В числе важных фактов приведена теорема о сходимости последовательности, порождаемой замкнутым отображением </?(•) G Fm в силу рекуррентного соотношения a^+i € <р(хк) при произвольном начальном xq € Rn, при этом предел последовательности принадлежит множеству М.

В §1.3 рассматривается вариант организации итерационного процесса решения совместной счетной системы выпуклых неравенств f3(x) < 0, j = 1,2,..., исходя из рекуррентного соотношения x^+i е ipk{xk), к = 0,1,2,...

Формулируется теорема о сходимости данного процесса к некоторому решению рассматриваемой системы:

Теорема 1.3.2 Пусть система выпуклых неравенств fj(x) <0, j — 1,2,..., совместна, при этом, выполнено условие

d{x) := sup fj(x) < +оо, Ух € Rn. U)

Положим

dk(x) := тах/Дх)

и

tpk(x) := {x - \kjrQhk\hk € ddk(x)}, Xk e [S, 2 - S\, S > 0;

ddk(x)— субдифференциал выпуклой функции dk(x). В приведенном соотношении при dk(x) < 0 полагается <рк(х) = х.

Тогда процесс хк+г € 4>к{хк), к = 0,1,2,... сходится к некоторому решению рассматриваемой системы.

В заключительном § 1.4 первой главы рассматривается процесс для счетной, вообще говоря, несовместной системы линейных неравенств над гильбертовым пространством H и доказывается теорема о его сходимости к точке квадратичной аппроксимации этой системы, при дополнительном ограничении x G S С Н, где S— выпуклый компакт.

В Главе II диссертации излагается обоснование основной теоремы, которая устанавливает сходимость специально сконструированного итерационного процесса

xk+i e Prs<pk (xk)

к некоторому решению х системы

fa{x) <0, Va е J, xeS.

В приведенной системе {/а(ж)} — выпуклые на R" функции для всех a € J, S — выпуклое замкнутое множество из

Rn, J — произвольное множество индексов (конечное, счетное или континуальное).

Как видно из выписанной системы, ее отличие от совместной счетной системы выпуклых неравенств

fj(z) < 0, ¿ = 1,2,...,

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

Континуальная мощность множества индексов неравенств системы приводит к необходимости наложения дополнительных условий, выполнение которых гарантирует сходимость итерационного процесса к решению такой системы. Среди таких условий - представление индексного множества J цепочкой его подмножеств Jk '■

Л С J2 С ... С J к С ...,

при этом (J Jk = J, а также предположение достижимости

(fc)

супремума функции fa(x) в каждой точке х :

d(x) :— sup fQ(x) < +00, Vx. aeJ

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

Изучается поведение последовательности вспомогательных функций dk(xk) и их субдифференциалов hk € ddk(xk) при стремлении {х^} к некоторой точке х . Указанные вспомогательные функции и их субдифференциалы участвуют в построении итерационного фейеровского процесса

хк+1 = Prs{xk - Хк ■ hk),

ИМ

ю

сходящегося к решению континуальной системы неравенств. Именно поэтому знание свойств последовательности функций dk(xk) и hk £ ddk(xk) необходимо для проведения доказательства основной теоремы сходимости.

В § 2.2 раскрывается смысл основной теоремы о сходимости итерационного фейеровского процесса к решению систе-• мы выпуклых неравенств (конечной, счетной или контину-

альной) и приводится доказательство данного факта. А Теорема 2.2.1 Пусть для совместной системы выпук-

лых неравенств fv(x) <0, Vi> G V, х Е S выполнены условия

v1cv2c...cvkc..., \Jvk = v,

(k)

d(x) := sup fv(x) < +oo, Ух. vev

и множество S телесно. Тогда при произвольном начальном х0 G R" процесс, рекуррентно задаваемый соотношением

d+(xk)

Xk+1 := Prs(xk - Лk Л ,l2 • hk),

\\hk\\

при произвольном начальном x0 G Rn, hk G ddk(xk) сходится к некоторому решению х' системы

/„(:г) <0, Vv G V, х G S,

' т.е. х' G М.

Глава III посвящена изучению систем линейных и выпуклых неравенств, имеющих особенности в своей структуре. Такую специфику целесообразно учитывать при построении итерационных, например, фейеровских операторов.

В § 3.1 приведены примеры структурированнных систем.

Особое место занимает так называемый основной тип континуальной системы (тип W):

fa(x)<0, VaeK

Для нахождения решения системы неравенств типа W строится следующее отображение:

= (х)},

где

d(x) = max fa(x)(= fax{x)).

aÇ.V

В параграфе §3.2 третьей главы показывается, что приведенное выше отображение является замкнутым и фейеров-ским относительно множества решений континуальной системы неравенств типа W. Данный факт позволяет сделать вывод о сходимости рекуррентного процесса, порожденного отображением <р(х), к некоторому решению системы типа W.

Также рассматривается вариант континуальной системы неравенств типа W с дополнительным требованием на область изменения аргумента: х € S. В этом случае формируется обобщенное отображение

ф(х) := Prs(ip(x)).

Доказано, что последовательность {х^}, порождаемая соотношением %k+\ € Ф{хк) при произвольном начальном | х0 € Rn, сходится к решению системы типа W с дополнительным ограничением х G 5". »

Для иллюстрации континуальных методов в §3.3 рассмотрен случай интервально заданной системы линейных неравенств. В анализе такой ситуации возникает интересная задача максимизации кусочно-линейной функции на паралле-пипеде. Приведен алгоритм решения этой задачи.

В параграфе §3.4 изучен случай системы, объединяющий конечное число подсистем типа Ж Система в данном случае имеет вид

/3{х,у3) < 0, \/ь3 е У3, хе^'СЙ", з = 1 ,...,т.

Здесь ь3, V/ играет роль индекса а в рассмотренной ранее системе типа IV. Конструирование итерационного процесса, решающего такую систему, требует модернизации функций невязки, приобретающих вид

¿3{х) := шах ^ = /3(х,р3(х)).

Далее формируются отображения ф3{х), ] = 1 ,...,т, то есть

ф3(х) := Рг5. (<р,(х)),

х, ¿3(х) = 0; = < {* - Л, ¿^Л, I Л, е ¿Ш*. «,(*)). ь,(х) €

А, € (0,2), з = 1,..., т; З3(х) := {^(я) | ^(ж) = ¡3{х, ь^х))}.

Окончательно искомый фейеровский процесс выглядит следующим образом :

то т

Хк+1 6 X] агФг(^к), = а<>0, * = 1 ,...,771.

г-1 г=1

Четвертая глава диссертации посвящена синтезу (сращиванию) отдельных фейеровских отображений <р3(-) € Гщ, 3 — 1,..., т с разными пространствами их образов в единое отображение (р(-).

В § 4.1 даются пояснения к постановке вопроса. Рассмотрен пример отображений {^(ач)}"-!, <fio(xi, ■ ■ ■, хп), хг € R™1, Мг Fixip1, г = 0,1,...,п. Одна из схем синтеза выписанных {<рг}?= о состоит в операции подстановки хг —> <*рг(х{) в аргументах отображения ipo(-), т.е.

<Po(<Pi(xi), ■ • •, Vu M) т(х 1, ■ ■ ■ ,хп).

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

Поясним это на примере. Пусть даны (pi(x,z) € FMl, tp2(y, z) € Fm2, leR"1, y G R712, -г E RnK Положим

(pi{x,z) = [x,zi], <p2(y,z) = [y,z2]-,

где черта над векторами означает:

х— алгебраический след (x,z) в R"1; у— алгебраический след (p2(y,z) в R"2; z\— алгебраический след ф\{х, z) в R"3; z2— алгебраический след (p2(x,z) в R"3. Образуем отображения

V\{x,y,z) := %y,zt], Щ{х,у,г) := [x,y,z2]

и

(pa(x,y,z) := ойрх(х,у,г) + (1 - а)Щ(х, у, z), a G (0,1).

В § 4.1 доказывается :

Fix(pa(x,y,z) = = [ж, 2], ¥>г(у,5) = [у, 2]}.

В § 4.2 проиллюстрированная схема распространяется на общую (зернистую) структуру матрицы аргументов отображений (pj(xt\i б Ij), где U^j/j — {1,... , n}.

В § 4.4 предложен еще один вариант синтеза для исходных отображений щ(х,у),<р2(у, г), <р3(г,х).

В § 4.5 рассматривается общая схема синтеза из § 4.2 при наиболее важных и интересных (с точки зрения приложений) структурах аргументов отображений {срг}.

Содержание § 4.6 состоит в уточнении вида синтезирующих отображений в предположении, что исходные отображения заданы так называемыми М— разделяющими парами. '* Наконец, заключительный параграф 4.7 посвящен при-

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

ЗАКЛЮЧЕНИЕ

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

Получены следующие основные результаты: I 1. Предложен и исследован итерационный метод фейеров-

ского типа решения системы выпуклых неравенств континуальной мощности.

2. Рассмотрен вариант метода для структурированных (однотипных)систем.

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

4. Разработан метод синтеза (сращивания) конечной совокупности фейеровских отображений с различными пространствами их образов.

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

Публикации по теме диссертации

[1] Пацко C.B. Релаксационный метод решения гладких вогнуто-выпуклых игр // Проблемы теоретической и прикладной математики (Тезисы докладов 30-й Региональной молодежной конференции)Екатеринбург: УрО РАН, 1999. - С. 73-74.

[2] Пацко C.B. Фейеровский итерационный метод решения систем выпуклых неравенств континуальной мощности // Информационный бюллетень N 8 Ассоциации матем. программирования (Тезисы докладов). - Екатеринбург: УрО РАН, 1999. - С. 221-222.

[3] Пацко C.B. Фейеровские отображения для несовместных систем линейных неравенств счетной мощности // Проблемы теоретической и прикладной математики (Труды 33-й Региональной молодежной конференции). - Екатеринбург: УрО РАН, 2002. -С. 290-293. (1

[4] Пацко C.B. Аппроксимация решения несовместных систем линейных неравенств счетной мощности при ограничении на множество аргументов// Проблемы теоретической и прикладной математики (Труды 34-й Региональной молодежной конференции).- Екатеринбург: УрО РАН, 2003. - С. 208-211.

[5] Пацко С.В. Синтез фейеровских отображений, заданных М-разделяющими ларами // Информационный бюллетень N 10 Ассоциации матем. программирования (Тезисы докладов). - Екатеринбург: УрО РАН, 2003. - С. 200-201.

[6] Patsko S.V. Fejer Methods for Solving Infinite Systems of Convex Inequalities // Yugoslav Journal of Operations Research. - 2001. - Vol.11, N2. -P. 131-150.

v [7] Пацко С.В. Фейеровские процессы для бесконечных си-

стем выпуклых неравенств // Известия Уральского Государственного Университета, серия "Математика и механика". - 2002, Вып. 4, С. 129-147.

[8] Eremin I.I., Patsko S.V. Fejer Processes for Infinite Systems of Convex Inequalities // Proceedings of the Steklov Institute of Mathematics, Suppl. 1. - 2002. P. S32-S51.

Падко Сергей Валерьевич

РЕШЕНИЕ БЕСКОНЕЧНЫХ СИСТЕМ ВЫПУКЛЫХ НЕРАВЕНСТВ ФЕЙЕРОВСКИМИ

МЕТОДАМИ

Автореферат

Подписано в печать ... 2005. Формат 60x84 1/16. Объем 1.0

п.л.

Тираж 100 экз. Заказ №70 Размножение с готового оригинал-макета в типографии

УрО РАН

620219, Екатеринбург, ул.С.Ковалевской, 18

1

t

4

Ш -9 20 3

РНБ Русский фонд

2006-4 5478

ВВЕДЕНИЕ

1 ИТЕРАЦИОННЫЕ ПРОЦЕССЫ

ФЕЙЕРОВСКОГО ТИПА

1.1 Фейеровские отображения и их свойства.

1.2 Фейеровские процессы и их свойства.

1.3 Фейеровские процессы для счетных систем выпуклых неравенств.

1.4 Счетные несовместные системы линейных неравенств.

2 КОНТИНУАЛЬНЫЕ СИСТЕМЫ ЛИНЕЙНЫХ

И ВЫПУКЛЫХ НЕРАВЕНСТВ

2.1 Предварительные результаты

2.2 Основная теорема.

3 СТРУКТУРИРОВАННЫЕ СИСТЕМЫ ЛИНЕЙНЫХ И ВЫПУКЛЫХ НЕРАВЕНСТВ

3.1 Примеры структурированных систем.

3.2 Основной тип континуальной системы (тип W).

3.3 Интервально заданная система линейных неравенств.

3.4 Случай системы, объединяющей конечное число подсистем типа W.

4 СИНТЕЗ ФЕЙЕРОВСКИХ ОТОБРАЖЕНИЙ С НЕСОВПАДАЮЩИМИ ПРОСТРАНСТВАМИ ИХ

ОБРАЗОВ И ПРИЛОЖЕНИЯ

4.1 Постановка вопроса.

4.2 Общий случай синтеза конечной последовательности Mj- фейеровских отображений, j = 1,., m.

4.3 Анализ ситуации отображений (pi(xi), i = 1,., п, <po(xi,. ,xn)

4.4 Синтез отображения ip(x, у, z) из отображений ip\(x, у), cp2{y,z), ip2(z,x)

4.5 Частные реализации синтеза фейеровских отображений из

§4.2.

4.6 Синтез фейеровских отображений, заданных М- разделяющими парами

4.7 Применение к решению вогнуто-выпуклых игр.

В диссертации рассматривается применение фейеровских методов к решению континуальных систем линейных и выпуклых неравенств. В основе лежит построение фейеровских операторов (отображений из Rn в R™, либо из Rn в 2R"), которые порождают последовательности, сходящиеся к решению соответствующей системы неравенств.

Проблематика такого рода возникла из работ [5, б], посвященных конечным системам линейных неравенств. В этих работах были исследованы методы циклического проектирования и проектирования на наиболее удаленное полупространство из числа полупространств, определяемых неравенствами рассматриваемой системы.

Некоторые обобщения методов проектирования были рассмотрены в работах [9,10, 11], а также в серии работ И.И.Еремина [1]-[4]. В последних были предложены принципиальные обобщения, введено понятие фейеровского оператора, расширена терминологическая и понятийная база для методов фейеровского типа, доказан ряд основополагающих теорем, что в совокупности позволило говорить о создании теории фейеровских отображений и порождаемых ими процессов.

Дадим определение М-фейеровского отображения.

Пусть М С Rn и М ф 0.

Отображение Т 6 {Rn —» Rn} называется М- фейеровским, если Т(у)=у, ||Т(Ж) - у\\ < 2/||, V у G М, Vx<£M.

Здесь и далее под ||ж|| понимается евклидова норма элемента х.

Класс таких отображений относительно множества М обозначается через Fm- Отображения Т 6 Fm обладают рядом замечательных свойств. Отметим некоторые из них:

1°. Если М допускает хотя бы одно Т Е Fm, то есть Fm ф 0, то множество М является автоматически выпуклым и замкнутым.

2°. Если Т из FM непрерывен, то {xk+i = Т(хА:)}^ х е М при произвольном начальном xq Е R". тп

3°. Если 7) Е FMj, j = 1,. • •, m и M := nf=1Mjt то Т ajTJ е

3=1 m aJ > аэ ~ а также • • СТт{х)) £ Fm-j=i

Системы неравенств, к которым применяется фейеровская технология, могут быть классифицированы по признакам:

- линейные и выпуклые;

- конечные, счетные и континуальные.

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

Эту конструкцию можно описать следующим образом (схема экстремальной релаксации). Пусть дана система выпуклых неравенств fa(x) < о, aeJ, (0.0.1) где fQ(х)—выпуклые на Rn функции, J— произвольное множество индексов (конечное, счетное, континуальное). Положим d(x) := sup/+(a:), f+{x) := max{/(ar),0}. aeJ

Обозначим

J(x) := {a\ d(x) = /+(*)}•

Построим отображение (оно же - оператор для решения системы (0.0.1)):

Т(х) := х, если d{x) < 0, иначе

Т(х) := {х - h Е dfa(x),a Е J(s)}, (0.0.2) где Л Е (0,2) (коэффициент релаксации), dfa(x)— субдифференциал выпуклой функции /а(ж) в точке ж. Обратим внимание на то, что если d(x) > 0, то h из dfa(x) из (0.0.2) отличен от нуля. Сама структура отображения (0.0.2) говорит о том, что оно, вообще говоря, не является однозначным. В этой ситуации требуются некоторые ограничения, которые обеспечивают смысловую корректность этого отображения (например, достижимость операции sup faix))t а также свойство для Т, родственное непрерывности, а именно aeJ свойство замкнутости. Это свойство здесь понимается в следующем смысле: хк} х, у, ук е Т(хк) =$> у € Т(х). (0.0.3)

Основная теорема о сходимости итерационного процесса для континуальной системы выпуклых неравенств будет связана с конструкцией оператора вида (0.0.2) [Глава 2].

Ниже кратко изложено содержание диссертации по главам и параграфам.

В §§1.1 и 1.2 первой главы даются необходимые определения и свойства фейеровских отображений и порождаемых ими процессов, которые используются в дальнейшем. В числе важных фактов приведена теорема о сходимости последовательности, порождаемой замкнутым отображением <£>(•) £ Fm в силу рекуррентного соотношения хк+\ Е <р(хк) при произвольном начальном xq Е Rn, при этом предел последовательности принадлежит множеству М. В §1.3 рассматривается вариант организации итерационного процесса решения совместной счетной системы выпуклых неравенств fj(%) < О? j = 1, 2,., исходя из рекуррентного соотношения хк+\ Е <рк(хк), к = 0,1,2,., где dk(x) рк(х) := {х - \kjj-^hk\ hkeddk(x)}, АЛ G [J, 2 - <J], 5 > 0; dk(x) := max fj(x), 3 = 1,.,k ddk{x)— субдифференциал выпуклой функции dk(x). В приведенном соотношении при dk(x) < 0 полагается срк(х) — х. Формулируется теорема о сходимости данного процесса к некоторому решению рассматриваемой системы. Эта теорема является частным случаем теоремы 1.3.1, обоснование которой вытекает из более общей теоремы 2.2.1, относящейся к континуальным системам.

В заключительном § 1.4 первой главы рассматривается процесс для счетной, вообще говоря, несовместной системы линейных неравенств над гильбертовым пространством Н и доказывается теорема о его сходимости к точке квадратичной аппроксимации этой системы (теорема 1.4.1) при дополнительном ограничении х Е S С Н, где 5— выпуклый компакт.

В главе II излагается обоснование основной теоремы 2.2.1, которая устанавливает сходимость специально сконструированного итерационного процесса хш Е PrS(fk (хк) к некоторому решению х системы fa(x) <0, \/а Е J, xes.

В приведенной системе {fa{x)} ~~ выпуклые на Rn функции для всех а Е J, S — выпуклое замкнутое множество из Rn, J — произвольное множество индексов (конечное, счетное или континуальное).

Как видно из выписанной системы, ее отличие от совместной счетной системы выпуклых неравенств fj(x)< 0, i = 1,2. рассмотренной в первой главе, заключается в числе неравенств системы, а также в наличии дополнительного ограничения на область изменения аргумента х: х Е S.

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

Ji С J2 С . С J и С ., при этом (J Jk = J, а также предположение о достижимости супремума се-(*) мейства функций fa(x) в каждой точке х : d(x) := sup fa(x) < +оо, Ух. aeJ

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

В леммах 2.1.1 и 2.1.2 изучается поведение последовательности значений dk(xk) вспомогательных функций dk(x) и последовательности субградиентов hk Е ddk(xk) при стремлении {гса;} к некоторой точке х . Указанные вспомогательные функции и их субградиенты участвуют в построении итерационного фейеровского процесса о / х dk(xk) и ч хк+1 := Prs{xk - Afc • hk), сходящегося к решению континуальной системы неравенств. Именно поэтому знание свойств последовательности значений dk{xk) и субградиентов h*k £ ddk{xk) необходимо для проведения доказательства основной теоремы сходимости.

В § 2.2 раскрывается смысл основной теоремы о сходимости итерационного фейеровского процесса к решению системы выпуклых неравенств (конечной, счетной или континуальной) и приводится доказательство сходимости. В качестве следствия формулируется утверждение о сходимости фейеровского процесса (1.3.3), изученного в главе I, к решению счетной системы выпуклых неравенств (1.3.4).

1. Еремин И.И. Обобщение релаксационного метода Моцкина-АгмонаУспехи математических наук. — 1965. — т. XX, вып. 2 (122). — С. 183-187.

2. Еремин И.И. Релаксационный метод решения систем неравенств с выпуклыми функциями в левых частях // ДАН СССР. — 1965. — т. 160, № 5.

3. Еремин И.И. К общей теории фейеровских отображений // Математические записки УрГУ. 1969. - т. 7, № 2. - С. 50-58.

4. Еремин И.И. Применение метода фейеровских приближений к решению задач выпуклого программирования с негладкими ограничениями // Журнал выч.мат-ки и мат.физики. — 1969. — т. 9, № 5. — С. 1153—1160.

5. Motzkin T.S., Schoenberg J.J. The Relaxation Method for Linear Inequalities // Canad. J. Math. 1954. - 6, N 3. - S. 393-404.

6. Agmon S. The Relaxation Method for Linear Inequalities // Canad. J. Math. 1954. - 6, N 3. - S. 382-392.

7. Еремин И.И., Мазуров В.Д. Нестационарные процессы математического программирования. (Глава II: Итерационные процессы фейеровского типа, С. 47-100) М.: Наука, 1979. - 228 с.

8. Еремин И.И. Теория линейной оптимизации. — УрО РАН, г. Екатеринбург, изд-во "Екатеринбург", 1999. — 312 с.

9. Мерзляков Ю.И. Об одном релаксационном методе решения систем линейных неравенств //Журнал выч.мат-ки и мат.физики. — 1962. — т. 2, № 3.

10. Еремин И.И. О скорости сходимости в методе фейеровских приближений // Математическая экономика. — 1968. — т. 4, вып. 1. — С. 53—60.

11. Еремин И.И. Методы фейеровских приближений в выпуклом программировании // Математические заметки. — 1968. — т. 3, вып. 2. — С. 217-234.

12. Еремин И.И., Попов Л.Д. Параллельные фейеровские методы для сильно структурированных систем линейных неравенств и уравнений // ИММ УрО РАН, Алгоритмы и программные средства параллельных вычислений. — 2002. — вып. 5.

13. Тарасова Т.А. Об одном итерационном методе решения бесконечных систем выпуклых неравенств // УрО АН СССР, г. Свердловск, кн. "Методы фейеровского типа в выпуклом программировании". — 1975. — С. 58—61.

14. Бесконечные антагонистические игры. — Сборник статей под редакцией Н.Н.Воробьева. М. — Изд-во физ.-мат. лит., 1963, — 504 с.

15. Плотников С.В. Методы проектирования в задачах нелинейного программирования. Диссертация на соискание ученой степени кандидата физико-математических наук. — Свердловск, АН СССР, 1983, — 126 с.

16. Пацко С.В. Релаксационный метод решения гладких вогнуто-выпуклых игр // Проблемы теоретической и прикладной математики: Тезисы докладов 30-й Региональной молодежной конференции. Екатеринбург, 1999, С. 73-74.

17. Пацко С.В. Фейеровский итерационный метод решения систем выпуклых неравенств континуальной мощности // Информационный бюллетень №8 конференции "Математическое программирование и приложения". Екатеринбург, 1999, С. 221-222.

18. Пацко С.В. Фейеровские отображения для несовместных систем линейных неравенств счетной мощности // Проблемы теоретической и прикладной математики: Труды 33-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2002, С. 290-293.

19. Пацко С.В. Синтез фейеровских отображений, заданных М—разделяющими парами / / Информационный бюллетень №10 конференции "Математическое программирование и приложения". Екатеринбург, 2003, С. 200-201.

20. Patsko S.V. Fejer Methods for Solving Infinite Systems of Convex Inequalities // Yugoslav Journal of Operations Research, 11(2001), N 2, pp. 131 — 150.

21. Пацко С.В. Фейеровские процессы для бесконечных систем выпуклых неравенств // Известия Уральского Государственного Университета, серия "Математика и механика", Вып. 4, Екатеринбург, 2002, С. 129—147.

22. Eremin I.I., Patsko S.V. Fejer Processes for Infinite Systems of Convex Inequalities // Proceedings of the Steklov Institute of Mathematics, Suppl. 1, 2002, pp. S32-S51.