Вопросы построения комитета несовместной системы неравенств тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи

КОБЫЛКИН КОНСТАНТИН СЕРГЕЕВИЧ

ВОПРОСЫ ПОСТРОЕНИЯ КОМИТЕТА НЕСОВМЕСТНОЙ СИСТЕМЫ НЕРАВЕНСТВ

01.01.09 — дискретная математика и математическая

кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Екатеринбург - 2005

Работа выполнена в Институте математики и механики УрО РАН.

Научный руководитель: доктор физико-математических наук,

профессор Мазуров Владимир Данилович.

Официальные оппоненты: доктор физико-математических наук,

профессор Баранский Виталий Анатольевич, кандидат физико-математических наук Рыбин Алексей Игоревич.

Ведущая организация: Уральский государственный технический университет (УГТУ-УПИ).

Защита состоится " 29 " ис?я Ну 2005 г. в часов на заседании диссертационного совета К 004.006.01 по защите диссертаций на соискание ученой степени кандидата наук в Институте математики и механики УрО РАН (620219, г. Екатеринбург, ГСП-384, ул. С.Ковалевской, 16).

С диссертацией можно ознакомиться в библиотеке ИММ УрО РАН.

Автореферат разослан " 2005 г.

Ученый секретарь

диссертационного совета К 004.006.01 кандидат физико-математических наук

Скарин В.Д.

ШТ

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

В диссертационной работе изучаются два взаимосвязанных круга задач теории несовместных систем неравенств: выяснение условий существования комитета несовместной, в общем случае бесконечной системы неравенств и нахождение методов построения комитета. Актуальность темы. Исследование несовместных систем линейных неравенств является актуальным направлением в современной математике, поскольку такие системы часто возникают в практических задачах как следствие сложности изучаемых процессов и явлений. Так, например, к несовместной системе линейных неравенств сводится задача обучения распознаванию двух образов, заданных обучающими подмножествами А и В в R", выпуклые оболочки которых имеют непустое пересечение, состоящая в нахождении так называемой разделяющей гиперплоскости, т.е. такой гиперплоскости {х € R" : (а, х) = а}, а е И", а е К, что А С {х : (а,х) > а} и В С {х : (а, х) < а), где (•,•) - скалярное произведение в R". Как известно, при условии, что conv А П conv 6/0,' разделяющей А и В гиперплоскости не существует. Одним из подходов к решению этой задачи, получившим в распознавании образов практическое обоснование,2 является построение некоторой кусочно-постоянной (относительно вектора х) функции вида:

я

