Вариационный подход к проблеме обобщенной отделимости тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Дружинина, Оксана Владимировна

• Дружинина, Оксана Владимировна
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Дружинина, Оксана Владимировна

Введение

1 Элементы негладкой d.c. минимизации

1.1 Локальный поиск.

1.2 Условия глобальной оптимальности.

1.3 Минимизирующие последовательности.

1.4 Стратегия глобального поиска.

1.5 Сходимость стратегии глобального поиска.

1.6 О разрешающих наборах.

1.7 Заключительные замечания.

2 Задача о полиэдральной отделимости

2.1 Постановка задачи о полиэдральной отделимости.

2.2 D.C. представление функции ошибки.

2.3 Нахождение субдифференциалов функции ошибки

2.4 Построение аппроксимации поверхности уровня.

2.4.1 Первый прием построения аппроксимации поверхности уровня функции /(•).

2.4.2 Второй прием

2.4.3 Третий прием

2.4.4 Построение наборов направлений Dir.

2.5 Вычисление интервала одномерного поиска параметра /?.

2.6 Заключительные замечания.

3 Численное решение задачи о полиэдральной отделимости

3.1 Локальный поиск в задаче о полиэдральной отделимости.

3.1.1 Первый этап тестирования локального поиска.

3.1.2 Тестирование алгоритма локального поиска на задачах о полиэдральной отделимости большой размерности.

3.2 Алгоритм глобального поиска и особенности численного эксперимента

3.3 Первый этап численного эксперимента.

3.4 Второй этап численного эксперимента

3.5 Минимизация количества отделяющих гиперплоскостей

3.6 Решение тестовой задачи с множествами большой мощности

3.7 Заключительные замечания.

Введение диссертации (часть автореферата) на тему «Вариационный подход к проблеме обобщенной отделимости»

При решении практических задач во многих областях человеческой деятельности может возникать потребность во введении процедуры отделения множеств. Примерами таких задач могут быть, например, распознавание текста, распознавание речи, идентификация личности, обучение машин; экономические задачи, такие как задача определения кредитоспособности клиента банка, задачи управления портфелем ценных бумаг, задача определения жизнеспособных и склонных к банкротству фирм [58, 100, 112, 116, 143, 144]; медицинские задачи (диагностика и прогнозирование)[129, 130, 151, 152]; горно-геологические задачи [62].

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

Наиболее распространенным способом представления данных является представление объекта'в виде вектора х = (х\,. ■, хп) € ]Rn, где г-я координата вектора х определяет значения г-й характеристики, влияющей на принятие решения о том, к какому классу можно отнести данный образец.

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

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

Дадим математическое описание задачи классификации.

Пусть заданы множество М С JRn и класс функций {Г\ F : Iff1 —► Ш}. Известно, что М = к,ик2, причем множества и К2 заданы своими конечными подмножествами Л С Яъ В С к2.

Определение 0.0.1 (37, 59, 60, 133] Задачей дискриминантного анализа назовем задачу нахождения функции F такой, что

Г {а) < О Va € Л, F(b) >0 \/ЬеВ

1)

- (•) в этом случае называется дискриминантной (решающей функцией, классификатором). ■ #

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

Дискриминантная функция Г(-) реализует правило соотнесения (по свойству принадлежности одному из подмножеств К\ и К2) предъявляемого для распознавания вектора х по правилу: х е Кх, если F(x) < 0; w (2) х € К2, если F(x) > 0. Чаще всего предполагается, что функции /г(-) выбираются из класса функций наиболее простого вида: аффинных или кусочно-линейных. Однако, например в [133], рассматривается и отделимость множеств некоторой квадратичной функцией. Отметим, что более точно называть кусочно-линейные функции кусочно-аффинными. Однако, далее будем применять первый, более устоявшийся термин. Важность класса кусочно-линейных функций [10, 37, 77, 110, 124, 126, 137] иллюстрирует, например следующий факт. Оказывается [37, 77], что любые два конечных множества точек из пространства ]Rn могут быть отделены некоторой кусочно-линейной функцией.

Рассмотрим несколько определений отделимости конечных множеств точек пространства Шп кусочно-линейными функциями.

Если выпуклые оболочки множеств не пересекаются, то они могут быть отделены аффинной отделяющей функцией [8], [15]—[31], [37], [54], [132], [133]. В этом случае говорят о линейной отделимости множеств.

Наибольший интерес представляет задача отделения множеств, выпуклые оболочки которых имеют непустое пересечение. Для отделения таких множеств требуются более общие, чем линейная отделимость, понятия отделимости множеств. В качестве примеров определений обобщенной отделимости множеств можно привести отделимость множеств k-функцией (И.И. Еремин, С.В. Плотников [37, 77]) и отделимость множеств комитетом большинства (Вл.Д. Мазуров, М.Ю. Хачай [36], [37], [53]—[60], [77], [83], [106], [134]—[136]), разрабатываемые в ИММ УрО РАН (г. Екатеринбург). Еще одним вариантом обобщенной отделимости является полиэдральная отделимость в смысле определения Мангасарьяна [109], иначе называемая отделимостью множеств комитетом единогласия [60].

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

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

