Решение бесконечных систем выпуклых неравенств фейеровскими методами

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

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

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

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

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

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

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

Класс таких отображений относительно множества М обозначается через 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 — 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.