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

На правах рукописиВздыхалкина Екатерина КонстантиновнаНАИЛУЧШЕЕ ОТДЕЛЕНИЕ ДВУХ МНОЖЕСТВС ПОМОЩЬЮ НЕСКОЛЬКИХ ГИПЕРПЛОСКОСТЕЙСпециальность 01.01.09 — дискретная математика иматематическая кибернетикаАвтореферат диссертации на соискание ученой степеникандидата физико-математических наукСанкт–Петербург2014Работа выполнена в Санкт–Петербургском государственном университете.Научный руководитель: доктор физико–математических наук, профессорПолякова Людмила НиколаевнаОфициальные оппоненты:Ерохин Владимир Иванович, доктор физико–математических наук,профессор,Санкт–Петербургскийгосударственныйтехнологическийинститут (технический университет), заведующий кафедрой инноватикии информационных технологийПевный Александр Борисович, доктор физико–математических наук,профессор, Сыктывкарский государственный университет, профессоркафедры прикладной математикиВедущая организация: Академический университет РАНЗащита состоится “2014 г.

в”часов на заседании диссер-тационного совета Д.212.232.29 на базе Санкт–Петербургского государственного университета по адресу: 199178, Санкт–Петербург, 10 линия В.О., д. 33/35,ауд. 74.С диссертацией можно ознакомиться в Научной библиотеке им. М. ГорькогоСанкт–Петербургского государственного университета по адресу: 199034,Санкт–Петербург, Университетская наб., д.

7/9 и на сайте http://spbu.ru/science/disser/dissertatsii-dopushchennye-k-zashchite-i-svedeniya-o-zashchite.Автореферат разослан “”2014 года.Ученый секретарь диссертационного советадоктор физ.–мат. наук, профессорНежинский В.М.ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫАктуальность темы исследования. Область прикладной математики,которая теперь называется математической диагностикой, активно развивается с 60-х годов прошлого столетия. Она включает широкий круг задач: распознавание образов, классификацию и кластеризацию данных, машинное обучение, медицинскую и техническую диагностику. Простейшей задачей такогорода является отделение двух множеств в конечномерном или бесконечномерном пространствах.При решении задач математической диагностики используются статистические методы, методы математического программирования (линейного, билинейного, выпуклого) и методы глобальной оптимизации.

Значительный вклад вразвитие этого направления внесли М. А. Айзерман, Э. М. Браверман, Л. И. Розоноэр, В. Н. Вапник, А. Л. Горелик, Ю. И. Журавлев, Ю. И. Неймарк, В. Н. Фомин, Я. З. Цыпкин, В. А. Якубович. Особо следует отметить О. Л. Мангасаряна.По его работам 1965–2014 годов можно проследить за всеми этапами развитияматематической диагностики.При решении конкретных задач математической диагностики возникаетнеобходимость в построении правила, в соответствии с которым судят о принадлежности данной точки тому или другому множеству. Это правило называют диагностическим правилом. Чаще всего его реализуют в виде дискриминантной функции (функционала). С начала 90-х годов прошлого столетия вкачестве дискриминантной активно используются недифференцируемые функции. С их помощью удается, в частности, улучшить результаты в следующемнаправлении: в случае, когда выпуклые оболочки двух отделяемых множествпересекаются, более точно выделить «смешанную полосу», содержащую точкикак одного, так и другого множества.Для решения негладких задач математической диагностики привлекаются3методы недифференцируемой оптимизации.

Примечательно, что при их реализации важную роль играет линейное программирование.Целью диссертационной работы является исследование параметрического варианта задачи наилучшего отделения выпуклой оболочки одного конечного множества от другого конечного множества с помощью несколькихгиперплоскостей и разработка численных методов решения таких задач. Исследование проводилось в русле работ Беннет-Мангасаряна1 и Асторино-Гаудиозо2 .Основные результаты, полученные в диссертации и выносимые на защиту:• получены необходимые и достаточные условия строгой отделимости двухмножеств с помощью h гиперплоскостей;• показано, что задача h-отделения сводится к конечному числу задач линейного программирования;• введен параметр для преодоления вычислительных трудностей, связанныхс принципиальной неединственностью решения соответствующих экстремальных задач;• разработан метод градиентного типа построения семейства разделяющихгиперплоскостей;• разработан безградиентный метод h-отделения, максимально учитывающийспецифику данной задачи;• оба предложенных метода реализованы в системе MATLAB;• исследована проблема выбора начального приближения в задачах строгойh-отделимости.Научная новизна.