Достаточно сложно привести полную классификацию задач невыпуклой или, как еще принято говорить, глобальной оптимизации. Тем не менее, в литературе [121, 122] принято рассматривать следующие четыре класса задач.

1. Выпуклая максимизация (или вогнутая минимизация): f(x) | max, х е D, (3) где /(•) — выпуклая функция на некотором открытом выпуклом множестве Q С Мп, содержащем допустимое множество D.

2. Обратно-выпуклые задачи или задачи на дополнениях выпуклых множеств. Простейшей задачей подобного типа является следующая задача tp(x) 1 min, х G S, g(x) > 0, (4) где g(-) — выпуклая функция на выпуклом открытом множестве О, С lRn, содержащем множество S, <р(-) — непрерывная функция на IRn.

3. D.C. минимизация. Эта задача имеет вид

- F{x) = д{х) - f(x) I min, х е D, (5) где </(•), /(•) — выпуклые функции на некотором открытом выпуклом множестве С iR™, £>cfi, т.е. F(-) — d.c. функция.

4. Экстремальные задачи с d.c. ограничениями, простейшей из которых является следующая задача р(х) | min, хе S, F(x) > 0, (6) где F(x) = f(x) — д(х), х G Q, а /(•), д(-) являются выпуклыми функциями на выпуклом открытом множестве И С iR", содержащем множество S, </?(•) — непрерывная функция на IRn.

Нетрудно видеть, что при д(х) = 0 задача d.c. минимизации (5) обращается в задачу выпуклой максимизации (3), так что последняя является частным случаем (5). Аналогично задача с d.c. ограничениями (б) при f(x) = 0 обращается в задачу (4) на дополнении выпуклого множества, которая, таким образом, оказывается частным случаем (6). Итак, можно сказать, что простейшие задачи d.c. программирования (5) и (6) являются основными согласно предложенной классификации. Задачи с d.c. структурой играют важную роль в невыпуклой оптимизации как с теоретической точки зрения, так и ввиду огромного количества приложений. Пространство d.c. функций является линейным [122, 123,150] и содержит, как нетрудно видеть, конус выпуклых функций, также как и конус вогнутых функций. Более того, каждая дважды непрерывно дифференцируемая функция является d.c. функцией [122, 150] (хотя в большинстве случаев достаточно сложно получить ее d.c. разложение, и в общем случае эта задача остается открытой). Поэтому [115], пространство d.c. функций на компактном выпуклом множестве плотно в пространстве непрерывных функций в смысле топологии равномерной сходимости. Другими словами, каждая непрерывная функция может быть приближена d.c. функцией с любой точностью. Следовательно, и любая непрерывная экстремальная задача с любой степенью точности может быть аппроксимирована некоторой задачей d.c. программирования, т.е. задачей из вышеприведенной классификации.

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

Пионером в изучении свойств d.c. функций является А.Д. Александров [1, 2]. Позже этой проблемой занимались Е.М. Лаидис [52] и П. Хартман [115]. Некоторые более поздние работы по d.c. структурам можно пайти в [117, 142].

Хотя исследование задач d.c. оптимизации (исключая частный случай — выпуклую максимизацию) началось сравнительно недавно, не более 40 лет назад, к настоящему моменту достигнуты определенные успехи. Во-первых предложены условия глобальной оптимальности [88, 118, 119, 146], использующие современный аппарат выпуклого анализа [48, 81, 107]. Кроме того, разрабатывается теория двойственности [117, 123, 150] и связанные с характеризацией оптимума и двойственностью задач различные условия регулярности [123, 150].

Для построения численных методов решения задач d.c. программирования, исключая стохастику, в основном применяются три основных подхода. Таковыми являются методы

1) отсечений [6, 150];

2) ветвей и границ [122, 141, 150];

3) внешней и внутренней аппроксимации [6, 150].

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

С другой стороны, ведутся разработки по построению алгоритмов па основе различных вариантов условий глобальной и локальной оптимальности. В частности, Ж.-Б. Ириарт-Уррути [118] были предложены необходимые и достаточные условия для задач d.c. минимизации (5), представленные здесь для случая D = Шп: dj(z) С deg(z) Ve > 0.

Кроме того, другими математиками были получены условия глобальной оптимальности для некоторых более частных задач d.c. минимизации (см. обзор [118]). Другой подход к решению подобных задач был развит в работах А.С. Стрекаловско-го. На основе предложенных условий глобальной оптималыюсти для четырех приведенных выше классов задач [86], [88], [90]-[93], [95], им и его учениками были разработаны стратегии глобального поиска для решения многих актуальных теоретических и прикладных задач оптимизации [51], [87], [94], [96], [97]. Особо следует отметить работы А.А. Кузнецовой по решению NP-трудной задачи дискретной оптимизации— поиск максимальной клики в неориентированном графе [127], Т.В. Яковлевой по решению задач об одномерном и многомерном рюкзаках [108], а также работу А.В. Орлова о поиске ситуаций равновесия в биматричных играх [76].

