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

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

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

ХАЧАЙ МИХАИЛ ЮРЬЕВИЧ

КЛАССИФИКАЦИЯ И ОЦЕНКИ КОМИТЕТОВ СИСТЕМ НЕРАВЕНСТВ

Специальность: 01.01.09 — математическая кибернетика

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

Екатеринбург — 1996

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

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

профессор Мазуров Вл.Д.

Официальные оппоненты:

доктор технических наук, профессор Лабунец В.Г., кандидат физико-математических наук Кривоногов А.И.

Ведущая организация:

Вычислительный Центр РАН.

Защита состоится ОПЛсли.1996 г. в ' ^ часов на

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

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

Автореферат разослан кХкУ-^ьо^

1996 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук / Скарин В.Д.

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

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

Задачей распознавания или классификации, согласно Ю.И.Журавлеву1, называется следующая задача. Пусть задано множество М объектов, называемое допустимым, и задано неизвестное покрытие множества М множествами К\,.. .,Кт С М, Ц/=1 = называемыми классами (образами). Обычно предполагается, что К{ П = 0 для любых г ф Информация о множествах /\*1,..,, Кт задана не полностью, обычно известны конечные Щ С К^. В общем случае задается некоторая информация 1о{К\,..., Кт). Задача состоит в том, чтобы для произвольного объекта й" € М, заданного описанием ЦБ), определить значения предикатов:

■*ч ' ^ 0, иначе

Далее, не уменьшая общности, будем полагать т = 2.

Исторически сложилось несколько подходов к постановке и решению задач распознавания, такие как, например, вероятностный, представленный работами В.Н.Вапника,А.Я.Червоненкиса и др., алгебраический — работами Ю.И.Журавлева, Ю.А.Зуева, К.В.Рудакова и других авторов. В каждом случае приведенное выше общее определение задачи распознавания тем или иным способом конкретизируется. Автор в своей работе придерживался подхода, сформированного работами Вл.Д.Мазурова и И.И.Еремина, основанного на применении фундаментальных результатов теории линейных неравенств, полученных С.Н.Черниковым, Фань-Цзи, Д.Гейлом и др.

'Журавлев Ю.Н. Об алгебраическом подходе к решению задач распознавания или классификации// Проблемы кибернетики, вып.33.-1978.-С.5-68.

Согласно работе2, задачей дискриминантного анализа называется следующий частный случай задачи распознавания. Пусть мно-

♦

жество М С Rn, М = К\ (J К?, заданы конечные подмножества А С Кь В С Л'а и класс функций F С {Я" —► Я}. Требуется найти функцию / 6 F, такую что

/(а) > 0 (абЛ), f{b) < О (6G5).

Если такая функция найдена, то полагается К\ = {х g Л/| /(г) > 0} и А'г = {i € М) /(г) < 0). Поставленная задача часто может быть сведена к задаче поиска решения подходящей системы неравенств (в частности, линейных, если F — класс аффинных функций). К сожалению, как правило, эта система несовместна, поэтому для решения исходной задачи требуется то или иное обобщение понятия решения системы неравенств.

Одним из требуемых обобщений является понятие комитета, впервые введенное в работе3 для системы строгих однородных линейных неравенств. Вместо одной точки xq 6 Rn, удовлетворяющей всем неравенствам несовместной системы, предлагалось искать конечную последовательность (ас1,..., (ж* € Я") точек, называемую комитетом исследуемой системы, такую что каждому неравенству удовлетворяют более половины ее членов. В работах Вл.Д.Мазурова, Л.И.Тягунова, Д.Н.Гайнаноъа и других авторов понятие комитета получило широкое развитие. Были доказаны теоремы существования комитетов и обобщающих их конструкций для различных классов систем неравенств и получены верхние оценки числа членов комитетов с минимально возможным числом членов (называемых минимальными), разрешающих заданную систему неравенств. На основе понятия комитета системы неравенств введено понятие разделяющего комитета, являющегося обобщением понятия решения задачи дискриминантного анализа. Полученный таким образом метод формирования алгоритмов распознавания, называемых комитетными, исследовался в работах Н.Г.Белецкого, Ю.А.Зуева, В.В.Рязанова и других авторов.

2 Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. Наука. Москва. 1990.

3 A tlou: С.М, Kaylor D.J Inconsistent homogenous linear inequalities// Bull.Amer.Math.Soc.-1965.-v.71.№5.

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

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

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

Полученные результаты позволили классифицировать минимальные комитеты произвольных систем включений с 3 и 5 членами и указать способ построения такой классификации для произвольного числа членов.

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

На основе указанных результатов предложен метод нахождения комитета системы линейных неравенств с числом членов, не большим, а в ряде нетривиальных случаев строго меньшим, чем в алгоритме проектирования на плоскость, и превосходящим его по вычислительной сложности не более, чем на 0(т3), где т — число неравенств исследуемой системы.

Кроме того предложен конечношаговый алгоритм нахождения

4 Мазуров Вл.Д. О построении комитета системы выпуклых неравенств // Кибернетика.-Х!2.-19б7.-С.5б-59.

оценки числа шагов известного метода линейной коррекции для нахождения решений МСП системы линейных неравенств.

Практическая ценность. Полученные в работе новые методы могут быть положены в основу конкретных эффективных алгоритмов распознавания, которые предполагается использовать при проектировании программного продукта " КВАЗАР+" в рамках проекта ГНТП "Перспективные информационные технологии" (05.05.1190).

Апробация работы. Основные результаты диссертации докладывались на Конференции с международным участием "Математические методы распознавания образов" (г.Пущино, 1995), 27 Школе-конфереции молодых ученых (г.Екатеринбург, 1996), обсуждались на семинарах отдела проблем распознавания и методов комбинаторного анализа ВЦ РАН и отдела математического программирования ИММ УрО РАН.

Публикации. По теме диссертации автором опубликовано четыре работы.

Структура, и объем диссертации. Диссертация состоит из введения, трех глав, объединяющих 10 параграфов, заключения и списка литературы. Объем работы 101 страница, 18 рисунков на 18 страницах. Список литературы включает 74 наименования.

Содержание работы

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

Глава 1 является вступительной, в ней приводятся основные понятия теории комитетов: несовместной системы включений, коми-тетных конструкций, графа МСП и перечисляются те их известные 'свойства, которые будут необходимы для дальнейших рассуждений.

В обзоре автор в основном следует работам56. Материал главы разбит на четыре параграфа.

Первый параграф содержит определения комитета и его обобщений (комитетных конструкций) произвольной системы включений и определения разделяющих комитетных конструкций. Пусть в пространстве X, в котором справедлива аксиома выбора, заданы множества ..., Рассмотрим систему включений:

0'еад (1)

Система (1) называется несовместной, если ^ — Ряд утверждений, приводимых ниже, справедлив для произвольной системы (1), однако большая часть результатов будет сформулирована для частного случая системы (1) — системы неравенств:

ш >0 и е ад (2)

где X вещественное линейное пространство, /ь ••■)/т £ I" С {X —► Я} и ^ заданный класс функций (линейных, аффинных и т.д.). Систему

«6 А- (¿6 1.) (3)

для произвольного 0 ф Ь С Л>п будем называть подсистемой с индексом Ь системы (1). Обозначим через 0{Ь) — р),ел множество решений подсистемы (3).

Определение 1.1.1 Подсистема с индексом Ь называется лшк-сималъной совместной подсистемой (МСП) систелш (1), если Б{Ь) ф 0, и и О'}) = 0 для всякого е Ыт \ Ь.

Видно, что система (1), в которой не все £)_,• = 0, либо совместна, либо имеет собственные МСП.

Определение 1.1.2 Комитетом большинства системы (1) называется конечная последовательность <2 = (ж1,.. -,хч), х1 £ X, такая что |{г : Xх £ Dj}\ > (<?/2) для каждого ) £ Nm■

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

