Построение семейств разделяющих гиперплоскостей тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

Кетабчи Саеид

ПОСТРОЕНИЕ СЕМЕЙСТВ РАЗДЕЛЯЮЩИХ ГИПЕРПЛОСКОСТЕЙ

01.01.09 — Дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва — 2005

Работа выполнена на Факультете вычислительной математики и кибернетики МГУ им М.В. Ломоносова и в Вычислительном центре им. А.А Дородницына Российской Академии наук

Научные руководители:

член - корр. РАН, доктор физико-математических наук, профессор Ю. Г. Евтушенко,

кандидат физико-математических наук А. И. Голиков

Официальные оппоненты:

доктор физико-математических наук,

профессор

В. В. Дикусар,

доктор физико-математических наук,

профессор

М. С. Никольский

Ведущая организация-

Институт системного анализа Российской Академии наук

Защита состоится "'2-1 ". О ^ - 2005 в ч- О Омин. на заседании Диссертационного совета Д 002.017.02 при Вычислительном центре им. А.А Дородницына РАН по адресу: 119991, г. Москва, ул. Вавилова, дом 40, тел: 135-24-89 .

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан '"2.^' - (Ц> ^ — 2005.

Ученый секретарь Диссертационного совета Д 002.017.02 при ВЦ РАН доктор физико-математических наук Рязанов В. В

ты.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Крупные результаты в этой области были получены во второй половине прошлого века. Укажем лишь некоторых из ведущих ученых, стоявших у истоков исследований в этой области: А.А. Ляпунов, О.Б. Лупанов, С.В. Яблонский, Ю.И. Журавлев, С.Н. Черников, И.И. Еремин, М.А. Айзерман. В 1998 году вышли в свет "Избранные научные труды Ю.И. Журавлева", в которых изложены основополагающие работы по математическим методам распознавания образов и дискретной математике. Научная школа Ю.И. Журавлева, создававшаяся на базе Института математики СО РАН и Вычислительного центра РАН, постоянно расширяется и сейчас имеет своих последователей не только в нашей стране, но и за рубежом.

Среди других научных школ упомянем коллектив МГУ, созданный А.А. Ляпуновым, С.В. Яблонским, О.Б. Лупановым. В Институте математики и механики УрО РАН успешно работает группа, образованная в 60-е годы С.Н. Черниковым и впоследствии возглавляемая И.И. Ереминым.

На протяжении последних 14 лет в Москве издается журнал "Pattern recognition and image analysis", в котором публикуются важнейшие работы, выполненные в области кибернетики и теоретической информатики.

Большое влияние на развитие теории и методов распознавания образов оказали работы В.Н.Вапника и О.Мангасарьяна. Вместе со своими учениками О. Мангасарьян провел обширные исследования по применению методов оптимизации в распознавании образов, решению прикладных задач в медицине и биологии.

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

роль в функциональном а^авивелайадрйй^яй^^зации и исследовании опе-

библиотрка

200i РК

Петербург

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

Предлагаемые численные методы основаны на использовании теорем об альтернативах. Подход, связанный с применением теорем об альтернативах в численных методах, возник несколько лет назад. Он основан на отыскании псевдорешений несовместных систем линейных равенств и неравенств. По найденным псевдорешениям строятся нормальные решения альтернативных совместных систем и с их помощью определяются гиперплоскости, разделяющие полиэдры. При этом актуальным является не только создание эфективных численных методов, но и получение разделяющих гиперплоскостей, обладающих некоторыми полезными свойствами. Например, построение гиперплоскостей, соответствующих расстоянию между разделяемыми множествами.

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

В соответствии с целью исследования были поставлены следующие конкретные задачи:

1. Разработать численный метод построения семейства гиперплоскостей, разделяющих полиэдры, на основе применения теоремы об альтернативах. Изучить свойства получающегося семейства разделяющихся гиперплоскостей.

2 Рассмотреть возможность выделения из совместной альтернативной системы решения, соответствующего семейству разделяющих гиперплоскостей максимальной толщины.

3. Обобщить теорему И.И.Еремина о конструктивном построении семейства гиперплоскостей, разделяющих полиэдры, заданные системами равенств

на неотрицательном ортанте.

4. Программно реализовать в системе МАТ1.АВ численные методы построения разделяющих гиперплоскостей на основе применения теорем об альтернативах и обобщенного метода Ньютона для минимизации выпуклой кусочно - квадратичной функции Провести вычислительные эксперименты по решению задач большой размерности.

К методам исследования, примененным в данной работе, относятся: теория и численные методы оптимизации, линейная алгебра, программирование в системе МАЛАВ.

Научная новизна:

1. На основе применения теорем об альтернативах разработаны новые численные методы построения семейств гиперплоскостей, разделяющих полиэдры, заданные в гс-мерном пространстве. При этом простейший метод состоит в безусловной минимизации кусочно-квадратичной выпуклой функции в п-мерном пространстве.

2. Исследована возможность построения семейства разделяющих гиперплоскостей максимальной толщины на основе применения теорем об альтернативах.

3 Дано обобщение теоремы И И Еремина о семействе гиперплоскостей, разделяющих полиэдры, при задании их системами равенств на неотрицательном ортанте. Показано, что в этом случае каждому решению альтернативной совместной системы соответствуют два семейства разделяющих гиперплоскостей.

4 Программно реализованы в системе МАТ1.АВ численные методы построения семейства гиперплоскостей1, разделяющих полиэдры, заданные большим числом (несколько миллионов) линейных неравенств

5. На основе модифицированной функции Лагранжа и обобщенного метода Ньютона предложены и программно реализованы численные методы построения семейства гиперплоскостей, разделяющих политопы Численные эксперименты показали возможность решения таких задач с количеством данных до пяти миллионов.

Теоретическая и практическая ценность данной работы состоит в том,

что разработаны, исследованы и программно реализованы методы построения

гиперплоскостей, разделяющих полиэдры и политопы.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всероссийской конференции "Математическое программирование и приложения"(Екатеринбург, 2003 г.), Всероссийской конференции "Алгоритмический анализ неустойчивых за-дач"(Екатеринбург, 2004 г.), на научных семинарах ВЦ РАН, на научном семинаре факультета ВМиК МГУ по оптимизации под рук. Ф.П.Васильева и А.С.Антипина.

Публикации. По теме диссертации опубликовано четыре работы.

Объем и структура работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Общий объем работы составляет 92 страницы, включая 17 рисунков, 2 таблицы и список литературы из 42 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении указано на важность построения семейств разделяющих гиперплоскостей и дано краткое описание содержания диссертации. В главе 1 рассмотрено применение нормального решения альтернативной системы для построения семейства разделяющих гиперплоскостей. Этот подход позволяет найти нормальное решение альтернативное системы из решения задачи безусловной минимизации невязки несовместной системы неравенств, задающих пересечение двух полиэдров. Если число переменных в задаче безусловной минимизации гораздо меньше, чем в альтернативной совместной системе, то такие расчеты менее трудоемки, чем нахождение решения альтернативной системы.

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

41И Еремин Теория линейной оптимизации. Екатеринбург: УрО РАН, 1998, теорема 10.1.

ляет непустой полиэдр. Система несовместна, так как эти полиэдры не пересекаются. Построение разделяющих гиперплоскостей существенно опирается на теоремы об альтернативах.

В главе 1 рассмотрены два полиэдра

Хг = {х е Я" : А1Х > Ьх>, Х2 = {х € ВТ : А2х > 62}-

Предполагается , что эти полиэдры непусты, а их пересечение пусто. Тогда система

А\х > Ьь А2х > b2 (1)

несовместна, а альтернативная система

Ajui + Ajи2 = 0n, bjui + biui = Р. «1 > От,, «1 > 0т2, (2)

где р > 0, напротив, совместна . Определим линейную функцию <р(х,а) от переменного вектора х, скаляра а из интервала [0,1]:

<р(х, а) = uJ(Aix - bi) + ар, (3)

где Mj - решение системы (2). Уравнение ¡р(х, а) = 0 задает гиперплоскость, разделяющую полиэдры Х\ и Х2. Гиперплоскость, (3) при а = 0.5 была впервые построена И.И.Ереминым. Решать систему (2) весьма затруднительно в том случае , когда п. Поэтому в первой главе данной работы для построения разделяющей гиперплоскости предлагается решать следующую задачу безусловной минимизации в п - мерном пространстве :

min 1(11(6, - Агх)+1|2 + ||(62 - А2х)+1|2]. (4)

zeit" L

Доказана теорема, утверждающая, что найденный из этой задачи вектор х* является псевдорешением системы (1) и нормальное решение й*т = [й}т, й^] системы (1) определяется по формулам

z\ = (h - Ахх')+, z*2 = (Ь2 - А2х*)+, (5)

й{ = pz\/{\\z{f + ll^ll2), «5 = pz'2/(\\zl ||2 + \\4\\2). (6)

Функция ifi, которая определяет разделяющую гиперплоскость, записывается в виде

V? = ü\T(Aix - bi) + ар = 0, где 0 < а < 1. (7)

Семейство разделяющих гиперплоскостей можно записать следующим образом :

Г{а) = {х&Н" : з$т(А1х-Ь1) + а\\г*\\2 = 0}. (8)

Объединение всех таких гиперплоскостей, когда а изменяется от 0 до 1, называется семейством параллельных разделяющих гиперплоскостей и обозначается через Г.

Теорема 1.2 (о семействе параллельных разделяющих гиперплоскостей ). Пусть полиэдры Х\ и Х2 непусты, з их пересечение пусто; решением задачи (4) является х*; векторы г* и й* определяются из (5) и (6). Тогда

1) существует решение системы (2) и для любого решения этой системы справедливо ЦщН ф 0, ||и2|| фО и = ф 0;

2) при 0 < а < 1 множество Г(а) задает семейство параллельных гиперплоскостей, разделяющих множества Х\ и Хч: при 0 < а < 1 гиперплоскости Г(а) строго разделяют Х\ и Х2;

3) если в качестве а взять а» = Н^Цр/Цг'Ц2, то точка х* лежит на разделяющей гиперплоскости, соответствующей этому значению а;

4) вектор сдвига у = Г(1) — Г(0) и толщина семейства гиперплоскостей Г (а) определяются соответственно по формулам

У =

-рА[й\ -¿¡г!

.»1|2

1№1112 \\Ajzi Г

N1= ' - |И|2

1№;|| №¡11'

5) если а > 0, то Х^ П Г(а) = 0; если а < 1, то Х2 П Г(а) = 0,

6) если Х\ П Г(0) ф 0, то Г(0) - гиперплоскость, опорная к множеству Х\; если Х2 П Г(1) ф 0, то Г(1) — гиперплоскость, опорная к множеству Хг,