Общая идеология методики, развиваемой А.С. Стрекаловским и его учениками, заключена всего в трех принципах.

1. Линеаризация по базовой невыпуклости исследуемой задачи и, как следствие, редукция исходной невыпуклой задачи к семейству (частично) линеаризованных задач.

2. Повсеместное применение методов выпуклой оптимизации для решения линеаризованных задачи, и как следствие, "внутри" локального поиска.

3. Построение "хороших" аппроксимаций (разрешающих наборов) для поверхностей уровня или границ надграфика выпуклых функций.

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

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

Проблематикой негладкого анализа, в частности, развитием теоретической базы и построение численных методов занимается большая группа отечественных и зарубежных математиков, среди которых выделяют, например, таких выдающихся ученых, как Б.Н. Пшеничный, В.Ф. Демьянов, А.Д. Иоффе, Ж.-Б. Ириарт-Уррути, Ф.Кларк, Е.А. Нурминский, Ж.-П. Пено, Б.Т. Поляк, Р. Рокафеллар, В.М. Тихомиров, Н.З. Шор, И. Экланд и многих других.

Среди методов негладкой оптимизации, которые в той или иной мере нашли практическое применение, можно выделить следующие классы.

1. Обобщенный градиентный спуск [14, 65, 66, 79, 99, 101]. Это класс субградиентных процессов минимизации выпуклых функций, основанных на движении в направлении, которое дает уменьшение расстояния до точки минимума, если шаговый множитель достаточно мал. К преимуществам этих методов следует отнести простоту их реализации, а к недостаткам — медленную, как правило, сходимость.

2. Обобщенные градиентные методы с растяжением пространства [65], [66], [79], [101]—[105], в которых для ускорения сходимости используются преобразования пространства. Это часто применяемый в настоящее время класс методов, показавший свою высокую эффективность при решении практических задач.

3. Использование секущих гиперплоскостей для аппроксимации графика функции [14] или для последовательного уменьшения объема области локализации экстремума [79, 81]. К числу методов этого типа относится и получивший широкую известность метод эллипсоидов и его модификации [65, 66, 79]. С другой стороны, метод эллипсоидов можно отнести к методам обобщенного градиентного спуска с растяжением пространства.

4. Методы, основанные на замене экстремальной задачи вычислением значения сопряженной функции в начале координат [68]—[74], [128], [138]—[140].

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

Перейдем к подробному изложению содержания диссертации.

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Дружинина, Оксана Владимировна

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

1. Предложены новые алгоритмы локального и глобального поиска для негладкой задачи d.c. минимизации, и для них доказаны теоремы сходимости.

2. Обоснованы основные этапы алгоритма глобального поиска в задаче о полиэдральной отделимости посредством аналитических исследований и численного тестирования.

3. Разработано программное обеспечение для решения задач негладкой d.c. минимизации, которое доказало свою эффективность на серии специальных тестовых примеров, а также во время численного решения задач полиэдральной отделимости различной размерности.

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

Заключение

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

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

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

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

Кроме того, предложено несколько вариантов построения аппроксимаций поверхности уровня негладких выпуклых функций, используемых в алгоритме глобального поиска.

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

В частности анализ численного эксперимента говорит об эффективности предложенной методики решения задач полиэдральной отделимости.

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

1. Александров А. Д. О поверхностях, представимых разностью выпуклых функций / Александров А. Д. // Известия Академии Наук Казахской ССР. Серия математики и механики. — 1949. — Вып.З. — С. 3-20.

2. Александров А. Д. Поверхности, представимые разностями выпуклых функций / Александров А. Д. // Доклады Академии Наук СССР. — 1950. — Т.72, №.4.- С. 613-616.

3. Алексеев В. М. Оптимальное управление / В. М. Алексеев, В. М. Тихомиров, С. В. Фомин — М.: Наука. Гл. ред. физ.-мат. лит., 1986.

4. Бахвалов Н. С. Численные методы / Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. ^ М.: Наука, 1987.

5. Белецкий Н. Г. Комитетные конструкции в многоклассовых задачах распозно-вания образов: Дис. . канд. физ.-мат. наук / Белецкий Н. Г. — Свердловск, 1984.

6. Булатов В. П. Методы погружения в задачах оптимизации / Булатов В. П. — Новосибирск: Наука, 1977.

7. Вапиик В.Н. Теория распознавания образов / Вапник В.Н., Червоиенкис А.Я.- М.: Наука, 1974.

8. Васильев Ф. П. Численные методы решения экстремальных задач / Васильев Ф. П. — М.: Наука, 1988.

