ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ 4
1. ПОСТРОЕНИЕ СЕМЕЙСТВ ГИПЕРПЛОСКОСТЕЙ, РАЗДЕЛЯЮЩИХ ПОЛИЭДРЫ 12
1.1. Построение разделяющих гиперплоскостей с помощью решения задач безусловной минимизации ..........................12
1.2. Расширение семейства разделяющих гиперплоскостей..........21
1.3. Свойства разделяющих гиперплоскостей......................28
1.4. Разделение скорректированных полиэдров....................29
1.5. Операция масштабирования..................................34
2. ПОСТРОЕНИЕ СЕМЕЙСТВА РАЗДЕЛЯЮЩИХ ГИПЕРПЛОСКОСТЕЙ МАКСИМАЛЬНОЙ ТОЛЩИНЫ 38
2.1. Определение семейства разделяющих гиперплоскостей с помощью решения двойственной задачи.............................38
2.2. Определение решения системы Еремина для построения семейства разделяющих гиперплоскостей максимальной толщины . . 42
3. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩИХ ГИПЕРПЛОСКОСТЕЙ ДЛЯ ПОЛИЭДРОВ, ЗАДАННЫХ СИСТЕМАМИ РАВЕНСТВ НА НЕОТРИЦАТЕЛЬНОМ ОРТАНТЕ 46
3.1. Построение двух семейств разделяющих гиперплоскостей ... 46
3.2. Решение двойственной задачи...............................53
4. ПОСТРОЕНИЕ СЕМЕЙСТВА ГИПЕРПЛОСКОСТЕЙ, РАЗДЕЛЯЮЩИХ ПОЛИТОПЫ 55
4.1. Прямая и двойственная задачи..............................55
4.2. Построение гиперплоскостей, разделяющих выпуклые оболочки 59
4.3. Численный метод решения вспомогательных оптимизационных
задач в случае, когда п т..................................62
4.4. Численный метод решения вспомогательных оптимизационных
задач в случае, когда тп^п.................................66
2
5. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩИХ ГИПЕРПЛОСКОСТЕЙ В СЛУЧАЕ ПЕРЕСЕКАЮЩИХСЯ ПОЛИТОПОВ 70
5.1. Случай т^> п................................70
5.2. Случай п т..................................77
ПРИЛОЖЕНИЕ 83
ЗАКЛЮЧЕНИЕ 85
ЦИТИРОВАННАЯ ЛИТЕРАТУРА 87
ВВЕДЕНИЕ
В последние 50 лет бурное развитие получило новое направление в научных исследованиях — теории распознавания и обработка изображений. Интенсивное развитие этой области знаний обусловлено большой потребностью в решении практических задач в самых различных областях: в медицинской диагностике, в геологическом прогнозировании, в робототехнике, в оценке политических и экономических ситуаций, в предсказании землетрясений и других природных катаклизмов, в задачах идентификации букв для автоматического чтения, идентификации речи и т.д.
Крупные результаты в этой области были получены во второй половине прошлого века. Укажем лишь некоторых из ведущих ученых, стоявших у истоков исследований в этой области: A.A. Ляпунов, О.Б. Лупаиов, С.В. Яблонский, Ю.И. Журавлев, С.Н. Черников, И.И. Еремин, М.А. Айзерман. В 1998 го;^у вышли в свет “Избранные научные труды Ю.И. Журавлева”, в которых изложены основополагающие работы по математическим методам распознавания образов и дискретной математике. Научная школа Ю.И. Журавлева, создававшаяся на базе Вы числител ыюто центра АН СССР, постоянно расширяется и сейчас имеет своих последователей не только в нашей стране, но и за рубежом.
Среди других научных школ упомянем коллектив МГУ, созданный
A.A. Ляпуновым, С.В. Яблонским, О.Б. Луиановым. В Институте математики и механики УрО РАН успешно работает группа, образованная в 60-е тоды С.Н. Черниковым и впоследствии возглавленная И.И. Ереминым
На протяжении последних 14 лет в Москве издается журнал “Pattern recognition and image analysis”, в котором публикуются важнейшие работы, выполненные в области кибернетики и теоретической информатики.
Большая работа в области распознавания образов ведется в США в университете Висконсина под руководством профессора О. Мангасарьяна. Вместе со своими учениками О. Мангасарьяи провел обширные исследования но общей теории диагностики, классификации и по применению методов оптимизаций в распознавании образов, решение прикладной задач в меди-
4
цине и биологии. Укажем лишь на некоторые из многочисленных публикации О.Мангасарьяна и ею учеников: работа О. Мангасарьина, II.Стрита,
В.Волбсрта [44], К.Беннетт, Е.БредестеЙра [30]. Алгоритмы и программы распознавания образов приведены в книге В.Н. Банника [3]. Проблемы классификации изучаются в книге С.Бойда и Л. Ванденберга [32].
Среди многочисленных проблем, возникающих в области распознавания, укажем задачу построения гиперплоскостей, разделяющих два выпуклых множества. Построению численных методов решения этой задачи посвящена данная работа. В качестве выпуклых множеств рассмотрены полиэдры (пересечение конечного числа полупространств) и политопы (выпуклые оболочки конечного числа точек).
Теорема о существовании разделяющей гиперплоскости играет важную роль в функциональном анализе, в теории оптимизации и исследовании операций. При решении практических задач важно не только знать, что разделяющая гиперплоскость существует, но и уметь конструктивно ее строить. В данной работе в главах 1-3 предлагаются численные методы нахождения семейств гиперплоскостей, разделяющих два неиересскающихся непустых полиэдра, заданных с помощью систем линейных неравенств и систем линейных уравнений с неотрицательными переменными. В главах 4 и 5 разработаны численные методы построения разделяющих гиперплоскостей для политопов.
Предлагаемые численные методы основаны на использовании теорем об альтернативах и метода модифицированных функций Лагранжа . Подход, связанный с применением теорем об альтернативах в численных методах, возник несколько лет назад и изложен в работах [7]-[15], [33]- [37]. Он основан на отыскании исевдорешений несовместных систем линейных равенств и неравенств. По найденным псевдорешениям строятся нормальные решении альтернативных совместных систем и с их помощью определяются гиперплоскости, разделяющие'полиэдры. В работе приводятся иллюстративные примеры, даны таблицы с численными расчетами тестовых примеров. Теоремам об альтернативах посвященное большое количество публикаций. Укажем, например, [С],[22], [31]—[33], [38].
В главе 1 рассмотрено применение нормального решения альтернативной
5
системы дли построении семейства разделяющих гиперплоскостей. Использование результатов работы [9, 11, 12], позволяет найти нормальное решение из решении задачи безусловной минимизации невязки несовместной системы неравенств, задающей оба полиэдра. Если число переменных в задаче безусловной минимизации гораздо меньше, чем в альтернативной совместной системе, то такие расчеты менее трудоемки, чем нахождение решении альтернативной системы.
В основе лежит теорема И.И. Еремина о гиперплоскости, разделяющей полиэдры, заданные системами неравенств [15, теорема 10.1]. Используется специфический вид разделяющей гиперплоскости, нормаль и сдвиг которой выражены через произвольное решение некоторой системы, являющейся альтернативной к несовместной системе. Эта несовместная система состоит из двух совместных подсистем, каждая из которых определяет непустой полиэдр. Система несовместна, так как эти полиэдры не пересекаются. Построение разделяющих гиперплоскостей существенно опирается на теоремы об альтернативах.
В главе 1 рассмотрены два полиэдра
Х\ = {х Є &Л : Ліх > Ьі}, Хх = {х Є Кп : Л2х >Ь2}.
Предполагается , что эти полиэдры непусты, а их пересечение пусто. Тогда система
А\Х>Ъи А2х > (0.1)
несовместна, а альтернативная система
Л^і + Л?Д2 = 0п, ЬІщ + ЬІщ+ = р, щ > 0ТО1, щ > 0Ш2, (0.2)
где р > 0 , напротив, совместна . Определим линейную функцию <р(х,а) от переменного вектора х, скаляра а из интервала [0,1]:
ір(х, а) = (А\х - Ь\) + ар. (0.3)
Если щ - решение системы (0.2), то уравнение <р(х,а) = 0 задает гиперплоскость, разделяющую полиэдры Х\ и Х2. Гиперплоскость (0.3) при а = 0.5
С
была впервые построена И.И.Ереминым. Метод определения функции ср состоит в нахождении решении системы (0.2) и использовании формулы (0.3). Такой подход весьма затруднителен в том случае , когда т п. Поэтому в первой главе данной работы для построения разделяющей гиперплоскости предлагается решать следующую задачу безусловной минимизации в п - мерном пространстве:
Доказана теорема, утверждающая, что найденный из этой задачи вектор х* является псевдорешением системы (0.1) и нормальное решение й*Т =
Функция </?, которая определяет разделяющую гиперплоскость, записывается в виде:
Объединение всех таких гиперплоскостей, когда а изменяется от 0 до 1, называется семейством параллельных разделяющих гиперплоскостей.
В теореме 1.2 дан анализ решений задачи (0.4). Показано в частности , что, если Х\ 0, Х\ П Х2 — 0, 'їх) все решения системы (0.2) отлич-
ны от нуля, кроме того, дана формула для определения толщины семейства разделяющих гиперплоскостей. Предложенный подход к построению разделяющих гиперплоскостей наиболее эффективен в задачах, где размерность вектора п невелика,но количество ограничений тп может быть значительным, т.е. п <^т .
В § 1.2 показано, что в ряде случаев найденное семейство разделяющих гиперплоскостей можно расширить, решая две вспомогательные задачи линейного программирования. Приведены три примера, иллюстрирующие найденные свойства разделяющих гиперплоскостей . Система (0.2) имеет весьма глубокий смысл. Приведенная в диссертации теорема 1.4 утверждает, что
тіл І[||(Ь‘ - /1Іі)+||2 + ||(62 - АгаО+Н2].
(0.4)
й[Т(АіХ — 6і) + ар = 0, где 0 < а < 1.
(0.5)
7
- Київ+380960830922