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

• Автор: Дружинина, Оксана Владимировна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Иркутск
• Количество страниц: 155 с. : ил.

Оглавление
Введение

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

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

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

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

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

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

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

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

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

2.1 Постановка задачи о полиэдральной отделимости
2.2 Б.С. представление функции ошибки
2.3 Нахождение субдифференциалов функции ошибки
2.4 Построение аппроксимации поверхности уровня
2.4.1 Первый прием построения аппроксимации поверхности уровня функции .
2.4.2 Второй прием .
2.4.3 Трегий прием .
2.4.4 Построение наборов направлений Ог
2.5 Вычисление интервала одномерного поиска параметра 3.
2.6 Заключительные замечания.
3 Численное решение задачи
о полиэдральной отделимости
3.1 Локальный поиск
в задаче о полиэдральной отделимости.
3.1.1 Первый этап тестирования локального поиска
3.1.2 Тестирование алгоритма локального поиска на задачах о полиэдральной отделимости большой размерности
3.2 Алгоритм глобального поиска и особенности численного эксперимента .
3.3 Первый этап численного эксперимента.
3.4 Второй этап числешюго эксперимента .
3.5 Минимизация количества
отделяющих гиперплоскостей
3.6 Решение тестовой задачи с множествами
большой мощности .
3.7 Заключительные замечания.
Заключение
А Об галгоритме Н.З. Шора
А.1 Описание алгоритма.
А.2 Численное тестирование галгоритма
Н.З. Шора
В Тестирование специального метода локального поиска
С Численная апробация метода глобального поиска
на тестовых примерах
О Иллюстрации к главе 3
0.1 Характеризация аппроксимаций
поверхности уровня.
0.2 Точки отделяемых множеств в примере сЬескег раздел 3.6.
Список использованной литературы


Обобщенные градиентные методы с растяжением пространства [|, [], [], (1|-(5|, в которых для ускорения сходимости используются преобразования пространства. Эго часто применяемый в настоящее время класс методов, показавший свою высокую эффективность при решении практических задач. Использование секущих гиперплоскостей для аппроксимации графика функции 4) или для последовательного уменьшения объема области локализации экстремума [, 1. К числу методов этого типа относится и получивший широкую известность метод эллипсоидов и его модификации |, бб, |. С другой стороны, метод эллипсоидов можно отнести к методам обобщенного градиентного спуска с растяжением пространства. Методы, основанные на замене экстремальной задачи вычислением значения сопряженной функции в начале координат ||-|], [8), [8|-[0|. Настоящая диссертационная работа посвящена вариационному подходу к решению задачи о полиэдральной отделимости, который основан на равносильности этой задачи задаче безусловной негладкой <1. Актуальность данного направления исследований определяется необходимостью разработки математического аппарата решения задачи классификации двух конечных множеств из пространства /К7', а также решения задач дискриминантного анализа посредством методов невыпуклой негладкой оптимизации с исследованием их сходимости и численной проверкой их эффективности. Перейдем к подробному изложению содержания диссертации. Диссертация состоит из введения, трех глав, заключения, четырех приложений и списка литературы из 3 наименований. В каждой главе используется своя нумерация параграфов, предложений, лемм, теорем, замечаний и формул. Первая глава посвящена распространению теории с]. В разделе 1. Предложена и доказана теорема сходимости данного метода. Затем, в разделе 1. В разделе 1. Далее, в разделе 1. В конце главы (раздел 1. Вторая глава посвящена теоретическому исследованию задачи о полиэдральной отделимости и реализации этапов стратегии глобального поиска для этой задачи. Сначала, в разделе 2. В разделе 2. В разделе 2. Далее в главе проведена конкретизация всех этапов стратегии глобального поиска для задачи о полиэдральной отделимости: предложено три способа решения уравнения уровня (разделы 2. И наконец, последняя глава посвящена численному решению задачи о полиэдральной отделимости. Раздел 3. В разделе 3. В разделе 3. Далее, по итогам первого численного эксперимента предложены еще 2 способа построения аппроксимации поверхности уровня. В разделе 3. В разделе 3. Р — количеству отделяющих гиперплоскостей. В заключительном разделе 3. В заключении обсуждаются итоги проделанной работы, и дается их оценка. И наконец, приложения посвящены численной апробации алгоритмов локального и глобального поиска, предложенных в первой главе на тестовых задачах негладкой (1. Н.З. Шора. В приложении В построена серия тестовых задач негладкой б. Затем, в приложении С представлены результаты тестирования алгоритма глобального поиска на той же серии, подтвердившие эффективность применяемой стратегии для решения невыпуклых недифференцируемых задач. В приложении О приведены некоторые иллюстрации к главе 3. Научная новизна работы заключается в распространении на негладкий случай теории б. Предложенные негладкие алгоритмы глобального и локального поиска могут быть использованы при дальнейшем развитии теории б. Разработанное программное обеспечение может использоваться решения широкого круга прикладных задач экономического, экологиче(жого и медицинского характера. Алгоритм, лежащий в основе данного программного обеспечения, открывает возможности для разработки новых методов решения задач дискриминантного анализа и таксономии, а также для численного решения задач, имеющих важные практические приложения во многих областях человеческой деятельности. Предложены новые алгоритмы локального и глобального поиска для негладкой задачи б. Обоснованы основные этапы алгоритма глобального поиска в задаче о полиэдральной отделимости посредством аналитических исследований и численного тестирования. Разработано программное обеспечение для решения задач негладкой б.