f(q, (¡i,..., ая, ai,..., aq\х) = £egn ((ait х) - а,-),

«=1

где q - нечетное число, а;, х £ IR", а, £ ]R, i — 1,..., q,

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

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

Подход состоит в нахождении такого нечетного q, совокупности векторов ыи и вещественных чисел {а»}®=1, что А С {х : f(x) > 0} и

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

2Метод комитетов в распознавании образов : сб. науч тр. / отв. ред. И И. Еремин; АН СССР, УНЦ - Свердловск, 1974.- вып. 6 - 165 с.

Казанцев, B.C. Задачи классификации и их программное обеспечение /ВС Казанцев - М : Наука, 1990,- 135 с.

ТягУНОВ, Л.И. Управление качеством промышленных изделий / Л.И. Тягунов, Э.Г. Карапе-тяи, Р Г. Мирзоев. - Л ■ Изд-во Ленинградского ун-та, 1977 - 120 с.

з РОС. национальная! библиотека J

«•ЙОТ

В С {х : /(х) < 0}. Это, в свою очередь, сводится к построению комитета системы из \Л и В\ 3 строгих однородных линейных неравенств

где Л' = {[а, 1] : а е Л}, В' = {[Ь, 1] : Ь € В}, а г ~ вектор из п + 1 неизвестного. Точнее, комитетом системы (1) называется конечный набор векторов из Нп+1, такой, что каждому неравенству этой системы удовлетворяет более половины его членов. Комитет с наименьшим для данной системы (1) числом членов называется минимальным комитетом. С одной стороны, минимальный комитет соответствует функции / наиболее простого вида, с другой стороны его нахождение связано при подходе к обучению распознаванию образов, разработанном В.Н. Вапни-ком,4 с задачей минимизации емкости класса решающих правил.

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

отыскание методов построения комитета этой системы с возможно меньшим числом членов, и, в частности, ее минимального комитета. Первые результаты в этом направлении принадлежат Вл Д. Мазурову,5 который получил критерий существования комитета конечной системы (2), предложил метод отыскания ее комитета с числом членов, не превосходящим \J\, и решил задачу о минимальном комитете системы (2) при п = 2. Далее, в совместной работе М.Ю. Хачай и А.И. Рыбин6 развили результаты Вл.Д. Мазурова, получили более сильную верхнюю оценку числа членов минимального комитета конечной системы строгих линейных неравенств, а в случае системы (2) М.Ю. Хачай7 доказал точность найденной

3 \АUВ| означает мощность конечного множества Лив.

4Вапник, В Н. Восстановление зависимостей по эмпирическим данным / В.Н. Валник - М : Наука, 1979 - 448 с.

'МАЗУРОВ, Вл.Д Метод комитетов в задачах оптимизации и классификации / Вл Д. Мазуров.-М.: Наука, 1990.- 248 с.

®Кна(;на1, M.YiJ A New Estimate of the Number of Members in a Minimum Committee of a System of Linear Inequalities / M.Yu Khachai, A.I. Rybin // Pattern Recognition and Image Analysis - 1998-Vol.8, №4,- P. 491-496.

tKhachai, M.Yu Approximate Algorithm for Minimal Committee of a System of Linear Inequalities / M Yu Khachai // Pattern Recognition and Image Analysis.- 2003 - Vol. 13, №3 - P. 459-464.

(c, z) > 0, с € Л' U {-&), z € RB+\

(1)

(cj,x) > 0, j e J, cj,x e K"

(2)

верхней оценки и предложил алгоритм построения комитета с не превосходящим ее числом членов. Вместе с тем задача о минимальном комитете в случае конечной двумерной системы строгих неоднородных линейных неравенств, а также конечной системы (2) при п > 2 остается нерешенной. В случае бесконечной двумерной системы (2) А.И. Кривоногов8 сформулировал критерий существования комитета. Вопрос нахождения такого критерия и построения минимального комитета для бесконечной системы (2) при п > 2 остается открытым.

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

- задачи о р-комитете произвольной системы неравенств

/, (х) > 0, ] € 7, х € X, (3)

где 3 и X - некоторые множества, - функция над X, е а О < р < 1. При этом, р-комитетпом системы (3) называется конечный набор К (с возможными повторениями) элементов из X, такой, что каждому неравенству системы (3) удовлетворяет более, чем р ■ ы(К) членов этого набора, где и){К) - сумма кратностей всех элементов, входящих в К. Здесь Вл.Д. Мазуровым и М.Ю. Хачаем,9 М.Ю. Хачаем10 и автором [9] получен ряд необходимых условий существования комитета и р-комитета.

Цель работы:

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

a) конечной или бесконечной системой строгих однородных линейных неравенств в К", п > 2;

b) конечной двумерной системой строгих линейных неравенств;

'Кривоногое, А.И. Некоторые модификации комитетных алгоритмов в распознавании образов / А.И. Кривоногов // Методы математического программирования и приложения: сб. науч. тр -Свердловск: УНЦ АН СССР, 1979 - С 49-55

"мазуров, Вл Д. Комитетные конструкции / Вл.Д. Мазуров, М Ю. Хачай // Известия Уральского гос. ун-та.- 1999.- №14.- С. 77-108 (Сер. Математика и механика. Вып. 2).

шХачай, М.Ю. Об одном соотношении, связанном с процедурой принятия решений большинством голосов / М.Ю. Хачай // Доклады РАН.- 2001- Т.381, №6,- С. 748-752.

£

с) конечной системой нестрогих неравенств, имеющих выпуклые множества решений аффинной размерности 1;

