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

• Кобылкин, Константин Сергеевич
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Кобылкин, Константин Сергеевич

Введение

Глава 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. Существование минимального комитета с числом членов, равным мощности системы.

Введение диссертации (часть автореферата) на тему «Вопросы построения комитета несовместной системы неравенств»

Общая характеристика работы

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

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

Исследование несовместных систем линейных неравенств является актуальным направлением в современной математике, поскольку такие системы часто возникают в практических задачах как следствие сложности изучаемых процессов и явлений. Так, например, к несовместной системе линейных неравенств сводится задача обучения распознаванию двух образов, заданных обучающими подмножествами Л и В в Ип, выпуклые оболочки которых имеют непустое пересечение, состоящая в нахождении так называемой разделяющей гиперплоскости, т.е. такой гиперплоскости {х е Нп : (а,х) — а}, а е Нп, а € Н, что Л С {х : (а,х) > а} и В С {х : (а,х) < а}, где (•, •) - скалярное произведение в Ш". Как известно, при условии, что сопуДПсопуБ Ф 01, разделяющей Л и В гиперплоскости не существует. Одним из подходов к решению этой задачи, получившим в распознавании образов практическое обоснование [12, 29, 31, 30, 43, 58], является построение некоторой кусочно-постоянной (относительно вектора х) функции вида: я д, аъ., од, аь., ад, Ах,., Ад+1| х) - ^ А,- • sgn ((о,-, х) - + Ад+Ь 1 где q - натуральное число, а^ж € Нп, оц} \ € К, г — А?+1 Е Н, а

1, если а > О, sgn а = <

-1, в случае, когда а ^ 0.

1 сопу С означает выпуклую оболочку конечного множества С

Этот подход состоит в нахождении такого натурального д, совокупности векторов {аг}^=1» вещественных чисел {а*}^ и коэффициентов {Аг}-^1, что А С {х : /(х) > 0} и В С {ж : /(х) < 0}. При условии, что -нечетно, Ах = . = Хя — 1, а А^+1 = 0, нахождение функции / сводится к построению комитета системы из |АиВ\ строгих однородных линейных неравенств с, г) > 0, с € А! и {-В'), г е Нп+1, (0.1.1) где А! = {[а, 1] : а 6 А}, В' = {[Ь, 1] : Ь е В}, |А и В\ - мощность множества А и В, а г - вектор из п + 1 неизвестного. Точнее, комитетом системы (0.1.1) называется конечный набор (с возможными повторениями) векторов из Нп+1, такой, что каждому неравенству этой системы удовлетворяет более половины его членов. При этом сумма кратностей (повторений) элементов этого набора называется числом его членов. Комитет является обобщением понятия решения на случай несовместности системы (0.1.1). Если система (0.1.1) совместна, комитетом будет, например, набор из одного или нескольких элементов, являющихся решениями этой системы. Комитет с наименьшим для данной системы (0.1.1) числом членов, называется минимальным комитетом. С одной стороны, минимальный комитет соответствует функции / наиболее простого вида, с другой стороны его нахождение непосредственно связано при подходе к обучению распознаванию образов, разработанном В.Н. Вапником [2], с задачей минимизации емкости класса решающих правил (УС-сПтепБюп).

В рамках рассматриваемого подхода важными задачами являются нахождение условий существования комитета в общем случае бесконечной системы с^х) > 0, з 6 <7, с^х е Кп, (0.1.2) отыскание методов построения комитета этой системы с возможно меньшим числом членов, и, в частности, ее минимального комитета. Первые результаты в этом направлении принадлежат Вл.Д. Мазурову [29], который получил критерий существования комитета конечной системы (0.1.2), предложил метод отыскания ее комитета с числом членов, не превосходящим и решил задачу о минимальном комитете системы (0.1.2) при п = 2. Далее, в совместной работе [54] М.Ю. Хачай и А.И. Рыбин развили результаты Вл.Д. Мазурова, получили более сильную верхнюю оценку числа членов минимального комитета конечной системы строгих линейных неравенств, а в случае системы (0.1.2) М.Ю. Хачай [51] доказал точность найденной верхней оценки и предложил алгоритм построения комитета с не превосходящим ее числом членов. Вместе с тем задача о минимальном комитете в случае конечной двумерной системы строгих неоднородных линейных неравенств, а также конечной системы (0.1.2) при ть > 2 остается нерешенной. В случае двумерной бесконечной системы (0.1.2) А.И. Кри-воногову удалось сформулировать [23] критерий существования комитета. Вопрос нахождения критерия существования комитета и построения минимального комитета бесконечной системы (0.1.2) при п > 2 также является нерешенным.

