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

• Автор: Пацко, Сергей Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Екатеринбург
• Количество страниц: 78 с.

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

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

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

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

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

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

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

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

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

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

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

3.1 Примеры структурированных систем
3.2 Основной тип континуальной системы (тип IV)
3.3 Интервалыю заданная система линейных неравенств
3.4 Случай системы, объединяющей конечное число подсистем типа IV
4 СИНТЕЗ ФЕЙЕРОВСКИХ ОТОБРАЖЕНИЙ С НЕСОВПАДАЮЩИМИ ПРОСТРАНСТВАМИ ИХ
ОБРАЗОВ И ПРИЛОЖЕНИЯ
4.1 Постановка вопроса
4.2 Общий случай синтеза конечной последовательности М,- фейеровских отображений, у = 1 т
4.3 Анализ ситуации отображений <#(:г;), г = 1,... ,п, <Ро(®1> • • •!х„)
4.4 Синтез отображения (р(х, у, г) из отображений щ (а;, у), <Р2{у,г), <р3(г,х)
4.5 Частные реализации синтеза фейеровских отображений из §4
4.6 Синтез фейеровских отображений, заданных М- разделяющими парами
4.7 Применение к решению вогнуто-выпуклых игр
СПИСОК ЛИТЕРАТУРЫ

В диссертации рассматривается применение фейеровских методов к решению континуальных систем линейных и выпуклых неравенств. В основе лежит построение фейеровских операторов (отображений из К” в 11", либо из К” в 2К"), которые порождают последовательности, сходящиеся к решению соответствующей системы неравенств.
Проблематика такого рода возникла из работ [5, б], посвященных конечным системам линейных неравенств. В этих работах были исследованы методы циклического проектирования и проектирования на наиболее удаленное полупространство из числа полупространств, определяемых неравенствами рассматриваемой системы.
Некоторые обобщения методов проектирования были рассмотрены в работах [9, 10, 11], а также в серии работ И.И.Еремина [1]—[4]. В последних были предложены принципиальные обобщения, введено понятие фейеровского оператора, расширена терминологическая и понятийная база для методов фейеровского типа, доказан ряд основополагающих теорем, что в совокупности позволило говорить о создании теории фейеровских отображений и порождаемых ими процессов.
Дадим определение М-фейеровского отображения.
Пусть М С К" и М ф 0.
Отображение Т е {Я71 -» Я”} называется М- фейеровским, если Т{у) = У, ]|Г(ж) — у\ < \х — ?/||, V у € М, Ух^М.
Здесь и далее под ||ж|| понимается евклидова норма элемента х.
Класс таких отображений относительно множества М обозначается через Д/и. Отображения Т 6 Дм обладают рядом замечательных свойств

метим некоторые из них:
1°. Если М допускает хотя бы одно Т £ Fm, то есть Fm ф 0, то множество М является автоматически выпуклым и замкнутым.
2°. Если Т из Fm непрерывен, то {Xk+i — Т(а:*.)}£10 -> х Е М при произвольном начальном xq Е R".
• m
3°. Если Tj Е FMj, j — 1,... ,тп и М П=iMj, то Т := ^ afTj Е Fm,

aj > 0, dj = 1, а также Т{... (Tm(x)) £ Fm-з
Системы неравенств, к которым применяется фейеровская технология, могут быть классифицированы по признакам:
- линейные и выпуклые;
- конечные, счетные и континуальные.
В настоящей диссертации исследуются методы решения континуальных

' линейных и выпуклых систем неравенств, причем в основу построения соответствующих операторов кладется одна из базовых конструкций, предложенная ранее И.И.Ереминым [7].
Эту конструкцию можно описать следующим образом (схема экстремальной релаксации). Пусть дана система выпуклых неравенств
fa{x) <0, а £ J, (0.0.1)
где fa(x)—выпуклые на Rn функции, J— произвольное множество индексов 4 (конечное, счетное, континуальное).
Положим
d{x) :=sup/+(æ), f+{x) := max{/(x), 0}.

Обозначим
J(x) := {a d(x) = /+(*)}•
Наравне с задачей (3.3.7) выпишем задачу
шах [{й,г)~ 7]+. (3.3.9)
Н,7]6П„,7
Справедливо соотношение:
рр<(3.3.9) = | 7’ (3.3.10)
[0, 7 < 0.
Лемма 3.3.1 позволяет конструктивно вычислять значение функции невязки <1{х), заданной соотношением (3.3.6). Действительно, поскольку справедливо равенство

4*) = X]. тах [(а,-, ж) - Ь,-]+,
то отыскание значения с!(х) сводится к решению т задач того типа, который рассмотрен в лемме 3.3.1.

Введем обозначение /у(х) := У~^[(а^, т) — 6у]+. Так что сильное решение

системы (3.3.1) - это решение системы
/»(*) < о, Уу € п (3.3.11)
(см. (3.2.1)). В соответствии с (3.3.2) для системы (3.3.7) строим отображение
*х)!“{{«-А^1*еа/ьМ>, ад >°!} (3'ЗЛ2)
где ух е {у|/у(ж) = 4Ж)}> л € (0,2).
Условия 1)-4) для теоремы 3.2.1. в рассматриваемой ситуации выполняются, поэтому для этой ситуации справедлива теорема 3.2.1 вместе со следствием 3.2.1.
Замечание 1. Приведенная схема реализации фейеровского процесса подходит и для случая системы