Построение семейств разделяющих гиперплоскостей

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

1. ПОСТРОЕНИЕ СЕМЕЙСТВ ГИПЕРПЛОСКОСТЕЙ, РАЗДЕЛЯЮЩИХ ПОЛИЭДРЫ
1.1. Построение разделяющих гиперплоскостей с помощью решения задач безусловной минимизации
1.2. Расширение семейства разделяющих гиперплоскостей
1.3. Свойства разделяющих гиперплоскостей
1.4. Разделение скорректированных полиэдров
1.5. Операция масштабирования
2. ПОСТРОЕНИЕ СЕМЕЙСТВА РАЗДЕЛЯЮЩИХ ГИПЕРПЛОСКОСТЕЙ МАКСИМАЛЬНОЙ ТОЛЩИНЫ
2.1. Определение семейства разделяющих гиперплоскостей с помощью решения двойственной задачи
2.2. Определение решения системы Еремина для построения семейства разделяющих гиперплоскостей максимальной толщины
3. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩИХ ГИПЕРПЛОСКОСТЕЙ ДЛЯ ПОЛИЭДРОВ, ЗАДАННЫХ СИСТЕМАМИ РАВЕНСТВ НА НЕОТРИЦАТЕЛЬНОМ ОРТАНТЕ
3.1. Построение двух семейств разделяющих гиперплоскостей
3.2. Решение двойственной задачи
4. ПОСТРОЕНИЕ СЕМЕЙСТВА ГИПЕРПЛОСКОСТЕЙ, РАЗДЕЛЯЮЩИХ ПОЛИТОПЫ
4.1. Прямая и двойственная задачи
4.2. Построение гиперплоскостей, разделяющих выпуклые оболочки
4.3. Численный метод решения вспомогательных оптимизационных
задач в случае, когда п » т
4.4. Численный метод решения вспомогательных оптимизационных
задач в случае, когда т п

5. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩИХ ГИПЕРПЛОСКОСТЕЙ В СЛУЧАЕ ПЕРЕСЕКАЮЩИХСЯ ПОЛИТОПОВ
5.1. Случай то п
5.2. Случай п т
ПРИЛОЖЕНИЕ
ЗАКЛЮЧЕНИЕ
ЦИТИРОВАННАЯ ЛИТЕРАТУРА

В последние 50 лет бурное развитие получило новое направление в научных исследованиях — теория распознавания и обработка изображений. Интенсивное развитие этой области знаний обусловлено большой потребностью в решении практических задач в самых различных областях: в медицинской диагностике, в геологическом прогнозировании, в робототехнике, в оценке политических и экономических ситуаций, в предсказании землетрясений и других природных катаклизмов, в задачах идентификации букв для автоматического чтения, идентификации речи и т.д.
Крупные результаты в этой области были получены во второй половине прошлого века. Укажем лишь некоторых из ведущих ученых, стоявших у истоков исследований в этой области: A.A. Ляпунов, О.Б. Лупанов, С.В. Яблонский, Ю.И. Журавлев, С.Н. Черников, И.И. Еремин, М.А. Айзерман. В 1998 году вышли в свет “Избранные научные труды Ю.И. Журавлева”, в которых изложены основополагающие работы но математическим методам распознавания образов и дискретной математике. Научная школа Ю.И. Журавлева, создававшаяся на базе Вычислительного центра АН СССР, постоянно расширяется и сейчас имеет своих последователей не только в нашей стране, но и за рубежом.
Среди других научных школ упомянем коллектив МГУ, созданный A.A. Ляпуновым, С.В. Яблонским, О.Б. Лупановым. В Институте математики и механики УрО РАН успешно работает группа, образованная в 60-е годы С.Н. Черниковым и впоследствии возглавленная И.И. Ереминым
На протяжении последних 14 лет в Москве издается журнал “Pattern recognition and image analysis”, в котором публикуются важнейшие работы, выполненные в области кибернетики и теоретической информатики.
Большая работа в области распознавания образов ведется в США в университете Висконсина под руководством профессора О. Мангасарьяна. Вместе со своими учениками О. Мангасарьян провел обширные исследования по общей теории диагностики, классификации и по применению методов оптимизаций в распознавании образов, решение прикладной задач в меди-

щ и 42, удовлетворяющие (3.1) и такие, что разделяющая гиперплоскость стх — 7 = 0 принадлежит либо Г^а), либо Гг(а;).
Пример 3.1. Пусть полиэдры задаются условиями
Х — {х € К3 : х1 + х2 + х3 = 2, х1 + ж3 = 1, х > 0з},
Х2 = {а: е К3 : х1 — х2 — х3 = 1, х1 — х3 = 5, х > Оз}.
Тогда
' 1 1 Г и го Т 1 1—1 1 гЧ 1 гЧ | ' 2 " ' 1 ’
, ь1 = О4 ю II
1 0 1 1 0 -1 1
Введем гиперплоскость стх = 7 где ст = [1 0 0] и 7 = 3, т.е. х1 — 3 = 0. Пусть х € Х. Тогда из
х1 = 2 — х2 — х3, х2 > 0, х3 > 0 х1 = 1 — х3, х3 >
получим, что х1 < 2. Пусть теперь х 6 Х2. Тогда из
х1 = 1 + х2 ■+- х3, х2 > 0, х3 > О, х1 = 5 + х3, х3 >
следует, что х1 > 3. Поэтому гиперплоскость хх — 3 = 0 строго разделяет непустые непересекающиеся полиэдры Х И Х2.
Пусть существует и € Я2, ит = [к и^] и А{ и — с. Тогда получим, что щ + щ = 1, «1 = 0, и щ + и,2 — 0, но это невозможно. Если А^и = —с, то отсюда следует, ЧТО и + П2 = 1, —щ = 0, И —щ — 112 = 0. Это также невозможно. Мы доказали, что не существует таких щ и иг, удовлетворяющих совместной альтернативной системе (3.1), чтобы при этом выполнялось либо условие с = А{иъ либо с = —АГ иг-