6 Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. Наука. Москва. 1990.

Если последовательность <2 удовлетворяет приведенному определению, то число ? называется числом членов комитета и говорят, что система (1) разрешима комитетом из q членов. Как правило, при изучении комитетной разрешимости системы (1) в работе будут рассматриваться комитеты, составленные из решений ее МСП, что не уменьшает общности исходной задачи.

Во втором параграфе приводятся некоторые известные теоремы существования комитетных конструкций, основной среди которых является теорема (1.2.5), впервые доказанная Вл.Д.Мазуровым7 и являющаяся критерием существования комитета системы линейных неравенств. Пусть далее X — вещественное линейное пространство, , • • ч ¡т £ X* линейные функционалы над А' и ¿1,..., 6т £ Я. Рассмотрим вопрос существования комитета системы неравенств:

/у(*)>6; 0' € №т). (4)

, В силу конечности системы (4), задача исследования ее комитетной разрешимости эквивалентна аналогичной задаче для подходящей системы неравенств над Ип, где п ранг системы функционалов

и, - ■ - ,1т '■

{сц,х)>Ь} (jENm). (5)

Из свойств систем линейных неравенств следует, что достаточным условием существования комитета системы (5) с заданным числом членов является существование комитета с тем же числом членов системы:

(а,-,г)>0 (6)

полученной из (5) заменой правых частей нулями. Пусть далее система (5) удовлетворяет условию:

