Вопросы построения комитета несовместной системы неравенств

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

Глава 1. Свойства комитета системы множеств

§ 1.1. Необходимое условие существования комитета

§1.2. Критерий существования комитета системы одномерных

выпуклых множеств

• § 1.3. Условия допустимости

§ 1.4. Редукция систем множеств

Глава 2. Разделение комитетом двух множеств

§2.1. Критерий разделимости границ двух компактов в Ж” комитетом из 2п + 1 членов

§ 2.2. Разделение комитетом двух концентрических окружностей

§ 2.3. Теорема о существовании разделяющего комитета

Глава 3. Построение комитета системы линейных неравенств

§3.1. Метод исследования системы линейных неравенств
§ 3.2. Процедура нахождения членов комитета
ф §3.3. Системы на границе выпуклого т -угольника
§ 3.4. Решение задачи о комитете из трех членов
§3.5. Существование минимального комитета с числом членов,
равным мощности системы
Заключение
Список литературы

Общая характеристика работы
В диссертационной работе изучается два взаимосвязанных круга задач теории несовместных систем неравенств: выяснение условий существования комитета несовместной, в общем случае бесконечной системы неравенств и нахождение методов построения комитета.
Актуальность темы
Исследование несовместных систем линейных неравенств является актуальным направлением в современной математике, поскольку такие системы часто возникают в практических задачах как следствие сложности изучаемых процессов и явлений. Так, например, к несовместной системе линейных неравенств сводится задача обучения распознаванию двух образов, заданных обучающими подмножествами Л и В в И", выпуклые оболочки которых имеют непустое пересечение, состоящая в нахождении так называемой разделяющей гиперплоскости, т.е. такой гиперплоскости {х £ К71 : (а,х) = а}, а £ Шп, а £ Н, что Л С {х : (а,х) > а} и В С {ж : (а,х) < а}, где (•,•) - скалярное произведение в Ш". Как известно, при условии, что сопу .А П сопу £? ф 01, разделяющей А и В гиперплоскости не существует. Одним из подходов к решению этой задачи, получившим в распознавании образов практическое обоснование [12, 29, 31, 30, 43, 58], является построение некоторой кусочно-постоянной (относительно вектора х) функции вида:

$ (.Я > ^ 11 * • • ) ®д > ОД 5 • • • ? ^д ? А1 > • • ■ ) А^-Ы1 *^) ^ ' А,’ * ((щ, 3?) С^г) "Ъ ,

где д - натуральное число, щ,х £ И", щ, £ И, г — 1, д, А?+1 € И, а
{1, если а > О,
-1, в случае, когда а
1 сопу С означает выпуклую оболочку конечного множества С
Этот подход состоит в нахождении такого натурального q) совокупности векторов {щ}?=1, вещественных чисел {(Тг}^= 1 и коэффициентов {Л,}^1, что Л С {х : /(х) >0} и В С {х : /(х) < 0}. При условии, что q
нечетно, Ах = = — 1, а Ад+1 = 0, нахождение функции / сводится
к построению комитета системы из |Диб| строгих однородных линейных неравенств
(с, г) > 0, се Л'и {-В'), г € Еп+1, (0.1.1)
где Л' = {[а, 1] : а Е Л}, В' = {[Ь, 1] : Ь € В}, Л и В - мощность множества Ли В, а 2 - вектор из п + 1 неизвестного. Точнее, комитетом системы (0.1.1) называется конечный набор (с возможными повторениями) векторов из Нп+1, такой, что каждому неравенству этой системы удовлетворяет более половины его членов. При этом сумма кратностей (повторений) элементов этого набора называется числом его членов. Комитет является обобщением понятия решения на случай несовместности системы (0.1.1). Если система (0.1.1) совместна, комитетом будет, например, набор из одного или нескольких элементов, являющихся решениями этой системы. Комитет с наименьшим для данной системы (0.1.1) числом членов, называется минимальным комитетом. С одной стороны, минимальный комитет соответствует функции / наиболее простого вида, с другой стороны его нахождение непосредственно связано при подходе к обучению распознаванию образов, разработанном В.Н. Вапником [2], с задачей минимизации емкости класса решающих правил (УС-сНтепзюп).
В рамках рассматриваемого подхода важными задачами являются нахождение условий существования комитета в общем случае бесконечной системы
(су,х) > 0, 3 Е J, с^,х € И", (0.1.2)
отыскание методов построения комитета этой системы с возможно меньшим числом членов, и, в частности, ее минимального комитета. Первые результаты в этом направлении принадлежат Вл.Д. Мазурову [29], который получил критерий существования комитета конечной системы (0.1.2), предложил метод отыскания ее комитета с числом членов, не превосходящим |7|, и решил задачу о минимальном комитете системы (0.1.2) при п — 2. Далее, в совместной работе [54] М.Ю. Хачай и А.И. Рыбин развирешений этих двух неравенств соответственно. Достаточно показать, что М = До П О' П й, П ф 0 при условии, что среди полуплоскостей, входящих в это пересечение, нет совпадающих.
Пусть хотя бы одно из пересечений Ву П /о и В^Г1уу, скажем, первое, совпадает с некоторым лучом (обозначим его через Гу), который не имеет общих точек с лучом г = В' П /о, включая случай, когда г и г у имеют общую вершину. Так как Му = В0 П В' П Ву ф 0, то О'ПД С До- Действительно, никакое ребро Му не может лежать на прямой 1о» поскольку лучи Гу и г' не имеют общих точек. Так как Му = Д' П Д П В} ф 0 по условию, то М — Му Ф 0.
Пусть каждое из пересечений Б у П 1о и Dj П 1о есть либо прямая /о, либо луч, имеющий с лучом г общую точку. При этом, по построению полуплоскости Д', каждое из этих пересечений либо содержит вершину и луча г, либо совпадает с лучом г. Если и принадлежит одной из полуплоскостей Ву и Bj, например, первой, и лежит на границе второй, то при достаточно малом е > О получим, что и + е(К — и) & М, где к Е М^ = ВууГВ' Г Б у Аналогично доказывается непустота М в случае, когда иеВуП В у Если каждое из пересечений В у П /о и Bj П 1о совпадает с лучом г, то при малом е > 0 получим, что Ь! + е(к — к') € М, где Ь! е г, а к € ДоНеобходимость. Пусть неравенство (со, к) > Ьо несущественно в системе (1.4.2) по отношению к неравенству (Ф,к)>Ь Так как любая подсистема системы (1.4.2) из двух неравенств совместна, то по следствию 1.4.2 система (со,/г) > Ьо, {с!,К) > 6', (СуК) > bj совместна для любого j = 1,т. <