9. Васильев О. В. Лекции по методам оптимизации / Васильев О. В. — Иркутск: Изд-во Иркут. ун-та, 1994. — 344 с.

10. Волокитин Е. П. О представлении непрерывных кусочно-линейных функций / Волокитин Е. П. // Управляемые системы. — Новосибирск: Наука, 1979. — 19.- С. 14-21.

11. Габасов Р. Ф. Методы оптимизации / Габасов Р. Ф., Кириллова Ф. М. — Минск: Изд-во БГУ, 1981.

12. Гилл Ф. Практическая оптимизация / Гилл Ф., Мюррей У., Райт М. — М.: Мир, 1985.

13. Гуревич И. Б Минимизация булевых функций и эффективные алгоритмы распознавания / Гуревич И. В., Журавлев Ю. И. // Кибернетика, 1974, № 3. С. 16-20.

14. Демьянов В. Ф. Недифференцируемая оптимизация / Демьянов В. Ф., Васильев Л. В. М.: Наука, 1985. - 384 с.

15. Дружинина О. В. Задача полиэдральной отделимости как задача d.c. минимизации / Дружинина О. В., Стрекаловский А. С. // Тезисы докладов всероссийской конференции "Математическое программирование и приложения".

16. Информационный бюллетень Ассоциации математического программирования №10, Екатеринбург, 24-28 февраля 2003 г. — Екатеринбург, 2003. — С. 196.

17. Дружинина О. В. К решению задачи о полиэдральной отделимости / Дружинина О. В. // Материалы всероссийской научной молодежной конференции "Под знаком Сигма" — Омск, 2003. — С. 13-14.

18. Дружинина О. В. К решению задачи о полиэдральной отделимости / Дружинина О. В. // Материалы всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 1-5 июля 2003 г. — Омск, 2003. — С. 134.

19. Дружинина О. В. О задачи отделимости линейно неотделимых множеств / Дружинина О. В. // Тезисы докладов конференции "Ляпуиовские чтения и презентация информационных технологий", 24-26 декабря 2003 г. — Иркутск, 2003. С. 45.

20. Дружинина О. В. Глобальный поиск в задачах классификации / Дружинина О. В. // Тезисы докладов конференции "Ляпуновские чтения и презентация информационных технологий", 2004 г. — Иркутск, 2004. — С. 20.

21. Дружинина О. В. О глобальном поиске в задаче полиэдральной отделимости / Дружинина О. В. // Оптимизация. Управление. Интеллект. — 2004. — № 2 — С. 96-103.

22. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации / Журавлев Ю.И. j j Проблемы кибернетики. М.: Наука, 1978.

23. Журавлев Ю.И. Об алгебраических методах в задачах распознавания и классификации / Журавлев Ю.И. // Распознавание. Классификация. Прогноз. Математические методы и их применение. Вып. 1. М.: Наука. 1989. - С. 9-16. 16.

24. Журавлев Ю.И. Распознавание образов и распознавание изображений / Журавлев Ю.И., Гуревич И.В. // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 2. М.: Наука, 1989. - С. 5-72.

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

26. Еремин И. И. Теория линейной оптимизации / Еремин И. И. — Екатеринбург: Изд-во ИММ УрО РАН, 1999.

27. Еремин И. И. Введение в теорию линейного и выпуклого программирования / Еремин И. И., Астафьев Н. Н. — М.: Наука, 1976.

28. Еремин И. И. Нестационарные процессы математического программирования / Еремин И. И., Мазуров В. Д. — М.: Наука, 1979.

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

30. Еремин И. И. О методе "штрафов" в выпуклом программировании / Еремин И. И. // Кибернетика. 1966. - №4. - С. 63-67.

31. Еремин И. И. Двойственность для несобственных задач паретовской и лексикографической линейной оптимизации / Еремин И. И. // Труды Института математики и механики, УрО РАН, Екатеринбург. — 1996 N4. — С. 322-336

32. Еремин И. И. Сигма-кусочные функции и задачи дизънктивного программирования / Еремин И. И. // Труды Института математики и механики УрО РАН, Екатеринбург: УрО РАН. 1998 - С. 357-380

33. Еремин И. И. О квадратичных и полноквадратичных задачах выпуклого программировании / Еремин И. И. // Известия ВУЗов. Математика — 1998 (12)- С. 22-28.

34. Еремин И. И. Общая теория устойчивости в линейном программировании / Еремин И. И. // Известия вузов. Математика. — 1999. N 12.

35. Еремин И. И. Математические методы в экономике Еремин И. И., Мазуров Вл. Д., Скарин В. Д., Хачай М. Ю. — Екатеринбург: УрГУ-Центр "Фактория Пресс". 2000.

36. Иоффе А. Д. Теория экстремальных задач / Иоффе А. Д., Тихомиров В. М. — М.: Наука, 1974.

37. Кларк Ф. Оптимизация и негладкий анализ / Кларк Ф. — М.: Наука, 1988.