Комитетом аффинных функций, разделяющим два подмножества Л и В в Мп, называется такой конечный набор аффинных функций, что в любой точке из Л (соответственно из В) более чем половина функций этого набора принимает положительное значение (соответственно отрицательное значение). Задача нахождения условий существования разделяющего комитета и построения минимального по числу членов (функций) разделяющего комитета тесно связана с рассматриваемыми задачами, поскольку любой разделяющий комитет может быть преобразован [29] в комитет некоторой системы (0.1.2), рассматриваемой в

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

Дж)>0 ^Е^'хеХ, (0.1.3) где 3 и Х- - произвольные множества, 0 < р < 1. При этом, р-комитетом системы (0.1.3) называется конечный набор К (с возможными повторениями) элементов из X такой, что каждому неравенству системы (0.1.3) удовлетворяет более, чем р • и){К) членов этого набора, где и>{К) - сумма кратностей всех элементов, входящих в набор К. Вл.Д. Мазуровым [32], М.Ю. Хачаем [45] и автором данной работы [55] получен ряд необходимых условий существования комитета и р -комитета. Вместе с тем многие вопросы, касающиеся этой задачи, остаются нерешенными.

Цель работы получение различных условий существования комитета системы неравенств и нахождение методов его построения. Разработка подходов к решению этих задач как в общем случае, так и в случае, когда система неравенств является: a) конечной или бесконечной системой строгих однородных линейных неравенств в К", п > 2; b) конечной двумерной системой строгих неоднородных линейных неравенств; c) конечной системой неравенств, имеющих выпуклые множества решений аффинной размерности 1. формулировка геометрического метода исследования систем линейных неравенств; изучение задачи нахождения комитета аффинных функций, разделяющего два подмножества в Нп.

Методика исследований

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

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

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

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

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

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

Теоретическая и практическая значимость

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

Структура и объем работы

Диссертация состоит из введения, трех глав, объединяющих 12 параграфов и содержащих 15 иллюстраций, заключения и списка литерату

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Кобылкин, Константин Сергеевич

Основные результаты работы состоят в следующем:

• дан критерий существования комитета из трех элементов конечной двумерной системы строгих неоднородных линейных неравенств и предложен алгоритм построения такого комитета;

• сформулировано достаточное условие существования комитета бесконечной системы строгих однородных линейных неравенств в Нп, п > 2;

• предложен способ представления системы линейных неравенств в форме системы точек, основанный на известном преобразовании поляритета;

• даны два необходимых условия существования комитета несовместной системы неравенств;

• приведено решение ряда задач о разделимости минимальным комитетом аффинных функций границ двух компактов в 11", один из которых лежит внутри другого;

• предложены алгоритмы построения минимального комитета для некоторых классов систем линейных неравенств, называемых в работе системами;

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

Заключение

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

1. Еремин, И.И. Итерационный метод обучения дискриминации бесконечных множеств / И.И. Еремин, Вл.Д. Мазуров // Кибернетика.-1977.- №5.- С. 108-110.

2. Еремин, И.И. Нестационарные процессы математического программирования / И.И. Еремин, Вл.Д. Мазуров. М.: Наука, 1979 - 288 с.

3. ЖУРАВЛЕВ, Ю.И. Корректные алгебры над множествами некорректных алгоритмов I / Ю.И. Журавлев // Кибернетика.- 1977.— т.- С. 14-21.

4. Кобылкин, К.С. Вопросы существования комитета системы линейных неравенств / К.С. Кобылкин; ИММ УрО РАН. Екатеринбург,2005 18 е.- Библиогр.: 5 назв. Деп. в ВИНИТИ 30.03.2005, №430-В2005.

5. КОБЫЛКИН, К.С. Существование комитета системы линейных неравенств / К.С. Кобылкин // Тр. школы-семинара "Методы оптимизации и их приложения", Иркутск-Северобайкальск, 2005.- Т.1.- С. 131134.

6. КОЗИНЕЦ, Б.Н. Рекуррентный алгоритм разделения выпуклых оболочек двух множеств / Б.Н. Козинец // Алгоритмы обучения распознаванию образов / сб. науч. тр. под ред. В.Н. Вапника.- М.: Советское радио, 1973.- С. 43-50.

7. МАЗУРОВ, Вл.Д. О построении комитета системы выпуклых неравенств / Вл.Д. Мазуров // Кибернетика 1967 - №2 - С. 56-59.

8. РУДАКОВ, К.В. О некоторых классах алгоритмов распознавания / К.В. Рудаков. М.: ВЦ АН СССР, 1980.

9. РУДАКОВ, К.В. Алгоритм синтеза корректных процедур распознавания для задач с непересекающимися классами / К.В. Рудаков,

10. ЧЕРНИКОВ, С.Н. Линейные неравенства / С.Н. Черников. М.: Наука, 1968 - 488 с.