Диссертация (1149837)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

САНКТ–ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиУДК 519.7Вздыхалкина Екатерина КонстантиновнаНаилучшее отделение двух множествс помощью нескольких гиперплоскостейДиссертация на соискание ученой степеникандидата физико–математических наукпо специальности 01.01.09 — дискретная математикаи математическая кибернетикаНаучный руководительдоктор физ.–мат. наук, профессорЛ.

Н. ПоляковаСанкт–Петербург 2014СОДЕРЖАНИЕВведение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3§1. Наилучшее линейное отделение двух множеств. . . . . . . . . . . . . . 14§2. Постановка задачи строгого h-отделения. . . . . . . . . . . . . . .

. . . . 25§3. Строгая h-отделимость и линейное программирование. . . . . . . . . 30§4. Метод «градиентного типа» строгого h-отделения. . . . . . . . . . . . 37§5. Безградиентный метод локального поиска. . . . . . . . . . . . . . . . . . 47§6. Численные эксперименты . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 56Дополнение A. Двойственность в линейном программировании. . . 79Дополнение B. Свойства плюсиковой функции . . . . . . . . . . . . . . . 82Дополнение C. Производные по направлению. . . . . . . . . . . .

. . . . 85Дополнение D. Лемма о сумме минимумов . . . . . . . . . . . . . . . . . . 89СПИСОК ЛИТЕРАТУРЫ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91Введение1. Область прикладной математики, которая теперь называется математической диагностикой [35], активно развивается с 60-х годов прошлогостолетия.

Она включает широкий круг задач: распознавание образов, классификацию и кластеризацию данных, машинное обучение, медицинскую итехническую диагностику. Простейшей задачей такого рода является отделение двух множеств в конечномерном или бесконечномерном пространствах.При решении задач математической диагностики используются статистические методы [2,53] , методы математического программирования (линейного [12, 38, 41, 51], билинейного [30], выпуклого [52]) и методы глобальной оптимизации [28]. Значительный вклад в развитие этого направлениявнесли М. А.

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

С начала 90-х годов прошлогостолетия в качестве дискриминантной активно используются недифферен-3цируемые функции. С их помощью удаётся, в частности, улучшить результаты в следующем направлении: в случае, когда выпуклые оболочки двухотделяемых множеств пересекаются, более точно выделить «смешаннуюполосу», содержащую точки как одного, так и другого множества.Для решения негладких задач математической диагностики привлекаются методы недифференцируемой оптимизации [35, 36, 27, 5, 7]. Примечательно, что при их реализации важную роль играет линейное программирование. Отметим также работы [31,33,34,39,48–50], которые обогатилиарсенал методов математической диагностики.Данное исследование проводится в русле работ Беннет-Мангасаряна [29]и Асторино-Гаудиозо [27].

Изучается задача наилучшего отделения выпуклой оболочки одного конечного множества от другого конечного множества с помощью нескольких гиперплоскостей. Используется недифференциремая дискриминантная функция с параметром. Параметр вводится дляпреодоления вычислительных трудностей, связанных с принципиальнойнеединственностью решения соответствующих экстремальных задач.2. Диссертация состоит из шести параграфов и четырёх дополнений.В §1 рассматривается задача наилучшего линейного отделения двух конечных множеств A и B из Rn . ПустьkA = {ai }mi=1 и B = {bj }j=1 .(1)Введём функцию [29]mk1 X1 Xhw, ai i − γ + c + +−hw, bj i + γ + c + ,f (g) =m i=1k j=1где g = (w, γ), c > 0 — параметр (в [29] вместо c стоит единица), [u]+ =max{0, u} — плюсиковая функция.

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

Если µ = 0, то ги-перплоскость H∗ , определяемая уравнением hw∗ , xi = γ∗ , строго отделяетмножество A от множества B. При этом можно вычислить ширину отделяющей полосы.При µ > 0 множества A и B не допускают строгого линейного отделения. В этом случае будем говорить, что указанная ранее гиперплоскость H∗ , является наилучшей гиперплоскостью, приближённо отделяющей множество A от множества B.

Можно вычислить ширину «смешаннойполосы», содержащей точки обоих множеств.При µ > 0 имеется тонкость: может оказаться, что w∗ = O. Доказывается, что в этом случае у задачи (3) существует другое решение с w∗ 6= O.5Оно строится с помощью вспомогательной задачи линейного программирования.Приводятся примеры строгого и наилучшего приближённого линейногоотделения.

Выясняется, что аддитивный параметр c играет роль нормирующего множителя.§1 написан на основе работ [8, 10, 40].В §2 переходим к основной задаче — отделению выпуклой оболочки одного конечного множества от другого конечного множества с помощью hгиперплоскостей (задача h-отделения).Пусть множества A и B имеют вид (1). Обозначим co(A) выпуклую оболочку множества A.Введём функцию от матрицы [27]mk1X1 Xmax hws , ai i − γs + c + +min −hws , bj i + γs + c + .F (G) =m i=1 s∈1:hk j=1 s∈1:hЗдесь G — матрица размера h × (n + 1) со строкамиg s = (ws , γs ),s ∈ 1 : h,c > 0 — параметр (в [27] вместо c стоит единица).