38. Колмогоров А. Н. Элементы теории функций и функционального анализа / Колмогоров А. Н., Фомин С. В. — М.: Наука, Гл. ред. физ.-мат. лит., 1972.

39. Кривоногов А.И. О некоторых комитетпых конструкциях классификации / Кривоногов А.И. // в сб. Методы оптимизации и распознавания образов в задачах планирования. — Свердловск: УНЦ АН СССР. — 1980. — С. 92-98.

40. Кузнецова А. А. Об одном подходе к решению целочисленных задач оптимизации / Кузнецова А. А., Стрекаловский А. С., Цэвээндорж И. // Журнал вычислительной математики и математической физики. — 1999. — Т.39, JVfil. — С. 9-16.

41. Ландис Е. М. О функциях, представимых в виде разности двух выпуклых / Ландис Е. М. // Доклады Академии Наук СССР. 1951. - Т.80, № 1. - С. 9-11.

42. Мазуров Вл. Д. Об одном методе обучения машины интерпретации геофизических данных / Мазуров Вл. Д. // Применение математических методов в горнорудной и металургической промышленности. Свердловск: СОМИ АН СССР,- 1968. С. 3-8.

43. Мазуров Вл. Д. Распознование образов как средство автоматического выбора процедуры в вычислительных методах / Мазуров Вл. Д. // ЖВМ и МФ, — 1970. Т. 10, № 6. - С. 1520-1525.

44. Мазуров Вл. Д. Комитеты систем неравенств и задача распознавания / Мазуров Вл. Д. // Кибернетика, 1971. - № 2. - С. 140-146.

45. Мазуров Вл. Д. Дискриминантный анализ при математическом моделировании плохо формализуемых ситуаций / Мазуров Вл. Д. // Нелинейная оптимизация и приложения в планировании. Свердловск: УНЦ АН СССР, — 1973. — С. 26 35.

46. Мазуров Вл. Д. Методы математического программирования и распознования образов в планировании и производстве / Мазуров Вл. Д. // Свердловск: УНЦ АН СССР, 1977. - С. 3-27.

47. Мазуров Вл. Д. Несобственные задачи оптимизации и классификации в медицине и биологии / Мазуров Вл. Д. // Свердловск: УНЦ АН СССР, — 1983. — С. 39-40.

48. Мазуров Вл. Д. Метод комитетов в задачах оптимизации и классификации / Мазуров Вл. Д. — Москва: Наука, — 1990.

49. Мазуров Вл. Д. Комитетные конструкции / Мазуров Вл. Д., Хачай М. Ю. // Известия УрГУ. Математика и механика. — Вып. 2. 1999. №14. — С. 77-108.

50. Мазуров Вл. Д. Упорядочить хаос / Вл. Д. Мазуров, И. И. Еремин // Известия Уральского государственного университета. — 2001. — № 21. — С. 6-9.

51. Мазуров Вл. Д. Реализация диагностики и выбора вариантов в горногеологических задачах / Мазуров Вл.Д., Хачай М.Ю., Некрасов В.П. // Известия ВУЗ-ов. Горный журнал. — 2001. — №1. — С.10-15.

52. Мазуров Вл. Д. Комитетные конструкции как обобщение решений противоречивых задач исследования операций / Мазуров Вл.Д., Хачай М.Ю. // Дискретный анализ и исследование операций. — 2003. — Сер. 2, т.10, №2. — С.56-66.

53. Мазуров Вл. Д. Комитеты систем линейных неравенств / Мазуров Вл.Д., Хачай М.Ю. // Автоматика и телемеханика. — 2004. — №2. — С. 43-54.

54. Мину М. Математическое програмирование. Теория и алгоритмы / Мину М. Перевод с фр. и предисловие А.И.Штерна. — М.: Наука. Гл. ред. физ.-мат. лит., 1990.

55. Михалевич В. С. Оптимизационные задачи производственно-транспортного плпнирования: Модели, методы, алгоритмы / Михалевич В. С., Трубин В. А., Шор Н. 3. — М.: Наука. Гл. ред. физ.-мат. лит., 1986.

56. Нурминский Е. А. О непрерывности е-субградиентных отображений / Нурмин-ский Е. А. // Кибернетика №5, 1977. - С. 148-148.

57. Нурминский Е. А. Численные методы решения стохастических и детерминированных минимаксных задач / Нурминский Е. А. — Киев: Издательство: Нау-кова Думка, 1979.

58. Нурминский Е. А. Об одном классе методов выпуклого программирования / Нурминский Е. А. // Журнал вычислительной математики и математической физики. 1986. - Т.26, №8. - С. 1150-1159.

59. Нурминский Е. А. Численные методы выпуклой оптимизации / Нурминский Е. А. М.:Наука, 1991 - 168 с.

60. Нурминский Е. А. Экономико-математические модели и методы / Нурминский Е. А. — Владивосток: Издательство Дальневосточного университета, 1996.

