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

• Пацко, Сергей Валерьевич
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Пацко, Сергей Валерьевич

ВВЕДЕНИЕ

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).

Список литературы диссертационного исследования кандидат физико-математических наук Пацко, Сергей Валерьевич, 2005 год

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.