а, + аа,- ^ О (а > 0, г € (7)

Заметим, что приведенному условию удовлетворяют почти все системы (5) в том смысле, что вектора 01,...,ат произвольной системы (5) с любой степенью точности можно приблизить векторами а[,..., а'т, такими, что система

удовлетворяет условию (7).

7 Мазуров Вл.Д. О комитете системы выпуклых неравенств.-Труды ЮМ-66. -Москва: МГУ,-1966 -X« 14, С.41.

Теорема 1.2.5 Система (6) разрешима комитетом большинства тогда и только тогда, когда она удовлетворяет условию (7), при этом число членов ее минимального комитета не превосходит т.

Следствие 1.2.1 Число членов минимального комитета системы (5), удовлетворяющей условию (7), не превосходит т.

В теореме 1.2.5 указывается абсолютная оценка числа членов минимального комитета для очень широкого класса систем линейных неравенств (и предложен простой метод построения комитета — метод проектирования на плоскость). В указанном классе оценка точна, нетрудно привести примеры систем неравенств на плоскости (например, система (2.16) в доказательстве теоремы 2.2.2), чьи минимальные комитеты содержат ровно столько членов, сколько неравенств в системе. С другой стороны, полученная оценка, в силу своей абсолютности, никак не зависит от исходных параметров системы (5) — векторов «1,..., ат и 6. Поэтому, можно получать более точные оценки, обладающие этим свойством. В главе 2 рассматривается один подход к уточнению указанной оценки, основанный на исследовании гиперграфа МСП системы (6), свойства которого будут рассматриваться ниже.

В третьем параграфе дается определение и приводятся некоторые известные свойства графа МСП системы (1), который является удобным инструментом при анализе комитетной разрешимости заданной системы неравенств.

Пусть Л,..., — индексы всех МСП системы (1).

Определение 1.3.1 Графом МСП системы (1) называется граф С = (У,и), у которого V = {Л .. .,./р} и и = £ ¿7 тогда

и только тогда, когда Ж и ■]^ = Л^,.

Понятие графа МСП впервые было введено в работе8 для системы строгих однородных линейных неравенств. Свойства этого графа подробно изучены в работах Д.Н.Гайнанова, Л.И.Тягунова и В.А.Новокшенова. Параграф содержит некоторые утверждения, доказанные этими авторами, которые требуются автору для дальней-

8 Тягунов Л.И. О выделении последовательности максимальных совместных подсистем несовместной системы линейных неравенств.// Математические методы планирования и управления в больших системах.- Свердловск: УНЦ АН СССР,-1973,С. 152-162. (Цеп. в ВИНИТИ, №7467-73.)

ших рассуждений. Большинство приводимых утверждений (1.3.21.3.6) сформулированы для графа МСП системы неравенств:

(aJtx)>0 U е Nm), (8)

в которой dj,x € R||а,-|| = 1 и Oj ±а,- ф 0 для любых i,j 6 Nm. В теореме 1.3.1 доказывается свойство связности графа МСП системы включений более общего вида. В параграфе 1 главы 2 понятие графа МСП произвольной системы включений (1) автором обобщается до понятия гипреграфа МСП и исследуются некоторые его свойства.

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

В первую группу можно отнести методы , базирующиеся на применении к задаче поиска комитета системы линейных неравенств той или иной модификации известного метода линейной коррекции решения совместной системы линейных неравенств, для которого доказана9 теорема о сходимости его к решению указанной системы за конечное число шагов. Полученные методы также принято называть методами линейной коррекции (для построения комитета из q членов). К сожалению, для таких методов известны лишь некоторые достаточные условия, гарантирующие их сходимость к искомому комитету. К тому же, как правило, вопрос разрешимости конкретной системы комитетом из заданного числа членов требует отдельного изучения.

Вторая большая группа методов, исследовавшаяся в работах Вл.Д.Мазурова, Л.И.Тягунова и др., основана на поиске решений всех MCI1 рассматриваемой системы неравенств методом свертывания, безусловной оптимизации или др. и решении затем некоторой разрешимой задачи целочисленного программирования. Достоинством этих методов является то, что они позволяют находить оптимальные комитеты, например, минимальный комитет исследуемой системы, а недостатком — большая трудоемкость.

К третьей группе методов следует отнести эффективные ко-нечношаговые алгоритмы, основанные на понижении размерно-

8 Novikoß A.B.J. On convergence proofs for perceptrons.- Proc. of Symposium of

Mathematical Theory of Automata. N.Y.: "Polytechnika",1962.

сти исходной задачи, исследовавшиеся в работах Вл.Д.Мазурова, Л.Д.Тягунова и А.И.Кривоногова. Одним из основных представителей этой группы является метод проектирования на плоскость, основанный на принципе доказательства теоремы 1.2.5. Метод проектирования на плоскость состоит из двух этапов:

1. нахождения подходящего оператора Ф : Д" —♦ В? и построения системы