61. Нурминский Е. А. Параллельный метод проекции на выпуклую оболочку семейства множеств / Нурминский Е. А. // Известия ВУЗов. Математика — №12 (499), 2003. С. 78-82.

62. НурминскиЙ Е. А. Метод последовательных проекций для решения задачи о наименьшем расстоянии для симплексов / Нурминский Е. А. // Электронный журнал "Исследовано в России" 160, 2004. — С. 1732-1739.

63. Орлов А. В. Поиск глобального решения в задаче выпуклой максимизации / Орлов А. В., Стрекаловский А. С. // Оптимизация. Управление. Интелект. — 2000. №5. - С. 306-315.

64. Орлов А- В. Поиск ситуаций равновесия в биматричных играх: Автореферат дис. канд. физ.-мат. наук. — Иркутск, 2004. — 22 с.

65. Плотников С. В. Методы проэктирования в задачах нелинейного программирования: дис. .канд. физ.-мат. наук / Плотников С. В. — Свердловск: УрГУ, 1983.

66. Поляк Б. Т. Метод сопряженных градиентов / Поляк Б. Т. // Труды II зимней школы по мат. программированию и смеж. вопр., —1969. — вып 1. — С. 152-201.

67. Поляк Б. Т. Введение в оптимизацию / Поляк Б. Т. — М.: Наука, Гл. ред. физ.-мат. лит., 1983.

68. Пшеничный Б. Н. Необходимые условия экстремума (Серия: Оптимизация и исследование операций) / Пшеничный Б. Н. — М.: Наука, Гл. ред. физ.-мат. лит., 1969.

69. Пшеничный Б. Н. Выпуклый анализ и экстремальные задачи / Пшеничный Б. Н. -- М.: Наука, Гл. ред. физ.-мат. лит., 1980.

70. Пшеничный Б. Н. Численные методы в экстремальных задачах / Пшеничный Б. Н., Данилин Ю. М. М. Наука, 1975.

71. Рудаков, К.В. О числе гиперплоскостей, разделяющих конечные множества в эвклидовом пространстве / К.В. Рудаков // Доклады АН СССР- 1976 Т.231, N6.- С. 1296-1299

72. Рудин У. Основы математического анализа / Рудин У. — М.: Мир, 1976.

73. Скарин В.Д. О методе регуляризации для противоречивых задач выпуклого программирования // Известия вузов. Математика. 1995, N 12, с.81-88.

74. Стрекаловский А. С. К проблемам глобального экстремума в невыпуклых задачах оптимизации / Стрекаловский А. С. // Известия вузов. Сер. Математика- 1990. № 8. - С. 74-80.

75. Стрекаловский А. С. О поиске глобального максимума выпуклого функционала на допустимом множестве / Стрекаловский А. С. // Журнал вычислительной математики и математической физики. — 1993. — Т.ЗЗ, №3. — С. 349-364.

76. Стрекаловский А. С. Условия глобальной оптимальности в задачах d.c. программирования / Стрекаловский А. С. // Иркутский государственный университет, серия: Оптимизация и управление. — Иркутск: Изд-во ИГУ, 1997. — Вып.1. — 64 с.

77. Стрекаловский А. С. Об экстремальных задачах с d.c. ограничениями / Стрекаловский А. С. // Журнал вычислительной математики и математической физики. 2001. - Т.41, №12. - С. 1833-1843.

78. Стрекаловский А. С. Теоретические основы выпуклой максимизации / Стрекаловский А. С. // Иркутский государственный университет, серия: Оптимизация и управление. — Иркутск: Изд-во ИГУ, 2001. — Вып.4. — 48 с.

79. Стрекаловский А. С. Минимизация разности двух выпуклых функций / Стрекаловский А. С. // Иркутский государственный университет, серия: Оптимизация и управление. — Иркутск: Изд-во ИГУ, 2002. — Вып.5. — 52 с.

80. Стрекаловский А. С. Об условиях глобальной оптимальности в задачах d.c. минимизации / Стрекаловский А. С. // Оптимизация. Управление. Интеллект.- 2002. № 6. - С. 193-209.

81. Стрекаловский А. С. О минимизации разности двух выпуклые функций на допустимом множестве / Стрекаловский А. С. // Журнал вычислительной математики и математической физики. — 2003. — Т.43, №3. — С. 399-409.

82. Стрекаловский А. С. Элементы невыпуклой оптимизации / Стрекаловский А. С. — Новосибирск: Наука, 2003. — 352 с.

83. Стрекаловский А. С. О сходимости алгоритма глобального поиска в задаче выпуклой максимизации на допустимом множестве / Стрекаловский А. С., Кузнецова А. А. // Известия высших учебных заведений. Математика. — 1999. — №12.

84. Стрекаловский А. С. О численном решении задач невыпуклой оптимизации / Стрекаловский А. С., Кузнецова А. А., Яковлева Т. В. // Сибирский журнал вычислительной математики. — 2001. — Т.4, №2. — С. 185-199.