Все основные результаты диссертации являются новыми.Bennett K. P., Mangassarian O. L. Robust linear programming discrimination of two linearlyinseparable sets // Optimization Methods and Software. 1992. Vol. 1, pp. 23–34.2 Astorino A., Gaudioso M. Polyhedral separability througt successive LP // JOTA. 2002.Vol. 112. No. 2, pp. 265—293.14Обоснованность и достоверность полученных результатов подтверждаетсяприведенными доказательствами, опирающимися на теории негладкого анализа, недефференцируемой оптимизации и линейного программирования, а такжерезультатами численных экспериментов.Практическая значимость работы состоит в том, что в ней разработанметод градиентного типа построения семейства разделяющих гиперплоскостейи безградиентный метод h-отделения, максимально учитывающий спецификуданной задачи.

Оба предложенных метода реализованы в системе MATLAB ипротестированы на примерах.Апробация работы. Результаты, изложенные в диссертации, докладывались и обсуждались на на 40-й, 41-й, 42-й и 44-й Международных научныхконференциях аспирантов и студентов «Процессы управления и устойчивость»(г. Санкт-Петербург, 6-9 апреля 2009 г., 5-8 апреля, 2010 г., 4-7 апреля 2011 г., и1-4 апреля 2013г.), международной конференции «Конструктивный негладкийанализ и смежные вопросы» (CNSA-2012) (г. Санкт-Петербург, 18-23 июня 2012г.), на Всероссийской молодежной научной школе-семинаре «Дискретные модели и методы принятия решений» (г. Новосибирск, 21-23 июня, 2013 г.; диплом залучший доклад), на Санкт-Петербургском городском семинаре по дискретномугармоническому анализу и геометрическому моделированию и на семинарах кафедры математической теории моделирования систем управления (факультетприкладной математики - процессов управления СПбГУ).Публикации.

По результатам исследований опубликовано 9 печатных работ, две из которых в соавторстве и три в изданиях, рекомендуемых ВАК. Вработах [3, 9] все результаты принадлежат диссертанту: соавтору (руководителю семинара) принадлежит постановка задачи.Структура и объем диссертации. Диссертация состоит из введения,шести параграфов, четырех дополнений и списка литературы. Объем диссертации составляет 96 страниц. Список литературы содержит 53 наименования.В диссертации имеется 36 рисунков.5СОДЕРЖАНИЕ РАБОТЫВо введении приводится обзор литературы по теме работы, обсуждается актуальность исследования, его теоретическая и практическая ценность,научная новизна.В § 1 рассматривается задача наилучшего линейного отделения двух конечных множеств A и B из Rn .

ПустьkA = {ai }mi=1 и B = {bj }j=1 .(1)Введем функциюmk1 X1 Xhw, ai i − γ + c + +−hw, bj i + γ + c + ,f (g) =m i=1k j=1где g = (w, γ), c > 0 — параметр, [u]+ = max{0, u} — плюсиковая функция.Справедливо следующее утверждение.Теорема 1.1. Множества A и B строго линейно отделимы тогда и толькотогда, когда существует вектор g∗ , на котором f (g∗ ) = 0.Учитывая, что f (g) ≥ 0 при всех g, заключаем, что задача строгого линейного отделения множества A от множества B сводится к экстремальной задаче(2).f (g) → minn+1g∈RВ свою очередь задача (2) эквивалентна задаче линейного программированияmk1 X1Xyi +zj → min,m i=1k j=1−hw, ai i + γ + yi ≥ c,i ∈ 1 : m;hw, bj i − γ + zj ≥ c, j ∈ 1 : k;yi ≥ 0, i ∈ 1 : m;zj ≥ 0, j ∈ 1 : k.6(3)Задача (3) всегда имеет решение.

Обозначим его w∗ , γ∗ , {yi∗ }, {zj∗ } и пустьµ — минимальное значение целевой функции. Если µ = 0, то гиперплоскостьH∗ , определяемая уравнением hw∗ , xi = γ∗ , строго отделяет множество A отмножества B. При этом можно вычислить ширину отделяющей полосы.При µ > 0 множества A и B не допускают строгого линейного отделения.В этом случае будем говорить, что указанная ранее гиперплоскость H∗ , является наилучшей гиперплоскостью, приближенно отделяющей множество A отмножества B. Можно вычислить ширину «смешанной полосы», содержащейточки обоих множеств.При µ > 0 имеется тонкость: может оказаться, что w∗ = O.

Доказывается,что в этом случае у задачи (3) существует другое решение с w∗ 6= O. Оностроится с помощью вспомогательной задачи линейного программирования.Приводятся примеры строгого и наилучшего приближенного линейногоотделения. Выясняется, что аддитивный параметр c играет роль нормирующегомножителя.В § 2 мы переходим к основной задаче — отделению выпуклой оболочки одного конечного множества от другого конечного множества с помощью hгиперплоскостей (задача h-отделения).Пусть множества A и B имеют вид (1).