(Фв,-,у)>0 (¿€ЛГт): (9)

2. построения минимального комитета системы (9) = (у1,..., у?), согласно, например, алгоритму А.И.Кривоногова. После этого комитет исходной системы получается из по правилу:

Основными достоинствами этого метода, обусловившими его активное применение для решения конкретных задач дискриминантного анализа, являются малая вычислительная сложность и то, что получаемый в результате комитет <2 содержит не более ш членов, что соответствует оценке числа членов минимального комитета системы (6). В главе 2 будет получена более точная оценка для системы линейных неравенств общего вида, и в главе 3 рассматривается соответствующая ей модификация описанного метода.

Многие методы построения комитетов содержат блоки нахождения решения некоторой МСП системы (6), в которых применяются те или иные методы решения совместных систем линейных неравенств. Одним из наиболее простых методов по реализации является конечношаговый метод линейной коррекции, приведенный в завершении параграфа. В главе 3 автором рассматриваются некоторые новые соображения по поводу построения верхней оценки числа его шагов, зависящей от исходных параметров заданной системы неравенств.

В главе 2 исследуются свойства минимального комитета не обязательно совместной системы включений:

«со, (¿елгт), (10)

где Б] — некоторые множества в Лп. Критерий минимальности числа членов является одним из наиболее часто употребимых критериев оптимальности на множестве комитетов системы (10). Тем не

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

Глава разбита на 4 параграфа.

Задача исследования существования и строения минимального комитета системы (10) тесно связана с задачей исследования структуры ее гиперграфа максимальных совместных подсистем (МСП), изучению некоторых свойств которого посвящен параграф 1 настоящей главы.

Определение 2.1.1 Гиперграфом МСП системы (10) назовем гиперграф С? = (У,и), где V — ..., — множество индексов МСП системы (10), и {./,•,,.. .,>/»,} £ II тогда и только тогда, когда у*=1 = Ыт.

Видно, что понятие гиперграфа МСП является естественным обобщением понятия графа МСП. Следующая теорема определяет условия, необходимые и достаточные для того, чтобы произвольный конечный гиперграф Г являлся гиперграфом МСП некоторой системы (10) с точностью до изоморфизма. Как обычно10, будем говорить, что гиперграфы Г и С изоморфны, если существует биекция <р : VГ V, обладающая свойством: и = {«ь...,^} £ 1/Г тогда и только тогда, когда {<¿>(1)1),... ,<р(ь,)} € II. В дальнейшем будем обозначать {^(щ),..., у>(г>;,)} = <р(и).

Теорема 2.1.1 Пусть Г = (КГ, [/Г), где УТ = ,..., гр}, — конечный гиперграф без кратных ребер. Гиперграф Г изоморфен гиперграфу б МСП системы (10) для подходящих чисел га, п и лшо-жеств £>1 ,...,£),п С Яп тогда и только тогда, когда IIГ удовлетворяет условиям:

если р > 1, то ЦТ не содержит петель, (11)