7) всякое решение х* задачи (4) не принадлежит ни множеству Х\, ни множеству Х<1-

6 ряде случаев удается расширить найденное семейство параллельных разделяющих гиперплоскостей. Введем два вектора х € Х\ и х € Х2 такие, что

стх = тшсТ1, стх = шах стх. (9)

хеХг хеХг

Обозначим

а = {Ъ[и[-стх)1р< 0, а = 1-{стх + Ь1й\)/р> 1. (10)

Теорема 1.3. Пусть выполнены условия теоремы 1.2. Тогда существуют а < 0 и а > 1 такие, что семейство параллельных гиперплоскостей (8) разделяет множества Х\ и Х2 при а < а < а. Гиперплоскости Г(а) и Г(а) являются опорными ко множествам и Х2 соответственно, гиперплоскость Г(а) выражается через Т(а) по формулеТ(а) = = Г(а)+у, где вектор сдвига У = (а - а)с/||с||2, |Ы| = (а-а)/||с||.

На рис. 1 для примера 1 из диссертации показаны множества Х\ и Х2, семейство разделяющих гиперплоскостей. Гиперплоскости Г(0) и Г(1) не являются опорными ко множествам Х1 и Х1. В результате решения задачи (9) было получено, что а = —0.13 и а = 1.18. Соответствующие гиперплоскости Г(—0.13) и Г(1.18) изображены на рис. 1. Они являются опорными и Хч соответственно.

Рис. 1

Теорема 1.4. Пусть гиперплоскость стх = 7 строго разделяет непустые непересекающиеся полиэдры Xi и Х2. Тогда найдется решение щ, и2 системы

Ajm 4- A2u2 = 0, bju 1 + bju2 = р > 0, «1 > О, «2 > О (И) такое, что вектор с и скаляр ■у определятся по формулам

с = Aju 1 --A]u2, 7 = -pi = -b2u2 + P2,

где pi + p2 = p, pi, P2 — произвольные положительные константы.

Приведенная теорема 1.4 утверждает, что всякая строго разделяющая гиперплоскость такова, что всегда ее направляющий вектор с и сдвиг 7 выражаются через какое-нибудь решение системы (2).

При решении практических задач может оказаться, что полученные в результате экспериментов данные содержат погрешности, из -за которых матрица А и вектор b вычислены неточно . В результате этого множества Х\ и могут пересекаться. В этом случае рекомендуется так скорректировать множества Xi и Х2, что полученные вместо них множества Х\ С Х\ и Х2 С Х2 не пересекаются. Для этих множеств можно построить разделяющие гиперплоскости, используя технику, изложенную выше. При этом желательно, чтобы норма корректирующего вектора была бы минимально возможной. В §14 приведены формулы определения оптимальной коррекции и предлагаемая техника проиллюстрирована на простейшем примере.

В § 1.5 рассмотрена возможность применения масштабирования целевой функции для максимизации толщины семейства разделяющих гиперплоскостей. Вместо (4) решается промасштабированная задача

min h\\(b - AlX)+\|2 + А II (62 - А2х)+\\% (12)

геД" Z

где А —некоторый положительный коэффициент.

Толщина семейства становится функцией А . Найдя из (12) оптимальный вектор £*(А) , определим Ц(А) , uJM и п0 формулам, аналогичным (8), получим новое семейство разделяющих гиперплоскостей. В работе численно ищется максимум толщины семейства по А . Во всех примерах за счет введения А удалось так повернуть гиперплоскости, что в результате получались

семейства, толщины которых совпадали с расстояниями между множествами Хг и Х2.

Семейство разделяющих гиперплоскостей, изображенное на рис. 1, благодаря использованию А = 10 повернулось по часовой стрелке, и гиперплоскость Г(1) стала опорной ко множеству Х2 (см. рис. 2).

Рис. 2

В § 2.1 ставится задача квадратичного программирования об определении семейства гиперплоскостей максимальной толщины, совпадающей с минимальным расстоянием между полиэдрами. Задачу нахождения минимального расстояния между двумя непересекающимися множествами Х\ и Xi можно записать в виде

(13)

при ограничениях

Aix2 + Aip > А2х2 > Ьг.

Здесь вектор р соединяет две ближайшие точки из множеств Xi и Х2. Функция Лагранжа для задачи (13) имеет вид

L(p, х2, v) = ||р||2/2 + f J"(bi - Мр - Агх3) + vjih - А2х2).

С помощью этой функции запишем двойственную задачу

max тах min min L(p, х2, v). (14)

vieR™2 ъеЯ" ptR"

Двойственная к (13) является задача

ma£ тах Гб^х + б^- IH^xll2^} (15)

