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

• Кетабчи Саеид
• кандидат физико-математических наук
• 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- мерном пространстве.

Список литературы диссертационного исследования кандидат физико-математических наук Кетабчи Саеид, 2005 год

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.