автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Вариационный подход к проблеме обобщенной отделимости

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

Дружинина Оксана Владимировна

Вариационный подход к проблеме обобщенной отделимости

05.13.01 - Системный анализ, управление и обработка информации (в технике, экологии и экономике)

Автореферат

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

ИРКУТСК 2005

Работа выполнена в Институте динамики систем и теории управления (ИДСТУ) СО РАН

Научный руководитель: доктор физико-математических наук,

профессор Стрекаловский Александр Сергеевич.

Официальные оппоненты: доктор физико-математических наук,

профессор Нурминский Евгений Алексеевич; доктор физико-математических наук, с.н.с. Батурин Владимир Александрович;

Ведущая организация: Институт математики и механики

УрО РАН.

Защита состоится 27 декабря 2005 г. в 10.30 час. на заседании диссертационного совета Д 003.021.01 в ИДСТУ СО РАН по адресу: 664033, Иркутск, ул. Лермонтова, 134, зал заседаний Ученого Совета, ком. 407. С диссертацией можно ознакомиться в библиотеке ИДСТУ СО РАН. Автореферат разослан 25 ноября 2005 года.

Ученый секретарь диссертационного совета, д.т.н.

Опарин Г.А.

2 Ш2

ЗьЫ

Общая характеристика работы

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

Наибольший практический интерес представляет задача отделения множеств, выпуклые оболочки которых имеют непустое пересечение. Для отделения таких множеств требуются более общие, чем линейная отделимость, понятия отделимости множеств. В качестве примеров определений обобщенной отделимости множеств можно привести отделимость множеств к-функцией (И.И. Еремин, С.В. Плотников) и отделимость множеств комитетом большинства (Вл.Д. Мазуров, М.Ю. Хачай), разрабатываемые в ИММ УрО РАН (г. Екатеринбург).

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

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

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

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

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

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

Для этого необходимы:

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

2. Новые методы исследования глобальной и локальной сходимости, а также сравнительной эффективности построенных алгоритмов.

3. Новая технология программирования, в полной мере исиользую-

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

Цель работы. Целью диссертационной работы является создание алгоритмов глобального и локального поиска для задач негладкой с1.с. минимизации, обоснование всех этапов глобального поиска для задачи о полиэдральной отделимости конечных множеств из Мп, а также их численная верификация на тестовых и практических примерах.

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

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

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

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

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

• Разработано программное обеспечение для решения задач неглад-

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

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

Апробация работы. Основные результаты диссертации опубликованы в работах [1]-[18]. В виде докладов они представлялись на следующих конференциях:

• "Ляпуновские чтения и презентация информационных технологий" в ИДСТУ СО РАН (Иркутск, 2002-2004);

• ежегодной Школе-семинаре молодых ученых "Математическое моделирование и информационные технологии"(Иркутск, Ангасолка,

Зеленый мь:е. 2002 2005).

• Второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в ВУЗе (Иркутск, 2003);

• Всероссийской научной молодежной конференции "Под знаком Сигма" (Омск, 2003);

• Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2003);

• Всероссийской конференции "Инфокоммуникационные и вычислительные технологии и системы "(Улан-Удэ-Байкал, 2003);

• III Всероссийской конференции "Математика, информатика, управ-ление"(Иркутск, 2004);

• XIII Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск-Северобайкальск, 2005);

• IV Всероссийской конференции "Математика, информатика, управление" (Иркутск, 2005).

Результаты работы обсуждались на семинарах лаборатории методов глобальной оптимизации и объединенном семинаре ИДСТУ СО РАН.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, четырех приложений и списка литературы из 153 наименований. Общий объем работы — 155 страниц.

Содержание работы

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

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

F{х) = д(х) - f(x) | min, х € D, (Р)

где д(-) и /(•) — выпуклые, не обязательно дифференцируемые функции; D С Мп — выпуклое множество.

В разделе 1.1 представлен следующий негладкий вариант специального метода локального поиска.

Пусть задано некоторое начальное приближение х° 6 D. Далее, если известны допустимая точка ха 6 D и некоторый субградиент х* € df{xa) функции /(•) в точке ж®, то следующую итерацию 6 D будем искать как приближенное решение линеаризованной в точке х3 задачи:

д(х) - {х*,х) I min, х € D, ж* G df{xa). (PLS)

Более точно, это означает, что точка xs+1 € D удовлетворяет неравенству