— формулировка геометрического метода представления системы линейных неравенств;

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

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

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

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

Публикации. Результаты диссертационной работы опубликованы в одиннадцати научных работах, из которых одна в соавторстве.

Апробация. Результаты диссертации представлялись на следующих конференциях и научных семинарах: Всероссийской конференции "Математическое программирование и приложения", Екатеринбург (1999, 2003); Международной конференции "Интеллектуализация обработки

информации", Симферополь (2004); Международной конференции "Распознавание образов и анализ изображений", Санкт-Петербург (2004); Международной школе-семинаре "Методы оптимизации и их приложения", Северобайкальск (2005); Региональной молодежной конференции "Проблемы теоретической и прикладной математики", ИММ УрО РАН, Екатеринбург (2005); Научном семинаре под руководством академика РАН И.И Еремина, ИММ УрО РАН, Екатеринбург (2002, 2004, 2005).

Структура и объем работы. Диссертация состоит из введения, трех глав, содержащих 12 параграфов и 15 рисунков, заключения и списка литературы из 61 наименования. Общий объем работы - 141 страница.

Краткое содержание работы

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

Рассмотрим систему подмножеств Т> = {^Ье./ некоторого множества X, где 3 -в общем случае бесконечное множество. Конечную совокупность элементов множества X, которая может содержать повторяющиеся члены, будем называть набором. Сумму кратностей (повторений) всех элементов, входящих в некоторый набор К, назовем числом членов в этом наборе и обозначим через 1и{К).

Определение 0.1.1. Пусть 0 < р < 1. Конечный набор К элементов множества X называется р-комигпетпом системы множеств Х>, если каждому ее множеству И} принадлежит более, чем р-ъи(К) элементов набора К с учетом кратности. При этом р-комитетом системы неравенств называется р-комитет системы множеств их решений. При р—\ р-комитет называется комитетом.

Сформулируем задачи, изучаемые в работе. Задача 1. При каких условиях существует р-комитет системы множеств V ? Каковы условия существования комитета системы V с числом членов равным <7, где д - натуральное число?

Задача 2. Найти комитет системы V, по возможности, с наименьшим

числом членов (минимальный комитет).11

Определение 0.1.3. Комитетом аффинных функций, разделяющим два подмножества точек Л и В пространства И", называется такой конечный набор аффинных функций, что в любой точке из Л (соответственно из В) более чем половина функций этого набора положительна (соответственно отрицательна).

Задача 1*. При каких условиях существует комитет, разделяющий два подмножества в И"? ,

Задача 2*. Найти комитет, разделяющий два подмножества Л и В в К", по возможности, с наименьшим числом функций (минимальный |

разделяющий комитет).

Глава 1 состоит из четырех параграфов и в целом посвящена изучению свойств комитета произвольной системы подмножеств V = {Д,}^ некоторого множества X.

В §1.1 основным утверждением является Теорема 1.1.1. Пусть 0 < р < 1 и т = |7| < оо. Если система Т> имеет р-комитпет К, то в К найдется член, принадлежащий не менее, чем [тр] + 1 множествам системы Т>.12