85. Сухарев А. Г. Курс методов оптимизации / Сухарев А. Г., Тимохов Ф. И., Федоров В. В. — М.: Наука, Гл. ред. физ.-мат. лит., 1986.

86. Современное состояние теории исследования операций / Под редакцией Н. Н. Моисеева. — М.: Наука, Гл. ред. физ.-мат. лит., — 1979.

87. Ширяев О.В. Математизация оценки клинического течения гипертрофической кардиомиопатии на основе дискриминаптного анализа (метод комитетов): Ав-тореф. дис. . канд. мед. наук. — Челябинск, 2001. —18 с.

88. Шор Н. 3. Методы минимизации недифференцируемых функций и их приложения / Шор Н. 3. — Киев: Наукова думка — 1979.

89. Шор Н. 3. Использование операций растяжения пространства в задачах минимизации выпуклых функций / Шор Н. 3. // Кибернетика. — 1970. — №1. — С. 6-12.

90. Шор Н. 3. О скорости сходимости обобщенного градиентного спуска с растяжением пространства / Шор Н. 3. // Кибернетика. — 1970. — №2. — С. 80-85.

91. Шор Н. 3. Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов / Шор Н. 3., Журбенко Н. Г. // Кибернетика. 1971. - №3. - С. 51-59.

92. Шор Н. 3. Монотонные модификации r-алгоритмов и их приложения / Шор Н. 3. // Кибернетика и систем, анализ. — 2002. — N6. — С. 74-95. '

93. Хачай М.Ю. Об оценке числа членов минимального комитета системы линейных неравенств // Журнал вычислительной математики и мат. физики. 1997. т.37, N11.С.1399-1404

94. Экланд И. Выпуклый анализ и вариационные проблемы / И. Экданд, Р. Темам- М.: Мир 1979.

95. Яковлева Т.В. Поиск глобального решения в задачах обратно-выпуклого программирования: Автореферат дис. канд. физ.-мат. наук. — Иркутск, 2003. —22 с.

96. Astorino A. Polyhedral separability thought successive LP / Astorino A. // Доклад на международном симпозиуме Nonlinear Optimization and Appalachians, Erice,23 June-2 July 1998.

97. Benchekroun B. A nonconvex piecewise linear optimization problem / Benchekroun B. // Computers Math. Applic., 1991. V. 21, 6/7. - P. 77-85.

98. Bennett K. P. Bilinear Separation of Two Sets in n-Space / K. P. Bennett, O. L. Mangasarian // Computational Optimization and Applications — 1993. — №2. — P. 207-227.

99. DeSilets L. Prdictihg salinity in the Chesapeake Bay using bacpropagation / L. DeSilets, B. Golden, Q. Wang and R. Kumar j j Computer and Operations Research.- 1992. No. 19. - P. 277-285.

100. Dinur I. The hardness of 3-uniform hypergraph coloring / Dinur I., Regev O. and Smyth C. // In Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science, November 2002,

101. Handbook of global optimization / Ed. by Horst. R., Pardalos P. — Dordrecht: Kluwer Academic Publishers, 1995.

102. Hartman P. On Functions Representable as a Difference of Convex functions / Hartman P. // Pacific Journal of Mathematics. 1959. - V.9 - P. 707-713.

103. Hertz J. Introduction to the theory of neural computation / J. Hertz, A. Krogh and R. G. Palmer. — Addison-Wesley, Redwood City, California, 1991.

104. Hiriart-Urruty J. B. Conditions for Global Optimality // Handbook of Global Optimization / Ed. by Horst R., Pardalos P. — Dordecht: Kluwer Academic Publishers, 1995. P. 1-26.

105. Hiriart-Urruty J. B. Convex Analysis and Minimization Algorithms / Hiriart-Urruty J.B., Lemarshal C. Berlin: Springer Verlag, 1993. - P. 1-2.

106. Horst R. Global Optimization. Deterministic Approaches / Horst R., Tuy H. — Berlin: Springer-Verlag, 1993. — 698 p.

107. Horst R." Introduction to global optimization / Horst R., Pardalos P., Thoai N. V. — Dordrecht-Boston-London: Kluwer Academic Publishers, 1995. — V.3. — 246 p.

108. Horst R. D.C. Programming: Overview / Horst R., Thoai N. V. // Journal of Optimization Theory and Applications. — 1999. V.103, №1. - P. 1-43.

109. Gorokhovik V. V. Piecewise affine functions and polyhedral sets / Gorokhovik V. V., Zorko О. I. // Optimization, 1994. V. 33. - P. 209 221.

110. Kam T-. Building Projectable Classifiers of Arbitrary Complexity / Tin Kam Ho and Eugene M. Kleinberg // Proceedings of the 13th International Conference on Pattern Recognition, August 25-30, 1996 — Vienna, Austria — P. 880-885.