д(х°+1) - (»;, xs+1> < mf{g(x) - (х*„ ж)} + 6„ (1)

xüD

где последовательность 53 такова, что

00

6в > 0, s — 1,2,...; 6а < оо.

з=0

Теорема 1.1.1. Пусть в задаче (Р) целевая функция F(-) ограничена снизу на допустимом множестве D и в любой допустимой точке х можно найти некоторый субградиент х* € Э/(х).

i) Тогда последовательность {эг}, генерируемая но правилу (1). удовлетворяет условию

lim{inf [д(х) - g(xs+1) - {x*s, х - х3+1)]} = 0. (2)

з-Юо

ii) При этом, если последовательности {ж®} и {х*} сходятся согласованным образом, т.е.

Xs ->z, Х*в-+2* е df(z), X* е df(x°), (3)

то предельная точка z последовательности {х3} удовлетворяет условию

Ы{д(х) - д(г) - (z*, х - z)} = 0, z* € df(z). (4)

xQD

Из доказательства теоремы сходимости следует, в частности, что в качестве критерия останова метода можно использовать одно из следующих неравенств:

F{xs) - F(xs+1) < г, д{х°) - g(x3+1) + <х*, xs+1 - ха) < г, где г - заданная точность; х* G df(x3). В этом случае точка х3 является т-критической в задаче (Р), т.е является т-решением линеаризованной в этой же точке задачи (PLS).

Далее, в разделе 1.2, приведены необходимые и достаточные условия глобальной оптимальности в недифференцируемой задаче d.c. минимизации (Р), полученные A.C. Стрекаловским.

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

Пусть заданы начальная точка Xq Е D и числовые последовательности {т*} и {¿¿J, где тк, 5к > 0, к = 0,1,2,..., тк 4- 0, 6к J. О (к -> оо).

Шаг 0. Положить к := 0, хк := хд-

Шаг 1. Начиная с хк е D посредством некоторого метода локального поиска построить т*-критическую точку zk:

Ск = F(zk) < F(xk).

Шаг 2. Выбрать некоторое ¡3 6 [/3_,/3+]. В частности, процесс одномерного поиска по /3 можно начинать при Д) = g(zk).

Шаг 3. Построить некоторую аппроксимацию

Ак(Р) = {г;1,..., f(v<) = /3 - Ct, i = 1, • • •, Nk, Nk = Nk{/3)}. Шаг 4. Сформировать семейство индексов

Шаг 5. Для каждого i € Ik найти глобальное ¿¿-решение ul G D линеаризованной задачи:

д(и{) - (vf,и<) -5к< inf{д(х) - х>| z € D}, (5)

X

где vf е df(v').

Шаг 6. Для каждого г € найти глобальное ¿¿-решение го* (/(ги1) = ¡3 — С':)г задачи уровня:

К, и* - и?) + 6к> вир{(г)*, и*-у) | /(о) = /3 - й}, (6) где го* € д/(и)г), и* € 9/(и). Шаг 7. Положить %(/3) := ?$(/3) + /3, где

7?°(/3) := (ад), и* - - = тах{(ш*, «« - «,'") - д(и*)}, (7) а го* 6 9/(го*).

Шаг 8. Если ^(/З) > 0, то положить ж6"1"1 := и7 и вернуться на Шаг 1.

Шаг 9. Если щ(Р) < 0, то положить /3 /3 -Ь Д/3 € [/?_,/3+] и идти на Шаг 3. Число Д/3 может быть найдено одним из известных методов одномерной максимизации.

Шаг 10. Если щ(Р) < О У/3 6 [/3_,/3+] (т.е. одномерный поиск по /3 завершен), то положить к := к + 1, := гк и вернутся на Шаг 1.

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

Далее, в разделе 1.5, доказывается теорема сходимости алгоритма глобального поиска в негладком случае.

Теорема 1.5.1. Пусть в задаче (Р) целевая функция Р(-) ограничена снизу на О и в любой точке х £ И можно найти субградиент х* £ д/(х).

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

Тогда последовательность {zk}, генерируемая алгоритмом глобального поиска, является минимизирующей в задаче (Р), т.е.

lim F{zk) = inf(F, D).

fc-4 00

При этом всякая предельная точка 2 последовательности {zk} доставляет точную нижнюю грань функции F на D, а в случае замкнутости D является решением задачи (Р).

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

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

Яр = ЯрК, £р) = {хе JRnI К, х) = и? <= ШГ, ер е 2R}, р = 1,..., Р.

Определение 2.1.1. Множества А vi В полиэдрально отделимы семейством гиперплоскостей {Яр}, если для каждой точки а', i = 1,..., М, из множества Л и каждой гиперплоскости из {Яр}, р = 1,..., Р, выполняется неравенство