vLeR+ vi еД+

при ограничениях

Ajvi + Á¡v2 = 0„, vi > 0mi, v2 > 0m2.

Теорема 2.1. Всякое решение v*T = [vj, üJ] двойственной задачи (15) определяет единственную первую составляющую р* решения [р*, х2] задачи (13) по формуле

Р' = Ajv¡ = -Á¡v*2, (16)

и справедливо выражение

6V = ИМИ2 = И2Т^|[2 = ||р*||2. (17)

В § 2.2 ставится задача нахождения такого решения системы Еремина (2), при котором толщина семейства разделяющих гиперплоскостей была бы максимальной'

Ь||ЛМ||2 = тт^Ки1||2, (18)

1/ = {иеЯт : Л7«1 + ¿¡ч2 = 0п, 6^1 + Ъ^иг = р, Щ> 0т1, И2>0тг}.

Теорема 2.3. Пусть полиэдры Х\ и Х2 непусты, а их пересечение пусто. Тогда решение V* задачи (15) и решение и* задачи (18) связаны друг с другом соотношениями

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

Г(а) = {х € Я" : и?Ахх - ЬJu*1 + ар = 0}, (20)

Г (а) = {х € Я" : -и?А2х + b¡u*2 + (а - 1 )р = 0}, (21)

где 0 < а < 1. Толщина этого семейства совпадает с минимальным расстоянием между полиэдрами Х\ и Х2.

Построена задача, двойственная к этой задаче. В работе даны три варианта задач, позволяющих построить разделяющую гиперплоскость максимальной толщины. Выбор наиболее подходящего варианта производится в зависимости от конкретных чисел тип.

В главе 3 строятся семейства разделяющих гиперплоскостей для двух полиэдров, заданных с помощью системы линейных уравнений с неотрицательными переменными. В соответствии с теоремой Фаркаша об альтернативах для несовместной системы равенств с неотрицательными переменными

Aix — bi, А2х — Ь2, х > 0„ совместна следующая система:

Ajui + А2u2 < 0„, bfui + b2u2 = р. (22)

Здесь р — положительная константа.

Теорема 3.1. Пусть два непустых , непересекающихся полиэдра заданы системами равенств на неотрицательном ортанте. Тогда любое решение системы (22) определяет два семейства разделяющих гиперплоскостей

<р\(х, а) = uj(Axx-bi)+ap = 0, а) = -u2 {A2x—b2)-(l-a)p = 0,

где а 6 [0 1].

Показано, что в отличие от случая полиэдров, заданных с помощью системы линейных неравенств, любое решение альтернативной системы определяет dea различных семейства разделяющих гиперплоскостей. Установлено, что не любая разделяющая гиперплоскость может быть представлена с помощью решения альтернативной системы (2). Приведен соответствующий иллюстративный пример.

Пусть заданы прямоугольные матрицы М и N, имеющие размеры mi х п. 7П2 х п соответственно. Их строками являются Mi,..., Mmí и Ni,..., Nm2 соответственно. Выпуклые оболочки двух множеств политопы

представимы в виде

Хх = { € Д» : ®1 = 1 = Мтг«1, «1 € й},

Ш2

Х2 = { х2 6 Л" : х2 = ^и^ЛГ/ = ш2 е 5г},

3=1

где Эх, - симплексы, определяемые по формуле

т,

= = г = 1,2.

1=1

Можно сказать, что строки матрицы М задают тх точек, строки матрицы N задают т2 точек из Я". Для задач классификации важно уметь разделять выпуклые оболочки, натянутые на каждую из этих совокупностей точек.

Поставим задачу нахождения кратчайшего расстояния между выпуклыми оболочками Х\ и Х2

ш тш IIМТ«л - ЛГтгу2||2/2- (23)

Введем в рассмотрение векторы их £ Я+1 и € Щ2. Вместо задачи (23) определим близкую задачу минимизации на положительном ортанте

тш тш (\\МТ"1-ХТУ2\\2/2-е1^) (24)

при условиях

= > 0т,, У2 > 0тг-

Лемма 4.1 Пусть ад^кл!- решение задачи (23), - решение задачи (24). Между решениями этих задач существует взаимно однозначное соответствие: если известны ад* и и/2, то в качестве решение задачи (24) можно взять

VI = и>\, г>2 = ш2; (25)

если известны г^ и г>2, то решения задачи (23) определяются по формулам

и>1 = у{/5*, Ц = г^/5*, ^ = (26)

Для решения исходной задачи (24) воспользуемся методом модифицированных функций Лагранжа (МФЛ). Введем скаляр 7 и вектор А € Щ., составим модифицированную функцию Лагранжа

L{vh V2, А, 7) = ||Мтг>! - NTv21|2/2 - ¿^щ. + 7^2 " " <»i)a/2 + ||(А - г»)+||»/(2г),

где г -коэффициент штрафа, = [vj,v2], вектор Ао - произвольный начальный вектор из множества ifj* и 70 из множества Л1.

Последнее слагаемое в функции Лагранжа введено для учета ограничения v > 0т; А е Я+- соответствующий вектор множителей Лагранжа. С учетом объединения векторов rj и v2 имеем L(vь v2, А, 7) = L(v, А, 7). Метод МФЛ для решения задачи (25) запишется в виде

7*+1 = 7* + г(ет1г;1*+1 — em3v2)t+l)) Afc+1 = (Afc ~ TVk+l) + , (27)

где Vk+1 определяется из следующей задачи безусловной минимизации:

vk+i € arg min L(v, А*, 7*). (28)

v6Rm

Теорема 4.1. Задача, двойственная к (24), состоит в нахождении

minmm||9||2/2 (29)

7€Л ?6Я"

при условии, что

Mq-( 1 + 7)emi > 0mi, -JVg + 7em2 > 0mj.

Объединим вектор ? и скаляр 7 одним символом z = [9,7], введем множество

где Л =

М -emi -N ет2

-матрица m х (n + 1).

Двойственную задачу (29) можно записать в виде

тш||д||2/2. (30)

гег

Для решения этой задачи снова воспользуемся методом модифицированных функций Лагранжа . Введем следующую модифицированную функцию Лагранжа:

Ц.9,7,«) = [ /3|Ы|2 + ||(« + /3(ет - ^))+||2]/2,

где г = [д,7] и и £

Для определения оптимального вектора V используется итерационный процесс

Щ+1 = Ы + 0(ет - Агк+1))+, (31)