Матрицу G указанныхразмеров будем называть подходящей, если у неё все ws ненулевые.Справедливо следующее утверждение.Теорема 2.1. Выпуклая оболочка множества A и множество B строгоh-отделимы тогда и только тогда, когда существует подходящая матрица G∗ , на которой F (G∗ ) = 0.Учитывая, что F (G) ≥ 0 при всех G, заключаем, что задача строгогоh-отделения сводится к экстремальной задачеF (G) →min .G∈Rh,n+16(4)При минимизации функции F (G) наибольшую трудность доставляет второе слагаемое (сумма минимумов).

Оно делает функцию F (G) невыпуклой(к тому, что она негладкая).В §3 показывается, что задача (4) с помощью «леммы о сумме минимумов» сводится к конечному числу задач линейного программирования. Дляэтого вводятся индексные цепочки S = (s1 , s2 , . . . , sk ), где sj ∈ 1 : h прикаждом j ∈ 1 : k. Каждой такой цепочке S сопоставляется экстремальнаязадачаmk s1 X1 Xmax hw , ai i − γs + c + +−hwsj , bj i + γsj + c + → min,Gm i=1 s∈1:hk j=1эквивалентная задаче линейного программированияmk1 X1Xpi +qj → min,m i=1k j=1−hai , ws i + γs + pi ≥ c,(5)i ∈ 1 : m, s ∈ 1 : h;hbj , wsj i − γsj + qj ≥ c, j ∈ 1 : k;pi ≥ 0,i ∈ 1 : m;qj ≥ 0,j ∈ 1 : k.Задача (5) имеет решение при всех S. Выделим цепочку S∗ , на которой минимальное значение целевой функции в задаче (5) принимает наименьшеезначение.

Обозначим {w∗s }, {γs∗ }, {p∗i }, {qj∗ } соответствующее решениезадачи (5). В §3 доказывается (теорема 3.1), что матрица G∗ , составленнаяиз строк (w∗s , γs∗ ), s ∈ 1 : h, является решением задачи (4).Возможны такие случаи.1) F (G∗ ) = 0 и G∗ — подходящая матрица. Тогда система гиперплоскостей H∗s , определяемых уравнениями hw∗s , xi = γs∗ , s ∈ 1 : h, строгоотделяет co(A) от B.2) F (G∗ ) = 0, но матрица G∗ — неподходящая. В этом случае справедливо7утверждение (теорема 2.2): не все w∗s нулевые; если обозначить через Jмножество индексов ненулевых w∗s , то множества co(A) и B строгоh − |J| -отделимы.3) F (G∗ ) > 0 и G∗ — подходящая матрица.

По аналогии со случаем h = 1будем говорить, что система гиперплоскостей H∗s , s ∈ 1 : h, осуществляет наилучшее приближённое h-отделение множества co(A) от B.В §3 приведён пример строгого 2-отделения.§2 и §3 написаны на основе работ [19, 21, 22].3. Итак, в §3 установлен принципиальный факт: задача h-отделения сводится к конечному числу задач линейного программирования. Однако количество таких задач линейного программирования может быть большим.Это побуждает обратиться к итерационным методам, которые позволяютполучить приближённое решение задачи h-отделения с требуемой точностью.Из общих соображений следует, что функция от матрицы F (G) дифференцируема по направлениям (в качестве которых также выступают матрицы).

На этой основе в §4 строится метод «градиентного типа» для приближённого решения задачи h-отделения (4). Опишем его принципальнуюсхему.Начнём с производной по направлению. По определениюF (G + tV ) − F (G).t→+0tF ′ (G, V ) = limДля того чтобы записать для F ′ (G, V ) явную формулу, введём обозначения8f (v, u) = hv, ui + c,!!ai−bjâi =, b̌j =,−11ϕ̂i (G) = max f (g s , âi ),s∈1:hψ̌j (G) = min f (g s , b̌j ),s∈1:hψj (G) = ψ̌j (G) + .ϕi (G) = ϕ̂i (G) + ,Тогдаmk1X1 Xϕi (G) +ψj (G).F (G) =m i=1k j=1Положим далееR̂i (G) = s ∈ 1 : h | f (g s , âi ) = ϕ̂i (G) ,Řj (G) = s ∈ 1 : h | f (g s , b̌j ) = ψ̌j (G) .Теорема 4.1.

Справедлива формулаmk1X ′1 X ′ϕ (G, V ) +ψ (G, V ),F (G, V ) =m i=1 ik j=1 j′гдеmax hv s , âi i,s∈R̂i (G) sϕ′i (G, V ) =maxhv,âi,i+s∈R̂(G)i0,min hv s , b̌j i,s∈Ř (G) j sψj′ (G, V ) =,hv,b̌iminj+s∈Řj (G)0,9если ϕ̂i (G) > 0,если ϕ̂i (G) = 0,если ϕ̂i (G) < 0;если ψ̌j (G) > 0,если ψ̌j (G) = 0,если ψ̌j (G) < 0.В Дополнении C приводится доказательство этой теоремы.Переходим к описанию одного шага численного метода минимизациифункции F (G).

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов диссертации