(a'V) <£Р,

и для каждой точки V, j = 1,..., N, из множества В и хотя бы одной

из гиперплоскостей {Яр} (Эр 6 {1,..., Р}) справедливо неравенство

Нетрудно видеть, что множества Л к В входят в это определение несимметрично.

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

р(у,г) = р1(у,г) + адг), (8)

где

1 м

ВД'Г) = ш ^ тах{0, тах((а'", V") - Ъ + 1)}, 1=1

1 м

ВДГ) = -^т^тт (-<&>» +7р+ 1)}. ¿=1

(9)

В разделе 2.2 диссертации найдено явное представление этой функции в виде разности двух негладких выпуклых функций:

где д(-) и /(•) — выпуклые функции, имеющие следующий вид: 1 М

д(У,Г) = — тах{0, тах ((а<,у") -Ъ+ 1)}+ 1=1 ~

1 "

+ Л? X! тах{°; тахр((6^г)р} - 7Р - 1)};

N ^ 1 1<р<Р

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

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

Раздел 2.4 посвящен построению аппроксимации поверхности уровня

f(V*,r)=ß-t. (10)

Задача построения аппроксимации разбивается на два этапа. Первый этап состоит в построении некоторого множества направлений

Dir = {{U\Tl).....([/S,TS)}, {Us,Ta) е lRp<n+1>, s = l(11)

На втором этапе строится множество состоящее из векторов (Vs, Г3), построенных на основе Dir и лежащих на требуемой поверхности уровня (10).

Несколько вариантов реализации первого этапа построения аппроксимации поверхности уровня — построение наборов направлений Dir — рассмотрено в пункте 2.4.4.

В разделе 2.4.1 векторы (К, Г) € 71 строятся на основе (£/, Т) 6 Dir по правилу

(V, Г) = А(С/,Г), (12)

где (С/,Т) = {(u1,ii),...,(up,iP)} 6 € Dir. Соотношение (12)

означает покомпонентное равенство:

vP = \ир, 7р = Atp, vP, v" Е Ш", tp, ъ 6 R, p = 1,..., P. (12')

Найдено явное аналитическое представление множителя А.

В следующем разделе 2.4.2 найден множитель А для построения (У, Г) е TZ в виде, отличном от (12'):

vp = \up, 7Р = Aip + А — 1. (13)

Здесь вновь (U,T) = {{u\ti),... ,{up,tP)} € Dir.

Далее, в пункте 2.4.3, предложен еще один прием построения аппроксимации поверхности уровня, где, в отличие от двух предыдущих, отсутствует промежуточный этап — построение множества направлений Dir. Здесь представлено два варианта построения аппроксимации поверхности уровня, каждый из которых строился как некоторое решение уравнения /(У, Г) = /3 -

В целом в разделе 2.4 построено 10 аппроксимаций поверхности уровня, обозначенных через 7^.1-72.10.

В заключение второй главы, в разделе 2.5, найден интервал изменения параметра /3 .

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

Раздел 3.1 посвящен тестированию алгоритма локального поиска, предложенного в первой главе, на задачах о полиэдральной отделимости.

В разделе 3.2 представлен алгоритм глобального поиска для задачи о полиэдральной отделимости. Этот алгоритм является развитием стратегии глобального поиска из главы 1 и разработан с учетом специфики рассматриваемой задачи (гл.2). В частности, на шагах 3 и 7 введен дополнительный критерий останова (когда значение функции ошибки близко к нулю). Пусть заданы начальное приближение (Vo, Го) и числовая по-

15

следовательность {т/;}, т/: > 0, т/-_ 4- 0(/: се).

Алгоритм глобального поиска.

Шаг 0. Положить к := 0, г := 0, {Vk, Г,:) := (Vq, Г0), тк := т0. Вычислить ß+.

Шаг 1. Выбрать ДД е {ДД,..., ДД}.

Шаг 2. Начиная с (Vk, Г*) 6 МР1-п+1"> методом локального поиска построить ^-критическую точку (Wk,Ak): Ск := F(Wk,Ak) < F{Vk,Tk). Шаг 3. Если F(Wk, Ак) < Хи то stop, {Wh\ Ак) 6 Sol(P) . Шаг 4. Выбрать ß 6 [0,/3+]. Шаг 5. Построить аппроксимацию

Ak(ß) = {(У1, Г1),..., (V*M*)| f(V, п = ß - Cfc, в = 1,..., sk}.

Шаг 6. Для всякого 5 6 {1,..., S*} методом локального поиска построить Тк-критическую точку (U3, Т3).

Шаг 7. Если нашелся номер s € {1,..., Sk} такой, что F(U3, Т3) < хи Tostop, (U\Ta) е Sol(P) .

Шаг 8. Если для некоторого s € {1,..., Sk} имеем F(Ua,Ta) < Cfc, то положить к := к + 1, (V*+1,rfc+1) := (¡7s, Т3), тм = тк/2, и идти на Шаг 2.

Шаг 9. Если F{Ua,Ta) > Cfc Vs € {l,...,5fc}, то положить /3 := ^ + ДД- е [0,/?+], Шаг 5.

Шаг 10. Если F(Ua, Т3) > Cfc Vs € {1,..., Sk} V/3 e [0, ß+] итк< хз, то положить г := i + 1, ДД := ДД+i и вернуться на Шаг 2. Шаг 11. Если i = I, то stop.

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

Численный эксперимент но тестированию различных аппроксимаций поверхности уровня был проведен в два этапа. На первом этапе (раздел 3.3) были протестированы аппроксимации 721-7210, построенные во второй главе. Некоторые результаты этого этапа эксперимента представлены в таблице 3.4.3, где 72 — название исследуемой аппроксимации; 5 — количество элементов в данной аппроксимации; Бо1% — процент примеров, в которых найдено глобальное решение; Атах — максимальное отклонение полученного решения от оптимального по всей серии примеров; РЬтах — максимальное число решенных линеаризованных задач; Ытетах — максимальное время работы алгоритма.

Таблица 3.4.3.

те 5 5о/% Р^тах Ытетах

их п 68% 2.0 13127 0 : 01 : 18.94

И2 п 66% 2.0 18005 0 :01: 30.79

723 N 82% 2.0 36743 0 : 03 : 34.53

т М 88% 1.901 43576 0 : 22 : 30.86

М*Ы 82% 2.0 328235 1 : 03 : 43.57

т 1 46% 1.966 41627 0 : 08 : 38.18

т п 74% 1.98 6490 0 : 03 : 11.12

ш п 64% 2.086 12749 0 :06 : 54.16

п 74% 2.0 9466 0 : 03 : 11.02

то 1 90% 1.97 3701 0 : 01 : 29.17

пи Л/ + 2 94% 0.469 47018 0 : 24 : 05.46

1112 М + 2 92% 0.491 78022 0 : 31 : 28.14

По итогам данного численного эксперимента лучше всего показали себя аппроксимации 7210, 724 и 723, 725. Причем, при одинаковом проценте решенных примеров, аппроксимация 725 работает значительно дольше, чем аппроксимация 723.

Далее, в разделе 3.4, на основе компиляции наиболее удачны:-: аппроксимаций первого этапа были построены еще 2 аппроксимации 72.11 и 72-12, которые являются объединением аппроксимаций 723, 724, 72.10 и отличаются порядком вхождения элементов этих аппроксимаций:

7211 = {724 U 723 U 7210}; 72.12 = {7il0 U 724 U 723}.

Процент решенных примеров при применении аппроксимаций 7211 и 7212 выше, чем при применении любой из протестированных в течение первого численного эксперимента аппроксимаций. Однако аппроксимация 7212 проигрывает аппроксимации 7211 по всем параметрам.

Наиболее привлекательной для задачи о полиэдральной отделимости, оказалась аппроксимация 7210, т.к. она незначительно проигрывает наиболее сильным аппроксимациям 7211 и 7212 в проценте решенных примеров, но при этом весьма выигрывает по количеству решенных в процессе линеаризованных задач, и, как следствие, по времени работы алгоритма.

Далее, в разделе 3.5, представлены результаты тестирования алгоритма глобального поиска с дополнительным внешним циклом по параметру Р — количеству отделяющих гиперплоскостей.

В заключительном разделе (раздел 3.6) диссертации представлены результаты работы алгоритма на известной тестовой задаче (checker).

В приложении А подробно рассмотрен и протестирован известный метод выпуклой недифференцируемой оптимизации, называемый г-ал-горитмом Н.З. Шора.

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

В приложении D.1 представлена графическая интерпретация данных из таблицы 3.4.3 (характеристики аппроксимаций поверхности уровня TZWH10).

Приложение D.2 содержит изображение исходных данных для задачи checker, рассмотренной в разделе 3.6.

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

Результаты работы, выносимые на защиту

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

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

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

Публикации по теме диссертации

1. Дружинина О.В. Задача полиэдральной отделимости как задача d.c. минимизации / Дружинина О.В., Стрскаловский A.C. // Материалы российской конференции "Дискретный анализ и исследование операций", Новосибирск, 24 28 июня 2002 г. — Новосибирск: Изд-во Института математики, 2002. — С. 194.

2. Дружинина О.В. Задача полиэдральной отделимости как задача d.c. минимизации / Дружинина О.В., Стрскаловский A.C. // Тезисы докладов II школы-семинара молодых ученых "Математическое моделирование и информационные технологии", 25-29 сентября 2002 г., Иркутск-Ангасолка. - Иркутск, 2002. — С. 25-26.

3. Дружинина О.В. Задача полиэдральной отделимости как задача d.c. минимизации / Дружинина О.В., Стрекаловский A.C. // Тезисы докладов конференции "Ляпуновские чтения и презентация информационных технологий", 25-27 ноября 2002 г. — Иркутск, 2002. — С. 29.

4. Дружинина О.В. Задача полиэдральной отделимости как задача d.c. минимизации / Дружинина О.В., Стрекаловский A.C. // Тезисы докладов всероссийской конференции "Математическое программирование и приложения". Информационный бюллетень Ассоциации математического программирования №10, Екатеринбург, 24-28 февраля 2003 г. - Екатеринбург, 2003. - С. 196.

5. Дружинина О. В. Задача полиэдральной отделимости как задача d.c. минимизации / Дружинина О.В. // Труды второй Восточно-

Сибирской зональной межвузовской конференции но математике и проблемам ее преподавания в ВУЗе, 11-13 марта 2003 г. — Иркутск: Изд-во ИГПУ, 2003. - С. 194-197.

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

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

8. Дружинина О.В. К задаче отделения линейно неотделимых множеств / Дружинина О.В. // Материалы всероссийской конференции "Инфокоммуникационные и вычислительные технологии и системы". Улан-Удэ-Байкал, 5-9 августа 2003 г. часть II. — Улан-Удэ: Изд-во БГУ, 2003. - С. 55-58.

9. Дружинина О.В. О задачи отделимости линейно неотделимых множеств / Дружинина О.В. // Тезисы докладов III школы-семинара молодых ученых "Математическое моделирование и информационные технологии", 23-28 сентября 2003 г., Иркутск-Ангасолка — Иркутск, 2003. - С. 20-21.

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

11. Дружинина О.В. Локальный иоиск в задаче полиэдральной отделимости / Дружинина О.В. // Тезисы докладов всероссийской конференции "Алгоритмический анализ неустойчивых задач". Екатеринбург. 2 6 февраля 2004 г. Екатеринбург: Изд-во Уральского университета, 2004. С. 289 290.

12. Дружинина О.В. Сходимость метода глобального поиска в задаче безусловной негладкой d.c. минимизации / Дружинина О.В. // Тезисы докладов IV школы-семинара молодых ученых "Математическое моделирование и информационные технологии", 14-20 марта 2004 г., Иркутск-Ангасолка. - Иркутск, 2004. - С. 18.

13. Дружинина О.В. О негладких и невыпуклых задачах классификации / Дружинина О.В. // Тезисы докладов V школы-семинара молодых ученых "Математическое моделирование и информационные технологии", 23-31 октября 2004 г., Иркутск-Ангасолка. — Иркутск, 2004. - С. 14.

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

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

16. Дружинина О.В. К решению одной задачи негладкой невыпуклой оптимизации / Дружинина О.В. // Тезисы докладов VI школы-

семинара молодых учены:-: "Математическое моделирование и информационные технологии", 2-8 апреля 2005 г., Иркутск-Ангасолка. - Иркутск, 2005. - С. 17.

17. Дружинина О-В. О глобальном поиске в задаче полиэдральной отделимости / Дружинина О.В. // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения", 2-8 июля 2005 г., Иркутск-Северобайкальск. — Иркутск, 2005. — С. 301-307.

18. Дружинина О.В. Минимизация числа отделяющих гиперплоскостей в задаче о полиэдральной отделимости / Дружинина О.В. // Тезисы докладов VII школы-семинара молодых ученых "Математическое моделирование и информационные технологии", 30 сентября -6 октября 2005 г., Иркутск-Зеленый Мыс. — Иркутск, 2005. — С. 13-14.

Редакционно-издательский отдел Института динамики систем и теории управления СО РАН 664033, Иркутск, ул. Лермонтова, 134 Подписано к печати 22.11.05.

Формат бумаги 60 х 84 1/16 объем 1 п.л.

_Заказ 9. Тираж 100 экз._

Отпечатано в ИДСТУ СО РАН

/1А /О „О /<7

/>? Ух —/у^ ^

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

200Т4 9681

Введение

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. разложения.

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

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

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

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.