где /? - положительный коэффициент штрафа , вектор г>о - произвольная начальная точка из множества г^+г находится из условия

гк+1 € агёггшп §{ Ш? + Ц^ + Р(ет - Аг))+1|2}. (32)

В приведенных двух вариантах метода модифицированных функций Лагранжа основное время расчетов тратится на решение задач безусловной минимизации, которые считаются с помощью обобщенного метода Ньютона. В первом варианте метода (28) минимум ищется в т-мерном пространстве, во втором варианте (32) - в (п+1)- мерном пространстве. Поэтому первый вариант метода наиболее эффективен, когда п > т, второй вариант, когда п.

Методы (28) и (32) были реализованы в системе МАЛАВ в виде программ M1.F1 и М1.Р2 соответственно. В § 4.2 и § 4.4 даны результаты численных расчетов с помощью программ MI.F1, М1.Р2 и программ, содержащихся в библиотеке оптимизационных программ системы МАТ1.АВ Для вычислений

использовался компьютер с процессором Репйит-4, тактовой частотой 3 ГГц, оперативной памятью 1 Гб.

В результате вычислений определялись следующие невязки-

Д1 = |<Н1.Р11, = ДзЧК-чЫи, Д4 = У^х-ькИоо,

гДе ||°||оо есть чебышевская норма вектора а; <f есть найденное расстояние между множествами , ||р*|| = 50- расстояние между политопами , заложенное при генерации тестовых задач. Генератор тестовых задач приведен в§ 4.3 (программа Сос)е1). С его помощью задавались различные варианты задач, в том числе и задачи высокой размерности.

Результаты решения случайным образом сгенерированных задач приведены в табл. 1. В первом столбце таблицы указаны размерности т и п. Во втором столбце приведены имена используемых программ. В третьем - даны