Подсистема 23(7') = У С 7, системы V называется сов-

местной (обладающей решением х £ X), если Р) В^ ф 0 (если

х £ П Приведем необходимое условие существования р-комитета.

Следствие 1.1.2. Если система V имеет р-комитет, то в любой ее подсистеме £>(/') = У С Jí имеется совместная подсисте-

ма мощности не меньшей, чем [| + 1.

В случае системы из пяти множеств, состоящей из четырех граней правильного тетраэдра и вписанного в него шара, это условие не является достаточным при р = \.

В §1.2 с использованием следствия 1.1.2 доказан критерий существования комитета конечной системы V = {Д,}!^ выпуклых подмножеств в К", каждое из которых лежит на некоторой прямой. Теорема 1.2.1. Для того чтобы система V имела комитет, необ-

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

13 [тр] означает целую часть числа тр.

ходимо и достаточно, чтобы существовала упорядоченная тройка (не обязательно различных) точек (Со, D0, Е0) такая, что произвольное множество системы V либо содержит отрезок [Do, £bb либо содержит точку Со и имеет общую точку с отрезком [Do, Ео].

Пусть для системы подмножеств V = {Dj}™^ некоторого множества X существует хотя бы один комитет из q элементов, q > 1. Определим число m(q) как наименьшее из чисел min\{D б Т> : х € D}| по всем

X<zK

g-членным комитетам К системы Т>.

В §1.3 получена нижняя оценка числа m{q), зависящая от некоторых параметров системы Т>. Рассмотрим ее максимальные по включению подсистемы с непустым пересечением, далее называемые максимальными по включению совместными подсистемами (МСП) системы Т>. Пусть то - мощность МСП наибольшей мощности системы V. В случае, когда найдется МСП системы £>, имеющая мощность меньшую, чем то, рассмотрим среди последних некоторую МСП, состоящую из наибольшего числа множеств и обозначим ее мощность через mi. Далее, пусть щ - число всех различных МСП мощности то системы V. Рассмотрим множество из щ элементов, содержащее по одному решению каждой из таких МСП, и обозначим через р — р{щ) наибольшую сумму кратностей, с которой это множество элементов может входить в д-членный комитет системы Т>. Для нечетного q положим d = — ршо и определим число fh(q) по формуле:13

О, если p = q и < q,

^ mod mo, если p = q, [Щ=] = q и ^ Ф q,

m{q) = <

mo, если p = q и = q,

О, если p<q и [¿j < q - p,

mod mi, если p < q, W = q - p, £ ф q - p,

тпи если p<q и ^ = q - p.

При четном q положим m{q) m(q — 1). Пусть m'0 мощность произвольной МСП наибольшей мощности системы Т>х = {X\Dj}™=1.

13 k mod I означает остаток от деления к на I, где к и I - целые числа; [а] есть наименьшее целое, не меньшее, чем вещественное число а.

Теорема 1.3.1. Если система множеств V имеет комитет из ц членов, то выполнено неравенство: т(д) ^ тах{т(д),тп — тп'0}.

Для любой подсистемы £>(/) = {/^¿е/, I С {1,..., ш}, системы V, определим, аналогично, числа тп(д) = I) и Шд = тп'0(1). Сформулируем необходимое условие существования комитета из д членов. Следствие 1.3.1. Для того чтобы система множеств Т> имела комитет из д членов необходимо, чтобы некоторый элемент х £ X принадлежал не менее, чем тах{т(д,/), |/| — тп'0(1)} множествам в I

каждой подсистеме Т>(1), I С {1,..., т}.

В §1.4 рассматривается метод редукции конечной системы множеств (

Т> к некоторой ее подсистеме меньшей мощности. Определение 1.4.1. Пусть Д и Д - множества системы V, i ф Множество Д несущественно по отношению к О, в системе 2?, если Д содержится во всех МСП системы V, в которые входит множество Д. Система Т> несократима, если она не содержит множеств, несущественных в ней по отношению к какому-либо другому ее множеству.14

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

(с3, х) > Ъч, сх € К", ^ € И,з = 1,..., тп (4)

ранга п. Для того чтобы г-е неравенство системы (4) было несущественно в ней по отношению к ^'-му неравенству необходимо и достаточно, чтобы любая ее подсистема мощности не большей, чем п + 1, включающая ¿-ъ неравенство, и подсистема, полученная из последней добавлением г-го неравенства, были совместны одновременно.

Глава 2 состоит из трех параграфов и посвящена нахождению условий разделимости комитетом аффинных функций двух бесконечных подмножеств Л и В в И™ и построению минимального разделяющего их комитета. В §2.1 рассматривается следующий

Способ построения комитета. Пусть множество Л лежит внутри некоторого выпуклого многогранного множества М, имеющего в точно-

"Понятие несущественного неравенства в системе неравенств вводится аналогично

сти к граней размерности п — 1, а множество В лежит во внешности М. Рассмотрим набор Км{А, В) = {Д, • • •, Л, /о, ■ • •, /о} m 2fc — 1 аффинных функций такой, что соответствующие открытые полупространства Pi = {х : fi(x) > 0},..., Pk = {х : fk(x) > 0} попарно различны, содержат int М, и граничная гиперплоскость каждой из них проходит через некоторую (п—1)-мерную грань многогранника М, а fo(x) = —1, х € П1"; функция /о входит в Км(А,В) с кратностью к — 1. Тогда Км (А, В) - комитет, разделяющий подмножества А и В.

Похожий способ построения комитета рассматривался в совместной работе М.Ю. Хачая и А.И. Рыбина.15 Пусть С\ и Сг - компакты в Rn, Ci лежит в intC2, а множества А и В - границы Ci и Сг соответственно.

В §2.1 основным утверждением является Теорема 2.1.1. Минимальный комитет, разделяющий подмножества А и В, состоит не менее, чем из 2п+1 членов, причем равенство возможно тогда и только тогда, когда существует n-мерный симплекс, содержащий внутри С\ и лежащий в int Ci-

Следствие 2.1.1. Пусть Мо - выпуклый многогранник, содержащий внутри С\ и лежащий в intC2, с наименьшим числом (п-1)-мерных граней. Если это число равно п + 1 или п + 2, то Км0(А, В) - минимальный комитет, разделяющий подмножества А и В.

В §2.2 предложенный способ применен для нахождения минимального комитета, разделяющего два множества на плоскости. Пусть 0 < г < R.

Теорема 2.2.1. Пусть к =

2тг

. 2ГЗ-Д2

+ 1. Если Мо - выпуклый мно-

arccos д2"

гоугольник с наименьшим числом сторон, содержащий внутри круг радиуса г и лежащий во внутренности другого круга радиуса R с тем же центром, то Км0(А,В) - минимальный комитет из 2fc — 1 членов, разделяющий две концентрических окружности А и В радиусов г и R соответственно, лежащих на границе этих кругов.

Сохраним обозначения теоремы и сформулируем следствие. Следствие 2.2.1. Пусть А! и В' - два множества на плоскости,

15Khaohai, M Yu A New Estimate of the Number of Members in a Minimum Committee of a System of Linear Inequalities / M.Yu. Khachai, A.I. Rybin // Pattern Recognition and Image Analysis - 1998.-Vol 8, № - P 491-496

Л С Л' и В С В'. Если существует многоугольник Мо с к сторонами, содержащий внутри себя А! и не пересекающийся с В', то Км0(А', В') - минимальный комитет, разделяющий А' и В'.

В §2.3 дано достаточное условие разделимости двух, в общем случае бесконечных множеств комитетом. (Известно,16 что два конечных подмножества в К" могут быть разделены комитетом тогда и только тогда, когда эти два множества не имеют общей точки.) Теорема 2.3.2. Для любых двух непересекающихся замкнутых подмножеств в К", одно из которых ограничено и имеет конечное число предельных точек, существует разделяющий их комитет.

Условие ограниченности одного из разделяемых подмножеств является существенным. Так, например, не существует комитета, разделяющего подмножества А = {"2к}™=1 и В — {2к — на числовой прямой.

Рассмотрим систему строгих однородных линейных неравенств

(с^,х) > 0, с3,х € К", з £ .7, п > 2. (5)

Можно считать, что С — {9 : ] £ /} С 5, где 5 - единичная сфера с центром в 0. Пересечение сферы 5" с произвольным открытым полупространством, граница которого содержит 0, назовем открытой полусферой. Если Т - открытая полусфера, являющаяся пересечением некоторого открытого полупространства Р со сферой Б, то через Ь<1 Т обозначим пересечение сферы Б с граничной гиперплоскостью полупространства Р. Сформулируем достаточное условие существования комитета бесконечной системы (5).

Следствие 2.3.1. Пусть СпЪйТ — 0, где Т - некоторая открытая полусфера. Если —С П С = 0, множество Т П С содержит все свои предельные точки, лежащие на полусфере Т, а множество —Т П С замкнуто и имеет конечное число предельных точек, то существует комитет системы (5).

Глава 3 состоит из пяти параграфов. Первый из них посвящен методу представления системы линейных неравенств, четыре остальных -вопросам существования комитета системы линейных неравенств и методам его нахождения.

16мазуров, Вл.Д. Метод комитетов в задачах оптимизации и классификации / Вл Д. Мазуров. М.: Наука, 1990,- 248 с.

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

(с3,х) > Ь¡, с,-, х <Е К", Ь} еШ., j £ 3, (6)

имеющей отличные от нуля свободные коэффициенты. Подробнее, пусть Н: - граничная гиперплоскость полупространства решений ^'-го неравенства системы. Рассмотрим основание Щ перпендикуляра, опущенного из 0 на эту гиперплоскость и сопоставим ^'-му неравенству точку с* = сг(с^), где а(с) — -Щ1 - инверсия точки с относительно единичной сферы с центром в 0.17 Разобъем систему V — на две подсисте-

мы: в первую включим все ее точки, отвечающие неравенствам системы с положительным свободным коэффициентом, а во вторую - точки, соответствующие неравенствам, у которых этот коэффициент отрицателен. Первую из этих подсистем обозначим через А; во вторую добавим точку 0 и обозначим ее через В. Системе (6) поставим в соответствие систему точек V* = V и {0} = А и В. Она определена формулами:

А = : 3 € 3,6,- > о} , В = : э € ¿Л < о} и{0}.

При этом вектор Хо является решением системы (6) тогда и только тогда, когда гиперплоскость (хо, х) — 1 строго разделяет подсистемы точек А и В. Следовательно, методы построения гиперплоскости, разделяющей две выпуклых оболочки,18 могут рассматриваться как методы решения систем линейных неравенств. В свою очередь, построение комитета системы линейных неравенств (6), заданной в форме системы точек V* = А и В, сводится к нахождению такого конечного набора аффинных функций, что в любой точке из А (соответственно из В) более чем половина функций этого набора положительна (соответственно отрицательна), причем в точке 0 отрицательное значение принимают все функции этого набора.

Рассмотрим несовместную двумерную систему строгих линейных

17точка с* отвечает гиперплоскости Н} при преобразовании поляритета

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

неравенств

{с3, К) > Ьч, £ Е2, = т, (7)

для которой существует комитет.

Определение 3.2.1. Назовем МСП Т системы (7) отмеченной, если она содержит такую пару неравенств, называемую определяющей, что любая МСП системы (7), содержащая эту пару, совпадает с Т, причем любое решение определяющей пары неравенств, достаточно близкое к элементу, обращающему неравенства этой пары в равенства, удовлетворяет подсистеме Т.

Если К - комитет системы (7) с условием, что каждый его член является решением некоторой МСП системы (7), то любая отмеченная МСП этой системы обладает решением, входящим в комитет К.

В §3.2 дан алгоритм нахождения отмеченной МСП.

Процедура. Пусть V = {-О/}^*- система полуплоскостей, каждая из которых является множеством решений соответствующего неравенства системы (7). Рассмотрим некоторую полуплоскость € Т> и точку /г® на ее границе совпадающую с одной из двух крайних точек пересечения № с граничными прямыми других полуплоскостей системы V. Возьмем на прямой № луч г о с вершиной в точке содержащий обе крайних точки. Пересечение : И е Т>, ИНго — луч} совпа-

дает с некоторым лучом И' Г) £>' € £>, а пересечение [""]{£> П : О ОГ\1(0} = О'Ш^} - с некоторым конусом £>^П£>(0), £>(1) е V, вершину которого обозначим через где - грани-

ца полуплоскости им. Пусть Г\ — Аналогично, пересечение

: В € Х>, /?Пг1 — луч} совпадает с некоторым лучом £>" е V, а пересечение П{£> П ¿?(1) /М = I)" Л ДО} - с

некоторым конусом П € Р. Пусть /г^2' - вершина этого

конуса; = ДО П ДО, где ДО - граница полуплоскости ¿ДО.

Если

/ДО = /ДО, то процедура заканчивается. В случае, когда Л'1-1 ф /ДО, проведем аналогичные построения для прямой № и луча гг = П ДО. Будем продолжать данный процесс до тех пор, пока для некоторого ко, ко не будет выполнено равенство Выберем точку

лежащую в столь малой окрестности точки что Н Е ПР € I7: ^^ 6 £>}• Обозначим через Б

подсистему, составленную из двух неравенств системы (7), множествами решений которых являются полуплоскости Г)^-1) и О^ко\ Рассмотрим неравенство системы (7), образующее вместе с двумя неравенствами из Э совместную подсистему, и составим из всех таких неравенств подсистему, которую обозначим через Т. Процедура завершена.