(и € {/Г, иСги)=>и>е иТ. (12)

Далее будем рассматривать гиперграфы с точностью до изоморфизма, отождествляя изоморфные Гиб. Другими словами, гиперграф без кратных ребер, удовлетворяющий условиям (11-12), будем называть гиперграфом МСП. Как следует из доказанной теоремы, класс

10Емелинев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов.-М.: Наука. 1990.-384 с.

гиперграфов МСП систем вида (10) достаточно широк. Выделим в нем подкласс гиперграфов МСП систем (10), разрешимых комитетом из q членов, для некоторого заданного д £ N. Пусть к £ Л^-ь

Определение 2.1.2 Конечную последовательность вершин Б = (я»,,..., гиперграфа Г, обладающую свойством: для каждого

Ь С -Л^+ь такого что |£| = к + 1, выполняется {х>,- : ./ £ £ VГ, назовем (д, к)-симплексом в гиперграфе Г = (КГ, (/Г).

Обозначение (<7, &)-симплекс выбрано из геометрических соображений. Видно, например, что вершины-элементы (2,1)-симплекса образуют в гиперграфе Г треугольник (3-цикл с двухэлементными ребрами). Следующее простое утверждение содержит критерий, связывающий разрешимость системы (2.1) комитетом с существованием в ее гиперграфе МСП (<7, £)-симплекса для подходящих чисел q,k £ N.

Теорема 2.1.2 Система (10) разрешима комитетом из q членов тогда и только тогда, когда в гиперграфе С ее МСП найдется под-гиперграф, вершины которого образуют (9 — 1, [(</ — 1)/2])-силтлекс.

Из теоремы 2.1.2 следует, что что задача поиска комитета с заданным числом членов системы неравенств эквивалентна задаче поиска подгиперграфа специального вида в гиперграфе ее МСП.

Рассматриваемые нами до сих пор свойства гиперграфа МСП справедливы для произвольной системы включений (10). Однако, как правило, задачи распознавания сводятся к анализу системы линейных неравенств, гиперграф МСП которой обладает специфическими свойствами.

Пусть задана система:

(а,-,*)>() U€Nm), (13)

где <1], х £ Я2 и среди векторов а^ нет нулевых и противоположно направленных. Пусть {Д,..., 1Р] — множество индексов МСП системы (13). Известно, что р нечетно и равно числу членов минимального комитета системы (13), будем полагать р — 2< + 1. Пусть (?2 = (^2,^/2) — гиперграф МСП системы (13). Гиперграф 62 обладает своего рода экстремальным свойством относительно числа членов минимального комитета системы (13). При выбранной в параграфе нумерации неравенств системы (13) и индексов ее

МСП строение гиперграфа Gi описывается в предложении 2.1.1. Ниже всюду полагается, что запись: и — {/^,...,/,,} подразумевает Ч < ii < ■ ■ ■ < г, ■

Предложение 2.1.1 Подмножество вершин {/,-,,...,/¿,} гиперграфа 6*2 является его ребром тогда и только тогда, когда для каждого k £ N, выполняется (гщ. (m0(j — t'fc) (mod р) < t + 1.

Пусть далее G = (V,U) — гиперграф МСП системы включений (10). Как обычно, будем говорить, что Gi гомоморфно вкладывается в G, если существует отображение ф : Vo —1• V' С V такое, что из {/,,, ...,/,-,}€ U2 следует: {ф(Ь1),..., ф(к,)} £ U. Подгиперграф G(V), порожденный в G множеством вершин V', назовем гомоморфным образом G2 при гомоморфизме ф. Будем говорить, что G(V') "более связен", чем G2, если найдется такое {/¡д,..., /¡,} С V2, что {/,-j,..k,} fcU-i, а • • */>(£,)} € U. Будем понимать терми-

ны "цепь" и "цикл" в графовом смысле, а именно, вершины гиперграфа G J\,..., Js образуют в нем цепь тогда и только тогда, когда UG содержит ребра {J,-,, Jts}, {J,-2,Л3}> •••> {Л,_,,/«.} Для некоторых попарно неравных номеров ¿1,..., i, € Ns.

Теорема 2.1.3 Пусть гиперграф Go МСП системы (13) на плоскости гомоморфно вкладывается е гиперграф G некоторой системы включений (10), причем его гомоморфный образ "более связен", чем G2, тогда число членов минимального комитета, разрешающего систему (10), меньше р.

В доказательстве теоремы указан алгоритм оценки числа членов минимального комитета системы (10). Если G2 гомоморфно вкладывается в G, то минимальный комитет системы (10) содержит не более р членов. Если при этом гомоморфный образ G2 "более связен", чем G2, то есть найдется такое {/, 1} С Vh, что £ U-,, € U, И l'(((ifc (mod ,))н l) - й)

(mod p) > t + 1, то число членов в минимальном комитете системы (10) не превосходит 2((jfc - i{(k ^mod ,»+!)) (mod p)) + 1 < p. Этими соображениями автор воспользовался при оценке числа членов минимального комитета системы линейных неравенств и при построении алгоритма построения комитета этой системы.

В теореме 2.1.2 была установлена связь между существованием у системы включений (10) комитета с заданным числом членов q

и существованием в гиперграфе ее МСП подгиперграфа определенного вида, а именно, подгиперграфа, вершины которого образуют (<7 — 1, [(? — 1)/2])-слмллекс. Видно, что при <7 = 3 такой подгипер-граф определяется единственным образом, однако с ростом q число попарно неизоморфных подгиперграфов, удовлетворяющих этому свойству, быстро растет. Рассмотрение примеров конкретных систем неравенств показывает, что свойства комитета как обобщенного решения системы (10) зависят оттого, какой именно подгиперграф ему соответствует. В параграфе 2 произведено перечисление минимальных комитетов с заданным числом членов, на основании понятия изоморфизма гиперграфов.

Определение 2.2.1 Последовательность (J^,..., Jq) индексов МСП системы (10) назовем д-комитетообразующей совокупностью (ц-КОС), если найдется минимальный комитет системы (10) (3 = (г1,.. . ,ж3), такой что х' £ = Г^ел ^з дЛЯ каждого г £ Мя.

Из доказательства теоремы 2.1.2 следует, что если число членов в минимальном комитете, разрешающем систему (10), равно <7, то понятия д-КОС и (</ — 1, [(? — 1)/2])-симплекса совпадают. Далее будем рассматривать только те комитеты системы (10), которые состоят из решений ее МСП. При этом будем полагать, что два комитета ф] и <?2, соответствующие члены которых являются решениями одних и тех же МСП, эквивалентны. В соответствии с этим предположением для классификации минимальных комитетов из q членов достаточно произвести перечисление всех попарно неизоморфных <7-КОС.

Пусть К = (/ь - •.,— 5-КОС системы (10), и пусть Ь(К) = {,..., где г < (¡. — множество индексов в К.

Определение 2.2.2 Гиперграфом (графол1) q-кoлnlmemooбpaзyю-щей совокупности К назовем подгиперграф С(К) (подграф Г(Л')), порожденный в гиперграфе (графе) МСП системы (10) множеством вершин Х(А').

Рассмотрим несовместную систему включений:

(УеВД, (14)

в которой, как в системе (10), Щ € Нп. Пусть К' = {][,..., — <?-КОС системы (14).

Определение 2.2.3 у-КОС К и К' называются изоморфными тогда V только тогда, когда изоморфны гиперграфы С(К) и С(К').

В силу приведенного определения задача перечисления #-КОС эквивалентна задаче перечисления попарно неизоморфных гиперграфов О(К). Поскольку гиперграф произвольной 3-КОС — цикл длины 3, и, следовательно, нее 3-КОС попарно изоморфны, то решим поставленную задачу в простейшем нетривиальном случае, когда </ = 5. Обозначим через «У множество всех систем произвольных включений вида (10), а через 5 произвольный элемент Я, конкретную систему (10). Обозначим через £(5) множество всех 5-КОС, которыми обладает система 5, а через АС(5) = и5-е5 Из вспомогатель-

ного предложения (2.2.1), в частности, следует, что 5-КОС К и К' изоморфны тогда и только тогда, когда изоморфны соответствующие им подграфы Г(Л') и Г'(Я'). Следующая теорема характеризует множество АС(5).

Теорема 2.2.1 Множество 1С(3) содержит ровно 15 попарно неизоморфных элементов.

Множество £(3) всех 5-КОС, по-доказанному, разбивается на 15 классов эквивалентности попарно изоморфных элементов, по числу попарно неизоморфных простых графов, допустимых определением 5-КОС. Однако, в практических задачах, нас, как правило, будет интересовать число классов эквивалентности во множестве /С(<5') для некоторого подмножества Я' множества всех систем включений. Естественно предположить, что при достаточно узком Б' результат, справедливый для /С(5), не будет справедливым для £(£'). Действительно, если множество всех конечных систем линейных однородных неравенств на плоскости, то из результатов11 следует, что в К(3с) все элементы попарно изоморфны, поскольку граф каждой 5-КОС является простым циклом длины 5. Интересно, что уже для множества SQ всех конечных систем полиномиальных неравенств степени не выше 2 на плоскости справедлив результат, аналогичный теореме 2.2.1.

Теорема 2.2.2 Множество А^(^й) содержит ровно 15 попарно пе-изоморфных элельентов.

11 Гайианов Д.Н. О графах максимальных совместных подсистем несовместных систем линейных неравенств.-Москва, 1981 .-46 с.Деп.ВИНИТИ, X» 229-81.

В доказательстве теорему приводится 15 конкретных систем неравенств из SQ. Каждая из приведенных систем обладает единственной 5-КОС, граф которой- изоморфен одному из 15 попарно неизоморфных простых графов, используемых в доказательстве теоремы 2.2.1. В каждом случае,указываются индексы МСП системы неравенств, строение ее 5-КОС Л',- и, графа Г(Л';), на прилагаемом каждому примеру рисунку, (рис.2-1,6) изображены множества решений МСП рассматриваемой системы неравенств.

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

V 0'€ЛГт), (15)

у которой х 6 Я" и соответствующая система однородных неравенств • не, I

(а}-,х)>(У 0'<ЕЛГт) (16)

также разрешима некоторым комитетом. В силу теоремы 1.2.5 это условие эквивалентно тому, что среди векторов а^ отсутствуют нулевые и противоположно направленные. Теорема 2.1.3 позволяет указать более точную, чем т, оценку числа членов минимального комитета системы линейных неравенств, зависящую от векторов ах,..'., ат и Ь.

Воспользуемся методом, предложенным в доказательстве теоремы 1.2.5, а именно, рассмотрим линейный оператор Ф : Л" —► /?2, обладающий свойством: среди вбкторов Ф(а[),..., Ф(а,„) нет нулевых и противоположно направленных векторов. В этом случае система:

(Ф(аДу)>0 иемт) (17)

комитетно разрешима, следовательно, этим же свойством обладает система:

(Ф(аД»)>:6,- 0"еЛГт). (18)

Если (}' = (у1, ■ ■ ■ ,уч) — комитет системы (18), то ф = (Ф*(у1), ■ ■ ■, Ф*(у4)) — комитет системы (15).

Пусть {/1,...,/р} и {Л,...,/г} — множества МСП, а С(17) и С(18) гиперграфы МСП систем (17) и (18) соответственно. По определению гиперграфа МСП, УЦ^г) = { /1,..., /р }. Обозначим через

Ш = 2™<-> \ (С/С(17) и {0, {/х},..., {/„}}).

Для каждого элемента и> — {/;,,...,} £ IV, в силу предложения 2.1.1, найдется к £ Л^, такое что (¿((¡ь (тоа з))+1) — ч) (тос1 р) > < + 1, где р — 21 + 1. Определим функцию Д : IV —► как А(ш) = (и- - (то<) ,))+1)} (тос! р), множество:

IV' = = {1<>,..., и,} £ IV| V* £ N. : ^ Э , () = |

И ЧИСЛО

Г тт{Д(ш)|и) € Н"}, если Ф 0, --*<»> = { иначе. (19)

Теорема 2.3.1 Число членов минимального комитета системы (15) не превосходит 2(5(15)+ 1В теореме получена более точная, чем ранее, оценка числа членов минимального комитета в классе систем линейных неравенств, зависящая от векторов ах,..., ат, Ь и оператора Ф. А именно, в доказательстве теоремы для системы (18) находится минимальный среди комитетов, построенных из решений МСП, индексы которых содержат индексы МСП системы (17), образующие в С?(17) цепь (на рис.17 изображена одна из таких систем).

Завершает главу параграф 4, в котором показывается, что разрешимость системы комитетом из 2к — 1 членов не обязательно влечет разрешимость ее комитетом из 1к' — 1 членов, где к' > к — натуральные числа. Это подтверждается приведенным примером системы полиномиальных неравенств степени не выше 4, разрешимой комитетом из 5 и неразрешимой комитетом из 7 членов (рис.18). Тем не менее, в предложении 2.4.1 приводится простое достаточное условие, при котором это все-таки выполняется для системы включений общего вида (10).

Предложение 2.4.1 Пусть система (10) разрешима комитетом, составленным из решений МСП с индексами . .., /гк-ь взятыми для каждой по одному. Если найдутся г,; £ такие что /,• и

,1] — Ыт, то система (10) разрешима комитетом из '¿к' — 1 членов для произвольного натурального к' > к.

Глава 3 посвящена описанию предложенных автором модификаций известных и активно применяемых при построении комитетов систем линейных неравенств методов: проектирования на плоскость и линейной коррекции.

Глава разбита на 2 параграфа. В параграфе 1 предлагается алгоритм, являющийся модификацией алгоритма проектирования на плоскость, находящий комитет произвольной системы линейных неравенств с небольшим, а в ряде случаев, меньшим числом членов, чем алгоритм проектирования на плоскость, и отличающийся от него па сложности на величину, оцениваемую полиномом от числа неравенств. Параграф содержит два подпараграфа. В первом собраны необходимые вспомогательные утверждения, второй содержит описание алгоритма и утверждения, обосновывающие его корректность. Алгоритм состоит из четырех стадий.

1 стадия. С помощью начальной стадии алгоритма проектирования системе (15) ставится в соответствие некоторая система:

(с,, у) > Ь3 (j £ Nm), (20)

заданная на плоскости, где cj = Ф«^, находятся индексы ¡\,..., 1р, р — 2t + 1 МСП системы

(cj,y)> 0 (j£Nm) (21)

и решения j/J,..., соответствующих МСП системы (21).

2 стадия. Находятся не обязательно различные МСП системы (20) с индексами J\,..., Jp из условия Jjt Э I,t для каждого к £ Np.

3 стадия Находятся минимальное s £ {0,1...,(} и j £ Np, такие что

з

Jj U(|J (modp))4-l)) = Nm,

k = l

после чего находится комитет Q' = (у1,..., y2s+1) системы (20), либо являющийся ее решением, если s = 0, либо составленный из решений МСП с индексами Jj,JWj+t) (mod р))+1), J((j (mod р))+1),...,

%,+( + »-1) (mod р))+1)> —1) (modp))+l)-