Таблица 1 Результаты сравнения работы методов МЬП и МАТЬАВ на компьютере Р - IV, 3.0 (З/гг., 1 <36. , «о = 0т , Ло = 0т , 7о = 0

т х п МЕТОД Т, с д» д2 А3

50 х 105 МЬР1 3.5 2.5 х Ю-12 2.2 х 10"16 6.7 х Ю-16

МАТЬАВ 0.25 1.5 х 10"13 5.4 х Ю-19 5.2 х Ю-20

100 х 105 МЬР1 10.9 7.1 х Ю-13 1.5 х Ю-18 1.7 х Ю-18

МАТЬАВ 2.4 8.5 х Ю-14 7.0 х Ю-15 8.1 х 10~19

300 х 104 МЬР1 8.5 1.0 х Ю-18 6.7 х Ю-18 4.8 х Ю"20

МАТЬАВ ♦ * * *

200 х 10® МЬР1 30.8 9.3 х 10~13 2.1 х Ю-18 7.1 х Ю-18

МАТЬАВ 7.5 8.7 х Ю-6 2.9 х Ю-15 4.0 х Ю-16

500 х 104 МЬР1 25.5 2.1 х Ю-19 4.2 х Ю-14 2.2 х Ю-19

МАТЬАВ 77.0 1.1 х 10"1 5.7 х Ю-14 3.9 х 10"16

1000 х 104 МЬР1 96.6 4.8 х 10~14 3.4 х Ю-19 3.6 х 10~19

МАТЬАВ # * * *

времена счета (в секундах). В четвертом , пятом, шестом, столбцах указаны Д1 , Д2, Д3.

При решении задач небольшой размерности оба подхода давали примерно одинаковые результаты При решении задач большой размерности методы МФЛ показали более высокую эффективность расчетов по сравнению с алгоритмами, содержащимися в библиотеке МАЛАВ. Объясняется это тем, что в данной реализации метода МФЛ высокую эффективность демонстрирует обобщенный метод Ньютона.

Далеко не все задачи большой размерности удалось решить с помощью библиотеки программ оптимизации МАЛАВ. Например, задача с т = 300, п = 10000 и т = 1000, п = 10000 были решены программой MI.F1 за 8.5 с и 96.6 с соответственно, но не были решены программой МАЛАВ

Таблица 2 Результаты сравнения работы разных методов на компьютере Р - IV, 3.0 вИг., 1 <76. , = 0т, 20 = 0„+1

тхп МЕТОД Т, с Д1 Д4

5000 х 20 МЬР2 0.65 1.5 х Ю"20 1.4 х Ю-11

МАТЬАВ 0.62 2.3 х 10"15 4.0 х 10"14

105 х 10 МЬР2 6.6 6.1 х 10"12 3.4 х Ю-11

МАТЬАВ 7.0 4.6 х Ю-20 7.9 х Ю-14

2 • 10® х 2 МЬР2 59.5 3.1 х 10~13 1.1 х ИТ12

МАТЬАВ 155.3 1.3 х ИГ14 4.0 х Ю-13

106 х 5 МЬР2 38.5 1.1 х Ю-11 2.3 х Ю-11

МАТЬАВ 37.3 1.7 х Ю-15 3.8 х Ю-14

4 • 106 х 2 МЬР2 144.8 1.3 х Ю-13 7.3 х Ю-13

МАТЬАВ 317.3 5.7 х Ю-15 9.3 х Ю"20

5 • 106 х 2 МЬР2 167.4 2.9 х Ю"20 1.4 х Ю-12

МАТЬАВ * * *

Из табл 1 следует, что программа МАТ1.АВ оказалась более эффективной , чем ML.F1 только при решении первой задачи невысокой размерности. В третьем и шестом случаях (строка 3, 6) программа МАТ1.АВ не решила задачу. В примере, приведенном на четвертой строке, программа МАТ1.АВ оказалась лучшей по времени, однако точность определения й была низкой. Для задач большой размерности программа МАТ1.АВ существенно уступает программе Ml.Fl.

Результаты вычислений случайным образом сгенерированных задач методом М1_Р2 приведены в табл. 2. В § 4 4 с помощью программы МЬР2 решена задача с т = 5 • 10® и п = 2 за 167.7 с и эта задача не была решена программой МАТ1.АВ. При решением задачи с т = 4 ■ 10е, п = 2 время счета по

программе MLF2 было в 2 раза меньше, чем по программе MATLAB.

При решении практических задач может оказаться, что в результате разного рода погрешностей полученные экспериментальные данные таковы, что множества Х\ и Х2 пересекаются В главе 5 изучается этот случай. Вводится процедура сжатия выпуклых оболочек. В результате получаются два непересекающихся политопа и для скорректированных выпуклых оболочек строится семейство разделяющих гиперплоскостей .

Скорректируем (сузим) множества Х\ и Х2 так, что введенные вместо них множества Х\ и Х2 не пересекаются и таковы что Х\ С Х\ и Х2 С Х2. Определим новые множества по формулам

Xi = { х € ЯГ : х = = Мтчц, wi 6

ТП2

Х2 = { х € Я" : х = = Nrw2, w2 € S2},

j=i

где S\, S2- сжатые симплексы:

m,

5, = {wt eiC:5>? = l, wJ,<a}, ¿ = 1,2. }=i

Здесь <7- число из интервала [1/m, 1]. Задачи (23) запишется следующим образом

min min \\MTwi- Nrw2\\ (33)

при условиях

e^iui = 1, е^гю2 = 1, 0mi < vi < <remi, 0m2 <v2< aem2. Так же, как и в главе 4, переходим к следующей задачи минимизации: min min (||МЧ - ЛГЧИоо - e^i) (34)

«16Л+1 V26 R+

при условиях

e^vi = e^v2, 0mi <vi< aemi, 0m2 <v2< aem%.

Можно показать, что если w*,w2 - решение задачи (33) и v{, v2 - решение задачи (34), то в качестве решение задачи (34) можно взять

v[ = w{, v% = w2. (35)

Если известны v\ и v2, то решения задачи (33) определяются по формулам

w{ = vll<r, w*2=v*2/e*, в- = е1ух. (36)

Теорема 5.1. Задача, двойственная к (34), состоит в нахождении

min min minmjn[<rMi + <iV>||i + IM|2/2] (37)

при условиях, что

Mq - (1 + y)emi +ф> 0mil -Nq + 7em2 + ф> 0^,

где -уе&.фе Я™1 ip е Я+2.

После некоторых упрощений задача (37) сводится к задаче безусловной минимизации

min min{||9||2 + 72 + ткг||((1 + y)em - Mq)+\\4

q€R" feR1

m2<r\\(Nq-4em2)+\\2}/2-

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

В качестве разделяющей гиперплоскости берется гиперплоскость, проходящая через середину семейства гиперплоскостей, разделяющих скорректированные политопы. Она условно разделяет исходные множества точек

В Приложении приводятся краткие сведения об обобщенном методе Ньютона, применяемом для решения задач безусловной минимизации. В работах О. Мангасарьяна доказана глобальная конечношаговая сходимость метода в предположении, что минимизируемая функция выпуклая, кусочно-квадратичная и дифференцируемая. В возникших в данной работе задачах все эти условия выполнены. В приведенных автором расчетах обобщенный метод Ньютона показал высокую эффективность при решении задач с большим числом неизвестных на персональных компьютерах Pentium 4

Основное содержание диссертационной работы изложено в следующих публикациях:

1. Голиков А.И., Евтушенко Ю.Г., Кетабчи С. О семействах гиперплоскостей, разделяющих полиэдры //Ж вычисл. матем. и матем. физ. 2005. Т. 45. № 2. С. 238-253.

2. Голиков А.И., Кетабчи С. Нахождение нормального решения в задачах квадратичного программирования // Тез докл. конф "Математическое программирование и приложения". Екатеринбург- УрО РАН, 2003 С.281.

3. Evtushenko Yu.G., Golikov A.I., Ketabchi S., Mollaverdi N. Augmehted Lagrangin method for linear programming // Dynamics of non-homogeneous systems. M.: Russian Academy of Sciences Institute for System Analysis. 2004. V. 7. Pp. 101-106.

4. Кетабчи С. Построение семейства гиперплоскостей, разделяющих полиэдры // Тез. докл. конф. "Алгоритмический анализ неустойчивых задач". ЕкатеринбургурО РАН , 2004. С.287.

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

Подписано в печать 21.03.2005 Формат бумаги 60x84 1/16 Уч.-изд.л.1. Усл.-печ.л. 1,25 Тираж 100 экз. Заказ 8

Отпечатано на ротапринтах в Вычислительном центре им. A.A. Дородницына РАН 119991, Москва, Ул.Вавилова, 40

i

M-OJ- OS.03

РНБ Русский фонд

2005-4 41944

■""Чч

; ,"" 379

\ ; "

22 АПР 2005

ВВЕДЕНИЕ

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 лет бурное развитие получило новое направление в научных исследованиях — теория распознавания и обработка изображений. Интенсивное развитие этой области знаний обусловлено большой потребностью в решении практических задач в самых различных областях: в медицинской диагностике, в геологическом прогнозировании, в робототехнике, в оценке политических и экономических ситуаций, в предсказании землетрясений и других природных катаклизмов, в задачах идентификации букв для автоматического чтения, идентификации речи и т.д.

Крупные результаты в этой области были получены во второй половине прошлого века. Укажем лишь некоторых из ведущих ученых, стоявших у истоков исследований в этой области: А.А. Ляпунов, О.Б. Лупанов, С.В. Яблонский, Ю.И. Журавлев, С.Н. Черников, И.И. Еремин, М.А. Айзерман. В 1998 году вышли в свет "Избранные научные труды Ю.И. Журавлева", в которых изложены основополагающие работы по математическим методам распознавания образов и дискретной математике. Научная школа Ю.И. Журавлева, создававшаяся на базе Вычислительного центра АН СССР, постоянно расширяется и сейчас имеет своих последователей не только в нашей стране, но и за рубежом.

Среди других научных школ упомянем коллектив МГУ, созданный А.А. Ляпуновым, С.В. Яблонским, О.Б. Лупановым. В Институте математики и механики УрО РАН успешно работает группа, образованная в 60-е годы С.Н. Черниковым и впоследствии возглавленная И.И. Ереминым

На протяжении последних 14 лет в Москве издается журнал "Pattern recognition and image analysis", в котором публикуются важнейшие работы, выполненные в области кибернетики и теоретической информатики.

Большая работа в области распознавания образов ведется в США в университете Висконсина под руководством профессора О. Мангасарьяна. Вместе со своими учениками О. Мангасарьян провел обширные исследования но общей теории диагностики, классификации и по применению методов оптимизаций в распознавании образов, решение прикладной задач в медицине и биологии. Укажем лишь на некоторые из многочисленных публикации О.Мангасарьяна и его учеников: работа О. Мангасарьяна, Н.Стрита, В.Волберта [44], К.Беннетт, Е.Бредестейра [30]. Алгоритмы и программы распознавания образов приведены в книге В.Н. Вапника [3]. Проблемы классификации изучаются в книге С.Бойда и JI. Ванденберга [32].

Среди многочисленных проблем, возникающих в области распознавания, укажем задачу построения гиперплоскостей, разделяющих два выпуклых множества. Построению численных методов решения этой задачи посвящена данная работа. В качестве выпуклых множеств рассмотрены полиэдры (пересечение конечного числа полупространств) и политопы (выпуклые оболочки конечного числа точек).

Теорема о существовании разделяющей гиперплоскости играет важную роль в функциональном анализе, в теории оптимизации и исследовании операций. При решении практических задач важно не только знать, что разделяющая гиперплоскость существует, но и уметь конструктивно ее строить. В данной работе в главах 1-3 предлагаются численные методы нахождения семейств гиперплоскостей, разделяющих два непересекающихся непустых полиэдра, заданных с помощью систем линейных неравенств и систем линейных уравнений с неотрицательными переменными. В главах 4 и 5 разработаны численные методы построения разделяющих гиперплоскостей для политопов.

Предлагаемые численные методы основаны на использовании теорем об альтернативах и метода модифицированных функций Лагранжа . Подход, связанный с применением теорем об альтернативах в численных методах, возник несколько лет назад и изложен в работах [7]—[15], [33]- [37]. Он основан на отыскании исевдорешений несовместных систем линейных равенств и неравенств. По найденным псевдорешениям строятся нормальные решения альтернативных совместных систем и с их помощью определяются гиперплоскости, разделяющие полиэдры. В работе приводятся иллюстративные примеры, даны таблицы с численными расчетами тестовых примеров. Теоремам об альтернативах посвященное большое количество публикаций. Укажем, например, [6],[22], [31]-[33], [38].

В главе 1 рассмотрено применение нормального решения альтернативной системы для построения семейства разделяющих гиперплоскостей. Использование результатов работы [9, 11, 12], позволяет найти нормальное решение из решения задачи безусловной минимизации невязки несовместной системы неравенств, задающей оба полиэдра. Если число переменных в задаче безусловной минимизации гораздо меньше, чем в альтернативной совместной системе, то такие расчеты менее трудоемки, чем нахождение решения альтернативной системы.

В основе лежит теорема И.И. Еремина о гиперплоскости, разделяющей полиэдры, заданные системами неравенств [15, теорема 10.1]. Используется специфический вид разделяющей гиперплоскости, нормаль и сдвиг которой выражены через произвольное решение некоторой системы, являющейся альтернативной к несовместной системе. Эта несовместная система состоит из двух совместных подсистем, каждая из которых определяет непустой полиэдр. Система несовместна, так как эти полиэдры не пересекаются. Построение разделяющих гиперплоскостей существенно опирается на теоремы об альтернативах.

В главе 1 рассмотрены два полиэдра

Хг = {х € Шп : А& > h}, Xi = {xGRn: А2х >'b2}.

Предполагается , что эти полиэдры непусты, а их пересечение пусто. Тогда система

Агх > Ьи А2х > Ь2 (0.1) несовместна, а альтернативная система

Ajui + Aju2 = 0n, bjui + bjui+ = p, щ > 0mi, щ > 0m2, (0.2) где p > 0 , напротив, совместна . Определим линейную функцию ip(x, а) от неременного вектора я, скаляра а из интервала [0,1]: ip(x, а) = uJ{A\x — &i) + ар. (0.3)

Если щ - решение системы (0.2), то уравнение <р(х, а) = 0 задает гиперплоскость, разделяющую полиэдры Х\ и Х2. Гиперплоскость (0.3) при а = 0.5 была впервые построена И.И.Ереминым. Метод определения функции ip состоит в нахождении решения системы (0.2) и использовании формулы (0.3). Такой подход весьма затруднителен в том случае , когда т п. Поэтому в первой главе данной работы для построения разделяющей гиперплоскости предлагается решать следующую задачу безусловной минимизации в п - мерном пространстве: mini[||(bi - Aia;)+||2 + ||(Ь2 - Л2х)+||2]. (0.4) хеК ^

Доказана теорема, утверждающая, что найденный из этой задачи вектор х* является псевдорешением системы (0.1) и нормальное решение й*т = [£«iT,W2T] системы (0.1) определяется но формулам z\ = (bi - Aix*)+, 4 = fa - А2х*)+, fii = рА! (Ikl2 + II4II2), Й2 = Р4/( т2 + ш2)

Функция (р, которая определяет разделяющую гиперплоскость, записывается в виде: ufiAxx - Ъг) + ар = 0, где 0 < а < 1. (0.5)

Объединение всех таких гиперплоскостей, когда а изменяется от 0 до 1, называется семейством параллельных разделяющих гиперплоскостей.

В теореме 1.2 дан анализ решений задачи (0.4). Показано в частности , что, если Х\ ф 0, Х2 ф 0, Х\ П Хч = 0, то все решения системы (0.2) отличны от нуля, кроме того, дана формула для определения толщины семейства разделяющих гиперплоскостей. Предложенный подход к построению разделяющих гиперплоскостей наиболее эффективен в задачах, где размерность вектора п невелика,но количество ограничений т может быть значительным, т.е. п -С га .

В § 1.2 показано, что в ряде случаев найденное семейство разделяющих гиперплоскостей можно расширить, решая две вспомогательные задачи линейного программирования. Приведены три примера, иллюстрирующие найденные свойства разделяющих гиперплоскостей . Система (0.2) имеет весьма глубокий смысл. Приведенная в диссертации теорема 1.4 утверждает, что всякая строго разделяющая гиперплоскость такова, что всегда ее направляющий вектор с и сдвиг 7 выражаются через какое-нибудь решение системы (0.2).

При решении практических задач может оказаться, что полученные в результате экспериментов данные содержат погрешности, из -за которых матрица А и вектор b вычислены неточно . В результате этого множества Х\ и Х2 могут пересекаться. В этом случае рекомендуется так скорректировать множества Х\ и Х2, что полученные вместо них множества Х\ С Х\ и Х2 С Х2 не пересекаются. Для этих множеств можно построить разделяющие гиперплоскости, используя технику, изложенную выше. При этом желательно, чтобы норма корректирующего вектора были бы минимально возможной. В § 1.4 приведены формулы определения оптимальной коррекции и предлагаемая техника проиллюстрирована на простейшем примере.

В § 1.5 рассмотрена возможность применения масштабирования целевой функции для максимизации толщины семейства разделяющих гиперплоскостей. Вместо (0.4)решается иромасштабированная задача min 1[||(б! - А1Х)+1|2 + Л||(62 - Л2а;)+||2], (0.6) где Л — искомый коэффициент.

Толщина семейства (0.5) становится функцией Л . Найдя из (0.6) оптимальный вектор х*(Х) , определим и|(А) , А) и но формулам, аналогичным (0.5), получим новое семейство разделяющих гиперплоскостей. Численно ищется максимум толщины семейства по А . Во всех примерах за счет введения А удалось так повернуть гиперплоскости, что в результате получались семейства, толщины которых совпадали с расстояниями между множествами Xi и Х2.

В § 2.1 ставится задача квадратичного программирования об определении семейства гиперплоскостей максимальной толщины, совпадающей с минимальным расстоянием между полиэдрами. Эта задача сводится к минимизации функции от 2п переменных при наличии т линейных ограничений типа неравенства. Построена двойственная задача, состоящая в максимизации квадратичной функции от т неременных на положительном ортанте при наличии п линейных ограничений тина равенства. Показано, что, решив эту задачу, можно легко определить семейства разделяющих гиперплоскостей максимальной толщины.

В § 2.2 ставится задача нахождения такого решения системы Еремина (0.2), при котором толщина семейства разделяющих гиперплоскостей была бы максимальной . Показано, что эта задача состоит в минимизации квадратичной функции от т переменных при наличии п + 1 ограничений на положительном ортанте. Построена задача, двойственная к этой задаче. В работе даны три варианта задач, позволяющих построить разделяющую гиперплоскость максимальной толщины. Выбор наиболее подходящего варианта производится в зависимости от конкретных чисел тип.

В главе 3 строятся семейства разделяющих гиперплоскостей для двух полиэдров, заданных с помощью системы линейных уравнений с неотрицательными переменными. Показано, что в отличие от случая полиэдров, заданных с помощью системы линейных неравенств, любое решение альтернативной системы определяет два различных семейства разделяющих гиперплоскостей. Установлено, что не любая разделяющая гиперплоскость может быть представлена с помощью решения альтернативной системы (0.2) . Приведен соответствующий иллюстративный пример.

В главе 4 рассмотрен случай построения семейства гиперплоскостей, разделяющих два политопа. Предполагается, что в Rn задан набор из mi точек и другой набор из Ш2 точек. Общее число точек равно т\ + Ш2 = т. Выпуклые оболочки (политопы), натянутые на эти множества, обозначены через Х\ и Х-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*106, п = 2 время счета но программе MLF2 было в 2 раза меньше, чем по программе MATLAB .

В главе 5 изучается случай, когда выпуклые оболочки двух множеств (политопов) пересекаются. Вводится процедура сжатия выпуклых оболочек. В результате получаются два непересекающихся политопа и для скорректированных выпуклых оболочек строится семейство разделяющих гиперплоскостей . В качестве разделяющей гиперплоскости берется гиперплоскость, проходящая через середину семейства. Она условно разделяет исходные множества точек. В приведенном примере эта гиперплоскость отделяет 96% точек одного множества от 97% точек другого множества.

В Приложении приводятся краткие сведения об обобщенном методе Ньютона, применяемом для решения задач безусловной минимизации. В работах О. Мангасарьяна доказана глобальная конечношаговая сходимость метода в предположении, что минимизируемая функция выпуклая, кусочно-квадратичная и дифференцируемая. В возникших в данной работе задачах все эти условия выполнены. Поэтому теоретическое исследование обобщенного метода Ньютона не проводилось. В приведенных автором расчетах обобщенный метод Ньютона показал высокую эффективность при решении задач с числом неизвестных до нескольких тысяч на персональных компьютерах Pentium4.

ЗАКЛЮЧЕНИЕ

В диссертационной работе были получены следующие основные результаты.

1. На основе применения теорем об альтернативах разработаны новые численные методы построения семейств гиперплоскостей, разделяющих полиэдры, заданные в n-мерном пространстве. При этом простейший метод состоит в безусловной минимизации кусочно-квадратичной выпуклой функции в n-мерном пространстве. Безусловная минимизация проводится с помощью глобально сходящегося за конечное число шагов обобщенного метода Ныотона.

2. Исследована возможность построения семейства разделяющих гиперплоскостей максимальной толщины на основе применения теоремы об альтернативах.

3. Дано обобщение теоремы И.И.Ерёмина о семействе гиперплоскостей, разделяющих полиэдры, при задании их системами равенств на неотрицательном ортанте. Показано, что в этом случае каждому решению альтернативной совместной системы соответствует два семейства разделяющих гиперплоскостей.

4. Программно реализован в системе MATLAB численный метод построения семейства гиперплоскостей, разделяющий полиэдры, заданные большим числом (несколько миллионов) линейных неравенств.

5. На основе модифицированной функции Лагранжа и обобщенного метода Ньютона предложены и программно реализованы в системе MATLAB численные методы построения семейства гиперплоскостей максимальной толщины, разделяющих политопы. Численные эксперименты показали возможность решения таких задач с количеством данных до пяти миллионов.

6. Рассмотрен случай, когда два политопа пересекаются. С помощью операции сжатия из них образуются непересекающиеся политопы. Для скорректированных таким образом политопов задача построены семейства разделяющих гиперплоскостей максимальной толщины сведена к задаче безусловной минимизации в т + п + 1- мерном пространстве.

1. Антипин А.С. Методы нелинейного программирования, основанные на прямой и двойственной модификации функции Лагранэюа. М.: ВНИИ-СИ. 1979.

2. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 2003.

3. Вапник В.Н., Глазкова Т.Г., Кощеев В.А., Михальский А.И., Червоненкис А.Я. Алгоримы и программы восстановления зависимостей. М. : НАУКА 1984.

4. Bertsekas D.P. Nonlinear Programming. Athena Scientific, Belmont, MA, second edition, 1999.

5. Войтов O.H., Зоркальцев В.И., Филатов А.Ю. Исследование систем неравенств алгоритмами внутренних точек на задачах поиска допустимых режимов электроэнергетических систем. Препринт № 10. ИСЭМ СО РАН. 1997. Иркутск. 28 с.

6. Гейл Д. Теория линейных экономических моделей. М.: Изд-во иностр. лит., 1963.

7. Голиков А.И., Евтушенко Ю.Г. Отыскание нормальных решений в задачах линейного программирования // Ж. вычисл. матем. и матем. физ. 2000. Т. 40. № 12. С. 1766-1786.

8. Голиков А.И., Евтушенко Ю.Г. Двойственный подход к решению систем линейных равенств и неравенств // Труды XII Байкальской междунар. конф. "Методы оптимизации и приложения". Пленарные доклады. Иркутск. 2001. С. 91-99.

9. Голиков А.И., Евтушенко Ю.Г. Новый метод решения систем линейных равенств и неравенств // Докл. РАН. 2001. Т. 381. №4. С. 1-4.

10. Голиков А.И., Евтушенко Ю.Г. Теоремы об альтернативах и их применение в численных методах // Ж. вычисл. матем. и матем. физ. 2003. Т. 43. №3. С. 354-375.

11. Голиков А.И., Евтушенко Ю.Г. Определение направления наискорейшего спуска с помощью теорем об альтернативах // "Математическое моделирование. Проблемы и результаты". М.: Наука, 2003. С. 36-42.

12. Голиков А.И., Евтушенко Ю.Г. Применение теорем об альтернативах к нахождению нормальных решений линейных систем // Изв. вузов. Математика. 2001. № 12 (475). С. 21-31.

13. Голиков А.И., Евтушенко Ю.Г., Кетабчи С. О семействах гиперплоскостей, разделяющих полиэдры // Ж. вычисл. матем. и матем. физ. 2005. Т. 45. №2. С. 238-253.

14. Голиков А.И., Евтушенко Ю.Г., Моллаверди Н. Применение метода Ньютона к решению задач линейного программирования большой размерности // Ж. вычисл. матем. и матем. физ. 2004. Т. 44. № 9. С. 1564-1573.

15. Голиков А.И., Кетабчи С. Нахождение нормального решения в задачах квадратичного программирования. Тезисы докладов конференции "Математическое программирование и приложения", Екатеринбург, 2003, с.281.

16. Еремин И.И. Теория линейной оптимизации. Екатеринбург: УрО РАН, 1998.

17. Еремин И.И., Мазуров В.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983.

18. Еремин И.И. Противоречивые модели оптимального планирования. М.: Наука, 1983.

19. Еремин И.И. Двойственность в линейной оптимизации. Екатеринбург: УрО РАН, 2001.

20. Еремин И.И. О квадратичных задачах и полноквадратичных задачах выпуклого программирования // Известия вузов. Матем. 1998. № 12. С. 2228.

21. Кетабчи.С.Посгпройнние семейства гиперплоскогпей, разделяющих полиэдры докладов конференции "Алгоримический анализ неустойчивых задач "Екатинбург, 2004, с.287.

22. Зоркальцев В.И. Теорема Фаркаша и теория двойственности в линейной оптимизации. Препринт № 9. Иркутск: ИСЭМ СО РАН. 2001.

23. Гольштейн Е.Г. Третьяков Н.В. Модифицированные функции Лагранжа. Теория и методы оптимизации. М.: Наука. 1989.

24. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.

25. Поляк Б.Т., Третьяков Н.В. Об одном итерационном методе линейного программирования и его экономической интерпретации // Эконом, и матем. методы. 1972. Т. VIII. Вып. 5.

26. Разумихин Б.С. Физические модели и методы теории равновесия в программировании и экономике. М.: Наука, 1975.

27. Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир, 1991.

28. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М.: Мир, 1972.

29. Черников С.Н. Линейные неравенства. М.: Наука, 1968.

30. Bennett К.P., Bredensteiner E.J. Duality and Geometry in SVM Classifiers // Proceedings of the 17th International Conference on Machine Learning.2000. San Francisco. Pp.57-64.

31. Broyden C.G. On theorems of alternative // Optimizat. Meth. and Software.2001. V. 16. №1-4. Pp. 101-111.

32. Boyd S., Vandenberghe L. Convex Optimization // Cambrige University Press. 2004.

33. Dax A. The relationship between theorems of the alternative, least norm problems, steepest descent directions, and degeneracy: A review // Ann. Operat. Res. 1993. V. 46. № 1. Pp. 11-60.

34. Evtushenko Yu. Computational of exact gradients in disributed dynamic systems // Optimiz. Meth. and Software. 1998. V. 9. № 1-3. Pp. 45-75.

35. Evtushenko Yu.G., Golikov A.I. New perspective on the theorems of alternative // High Performance Algorithms and Software for Nonlinear Optimization. Kluwer, 2003. Pp. 227-241.

36. Evtushenko Yu.G., Golikov A.I. The augmented Lagrangian function for the linear programming problems // Dynamics of non-homogeneous systems. M.: Russian Academy of Sciences Institute for System Analysis. 1999. V. 2. Pp. 63-67.

37. Evtushenko Yu.G., Golikov A.I., Ketabchi S., Mollaverdi N. Augmented Lagrangin method for linear programming j/ Dynamics of noil-homogeneous systems. M.: Russian Academy of Sciences Institute for System Analysis. 2004. V. 7. Pp. 101-106.

38. Giannessi F. Theorems of the alternative and optimization // Encyclopedia of Optimization. Dordrecht etc.: Kluwer acad. publ. 2001. V. 5. Pp. 437-444.

39. Fung G., Mangasarian O.L. A feature selection Newton method for support vector machine classification // Computational Optimization and Applications. 2004. V.28. N.2. Pp 185-202.

40. Kanzow C., Qi H., Qi L. On the Minimum Norm Solution of Linear Programs // Journal of Optimization Theory and Applications. 2003. V. 116. Pp. 333345.

41. Mangasarian O.L. Nonlinear programming. Philadelphia: SIAM, 1994.

42. Mangasarian O.L. A Finite Newton Method for Classification // Optimizat. Meth. and Software. 2002. V. 17. Pp. 913-930.

43. Mangasarian O.L. A Newton Method for Linear Programming // Data Mining Institute. Technical Report 02-02. March 2002.

44. Mangasarian O.L., Street W.N., Wolberg W.H. Breast carter diagnosis and prognosis via Linear Programrnig // Operation Research Vol. 43, No 4, July-August 1995.