При этом, подсистема Т — Т(£>(°\го) совпадает с некоторой отмеченной МСП системы (7), два неравенства из в составляют определяющую пару в Т, а вектор Л является решением подсистемы Т. Применяя процедуру с определенными параметрами и го, можно найти любую из отмеченных МСП системы (7). Процедура используется в §3.4 при построении комитета из трех членов системы (7).

Рассмотрим трехмерную систему строгих однородных линейных неравенств

(с,,:г) > 0, с3,х еП3, ¿ = 1,..., ш, (8)

где множество С = {с} : j = 1,...,ш} лежит на единичной сфере с центром в 0 и с, ф -с3 для любых различных г и 3. Обозначим через С а*1 и С® подмножества С, разделяемые некоторой плоскостью а, проходящей через 0 и не содержащей точек из С. Определение 3.3.1. Система (8) называется в-системой относительно плоскости а, если для любых г = 1,2 и с Е Са\ множества СГ!) и {с} и Сд\{с} строго разделяет некоторая плоскость, проходящая через 0.

В первой части §3.3 предложен и обоснован алгоритм построения минимального комитета трехмерной 5-системы. Определение 3.3.2. Несовместную двумерную систему

(с}, И) > с3, к 6 И2, Ь, еШ., 3 = 1,... ,т, т > 3, (9)