4 стадия совпадает с заключительной стадией алгоритма проектирования на плоскость: с помощью линейного оператора Ф* найденный на 3 стадии комитет Q' преобразуется в комитет Q =

• системы (15).

Основным результатом параграфа является

Теорема 3.1.1 1. Модифицированный метод проектирования на плоскость находит комитет и£>-2^15у+ 1 членов несовместной системы (15), при этоль 1 < <5(15) < < I и вычислительная

сложность метода превышает вычислительную сложность метода проектирования на плоскость не более нем на 0(гп3). 2. Существует непустой нетривиальный класс систем вида (15) , для которых указанный метод строит минимальный комитет из 2«(18) + 1 < р < т членов.

В формулировке теоремы число ¿(15) определяется по формуле (19), а число ¿(15) зависит от параметров метода и заданной системы.

Во втором случае предложен конечношаговый алгоритм, находящий верхнюю оценку числа шагов метода линейной коррекции (МЛК) для решения системы линейных неравенств:

(а,-,*)>0 UeNm) (22)

над вещественным гильбертовым пространством Н, в которой (ау, •) — непрерывные линейные функционалы над Н и а^ — элементы Я, удовлетворяющие' условию:

||а,-||=1, и'а)ф±аг V» ф з- (23)

Согласно теореме Новикова, метод линейной коррекции для произвольного начального приближения сходится за конечное число шагов к некоторому х(х°) <Е Н л— решению системы (22) тогда и только тогда, когда (22) совместна. В силу этой теоремы указанный метод является конечношаговым. Естественной является задача определения верхней оценки числа шагов (или числа коррекций), необходимых МЛК для нахождения некоторого решения наперед заданной системы (22) или установления ее несовместности. В доказательстве теоремы находится такая оценка при условии, что известно некоторое решение системы (22). Однако, вероятно, более интересной является задача нахождения верхней оценки, зависящей только от исходных параметров задачи:' элементов а\,..., ат и начального приближения я0. В работах И.И.Еремина и Вл.Д.Мазурова предложен подход для построения такой оценки, основанный на свойствах фейеровских отображений. Предлагаемый в параграфе метод реализует другой подход к решению этой задачи.

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