111. Kripfganz A.Piecewise affine functions as a difference of two convex functions / Kripfganz A., Schulze R. // Optimization, 1987. — V. 18, 1. P. 23-29.

112. Kuznetsova A. A. On solving the maximum clique problem / Kuznetsova A. A., Strekalovsky A. S. // Journal of Global Optimization. — 2001. — V.21, №3. P. 265-288.

113. Lemarechal C. Sur la differentiabilite de la fonction d'appui du sousdifferentiel approche / Lemarechal C., Nurminski E.A. // Compt. Rend. Acad. Sci. Ser. A., 290, 1980. P. 855-858.

114. Mangasarian O. L. Mathematical Programming in Neural Networks / O. L. Mangasarian // Journal on Computing. — 1993. — No. 5. — P. 349-360.

115. Mangasarian O. L. Misclassification Minimization / O. L. Mangasarian // Journal of Global Optimization. 1994. - No. 5(4). - P. 309-323.

116. Mangasarian O. L. Breast Cancer Diagnosis and Prognosis via Linear Programming * / O. L. Mangasarian, W. Nick Street, W. H. Wolberg // Operations Research. —1995. № 43.- P. 570-577.V

117. Mangasarian O. L. Linear and Nonlinear Separation of Patterns by Linear Programming / O. L. Mangasarian // Operations Research. — 1965. — № 13. — P. 444-452.

118. Mazurov VI. D. Duality in pattern recognition and operation research / Mazurov VI. D. // Pattern Recognition and Image Research. — 1991. — V. 8, N 4. — P. 376-384.

119. Mazurov VI. D. Recognition and choice in a multistage of modeling complex systems / Mazurov VI. D. // Pattern Recognition and Image Research. — 1994. — V. 4, N 2. P. '87-92.

120. Mazurov VI. D. Generalized existence in nonequilibrium models of choice in modeling complex systems / Mazurov VI. D. // Pattern Recognition and Image Research. 1995. - V. 5, N 1. - P. 7-12.

121. Meltzer D. On the expressibility of piecewise linear continuous functions as the difference of two piecewise linear convex functions / Meltzer D. // Math. Program., Study 29, 1986. P. 118-134.

122. Nurminski E. A. Toward Newton method in nondifferentiable optimization / Nurminski E. A. // J. of Math res. and Expos., 1992. - № 12(2). - P. 159163.

123. Nurminski E. A. Superlinear convergence in convex nondifferentiable optimization / Nurminski E. A. // Advances in Optimization (Lambrecht,1991). Lecture Notis in Economics and Mathematical Systems, 382, Springer, Berlin, 1992. — P. 267-277.

124. Nurminski E. A. Separating plane algorithms for convex optimization / Nurminski E. A. // Mathematical Programming. 1997. - № 76. - P. 373-391.

125. Pardalos P. M. Constrained Global Optimization: Algorithms and Applications / Pardalos P. M., Rosen J.B. // Lecture Notes in Computer Science, 1987. — Berlin: Springer Verlag. — V. 268.

126. Penot J.-P. Approximation and decomposition properties of some classes of locally d.c. functions / Penot J.-P., Bougeard M. L. // Mathematical Programming. — 1988. V.41. - P. 195-227.

127. Shavlik J. W. Symbolic and neural network learning algorithms: An experimental comparison // J. W. Shavlik, R. J. Mooney and G. G. Towell // Machine Learning. 1984. - No. 6. - P. 111-143.

128. Simpson P.K. Artifical neural systems / P.K. Simpson. — Pergamon Press, New York, 1990.

129. Strekalovsky A. S. Global Optimality Conditions for Nonconvex Optimization / Strekalovsky A. S. // Journal of global optimization. 1998. - №12. - P.415 434.

130. Strekalovsky A. S. On d.c. Minimization Problems / Strekalovsky A. S. // Оптимизация. Управление. Интеллект. — 2000. — №5. С. 392-402.

131. Strekalovsky A. S. Testing the 5R-strategy for a Reverse Convex Problem / Strekalovsky A. S., Tsevendorj I. // Journal of global optimization. — 1998. — V.13. P.61-74.

132. Thach P. T. D.C. sets, d.c. functions and nonlinear equations / Thach P. T. // Mathematical Programming. 1993. - V.58. - P. 415-428.

133. Tuy H. D. C. Optimization: Theory, Methods and Algorithms / Tuy H. D. // Handbook of Global Optimization / Ed. by Horst. R., Pardalos P. — Dordrecht: Kluwer Academic Publishers, 1995. P. 149-216.

134. WDBC — Режим доступа: ftp://ftp.cs.wisc.edu/math-prog/cpo-dataset/machine-learn/Cancer/WDBC.

135. WPBC .— Режим доступа: ftp://ftp.cs.wisc.edu/math-prog/cpo-dataset/machine-learn/Cancer/WPBC.

136. Checker — Режим доступа: ftp://ftp.cs.wisc.edu/math-prog/cpo-dataset/machine-learn/checker.