для которой существует комитет, будем называть Б-системой, если прямые (с;,Н) — Ь], 3 = 1,...,ш, ограничивают некоторый выпуклый (возможно неограниченный) многоугольник с т сторонами.

Во второй части §3.3 дан алгоритм построения минимального комитета двумерной ^-системы. Изучение 5-систем является особенно важным с точки зрения возможных обобщений понятия 5-системы и нахождения алгоритмов построения минимального комитета для более широкого класса двумерных и трехмерных систем.

Рассмотрим несовместную двумерную систему строгих линейных неравенств

(с,-, К) > Ъ,, су, Л 6 В.2, € Е-, з = 1, -.., т, (10)

для которой существует комитет. Пусть Т> - система полуплоскостей, каждая из которых является множеством решений соответствующего неравенства системы (10).

В §3.4 дан алгоритм нахождения ее трехчленного комитета.

Алгоритм построения комитета из трех членов. Пусть

£>(0)

€ Т> - произвольная полуплоскость. Рассмотрим отмеченную МСП Тх системы (10), ее решение /¿х и определяющую пару неравенств Эх, входящую в Тх, которые найдены при применении процедуры, описанной в §3.2, к полуплоскости и произвольному лучу на ее границе. Пусть Е и Е' -полуплоскости, являющиеся множествами решений двух неравенств, составляющих подсистему Эх. Положим

