Содержание к диссертации
Введение
1 Элементы негладкой d.c. минимизации 15
1.1 Локальный поиск 16
1.2 Условия глобальной оптимальности 19
1.3 Минимизирующие последовательности 23
1.4 Стратегия глобального поиска 24
1.5 Сходимость стратегии глобального поиска 28
1.6 О разрешающих наборах 32
1.7 Заключительные замечания 38
2 Задача о полиэдральной отделимости 39
2.1 Постановка задачи о полиэдральной отделимости 39
2.2 D.C. представление функции ошибки 45
2.3 Нахождение субдифференциалов функции ошибки .' 47
2.4 Построение аппроксимации поверхности уровня 50
2.4.1 Первый прием построения аппроксимации поверхности уровня функции /() 52
2.4.2 Второй прием 54
2.4.3 Третий прием 55
2.4.4 Построение наборов направлений Dir 57
2.5 Вычислепие интервала одномерного поиска параметра /3 61
2.6 Заключительные замечания 63
3 Численное решение задачи о полиэдральной отделимости 64
3.1 Локальный поиск в задаче о полиэдральной отделимости 65
3.1.1 Первый этап тестирования локального поиска 66
3.1.2 Тестирование алгоритма локального поиска на задачах о полиэдральной отделимости большой размерности 70
3.2 Алгоритм глобального поиска и особенности численного эксперимента . 73
3.3 Первый этап численного эксперимента 76
3.4 Второй этап численного эксперимента 91
3.5 Минимизация количества отделяющих гиперплоскостей 96
3.6 Решение тестовой задачи с множествами большой мощности 100
3.7 Заключительные замечания 102
Заключение 103
- Локальный поиск
- Условия глобальной оптимальности
- Постановка задачи о полиэдральной отделимости
- Локальный поиск в задаче о полиэдральной отделимости
Введение к работе
При решении практических задач во многих областях человеческой деятельности может возникать потребность во введении процедуры отделения множеств, Приме а рами таких задач могут быть, например, распознавание текста, распознавание речи, идентификация личности, обучение машин; экономические задачи, такие как зада . ча определения кредитоспособности клиента банка, задачи управления портфелем цепных бумаг, задача определения жизнеспособных и склонных к банкротству фирм [58,100,112,116,143, 144]; медицинские задачи (диагностика и прогнозирование)[129, 130, 151, 152] ; горно-геологические задачи [62].
Целью данной процедуры является отнесение имеющихся статистических образцов (характеристики ситуации па рынке, данные медосмотра, информация о клиенте) к определенным классам.
Наиболее распространенным способом представления данных является представление объекта в виде вектора х — (xi,... , х„) € Жп, где і-я координата вектора х определяет значения г-й характеристики, влияющей на принятие решения о том, к какому классу можно отнести данный образец.
Набор заранее расклассифицированных объектов, использующийся для обнаружения закономерных связей между значениями характеристик и классом объекта, составляет обучающую выборку. Одна из основных задач классификации состоит в построении (в том числе на ос , новации данных, предоставляемых обучающей выборкой) некоторого правила (дис криминантной, решающей функции, классификатора), в соответствии с которым по значению характеристик образца х устанавливается его принадлежность к одному из классов. Дадим математическое описание задачи классификации. •
Наибольший интерес представляет задача отделения множеств, выпуклые оболочки которых имеют непустое пересечение. Для отделения таких множеств требуются более общие, чем линейная отделимость, понятия отделимости множеств. В качестве примеров определений обобщенной отделимости множеств можно привести отделимость множеств k-функцией (И.И. Еремин, СВ. Плотников [37, 77]) и отделимость множеств комитетом большинства (Вл.Д. Мазуров, М.Ю. Хачай [36], [37], [53]-[60], [77], [83J, [106], [134Н136]), разрабатываемые в ИММ УрО РАН (г. Екатеринбург). Еще одним вариантом обобщенной отделимости является полиэдральная отделимость в смысле определения Мангасарьяна [109], иначе называемая отделимостью множеств комитетом единогласия [60].
Настоящая диссертация посвящена исследованию именно такого понятия отделимости множеств, которое в дальнейшем будем называть просто полиэдральной отделимостью. При этом рассматривается вариационный подход к решению задачи классификации, основанный на том, что построение отделяющей функции в задаче о полиэдральной отделимости можно свести (глава 2) к поиску безусловного глобального минимума некоторой негладкой невыпуклой функции, являющейся d.c. функцией, т.е. представимой в виде разности двух выпуклых функций.
К сожалению, для певьшуклых задач оптимизации, несмотря на широкие и разнообразные исследования математиков, многие вопросы, связанные с теорией и методами поиска глобального экстремума, остаются открытыми. Более того, по-видимому, нельзя говорить о том, что уже созданы алгоритмы глобального поиска, применимые для широких классов невыпукльгх задач оптимизации.
Достаточно сложно привести полную классификацию задач невыпуклой или, как еще принято говорить, глобальной оптимизации. Тем не менее, в литературе [121, 122) принято рассматривать следующие четыре класса задач.
Нетрудно видеть, что при д(х) = О задача d.c. минимизации (5) обращается в задачу выпуклой максимизации (3), так что последняя является частным случаем (5).
1 Аналогично задача с d.c. ограничениями (6) при f(x) = О обращается в задачу (4)
на дополнении выпуклого множества, которая, таким образом, оказывается частным случаем (б). Итак, можно сказать, что простейшие задачи 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) внешней и внутренней аппроксимации [б, 150.
Идеи этих методов довольно прозрачны и использовались неоднократно в различных областях естествознания. Можно сказать, что данные подходы заимствованы из дискретной математики, хотя несомненно учитывают непрерывную структуру задач и свойства d.c. функций, но недостаточно, по нашему мнению, используют новейшие результаты теории экстремума.
Кроме того, другими математиками были получены условия глобальной оптимальности для некоторых более частных задач d.c. минимизации (см. обзор [118]). Другой подход к решению подобных задач был развит в работах А.С. Стрекаловско-го. На основе предложенных условий глобальной оптимальности для четырех приведенных выше классов задач [86], [88], [90]-[93], [95], им и его учениками были разработаны стратегии глобального поиска для решения многих актуальных теоретических и прикладных задач оптимизации [51], (87], [94], [96]. [97]. Особо следует отметить работы А.А. Кузнецовой по решению NP-трудной задачи дискретной оптимизации— поиск максимальной клики в неориентированном графе [127], Т.В. Яковлевой по решению задач об одномерном и многомерном рюкзаках [108], а также работу А.В, Орлова о поиске ситуаций равновесия в биматричиых играх [76].
Обіцая идеология методики, развиваемой А.С. Стрекаловским и его учениками, заключена всего в трех принципах.
1. Линеаризация по базовой певыпуклости исследуемой задачи и, как следствие, редукция исходной невыпуклой задачи к семейству (частично) линеаризованных задач.
2. Повсеместное применение методов выпуклой оптимизации для решения линеаризованных задачи, и как следствие, "внутри11 локального поиска.
3. Построение "хороших" аппроксимаций (разрешающих наборов) для поверхностей уровня или границ падграфика выпуклых функций.
Отметим, что до настоящего времени была развита в основном теория глобальной оптимизации гладких функций. В свете вышеобозначенпых принципов, при распространении данной методики на негладкий случай, представляется необходимым обратить особое внимание на методы выпуклой недиффереицируемой оптимизации.
Следует также отметить, что с прикладной точки зрения нет резкой границы между негладкими и гладкими функциями: функция с очень быстро меняющимся градиентом близка по своим свойствам к негладкой функции. Поэтому вычислительные методы, разработанные для решения задач негладкой оптимизации, оказываются эффективными и для оптимизации "плохих" гладких функций (функций овражного типа).
Проблематикой негладкого анализа, в частности, развитием теорегической базы и построение численных методов занимается большая группа отечественных и зарубежных математиков, среди которых выделяют, например, таких выдающихся ученых, как Б.Н. Пшеничный, В.Ф. Демьянов, А.Д. Иоффе, Ж.-Б. Ириарт-Уррути, Ф.Кларк, Е.А. Нурминский, Ж.-П. Пепо, Б.Т. Поляк, Р. Рокафеллар, В.М. Тихомиров, Н.З. Шор, И. Эклапд и многих других.
Среди методов негладкой оптимизации, которые в той или иной мере нашли практическое применение, можно выделить следующие классы.
1. Обоб7ценпый градиентный спуск [14, 65, 66, 79, 99, 101J. Это класс субградиентных процессов минимизации выпуклых функций, основанных на движении в направлении, которое дает уменьшение расстояния до точки минимума, если шаговый множитель достаточно мал. К преимуществам этих методов следует отнести простоту их реализации, а к недостаткам — медленную, как правило, сходимость.
2. Обобщенные градиентные методы с растяжением пространства [65], [66], [79], [101]—[105], в которых для ускорения сходимости используются преобразования пространства. Это часто применяемый в настоящее время класс методов, показавший свою высокую эффективность при решении практических задач.
3. Использование секущих гиперплоскостей для аппроксимации графика функции [14] или для последовательного уменьшения объема области локализации экстремума [79, 81]. К числу методов этого типа относится и получивший широкую известность метод эллипсоидов и его модификации [65, 66, 79]. С другой стороны, метод эллипсоидов можно отнести к методам обобщенного градиентного спуска с растяжением пространства. 4. Методы, основанные на замене экстремальной задачи вычислением значения сопряженной функции в начале координат (68)-(74], (128], [138]-(140].
Настоящая диссертационная работа посвящена вариационному подходу к решению задачи о полиэдральной отделимости, который основан па равносильности этой задачи задаче безусловной негладкой d.c. минимизации. Актуальность данного направления исследований определяется необходимостью разработки математического аппарата решения задачи классификации двух конечных множеств из пространства Шп, а также решения задач дискриминантиого анализа посредством методов невыпуклой негладкой оптимизации с исследованием их сходимости и численной проверкой их эффективности.
Перейдем к подробному изложению содержания диссертации.
Диссертация состоит из введения, трех глав, заключения, четырех приложений и списка литературы из 153 наименований. В каждой главе используется своя нумерация параграфов, предложений, лемм, теорем, замечаний и формул. Первая глава посвящена распространению теории d.c. минимизации на недифферен-цируемый случай.
В разделе 1.1 представлен негладкий вариант специального метода локального поиска. Предложена и доказана теорема сходимости данного метода. Затем, в разделе 1.2 приведены необходимые и достаточные условия глобальной оптимальности в недиффереицируемой задаче d.c. минимизации из (93, 95]. В разделе 1.3 эти условия глобальной оптимальности обобщаются на минимизирующие последовательности, затем, в разделе 1.4, па основе этих условий предлагается теоретическая схема глобального поиска в задаче недиффереицируемой d.c. минимизации.
Далее, в разделе 1.5 доказывается теорема сходимости алгоритма глобального поиска в негладком случае.
В конце главы (раздел 1.6) произведено теоретическое обоснование использования слабо разрещающих наборов при решении негладких задач.
Вторая глава посвящена теоретическому исследованию задачи о полиэдральной отделимости и реализации этапов стратегии глобального поиска для этой задачи. Сначала, в разделе 2.1, рассматривается постановка задачи. В разделе 2.2 найдено явное d.c. разложение функции ошибки, являющейся целевой функцией в задаче о полиэдральной отделимости. В разделе 2.3 получен явный вид субдифференциалов функций входящих в d.c. разложение.
Далее в главе проведена конкретизация всех этапов стратегии глобального поиска для задачи о полиэдральной отделимости: предложено три способа решения уравнения уровня (разделы 2.4-2.4.3), рассмотрено 10 вариантов построения поверхности уровня в задаче о полиэдральной отделимости (разделы 2.4.3 и 2.4.4), найден интервал изменения параметра /? (раздел 2.5).
И наконец, последняя глава посвящена численному решению задачи о полиэдральной отделимости.
Раздел 3.1 посвящен тестированию алгоритма локального поиска на задачах о полиэдральной отделимости.
В разделе 3.2 построена серия из 50 тестовых примеров задачи о полиэдральной отделимости. В разделе 3.3 представлены результаты численного эксперимента по тестированию алгоритма глобального поиска с использованием 10-ти способов построения аппроксимации поверхности уровня, рассмотренных в разделе 2.4.4. Далее. по итогам первого численного эксперимента предложены еще 2 способа построения аппроксимации поверхности уровня. В разделе 3.4 представлены результаты тестирования алгоритма глобального поиска с использованием новых способов построения аппроксимации и проведен общий анализ работы всех рассмотренных аппроксимаций.
В разделе 3.5 представлены результаты тестирования алгоритма глобального поиска с дополнительным внешним циклом по параметру Р — количеству отделяющих гиперплоскостей. В заключительном разделе З.б данной главы проведено тестирование работы программного обеспечения на известной тестовой задаче с большой мощностью множеств.
В заключении обсуждаются итоги проделанной работы, и дается их оценка. И наконец, приложения посвящены численной апробации алгоритмов локального и глобального поиска, предложенных в первой главе на тестовых задачах негладкой d.c. минимизации. В приложении А подробно рассмотрен и протестирован один метод выпуклой недиф ферепцируемой оптимизации, называемый r-алгоритмом Н.З. Шора. В приложении В построена серия тестовых задач негладкой d.c. минимизации и приводятся результаты численного тестирования работы алгоритмом локального поиска на рассмотренной серии тестовых задач. Затем, в приложении С представлены результаты тестирования алгоритма глобального поиска на той же серии, подтвердившие эффективность применяемой стратегии для решения невыпуклых недиффе-ренцируемых задач.
В приложении D приведены некоторые иллюстрации к главе 3.
Научная новизна работы заключается в распространении на негладкий случай теории d.c. минимизации, а также теоретическом обосновании и проверке численной эффективности вариационного подходя для решения задачи о полиэдральной отделимости.
Предложенные негладкие алгоритмы глобального и локального поиска могут быть использованы при дальнейшем развитии теории d.c. оптимизации. Разработанное программное обеспечение может использоваться решения широкого круга прикладных задач экономического, экологического и медицинского характера. Алгоритм, лежащий в основе данного программного обеспечения, открывает возможности для разработки новых методов решения задач дискримипантного анализа и таксономии, а также для численного решения задач, имеющих важные практические приложения во многих областях человеческой деятельности. Основные результаты диссертационной работы являются новыми и заключаются в следующем:
1. Предложены новые алгоритмы локального и глобального поиска для негладкой задачи d.c. минимизации, и доказаны их теоремы сходимости.
2. Обоснованы основные этапы алгоритма глобального поиска в задаче о полиэдральной отделимости посредством аналитических исследований и численного тестирования.
3. Разработано программное обеспечение для решения задач негладкой d.c. минимизации, которое доказало свою эффективность на серии специальных тестовых примеров, а также во время численного решения задач полиэдральной отделимости различной размерности.
Все результаты, включенные в диссертацию получены автором самостоятельно. Основные результаты диссертации опубликованы в работах [15]—[31] и докладывались на конференции "Ляиуповские чтения и презентация информационных технологий" в ИДСТУ СО РАН (Иркутск, 2002-2004); ежегодной школе-семинаре молодых ученых "Математическое моделирование и информационные технологии" (Ир-кутск-Ангасолка, 2002 -2005), Второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в ВУЗе (Иркутск, 2003): Всероссийской научной молодежной конференции "Под знаком Сигма" (Омск, 2003); Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2003); Всероссийской конференции "Инфокоммупикациопные и вычислительные технологии и системы "(Улан-Удэ-Байкал, 2003); III Всероссийской конференции "Математика, информатика, управление" (Иркутск, 2004): XIII Байкальской международной школе-семипаре "Методы оптимизации и их приложения" (Иркутск-Се-веробайкальск, 2005); IV Всероссийской конференции "Математика, информатика, управление"(Иркутск, 2005).
Результаты работы обсуждались на семинарах лаборатории методов глобальной оптимизации ИДСТУ СО РАН и объединенном семинаре ИДСТУ СО РАН. Автор выражает глубокую благодарность своему научному руководителю за помощь и постоянное внимание при выполнении работы. Автор также признателен участникам семинаров, на которых ему удалось выступить, за ценные советы, позволившие значительно улучшить представление и содержание диссертации.
Локальный поиск
Подведем итоги двух этапов вычислительного эксперимента. Во время первого численного эксперимента было протестировало 10 аппроксимаций. По итогам этого эксперимента были выделены 3 наиболее удачные аппроксимации и на основе их компиляции построено еще две. По результатам двух этапов численного эксперимента можно сделать следующие выводы. 1. Лучше всего среди всех аппроксимаций 721-7212 показали себя аппроксимации Ш1 (решено 94% примеров), 7212 (92%) и 7210 (90%). 2. С точки зрения максимального отклонения от глобального решения (менее 0.5) лучше всего вновь зарекомендовали себя аппроксимации 7211 и 72.12. 3. В качестве еще одного параметра качества аппроксимации можно рассматривать число примеров, в которых не удалось получить улучшение за счет ее элементов. Здесь хуже всего показала себя аппроксимация 721 — не удалось получить улучшение в 8 примерах. Снова оказываются хорошими аппроксимации 7211 и 72.12, а также 724, 72.7 и 728. При использовании этих аппроксимаций во всех примерах получено улучшение за счет элементов аппроксимации. 4. Самое большое время работы алгоритма, а также наибольшее количество линеаризованных задач было решено в процессе работы алгоритма глобального поиска с использованием аппроксимации 725. Это объясняется тем, что данная аппроксимация содержит наибольшее число элементов. 5. С точки зрения трудности тестовых задач стоит отметить задачи 26 и 30. При использовании большинства аппроксимаций (722, 723, 724, 728, 729, 7210, 7211, 7212) максимум числа решенных линеаризованных задач достигается на примере 26. Максимальное время достигается на этом примере при использовании аппроксимаций 722, 723, 724 и 7212. На примере 30 максимальное время достигается при использовании аппроксимаций 726, 72.7, 728 и 729.
В целом, наиболее привлекательной для задачи о полиэдральной отделимости, оказалась аппроксимация 7210, т.к. она незначительно проигрывает наиболее сильным аппроксимациям Xll и 7tl2 в проценте решенных примеров, но при этом весьма выигрывает по количеству решенных в процессе линеаризованных задач, и, как следствие, по времени работы алгоритма. Графическую информацию, иллюстрирующую выводы, представленные в данном разделе, можно найти, в приложении D.I.
Предыдущие два численных эксперимента были посвящены отделению двух конечных множеств точек Ли В заранее заданным количеством гиперплоскостей Р. Однако, в общей постановке задаче о полиэдральной отделимости говорится об отделении множеств минимальным количеством гиперплоскостей (см. раздел 2.1). Следовательно, существует необходимость в дополнительном поиске — по параметру Р. Поэтому данный раздел будет посвящен тестированию алгоритма глобального поиска с дополнительным внешним циклом по параметру Р - количеству отделяющих гиперплоскостей.
Определим сначала интервал изменения этого параметра. Напомним, что в случае линейной отделимости множеств Р = 1. С другой стороны, если множества ие отделимы при Р — Nь то они полиэдрально не отделимы (см. раздел 2.1). Таким образом, Ре{1,... ,Щ.
Далее обратимся к нашему набору тестовых примеров (таблица 3.2.1). Значение параметра N доходит в этом наборе до 100 (пример 7). Однако, в разделе 3.1.2 было установлено, что увеличение параметра Р очень существенно увеличивает время работы метода локального поиска, а, следовательно, время работы алгоритма глобального поиска будет также значительно возрастать.
С другой стороны, в процессе тестирования алгоритма глобального поиска с использованием различных аппроксимаций в предыдущих двух разделах во всех примерах множества Л и В были полиэдрально отделены, причем количество отделяющих гиперплоскостей ни в одном примере ие превысило 5,
Таким образом, для ускорения работы алгоритма поиска минимального числа отделяющих гиперплоскостей интервал изменения параметра Р сокращаем искусствеи иым образом Р Є {1,..., Ртах У) ГДЄ Ртах — min{/V, 5}. Для поиска минимального количества отделяющих гиперплоскостей Р+ в алгоритме глобального поиска был введен дополнительный внешний цикл по Р, состоящий в пошаговом уменьшении Р. Если при данном значении Р множества удалось отделить, то уменьшаем Р па единицу. Если же множества Л и В не отделимы полиэдрально данным числом гиперплоскостей Р, то за Р принимаем предыдущее значение Р: P. = Р+ 1 Это обозначение будет использовано ниже в таблице, PQ — начальное число гиперплоскостей. Если множества Ли. В не удалось отделить при Р = Ртах то полагаем что множества полиэдрально не отделимы. В целях экономии общего времени работы алгоритма, алгоритм глобального поиска был "огрублен11 по сравнению с его реализацией в предыдущих двух разделах. Во-первых, была ослаблена точность критерия останова. Здесь полагаем Х1=Х2 = 0.001.
Условия глобальной оптимальности
Настоящая диссертация посвящена разработке и обоснованию вариационного подхода, а также непосредственному численному решению одной из задач дискриминант-ного анализа — задачи о полиэдральной отделимости.
Во введении, в частности, обоснована актуальность направления исследований, произведен обзор литературы, установлены некоторые взаимосвязи с результатами исследований различных школ в России и за рубежом.
Далее, в первой главе диссертации теория глобального поиска в задачах d.c. минимизации распространена на псдифференнируемый случай- В частности, доказаны теоремы сходимости алгоритмов локального и глобального поиска для негладких задач d.c. минимизации, а также произведено теоретическое обоснование использования слабо.разрешающих наборов в негладких задачах.
Вторая глава посвящена теоретическому исследованию задачи о полиэдральной отделимости. Вначале произведено сведение этой задачи к некоторой задаче минимизации функции ошибки и доказана эквивалентность вариационной постановки и полиэдральной отделимости. Далее, найдено явное разложение функции ошибки в виде разности двух негладких выпуклых функций. Затем, с целью использования известного r-алгоритма Н.З. Шора в методе локального поиска получен явный вид субдифферепциалов функций d.c. разложения.
Кроме того, предложено несколько вариантов построения аппроксимаций поверхности уровня негладких выпуклых функций, используемых в алгоритме глобального поиска.
Третья глава посвящена численному решению задачи о полиэдральной отделимости на теоретической основе и аналитических результатах, полученных в предыдущих двух главах. Так, например, произведен обширный численный эксперимент на достаточно большом и разнообразном спектре задач о полиэдральной отделимости различной размерности. Кроме того, результаты компьютерного эксперимента довольно подробно проанализированы.
В частности анализ численного эксперимента говорит об эффективности предложенной методики решения задач полиэдральной отделимости.
В приложениях производится численное тестирование предложенных в первой главе алгоритмов локального и глобального поиска па тестовых негладких задачах d.c. минимизации. Кроме этого подробно рассмотрен и протестирован г-алгоритм Н.З. Шора, который применяется на каждой итерации метода локального поиска для решения выпуклых негладких линеаризованных задач.
Основные результаты диссертационной работы, выносимые на защиту, заключаются в следующем.
1. Предложены новые алгоритмы локального и глобального поиска для негладкой задачи d.c. минимизации, и для них доказаны теоремы сходимости.
2. Обоснованы основные этапы алгоритма глобального поиска в задаче о полиэдральной отделимости посредством аналитических исследований и численного тестирования.
3. Разработано программное обеспечение для решения задач негладкой d.c. минимизации, которое доказало свою эффективность на серии специальных тестовых примеров, а также во время численного решения задач полиэдральной отделимости различной размерности.
Предложенные негладкие алгоритмы глобального и локального поиска могут быть использованы при дальнейшем развитии теории d.c. оптимизации. Разработанное программное обеспечение может использоваться для решения проблем системного анализа и исследования операций, в частности, для решения широкого круга прикладных задач экономического, экологического и медицинского характера. Алгоритм, лежащий в основе данного программного обеспечения, открывает возможности для разработки новых методов решения задач дискриминантного анализа и таксономии, а также для численного решения задач, имеющих важные практические приложения во многих областях человеческой деятельности.
На каждой итерации специального метода локального поиска (раздел 1.1) производится приближенное решение линеаризованной задачи. Эта задача является безусловной задачей выпуклой негладкой оптимизации. В данной работе, для ее решения применяется метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных субградиентов (г-алгоритм Н.З. Шора)[101], занимающий, по мнению специалистов [66\, особое положение по практической эффективности среди методов негладкой оптимизации. Как известно [66], методы обобщенного градиентного спуска имеют довольно низкую скорость сходимости, так как антиградиепт, в направлении которого происходит движение, может образовывать угол, близкий к тг/2, с направлением на точку минимума. Эта проблема решается с помощью проведения операции растяжения пространства в направлении субградиента, что позволяет уменьшить на последующих шагах составляющие субградиептов, параллельные субградиенту, полученному на данном шаге. Тем самым значительно уменьшается составляющая антяградиента, ортогональная направлению на точку минимума.
Постановка задачи о полиэдральной отделимости
Во всех задачах получено глобальное решение задачи fmm — 0.0. Далее, что вполне ожидаемо, время решения задачи существенно возрастает при возрастании размер ности задачи. Кроме того, время решения задачи и количество итераций зависят от точности критерия останова. Однако, например, в данном численном эксперимен те, при различных точностях останова получены значения функции одного порядка. Учитывая последний факт, и то, что время работы метода значительно возрастает при использовании более "топкой" точности (rj = 10 4,т2 = 10 6) останова, пред ставляется более естественным использовать точность останова Tj = г2 = 0.1. #
Итак, метод минимизации, использующий операцию растяжения пространства в па-правлении разности двух последовательных субградиептов, называемый также г-алгоритмом Н.З. Шора, является одним из наиболее популярных методов выпуклой недифференцируемой оптимизации. Результаты численных экспериментов подтвердили его "хорошую репутацию": во всех рассмотренных примерах получено решение задачи с достаточной точностью и за приемлемое время. Время работы метода и количество итераций, необходимых для получения решения задачи существенно зависит от размерности задачи, начального приближения и точности останова. Нет смысла использовать очень "жесткую" точность (ті — Ю-4, т2 + 10_6) останова, вполне достаточно точности тг — т2 — 0.01 либо т-[ = г2 — 0.1.
Кроме того, время работы метода в общем случае существенно зависит от величины коэффициента растяжения пространства а. Самым плохим значением этого коэффициента является а = 1, при котором г-алгоритм Н.З. Шора совпадает с методом обобщенного градиентного спуска, со всеми вытекающими отсюда недостатками. Как утрверждается в литературе [66, 101, 102, 103, 104, 105J, значение коэффициента растяжения пространства а целесообразно выбирать равным 2 или 3, так как в большинстве случаев при дальнейшем увеличении а количество итераций, если и уменьшается, то незначительно, зато заметно увеличивается среднее число вычислений функции при поиске минимума по направлению.
В данном приложении будут представлены результаты численного тестирования метода локального поиска, рассмотренного в первой главе. Напомним его основные элементы.
Метод локального поиска заключается в последовательном решении линеаризованных по базовой невыпуклости задач. Пусть задано некоторое начальное приближение х. Далее, если известны допустимая точка Xs и некоторый субградиент ж Є df(xs), то следующее приближение х3+1 будем искать как приближенное решение линеаризованной в точке Xs задачи: д(х) - (х а, х) і min, х Є D, x s Є df(x ). (PLS) Линеаризованная задача (PLS) на каждой итерации метода решается г-алгоритмом Н. 3. Шора [66, 101, 102, 103, 104, 105], описанным и протестированным в приложении А. Напомним также, что критерием останова метода локального поиска служит выполнение одногб из неравенств (1,1.8): F(x ) - F(xs+i) т, д(х ) - g(xs+1) + {ха1 х+1 - х } т, ха Є df(x ), где т — заданная точность. В этом случае точка хя, в которой произошел останов метода локального поиска является (г + Йв)-рсшением задачи (PLS), где Ss — точ 116 пость решения линеаризованной задачи. С другой стороны, согласно определению 1.1.1, эта точка является (т + я)-критической в рассматриваемой задаче. Метод реализован в среде Microsoft Visual C++ 6.0, расчет производился на компьютере Pentium Celeron 660.
Для тестирования алгоритмов локального и глобального поиска было построено 5 примеров. Целевая функция в каждом примере является недифферепцируемой. Однако, в первых трех примерах, недифференцируемой является только функция /() из d.c. разложения целевой функции. Таким образом, линеаризованные задачи, решаемые на каждой итерации локального поиска оказываются дифференцируемыми. В оставшихся двух примерах обе функции д(-) и /(), входящие в d.c. разложение целевой функции, недифференцируемы, и следовательно, на каждой итерации метода локального поиска происходит решение уже недифференцируемых задач. Отметим, что во всех примерах, кроме первого, недифференцируемая составляющая целевой функции — это кусочно-линейная функция. Такое построение тестовых примеров объясняется тем, что функция ошибки, являющаяся целевой функцией задачи о полиэдральной отделимости (главы 2 и 3), также является кусочно-линейной функцией, по гораздо более сложной структуры, чем функции, рассматриваемые в данном приложении. Таким образом, очевиден интерес в апробации алгоритмов локального и глобального поиска па функциях такого типа, но достаточно простой структуры. Далее, свойства всех построенных примеров, такие как значение глобального минимума целевой функции и точки этого минимума, а также точки локального минимума и значения функции в этих точках, для размерностей п — 1, 2 найдены при помощи системы MathCad.
Локальный поиск в задаче о полиэдральной отделимости
Время решения во всех случаях оказалось менее 0.01 секунды. Из таблицы можно видеть, что из любого начального приближения, кроме точки (0,0), метод локального поиска опускается в ближайшую точку глобального минимума. Из точки (0,0) локальный поиск, по очевидным причинам, выйти не может, хотя она не является точкой минимума. Отметим, что при старте из этой точки, в процессе работы алгоритма локального поиска решена всего одна линеаризованная задача, поскольку здесь имеем F(xl) — F(x) = О, и срабатывает первый критерий останова из 1.1.8. При старте из любой другой точки, кроме (0,0), в процессе работы алгоритма решено всего 2 линеаризованных задачи. Это объясняется структурой рассматриваемой задачи. Здесь линеаризовашіая в любой (кроме (0,0)) точке функция представляет собой параболоид с вершиной на поверхности минимума целевой функции, и нахождение глобального минимума такой функции не представляет трудности для г-алгоритма. Вторую линеаризованную задачу приходится решать для срабатывания критерия останова алгоритма 1.1.8.
В следующей таблице представлены результаты исследования зависимости времени работы алгоритма локального поиска от размерности пространства п. Особое внимание уделено выяснению наиболее трудозатратных подзадач алгоритма. Для освещения последнего вопроса в данной таблице, помимо обозначений, общих для всех таблиц данного раздела, введены следующие обозначения: К — количество вычислений значения линеаризованной функции; QM — количество умножение двух матриц в процессе работы алгоритма; timeQM — среднее время, затрачиваемое на перемножение двух матриц данной размерности.
В результате работы метода локального поиска в данном примере, для всех рассмотренных размерностей, от 2 до 1000, была получена точка, со значением целевой функции Fioc = —0.25, что совпадает со значением глобального минимума задачи. Также, во всех случаях, в ходе работы алгоритма локального поиска было решено только 2 линеаризованных задачи, т.е. PL — 2. Поэтому эти параметры не включены в таблицу . Отметим, что, несмотря па возрастание размерности, все примеры решаются за приемлемое время. В частности, при п = 1000 время решения при любом из выбранных начальных приближений составило менее чем 6 с половиной минут. Причем, поскольку выбрано хорошее начальное приближение (т.е. Зі {1,..., п} : х ф 0), во всех случаях методом локального поиска удалось получить точку глобального минимума. Кроме этого, благодаря центральной симметрии целевой функции, значение функции в точках х\ и х\ совпадает. Процесс работы алгоритма при старте из любой из этих точек происходит за одинаковое число итераций и одинаковое время. В точке х\ значение целевой функции меньше, чем в двух других и при старте из этой точки метод локального поиска получает решение гораздо быстрее.
Оцепим теперь трудоемкость этапов алгоритма локального поиска. Как уже упоминалось выше, в процессе работы алгоритма в каждом примере решено всего 2 линеаризованных задачи, что объясняется структурой исходной задачи. Однако, время решения одной линеаризованной задачи существенно возрастает при увеличении размерности задачи. Рассмотрим причины столь значительного возрастания времени работы. С одной стороны, при возрастании п увеличивается время вычисления значения линеаризованной функции, однако это увеличение незначительно. Из таблицы В,2 можно видеть, что основной причиной увеличения работы алгоритма при возрастании размерности задачи является существенное увеличение времени, затрачиваемого на одну операцию перемножения двух матриц соответствующей размерности (при n = 1000, например, на одно умножение матриц затрачивается более 2-х минут).
