Наилучшее отделение двух множеств с помощью нескольких гиперплоскостей

• Автор: Вздыхалкина, Екатерина Константиновна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Санкт-Петербург
• Количество страниц: 96 с. : ил.

СОДЕРЖАНИЕ
Введение

§1. Наилучшее линейное отделение двух множеств

§2. Постановка задачи строгого /1-отделения

§3. Строгая /г-отделимость и линейное программирование

§4. Метод «градиентного типа» строгого /г-отделения

§5. Безградиентный метод локального поиска

§6. Численные эксперименты

Дополнение А. Двойственность в линейном программировании

Дополнение В. Свойства плюсиковой функции

Дополнение С. Производные по направлению

Дополнение О. Лемма о сумме минимумов
СПИСОК ЛИТЕРАТУРЫ

Введение
1. Область прикладной математики, которая теперь называется математической диагностикой [35], активно развивается с 60-х годов прошлого столетия. Она включает широкий круг задач: распознавание образов, классификацию и кластеризацию данных, машинное обучение, медицинскую и техническую диагностику. Простейшей задачей такого рода является отделение двух множеств в конечномерном или бесконечномерном пространствах.
При решении задач математической диагностики используются статистические методы [2,53] , методы математического программирования (линейного [12,38,41,51], билинейного [30], выпуклого [52]) и методы глобальной оптимизации [28]. Значительный вклад в развитие этого направления внесли М. А. Айзерман, Э. М. Браверман, Л. И. Розоноэр [1], В. Н. Вап-ник [2, 53], А. Л. Горелик [4], Ю. И. Журавлёв [6], Ю. И. Неймарк [11],
В. Н. Фомин [24], Я. 3. Цыпкин [25], В. А. Якубович [26]. Особо следует отметить О. Л. Мангасаряна. По его работам 1965-2014 годов [в частности, 41-47, 29, 30, 37] можно проследить за всеми этапами развития математической диагностики.
При решении конкретных задач математической диагностики возникает необходимость в построении правила, в соответствии с которым судят о принадлежности данной точки тому или другому множеству. Это правило называют диагностическим правилом. Чаще всего его реализуют в виде дискриминантной функции (функционала). С начала 90-х годов прошлого столетия в качестве дискриминантной активно используются недифферен-

цируемые функции. С их помощью удаётся, в частности, улучшить результаты в следующем направлении: в случае, когда выпуклые оболочки двух отделяемых множеств пересекаются, более точно выделить «смешанную полосу», содержащую точки как одного, так и другого множества.
Для решения негладких задач математической диагностики привлекаются методы недифференцируемой оптимизации [35, 36, 27, 5, 7]. Примечательно, что при их реализации важную роль играет линейное программирование. Отметим также работы [31,33,34,39,48-50], которые обогатили арсенал методов математической диагностики.
Данное исследование проводится в русле работ Беннет-Мангасаряна [29] и Асторино-Гаудиозо [27]. Изучается задача наилучшего отделения выпуклой оболочки одного конечного множества от другого конечного множества с помощью нескольких гиперплоскостей. Используется недифферен-циремая дискриминантная функция с параметром. Параметр вводится для преодоления вычислительных трудностей, связанных с принципиальной неединственностью решения соответствующих экстремальных задач.
2. Диссертация состоит из шести параграфов и четырёх дополнений.
В §1 рассматривается задача наилучшего линейного отделения двух конечных множеств А и В из Ж". Пусть
А = {щ}! и В — {6Д*Ц. (1)
Введём функцию [29]
- тп н к
Л^) = -5][(г{;>^)-/7 + с]+ + ^^[-<щбД+ 7 + с]+,
2=1 j=
где д = (ш,7), с > 0 — параметр (в [29] вместо с стоит единица), [11]+ = тах{0, и} — плюсиковая функция. Справедливо следующее утверждение.

Рис. 3.3. Строгое 2-отделение при £ = (1, 2, 1)
Этот случай симметричен случаю 5 = (1, 1, 2).
При 5 = (2, 1. 1) строгой 2-отделимости нет (см. рис. 3.4).
) ‘ч
У У К ► >

Рис. 3.4. Случай 6” = (2, 1, 1)
Решением задачи, аналогичной (3.6), при с = 1 является вектор
г = (0.0000, -112.0230, -1.0000, 0.0000, 111.8673, 273.7824,
2.0000, 2.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000).
Минимальное значение целевой функции равно единице.
3.5. В общем случае задание вектора в 6 П соответствует разбиению множества В, состоящего из к векторов, на И подмножеств. Число таких разбиений и определяет количество задач линейного программирования вида (3.5), к решению которых сводится решение задачи (3.1).
Если заранее известно, что множества со (Л) и В строго Л-отделимы, то решение задачи (3.1) можно упростить. После разбиения множества В