£>(0).

= Е. Применив процедуру к полуплоскости и лучу на ее границе противоположно направленному с лучом Е'п№\ найдем некоторую отмеченную МСП системы (10) и ее решение /¿2- Положим I)'0' :— Е'. Рассмотрим отмеченную МСП Т3 и ее решение /¿з, которые найдены при применении процедуры к полуплоскости О^ и лучу на ее границе противоположно направленному с лучом Е П №. Пусть К = К2, Лз}.

Оказывается, система (10) имеет комитет из трех членов тогда и только тогда, когда К является ее комитетом. Кроме того, справедлива Теорема 3.4.2. Для того чтобы система (10) имела комитет из трех членов необходимо и достаточно, чтобы любая ее подсистема из пяти неравенств включала в себя совместную подсистему из четырех неравенств.

В §3.5 дается критерий совпадения числа членов минимального комитета конечной системы строгих однородных линейных неравенств

(су, х) > 0, с,-, х е ЛГ, з = 1,..., т, (11)

обладающей комитетом, с известной верхней оценкой этого числа, данной Вл.Д. Мазуровым,19 которая равна числу неравенств в системе.

"Мазуров, Вл.Д. Метод комитетов в задачах оптимизации и классификации / Вл Д. Мазуров -М.: Наука, 1990.- 248 с.