описание.и обоснование модифицированного метода линейной коррекции (ММЛК), для которого удаегея оценить число шагов. Основным результатом параграфа является

Теорема 3.2.3 Модифицированный метод линейной коррекции находит решение системы (22), удовлетворяющей условию (23) (или устанавливает ее несовместность) за конечное число шагов, причем число От операций проектирования, необходимое для решения (3.9), не превосходит 2т~1 — 1.

Из доказательства теоремы 3.2.3 следует, что ММЛК находит, в частности, верхнюю оценку числа коррекций, необходимых МЛК с начальным приближением а;0 = 0 для решения системы (22), зависящую только от а\,..., ат.

Заключение Основные результаты диссертационной работы состоят в следующем:

1. Введено новое понятие гиперграфа максимальных совместных 'подсистем (МСП) несовместной системы включений, обобщающее известное понятие графа МСП, и исследованы некоторые его свойства, связанные с разрешимостью указанной системы комитетами с определенным числом членов. А именно, показано, что система включений разрешима комитетом с наперед заданным числом членов тогда и только тогда, когда в ее гиперграфе МСП имеется подгиперграф некоторого специального вида; гиперграф МСП системы линейных однородных неравенств на плоскости обладает своего рода экстремальным свойством по отношению к числу членов минимального комитета, разрешающего данную систему.

