Содержание к диссертации
Введение
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. Численный метод решения вспомогательных оптимизационных задач в случае, когда m 66
5. Построение разделяющих гиперплоскостей в случае пересекающихся политопов 70
5.1. Случай m70
5.2. Случай п 77
Приложение 83
Заключение 85
Цитированная литература 87
- Расширение семейства разделяющих гиперплоскостей
- Разделение скорректированных полиэдров
- Определение решения системы Еремина для построения семейства разделяющих гиперплоскостей максимальной толщины
- Построение гиперплоскостей, разделяющих выпуклые оболочки
Введение к работе
В последние 50 лет бурное развитие получило новое направление в научных исследованиях — теория распознавания и обработка изображений. Интенсивное развитие этой области знаний обусловлено большой потребностью в решении практических задач в самых различных областях: в медицинской диагностике, в геологическом прогнозировании, в робототехнике, в оценке политических и экономических ситуаций, в предсказании землетрясений и других природных катаклизмов, в задачах идентификации букв для автоматического чтения, идентификации речи и т.д.
Крупные результаты в этой области были получены во второй половине прошлого века. Укажем лишь некоторых из ведущих ученых, стоявших у истоков исследований в этой области: А.А. Ляпунов, О.Б. Лупанов, СВ. Яблонский, Ю.И. Журавлев, С.Н. Черников, И.И. Еремин, М.А. Айзерман. В 1998 году вышли в свет "Избранные научные труды Ю.И. Журавлева", в которых изложены основополагающие работы по математическим методам распознавания образов и дискретной математике. Научная школа Ю.И. Журавлева, создававшаяся на базе Вычислительного центра АН СССР, постоянно расширяется и сейчас имеет своих последователей не только в нашей стране, но и за рубежом.
Среди других научных школ упомянем коллектив МГУ, созданный А.А. Ляпуновым, СВ. Яблонским, О.Б. Лупановым. В Институте математики и механики УрО РАН успешно работает группа, образованная в 60-е годы СН. Черниковым и впоследствии возглавленная И.И. Ереминым
На протяжении последних 14 лет в Москве издается журнал "Pattern recognition and image analysis", в котором публикуются важнейшие работы, выполненные в области кибернетики и теоретической информатики.
Большая работа в области распознавания образов ведется в США в университете Висконсина под руководством профессора О. Мангасарьяна. Вместе со своими учениками О. Мангасарьян провел обширные исследования но общей теории диагностики, классификации и по применению методов оптимизаций в распознавании образов, решение прикладной задач в меди-
цине и биологии. Укажем лишь на некоторые из многочисленных публикации О.Мангасарьяна и его учеников: работа О. Мангасарьяна, Н.Стрита, В.Волберта [44], К.Беннетт, Е.Бредестейра [30]. Алгоритмы и программы распознавания образов приведены в книге В.Н. Вапника [3]. Проблемы классификации изучаются в книге С.Бойда и Л. Ванденберга [32].
Среди многочисленных проблем, возникающих в области распознавания, укажем задачу построения гиперплоскостей, разделяющих два выпуклых множества. Построению численных методов решения этой задачи посвящена данная работа. В качестве выпуклых множеств рассмотрены полиэдры (пересечение конечного числа полупространств) и политопы (выпуклые оболочки конечного числа точек).
Теорема о существовании разделяющей гиперплоскости играет важную роль в функциональном анализе, в теории оптимизации и исследовании операций. При решении практических задач важно не только знать, что разделяющая гиперплоскость существует, но и уметь конструктивно ее строить. В данной работе в главах 1-3 предлагаются численные методы нахождения семейств гиперплоскостей, разделяющих два непересекающихся непустых полиэдра, заданных с помощью систем линейных неравенств и систем линейных уравнений с неотрицательными переменными. В главах 4 и 5 разработаны численные методы построения разделяющих гиперплоскостей для политопов.
Предлагаемые численные методы основаны на использовании теорем об альтернативах и метода модифицированных функций Лагранжа . Подход, связанный с применением теорем об альтернативах в численных методах, возник несколько лет назад и изложен в работах [7]—[15], [33]- [37]. Он основан на отыскании исевдорешений несовместных систем линейных равенств и неравенств. По найденным псевдорешениям строятся нормальные решения альтернативных совместных систем и с их помощью определяются гиперплоскости, разделяющие полиэдры. В работе приводятся иллюстративные примеры, даны таблицы с численными расчетами тестовых примеров. Теоремам об альтернативах посвященное большое количество публикаций. Укажем, например, [6],[22], [31]-[33], [38].
В главе 1 рассмотрено применение нормального решения альтернативной
системы для построения семейства разделяющих гиперплоскостей. Использование результатов работы [9, 11, 12], позволяет найти нормальное решение из решения задачи безусловной минимизации невязки несовместной системы неравенств, задающей оба полиэдра. Если число переменных в задаче безусловной минимизации гораздо меньше, чем в альтернативной совместной системе, то такие расчеты менее трудоемки, чем нахождение решения альтернативной системы.
В основе лежит теорема И.И. Еремина о гиперплоскости, разделяющей полиэдры, заданные системами неравенств [15, теорема 10.1]. Используется специфический вид разделяющей гиперплоскости, нормаль и сдвиг которой выражены через произвольное решение некоторой системы, являющейся альтернативной к несовместной системе. Эта несовместная система состоит из двух совместных подсистем, каждая из которых определяет непустой полиэдр. Система несовместна, так как эти полиэдры не пересекаются. Построение разделяющих гиперплоскостей существенно опирается на теоремы об альтернативах.
В главе 1 рассмотрены два полиэдра
Хі = {х Є Шп : Аіх > Ьі}, Хі = {х Є Шп : Л2х >'b2}.
Предполагается , что эти полиэдры непусты, а их пересечение пусто. Тогда система
А\х > Ьи А2х > Ъ2 (0.1)
несовместна, а альтернативная система
Ajui + Aju2 = 0n, bJui + b[ui+ = р, wi>0mi, щ > 0m2, (0.2)
где p > 0 , напротив, совместна . Определим линейную функцию tp(x, а) от переменного вектора я, скаляра а из интервала [0,1]:
ip(x, а) = uJ{A\X — b\) + ар. (0.3)
Если щ - решение системы (0.2), то уравнение <р(х, а) = 0 задает гиперплоскость, разделяющую полиэдры Х\ и Х2. Гиперплоскость (0.3) при а = 0.5
была впервые построена И.И.Ереминым. Метод определения функции ip состоит в нахождении решения системы (0.2) и использовании формулы (0.3). Такой подход весьма затруднителен в том случае , когда т ^> п. Поэтому в первой главе данной работы для построения разделяющей гиперплоскости предлагается решать следующую задачу безусловной минимизации в п - мерном пространстве:
miriі ІцКЬ - AlX)+f + 11( - A2x)+f]. (0.4)
хЄК Л
Доказана теорема, утверждающая, что найденный из этой задачи вектор х* является псевдорешением системы (0.1) и нормальное решение й*т = [йіТ,Й2Т] системы (0.1) определяется но формулам
z\ = (&i - Агх*)+, 4 = (ь2 - Л2х*)+,
и! = />*i/(ll*i II2 + И4И2)> й2 = р4/(Ш2 + Itell2)-
Функция (р, которая определяет разделяющую гиперплоскость, записывается в виде:
ІЇ^ІАїх - bi) + ар = 0, где 0 < а < 1. (0.5)
Объединение всех таких гиперплоскостей, когда а изменяется от 0 до 1, называется семейством параллельных разделяющих гиперплоскостей.
В теореме 1.2 дан анализ решений задачи (0.4). Показано в частности , что, если Х\ фЪ,Х2ф 0, Х\ П Х2 = 0, то все решения системы (0.2) отличны от нуля, кроме того, дана формула для определения толщины семейства разделяющих гиперплоскостей. Предложенный подход к построению разделяющих гиперплоскостей наиболее эффективен в задачах, где размерность вектора п невелика,но количество ограничений т может быть значительным, т.е. п «С га .
В 1.2 показано, что в ряде случаев найденное семейство разделяющих гиперплоскостей можно расширить, решая две вспомогательные задачи линейного программирования. Приведены три примера, иллюстрирующие найденные свойства разделяющих гиперплоскостей . Система (0.2) имеет весьма глубокий смысл. Приведенная в диссертации теорема 1.4 утверждает, что
всякая строго разделяющая гиперплоскость такова, что всегда ее направляющий вектор с и сдвиг 7 выражаются через какое-нибудь решение системы (0.2).
При решении практических задач может оказаться, что полученные в результате экспериментов данные содержат погрешности, из -за которых матрица Л и вектор b вычислены неточно . В результате этого множества Х\ и Х2 могут пересекаться. В этом случае рекомендуется так скорректировать множества Х\ и Хг, что полученные вместо них множества Х\ С Х\ и Х2 С Х2 не пересекаются. Для этих множеств можно построить разделяющие гиперплоскости, используя технику, изложенную выше. При этом желательно, чтобы норма корректирующего вектора были бы минимально возможной. В 1.4 приведены формулы определения оптимальной коррекции и предлагаемая техника проиллюстрирована на простейшем примере.
В 1.5 рассмотрена возможность применения масштабирования целевой функции для максимизации толщины семейства разделяющих гиперплоскостей. Вместо (0.4)решается промасштабированная задача
тіл ІДКЬ - Л^+И2 + Л||(62 - Л2х)+\\% (0.6)
где Л — искомый коэффициент.
Толщина семейства (0.5) становится функцией Л . Найдя из (0.6) оптимальный вектор х*(\) , определим м|(Л) , «2(A) и по формулам, аналогичным (0.5), получим новое семейство разделяющих гиперплоскостей. Численно ищется максимум толщины семейства по Л . Во всех примерах за счет введения Л удалось так повернуть гиперплоскости, что в результате получались семейства, толщины которых совпадали с расстояниями между множествами
Xi и Х2.
В 2.1 ставится задача квадратичного программирования об определении семейства гиперплоскостей максимальной толщины, совпадающей с минимальным расстоянием между полиэдрами. Эта задача сводится к минимизации функции от 2п переменных при наличии т линейных ограничений типа неравенства. Построена двойственная задача, состоящая в максимиза-
ции квадратичной функции от т неременных на положительном ортанте при наличии п линейных ограничений типа равенства. Показано, что, решив эту задачу, можно легко определить семейства разделяющих гиперплоскостей максимальной толщины.
В 2.2 ставится задача нахождения такого решения системы Еремина (0.2), при котором толщина семейства разделяющих гиперплоскостей была бы максимальной . Показано, что эта задача состоит в минимизации квадратичной функции от т переменных при наличии п + 1 ограничений на положительном ортанте. Построена задача, двойственная к этой задаче. В работе даны три варианта задач, позволяющих построить разделяющую гиперплоскость максимальной толщины. Выбор наиболее подходящего варианта производится в зависимости от конкретных чисел тип.
В главе 3 строятся семейства разделяющих гиперплоскостей для двух полиэдров, заданных с помощью системы линейных уравнений с неотрицательными неременными. Показано, что в отличие от случая полиэдров, заданных с помощью системы линейных неравенств, любое решение альтернативной системы определяет два различных семейства разделяющих гиперплоскостей. Установлено, что не любая разделяющая гиперплоскость может быть представлена с помощью решения альтернативной системы (0.2) . Приведен соответствующий иллюстративный пример.
В главе 4 рассмотрен случай построения семейства гиперплоскостей, разделяющих два политопа. Предполагается, что в Rn задан набор из т\ точек и другой набор из 7772 точек. Общее число точек равно т\ + Ш2 = т. Выпуклые оболочки (политопы), натянутые на эти множества, обозначены через Х\ и Х<і соответственно.
В 4.1 ставится задача нахождения вектора, соединяющего две ближайшие точки из двух политопов. Эта задача заменена эквивалентной, более простой задачей, для которой построена двойственная к ней задача.
В 4.2 приведены формулы, определяющие семейство гиперплоскостей максимальной толщины, разделяющих два политопа.
В 4.3 метод модифицированных функций Лагранжа (МФЛ) применяется к прямой, а в 4.4 — к двойственной задаче. В задачах, где т ^$> п, целе-
сообразно использовать метод МФЛ для решения двойственной задачи, так как в ней ищется безусловный минимум в п + 1-мерном пространстве. Если п^> т, то, напротив, метод МФЛ применяется к прямой задаче , где вспомогательная задача состоит в отыскании безусловного минимума в т-мерном пространстве. Оба варианта метода МФЛ были реализованы автором в системе MATLAB. Программы использовали в качестве вспомогательной процедуры обобщенный метод Ньютона (краткое его описание приведено в приложении). Метод МФЛ, примененный для решения прямой задачи, оформлен в виде программы MLF1. Для решения двойственной задачи - в виде MLF2. В 4.3 и 4.4 даны результаты численных расчетов с помощью программ MLF1 MLF2 и программ, содержащихся в библиотеке оптимизационных программ системы MATLAB. При решении задач небольшой размерности оба подхода давали примерно одинаковые результаты. При решении задач большой размерности методы МФЛ показали более высокую эффективность расчетов по сравнению с алгоритмами, содержащимися в библиотеке MATLAB. Объясняется это тем, что в данной реализации метода МФЛ высокую эффективность демонстрирует обобщенный метод Ньютона.
В 4.4 приведен генератор тестовых задач (программа Codel). С его помощью задавались различные варианты задач, в том числе и задачи высокой размерности. В 4.3, например, решается задача, в которой т = 1000, п = 10000. В 4.4 - задача с т = 5 106, п = 2. Далеко не все задачи большой размерности удалось решить с помощью библиотеки программ оптимизации MATLAB. Например, задача с т = 300, п = 10000 и т = 1000, п = 10000 были решены программой MLF1 за 8.5 сек. и 96.6 сек. соответственно, но не были решены программой MATLAB .
Аналогично, в 4.4 с помощью программы MLF2 решена задача с т = 5 106 и п = 2 за 167.7 сек. Эта задача также не была решена программой MATLAB. При решением задачи с га = 4-Ю6, п = 2 время счета но программе MLF2 было в 2 раза меньше, чем по программе MATLAB .
В главе 5 изучается случай, когда выпуклые оболочки двух множеств (политопов) пересекаются. Вводится процедура сжатия выпуклых оболочек. В результате получаются два непересекающихся политопа и для скорректиро-
ванных выпуклых оболочек строится семейство разделяющих гиперплоскостей . В качестве разделяющей гиперплоскости берется гиперплоскость, проходящая через середину семейства. Она условно разделяет исходные множества точек. В приведенном примере эта гиперплоскость отделяет 96% точек одного множества от 97% точек другого множества.
В Приложении приводятся краткие сведения об обобщенном методе Ньютона, применяемом для решения задач безусловной минимизации. В работах О. Мангасарьяна доказана глобальная конечношаговая сходимость метода в предположении, что минимизируемая функция выпуклая, кусочно-квадратичная и дифференцируемая. В возникших в данной работе задачах все эти условия выполнены. Поэтому теоретическое исследование обобщенного метода Ньютона не проводилось. В приведенных автором расчетах обобщенный метод Ньютона показал высокую эффективность при решении задач с числом неизвестных до нескольких тысяч на персональных компьютерах Pentium4.
Расширение семейства разделяющих гиперплоскостей
В ряде случаев удается расширить найденное семейство параллельных разделяющих гиперплоскостей. Теорема 1.3. Пусть выполнены условия теоремы 1.2. Тогда существуют а 0 и а 1 такие, что семейство параллельных гиперплоскостей (1.20), (1.21) разделяет множества Х\ и Х2 при а а а. Гиперплоскости Г(&) и Т(а) являются опорными ко множествам Х\ и Х2 соответственно, гиперплоскость Т{а) выражается через Г(а) по формуле Г(а) = = Г(а) + у, где вектор сдвига у = (а — а)с/\\с\\2, \\у\\ = (а — d)/cjj. Доказательство. Из вида функции (р(х, а) следует, что при всех х Є Х\ и а 0 имеют место неравенства: Поэтому неравенство (1.32) справедливо для любого а а, где Гиперплоскость Г(а) = {ге Є Rn : cTrc = ст} имеет с множеством Х\ общую точку х. В силу (1.31) всякая точка из Х\ принадлежит полупространству ст(х — х) 0 . Следовательно, гиперплоскость Г(а) является опорной к множеству Х\. Вектор с — опорный к множеству Х\ в точке х. Если, в частности, а = 0, то опорной будет гиперплоскость Г(0). Аналогично показывается, что Г(а) есть опорная гиперплоскость к множеству Х2 в точке х. Вектор сдвига у получается после проведения простейших вычислений, аналогичных (1.12) и (1.13). В некоторых случаях, благодаря знанию нормального вектора й , удается легко определить оптимальные значения целевых функций в задачах (1.31) и установить, являются ли гиперплоскости Г(а) при а = 0иа = 1 опорными к множествам Х\ и Л"г соответственно.
Обозначим через w\ Є М+1, u 2 Є R+2 множители Лагранжа и введем функции Лагранжа для задач (1.31) Li{x, w\) = стх + wj(bi — А\х), L2{x, w2) = —стх + wj(b2 — А2Х). Пара [жі,гиі] образует точку Куна-Таккера, для первой задачи (1.31), если выполнены соотношения: с = Ajwh D(wi)(bi - А1Х1) = 0mi, wi 0mi, A&i 6b (1.37) Аналогично, для второй задачи (1.31) пара [ 2, ] образует точку Куна-Таккера, если: с = -Ajw2, D(w2)(b2 - Л2х2) = 0m2, w2 0Ш2, А2х2 b2. (1.38) Если в (1.37) в качестве w\ взять вектор й{ и для него найдется вектор Xi, удовлетворяющий (1.37), то [a:i,wj] — точка Куна-Таккера. При этом из (1.34) следует, что а = 0, т.е. Г(0) является опорной гиперплоскостью к Xі в точке х\. Аналогично, если для второй задачи (1.31) взять w2 = й2 и для него найдется вектор х2, удовлетворяющий (1.38), то с учетом (1.36) получим, что а = 1. Таким образом, Г(1) является опорной гиперплоскостью к Х2 в точке х2. Если а 0 или а 1, то ищем оптимальные множители Лагранжа w\ или w2 для соответствующих задач в (1.31). Из первых условий в (1.37) и (1.38) следует, что эти векторы удовлетворяют соотношению Ajw{ + Ajwl = 0. Из (1.33) и (1.35), взяв х = х\, х = х2} получим: стхі b\u\, —стх2 b2u\. Складывая эти неравенства, находим: h[w\ + bjw 2 = ст(хі - х2) bjul + 6 = р 0. Следовательно вектор w T = [wlT, w ] так же, как и й , удовлетворяет системе (1.5). Семейство разделяющих гиперплоскостей можно представить в виде: Г(а) = {x6Rn: wfiAxx - Ьг) + ар = 0}, (1.39) Г(а) = {хешп: -wf(A2x - 62) + (а - 1)р = 0}. (1.40) Таким образом, мы построили два семейства разделяющих гиперплоскостей вида (1.20), (1.21) и (1.39), (1.40). В первом семействе использовано нормальное решение системы (1.5), во втором - оптимальные множители Лагранжа задач линейного программирования (1.31). Оба эти вектора й и w удовлетворяют системе (1.5). Следующая теорема утверждает, что для любой строго разделяющей гиперплоскости определяющие ее вектор-нормаль с и скаляр у можно выразить через решение системы (1.5). На рис. 1.2 показаны множества Х\, Х2, семейство разделяющих гиперплоскостей, соответствующих а = а, а = 0, а = 1 и а = а, вектор х и нормированный вектор Q = с/с. Множество Х\ лежит в положительном полупространстве относительно вектора с, множество Х2 — в отрицательном полупространстве. Толщина семейства гиперплоскостей при 0 а 1 составляет \\у\\ = 2.13. После расширения за счет учета а и а получено ІІУІІ = 2.80.
Разделение скорректированных полиэдров
Система (1.2) имеет весьма глубокий смысл. Приведенная ниже теорема утверждает, что всякая строго разделяющая гиперплоскость такова, что всегда ее направляющий вектор с и сдвиг 7 выражаются через решение системы (1.2). Теорема 1.4. Пусть гиперплоскость сТх = 7 строго разделяет непустые непересекающиеся полиэдры Х\ и Х2. Тогда найдется решение щ, U2 системы такое, что вектор с и скаляр 7 определятся по формулам где pi+ p2 = p, P\, p2 — произвольные положительные константы. Доказательство. Пусть для определенности строго разделяющая гиперплоскость такова, что для всех х Є Xi выполнено неравенство сТх 7 и для всех х Є Х2 справедливо стх 7- Тогда система не имеет решения, а система, альтернативная к ней, совместна. Поэтому существуют q 0mi и 7] 0, т] Є Е1 такие, что: Здесь pi — положительная произвольная константа. Скаляр rj не может равняться нулю, так как в этом случае разрешимая система (1.42) имела бы вид: и, следовательно, альтернативная к ней система А\х bi была бы несовместна, что противоречит условию Х\ ф 0. Таким образом, из (1.42) получаем с = Ajq/г), 7 = = bjq/г] — рі/г). Введем обозначения щ = q/r], рі/г] = р\; тогда получим Рассуждая аналогично, приходим к соотношениям Складывая (1.43) и (1.44), получим совместную систему (1.41), альтернативную к (1.4). D При решении практических задач может оказаться, что полученные в результате экспериментов данные содержат погрешности, из -за которых матрица А и вектор Ъ вычислены неточно. В результате этого множества Х\ и Х2 могут пересекаться. В этом случае рекомендуется так скорректировать множества Х\ и Л 2, что полученные вместо них множества Х\ С Х\ и Хч С Л 2 не пересекаются. Для этих множеств можно построить разделяющие гиперплоскости, используя технику, изложенную выше. При этом желательно, чтобы норма корректирующего вектора были бы минимально возможной. Ниже оптимальную коррекцию множеств вида Ах Ь будем осуществлять в два этана. В начале к Ь прибавим вектор Ф с неотрицательными компонентами. Если обозначить W{$) — { х : Ах Ь + $}, то, очевидно, что при тЭ 0т зависимость W($) будет невозрастающая, т.е., если Ї?І і92, то Wtyi) 2 W{d2). Предполагаем, что непустые множества Х\ и Х% таковы, что существую ! векторы #1 Є Я"1 , $2 Є Л+г такие, что множества Хі = {ж:Ліаг 6і+йі }, (1.45) Х2 = {х:Л2х 62 + і32} 1.46) также непусты. Пусть множество решений системы при & = 0т непусто. Тогда можно найти вектор д 0 такой, что множество X = X1f]X2 = {x:Ax b + e} (1.48) пусто, а множества (1.45) и (1.46) по-прежнему непусты. Здесь дт = [щ,Щ]. Воспользуемся результатами раздела 1.1. Введем задачу безусловной минимизации: mm\\\{b + e-Ax)+f. (1.49) Согласно теореме 1.1 решение этой задачи х определяет ненулевой вектор z = (b + tf — Ах )+, который является решением двойственной задачи.
Будем говорить, что корректирующий вектор z оптимален, если он имеет наименьшую евклидову норму среди всевозможных векторов, обеспечивающих условие совместности системы Ах b -f в — Z. По теореме 5 из [10] оптимальным корректирующим вектором является вектор z . Описанную процедуру проиллюстрируем на следующему примере. Пример 1.5. Пусть п = 2, га = 4, Х1={хвШ2 :х2 х1, х2 0}, Х2 = {х Є R2 : х1 -1, х2 -1}; Л = -1 -1 Ао = 0 0 Ьі = z = min[-\\(b-Ax)+f = 0, т.е. множества Х\ и Х2 пресекаются (см. рис. 1.5). Поэтому требуется задать вектор $ Є Я+ такой, что система (1.47) несовместна, а множества (1.45) и (1.46) по-прежнему совместные. Возьмем вектор ёт — [5/6,5/6]. В результате получим множества Л\ и Хз, изображенные на рис. 1.6 пунктирными линиями. Эти множества непустые и не пересекаются. о Рис. Почти во всех приведенных выше примерах семейства разделяющих гиперплоскостей представляли собой по-разному наклоненные полосы, толщины которых не были максимальными. Только в примере 1.2 толщина полосы была равна расстоянию между множествами Х\ и Х2. Во всех остальных случаях толщины полос были меньше расстояния между множествами. Возникает идея - за счет масштабирования целевой функции в задаче минимизации (1.15) изменить наклон разделяющих гиперплоскостей проведя масштабирование целевой функции, добиваясь таким образом нахождения семейства разделяющих гиперплоскостей максимальной толщины. Для этого введем весовой коэффициент Л и задачу (1.15) заменим следующей: mm [ірх - А1Х)+\\2 + ЛІ(Ь2 - A2x)+f\. (1.50) Обозначим через х (Х) решение задачи (1.50) и, пользуясь теоремой 1.1, найдем Ї(А) = (Ьі - AlX {\))+, 25(A) = (Ь2 - А2х (\))+. Согласно теореме 1.1 , для новой задачи имеют место условия: Ajzl(X) + ХАТ24(Х) = 0, bJz 2(X) + Xbj4(X) = zf (А)2 + г2 (А)2. Если при этом решаются задачи ЛП (1.47), то определяются значения а(Х) и а(А). Толщина семейства разделяющих гиперплоскостей, согласно теореме 1.3, вычисляется по формуле Если а = 1 и а = 0, то толщина семейства разделяющих гиперплоскостей вычисляется но упрощенной формуле Поставим задачу отыскания максимальной и минимальной толщины семейства по параметру Л . Обозначим График функции ;г/(А) для примера 1.4 приведен на рис. 1.8. По горизонтальной оси отложены значения А в логарифмическом масштабе. В этом примере минимум d = 2 достигается при 101 А 105. Максимум d = 2.24 достигается при 10 5 А Ю-2.
Определение решения системы Еремина для построения семейства разделяющих гиперплоскостей максимальной толщины
Рассмотрим теперь вопрос о том, можно ли из системы (1.5), введенной И.И. Ереминым, выделить такое решение, чтобы определить семейство гиперплоскостей максимальной толщины, совпадающей с расстоянием между множествами Х\ и Х2. Согласно формулам (1.12) и (1.13), вектор сдвига у и толщина ЦЇ/ІІ семейства разделяющих гиперплоскостей Г(а) определяются как у = — pAjui/\\Ajui\\2 и у = p/ЦА иіЦ, где иТ = [uj,и2] является решением системы (1.5). Поэтому естественно поставить задачу о нахождении такого решения и т = [и{т,и2т] Є U системы (1.5), при котором толщина семейства разделяющих гиперплоскостей является максимальной Вектор сдвига у = Г(1) — Г(0) в данном случае дает толщину семейства гиперплоскостей, которая совпадает с минимальным расстоянием между полиэдрами Хі и Х2 Это связано с тем, что по решению и задачи (2.21) можно найти минимальное расстояние между Х\ и Х2. Оказывается, что задачи (2.21) и (2.7) эквивалентны в том смысле, что по решению одной из них находится решение другой. Теорема 2.3. Пусть полиэдры Х\ и X? непусты, а их пересечение пусто. Тогда решение v задачи (2.7) и решение и задачи (2.21) связаны друг с другом соотношениями Семейство разделяющих гиперплоскостей представимо в виде где 0 а 1. Толщина этого семейства совпадает с минимальным расстоянием между полиэдрами Х\ и Х2. Доказательство. Вектор и удовлетворяет системе (1.5), поэтому, согласно И.1 теоремы 1.2, имеет место J4I UIII ф 0. Согласно теореме 2.1 выполнено условие bTv ф 0. Формулы (2.23) получаются из сравнения условий Куна-Таккера для задач (2.7), и (2.21). Согласно (2.11), (2.23) и (1.12) Отсюда получаем, что толщина семейства (2.24), (2.25) разделяющих гиперплоскостей совпадает с минимальным расстоянием между полиэдрами Xi и Х2: Определим для задачи (2.21) двойственную задачу. Теорема 2.4. Задача, двойственная к (2.21), состоит в нахождении при ограничениях Доказательство. Воспользуемся функцией Лагранжа для задачи (2.21) где г R" и 6 М1-множители Лагранжа . С помощью этой функции запишем двойственную задачу УСЛОВИЯ Куна-Таккера для задачи (2.29) записываются следующим образом: Из (2.31) находим ujAiAjui = uj[A\r 4-&i) и из (2.33) находим u2A2r = —ttj&2 0m2. Подставляя эти выражения в (2.28), получим двойственную функцию Лагранжа L{v\,v2) = — \\Ajui\\2/2 -f р и, учитывая (2.30),(2.32), получим (2.26) и (2.27). В решении неизвестный вектор q выражается через решение и прямой задачи (2.21), (2.22) по формуле q = Aju\ = — А2и . Отсюда, согласно теореме двойственности, в решениях и и [q ,x ,, ] прямой и двойственной задач имеем р = 7itJ2.
Поэтому 0 и р = ? / х\ — Х /С Итак, построены три эквивалентных представления (2.13)-(2.14), (2.20), (2.24)-(2.25) одного и того же семейства разделяющих гиперплоскостей, толщина которого совпадает с минимальным расстоянием между полиэдрами р . Каждое представление требует решения своей оптимизационной задачи. Рассмотрим случай, когда два полиэдра представлены системами равенств на неотрицательном ортанте, т.е. заданы два непустых множества таких, что X = X\ П X2 = 0. В соответствии с теоремой Фаркаша об альтернативах для несовместной системы равенств с неотрицательными неременными совместна следующая система: Здесь p — положительная константа. Теорема 3.1. Пусть два непустых , непересекающихся полиэдра заданы системами равенств на неотрицательном ортанте. Тогда любое решение системы (3.1) определяет два семейства разделяющих гиперплоскостей Доказательство. Решение системы (3.1) существует, и для любых решений этой системы справедливы неравенства ui 0, гі2І ф 0 Mi ill Ф 0 ІИІМ2ІІ Ф 0. Действительно, пусть от противного А[и\ = 0П, тогда из того, что Х\ непусто следует, что альтернативная система Ajui 0, Ъ[и\ = р\ ф 0 неразрешима, но из предположения Aju\ = 0п получаем, что bjui — 0- Из (3.1) в этом случае имеем совместную систему Aju2 0П, Ь щ = р. Но она альтернативная к системе А х = Ь2, х 0п, которая но условию совместна, так как Х2 непусто. Противоречие доказывает, что равенство Ajui = 0п невозможно. Если щ = 0mi, то Ajui = 0„, что также невозможно. В (3.1), умножая неравенство скалярно на неотрицательный вектор х и вычитая из результата равенство, получим Определим две линейные функции от переменных х Є Кп и параметра а Є [ОД] (3.2) представим в виде рі(х, a) = 7( 1 - Ьі) + ар -uJ(A2x — 62) -(1- а)р = Зафиксируем векторы щ и «2, являющиеся произвольными решениями системы (3.1). При а Є [0,1] с помощью функций tpi(x, а) и /?2(# ) получаем два семейства гиперплоскостей, разделяющих множества Х\ и Х2. Если х Є Х\, то ipi(x, а) 0 при ск Є [0,1]. Если х Є Х2, то при а Є [0,1] функция (f2(x,а) 0 и, как следует из (3.3), при этом ip\(x,а) 0, т.е. семейство гиперплоскостей ipi(x, а) = 0 при а Є [0,1] является разделяющим множества Х\ и Х2. Из неравенства (3.3) следует, что при 0 а 1 гиперплоскость ірі(х, а) = 0 строго разделяет эти множества. Покажем теперь, что условие (р2(х, а) = 0 определяет семейство гиперплоскостей, разделяющих множества Х\ и Х2 при а Є [0,1], и строго разделяет эти множества при 0 а 1. Действительно, если х Є Хг, то 2( а) 0 при а Є [0,1] и /?2(#, OJ) 0 при 0 а 1. Если ж Є Хь то, как следует из (3.3), (р2(х, а) 0 при а Є [0,1] и ір2(х, а) 0 при 0 а 1.
Построение гиперплоскостей, разделяющих выпуклые оболочки
Пусть w = [wl,w2] —решение задачи (4.1). Тогда точки х\ = Мти \ Є Xi, х2 = NTw2 Є Х2 являются ближайшими из множеств Х\ и Х2 соответственно. Вектор р = MTw\ — NJw\ соединяет эти точки. Семейство гиперплоскостей, разделяющих множества Х\ и Х2, представим в виде Здесь Подставляя в (4.27) выражения для х\ и х\, получим р 2 = —Р, т.е. /?. Пусть х\ Є Х\. Тогда существует вектор w\ Є S\ такой, что х\ = MTw\. Поэтому, согласно (4.2), имеем Аналогично, если Х2 Є Х2, то существует вектор гі»2 Є % такой, что Х2 = NTW2 и, согласно ( 4.3), Из ( 4.28), ( 4.29) следует, что все точки из множества Х\ удовлетворяют условию р тх\ , и все точки из множества Хг удовлетворяют условию р тХ2 Р. Так как Р, получим, что (1 — а) + аР Р при всяком 0 а 1. Пусть х\ Є Х\, тогда и пусть х2 Є Х2, тогда Объединяя неравенства ( 4.30), ( 4.31), получим Неравенство( 4.32) имеет место при любых х\ Є Х\, х2 Є Х2 , а гиперплоскости Г(а) разделяют множества Х\ и Х2, при любых 0 а 1. Гиперплоскости р тх = и р та; = /3 являются опорными к множествам Х\ и Хг соответственно, так как р тх\ = , х\ Є Xi и р 7 = /5, Є Х2. Объединение всех гиперплоскостей Г(а), когда о; изменятся от 0 до 1, назовем семейством разделяющих гиперплоскостей и обозначим через Вектор р можно назвать нормалью этого семейства, евклидово расстояние от начала координат до гиперплоскостей Г(а) вычисляется по формуле и толщина семейства Г (евклидово расстояние между граничными плоскостями) равна От решения задачи (4.1) перейдем к решению задачи (4.4).
Это внесет некоторые коррективы в полученные формулы : вместо р будет фигурировать q , вместо , (3, скаляр 7- Имеют место следующие формулы: Опорными к множествами Х\ и Х-2 будут гиперплоскости q rx = 1 + 7 и д тх = 7 соответственно, расстояние между ними равно р — ? /# = 1/11(71 Рис. 4.1 Для случая п = 2 на рис.4.1 изображены два набора точек, натянутые на них выпуклые оболочки Х\ и .) две опорные гиперплоскости q Tx = 1+7 и q Tx = 7 , ортогональный к ними вектор р и семейство Г. Для решения исходной задачи (4.4) и двойственной к ней задачи (4.22) воспользуемся методом модифицированных функций Лагран-жа (МФЛ) (см. [1, 2, 4], [23]-[28]). Введем скаляр 7 и вектор А Є Л+, составим модифицированную функцию Лагранжа где г -коэффициент штрафа, vT = [vjjvj], вектор Ao и 7o - произвольные начальные точки Ao из множества R и 7о из множества R1. Обычно при расчетах берется г = 100 и А = 0т 7о = 0- Последнее слагаемое в функции Лагранжа введено для учета ограничения v 0m, А Є R- соответствующий вектор множителей Лагранжа. С учетом объединения векторов v\ и г 2 имеем Дг і,г 2, А,7) = L(v,X,j). Номер итерации будем обозначать дополнительным нижним индексом при соответствующих переменных. Тогда метод МФЛ запишется в виде где Vk+i определяется из следующей задачи безусловной минимизации В этой задаче функция Лагранжа выпуклая, кусочно квадратичная и дифференцируемая. Поэтому для ее минимизации можно применить обобщенный метод Ньютона ( см. Приложение ). В качестве иллюстрации работы метода решались сгенерированные случайным образом задачи (4.4) с большим числом неотрицательных переменных (до ста тысяч ) и средним числом ограничений-равенств (до одной тысячи), т.е. имело место п т. Итак, задавались числа тип, определяющие количество строк и столбцов матрицы А Элементы матрицы А определялись случайным образом . В матрице М элементы брались из интервала [—50,100], в матрице iV-из интервала [—50,120]. По особому определялись первые столбцы матриц М и N. Элементы первого столбца матрицы М брались из интервала [30,50] и элементы первого столбца матрицы N из интервала [100,120]. Кроме того, задавались три точки xi, Х2, %з из множество Х\, у которых первые компоненты были равны 50 ; у трех точек у\, у2, уз из множества X i первые компоненты были равны 100; то есть х\ = х\ — х\ = 50 и у\ = у\ — у\ = 100. Для всех 2 і пи1 _7 3 выполняются условия хгл = г/ -. Благодаря такому выбору гарантировалось, что расстояние между множествами Х\ и Х2 равно \\р \\ = 50, и оптимальный вектор w прямой задачи (4.14) имеет первую компоненту, равную единице, а остальные компоненты равны нулю. У вектора р отлична от нуля только первая компонента , равная 50. Кроме того, тестовая задача имеет не единственное решение, что усложняет расчеты. Для генерации тестовых задач использовалась следующая программа, предназначенная для системы MATLAB xM=[50 50 50];уМ=[50 0 -100] ;xN=[100 100 100] ;yN=[50 0 -100]; plot(M(:,1),M(:,2), .г ,N(:,1),N(:,2), bl ,xM,yM,xN,yN) 7, format short ; [ml m2 n ttl toe] , [max(M(: ,1)) min(N(: ,1))] Предлагаемый для решения прямой задачи (4.4) метод МФЛ представляет собой итерационный процесс (4.35). Обобщенный метод Ньютона применен к решению задачи безусловной минимизации (4.36). Алгоритм реализован в системе MATLAB 7 в виде программы MLF1 . Критерием остановки процесса минимизации (4.36) является выполнение условия Цг +i — Vk\\ toll. Критерием остановки итераций (4.36) является выполнение условий 7fc+i — 7&ІІ Ш2 и Ajfc+i - А Ш2. В качестве начальных условий для всех задач брались нулевые векторы VQ и Ао, а также принималось, что 7о = 0. Программа MLF1 сравнивается с программой MATLAB, составленной на базе библиотеки методов оптимизации коммерческой системы MATLAB. В результате вычислений определялись следующие невязки і"Де аоо есть чебышевская норма вектора a; d есть найденное расстояние между множествами , р = 50. Обычно в расчетах полагалось toll = 10 8, tol2 = 10"8. Для вычислений использовался компьютер с процессором Pentium-4, тактовой частотой 3 ГГц, оперативной памятью 1 Гб. Результаты решения случайным образом сгенерированных задач приведены в таблице 1. В первом столбце таблицы указаны размерности m и п; Во втором столбце приведены имена используемых программ. В третьем - даны времена счета (в секундах). В четвертом , пятом, шестом, столбцах указаны Ai , А2, А3. Из таблицы следует, что программа MATLAB оказалась более эффективной , чем MLF1 только при решении первой задачи невысокой размерности. На второй и четвертой строках выражение MATLAB обозначает, что этот