Теорема 3.5.3. Для того чтобы система (11) из тп неравенств имела минимальный комитет из т членов, необходимо и достаточно, чтобы любые два ее неравенства составляли вместе с некоторым неравенством системы (11) несовместную подсистему.

В заключение выражаю глубокую признательность научному руководителю Владимиру Даниловичу Мазурову за руководство исследованием и искреннюю благодарность Леониду Петровичу Власову и Михаилу Юрьевичу Хачаю за обсуждение результатов.

Основные результаты:

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

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

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

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

5) решение ряда задач о разделении двух подмножеств минимальным комитетом.

Публикации по теме диссертации

[1] КОБЫЛКИН, К.С. Несколько задач о комитетах / К.С. Кобылкин // Тез. докл. Всероссийской конф "Математическое программирование и приложения", Екатеринбург, 1999 - С. 153-(инф. бюллетень Х«8).

[2] Кобылкин, К С Двумерное представление трехмерных систем однородных линейных неравенств / К.С. Кобылкин, М Ю Хачай // Тез докл Всероссийской конф.

"Математическое программирование и приложения", Екатеринбург, 2003.- С. 146.-(инф. бюллетень N«10).

[3] Кобылкин, К С. Двумерное представление трехмерных систем однородных линейных неравеиств / К.С. Кобылкин // Автоматика и Телемеханика.-2004.--Х»3.-С. 17-22.

[4] Кобылкин, КС О разделении двух множеств комитетом /КС Кобылкин // Теч докл. междунар конф "Интеллектуализация обработки информации", Симферополь, 2004.- С. 80. (Математическая теория, алгоритмы и системы распознавания образов).

[5] КОБЫЛКИН, К.С. О разделении двух множеств комитетом / К.С. Кобылкин // Искусственный интеллект,- 2004.- №2.- С. 96-100.

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

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

[8] КОБЫЛКИН, К.С. О существовании комитета системы множеств / К.С. Кобылкин // Тр. 36-й Региональной молодежи конф "Проблемы теоретической и прикладной математики", Екатеринбург, 2005- С. 302-304- (Математическое программирование и распознавание образов).

[9j Kobylkin, K.S. Necessary Condition for Committee Existence / K.S. Kobylkin // Pattern Recognition and Image Analysis. - 2002,- Vol. 12, №1- P. 26-31

[10] KOBYLKIN, K.S. Constructing a committee of a system of linear inequalities / K.S. Kobylkin // Proc. of the 7th Int. Conf. "Pattern Recognition and Image Analysis: New Information Technologies -7", St. Petersburg, 2004.- P. 62-65. (Mathematical methods in pattern recognition; vol. 1).

[11] Kobylkin, K.S Constructing a Committee of a System of Linear Inequalities / K.S Kobylkin // Pattern Recognition and Image Analysis - 2005.- Vol.15, №1.- P.62-64.

Подписано в печать 22.09.2005. Формат 60x84/16. Объем 1.0 п.л. Тираж 100 экз. Заказ №48 Размножение с готового оригинал-макета в типографии УрО РАН 620219, г. Екатеринбург, ул. С. Ковалевской, 18.

1 4

i

РНБ Русский фонд

2006-4 18925

Введение

Глава 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", один из которых лежит внутри другого;

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

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

Заключение

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