2. Показано, что во множестве всех 5-комитетообразующих совокупностей в классе произвольных систем включений имеется ровно 15 попарно неизоморфных. Поскольку этот результат неверен для множеств 5-КОС более узких классов систем включений (например, для класса систем линейных однородных неравенств на плоскости), отдельно показывается справедливость результата в классе всех полиномиальных неравенств степени не выше 2, заданных на плоскости.

3. Пользуясь свойством гиперграфа МСП системы линейных однородных неравенств на плоскости, построена более точная оценка числа членов минимального комитета произвольной системы линейных неравенств.

4. На основе полученной оценки построен алгоритм поиска комитета системы линейных неравенств, родственный алгоритму проектирования на плоскость, получающий комитет с не большим, а для нетривиального класса систем с меньшим числом членов, чем алгоритм проектирования, и превосходящий его по вычислительной сложности не более чем на 0(гп3).

5. Кроме того предложен новый метод построения верхней оценки числа шагов метода линейной коррекции решения совместной системы линейных неравенств.

Публикации

[1]. Iihachai М. Estimating the Number of Steps in the Linear Correction Method for Solving a System of Linear Inequalities// Pattern Recognition and Image Analysis.-1993.-v.3.-№l.-p.l-5.

[2]. Ханай МАО. О комбинаторно устойчивых системах линейных неравенств.// Труды ИНПРИМ-96.-Новосибирск: ИМ СО РАН.-1996.-С.171-172.

[3]. ХачаА МАО. О построении комитета системы линейных неравенств методом проектирования на плоскость. -Москва, 1996, -21с., Деп. в ВИНИТИ, W3161-B96.

[4]. Хачай М.Ю. О существовании комитета большинства.// в сб. "Проблемы теоретической и прикладной математики". Тезисы докладов молодежной конференции №27, Екатеринбург: УрО

РАН, 1996, С.53-54.