Введение 3
Глава 1. Обзор литературы 5
1.1. Явные методы Рунге - Кутты 6
1.2. Разложение Лагранжа - Бюрмана 8
1.2.1 Формула разложения Лагранжа - Бюрмана 8
1.2.2 Явные методы Рунге - Кутты с разложением Лагранжа
- Бюрмана 9
1.2.3 Метод второго порядка точности 10
1.3. Применение методов Рунге - Кутты к решению оптимиза-ционных задач 12
1.4. Выводы 13
Глава 2. Построение и анализ градиентных методов 14
2.1. Случай квадратичной функции 14
2.1.1 Одношаговый метод 15
2.1.2 Двухшаговый метод 21
2.2. Случай возмущенной квадратичной функции 28
2.3. Результаты 30
Глава 3. Решение задач 31
3.1. Решение двумерной задачи для уравнения Пуассона .... 32
3.2. Решение трехмерной задачи для уравнения Пуассона . ... 34
3.3. Решение задачи минимизации интегрального функционала 36
3.4. Решение задачи для нелинейного интегро-дифференциального
уравнения 38
3.5. Решение задачи логистической регрессии 40
3.6. Результаты 42
Заключение 43
Список литературы 44
В настоящее время методы оптимизации широко используются во многих областях науки и техники. Эти методы активно применяются в задачах
машинного обучения [14], теории управления [23] и линейной алгебры [15,
28]. Их использование позволяет находить наилучшие решения в условиях
ограниченных времени и ресурсов. На практике большинство задач оптимизации можно решить только численно. В связи с этим разработка и исследование численных методов оптимизации являются актуальными задачами в
вычислительной математике.
Наиболее часто при решении оптимизационных задач используются
градиентные методы, которые основаны на движении вдоль антиградиента
— направления наискорейшего убывания функции. Примерами таких методов являются градиентный спуск, метод Нестерова [26] и метод тяжелого шарика [8]. Также в задачах оптимизации широко применяются численные методы второго порядка, среди которых наиболее распространен метод Ньютона. Стоит отметить, что методы первого порядка не используют матрицу
Гессе, вычисление которой может потребовать значительных вычислительных ресурсов для решения задач большой размерности.
В последние годы идет активное исследование методов оптимизации,
построенных на аналогии между градиентным спуском и задачей Коши для
обыкновенных дифференциальных уравнений [12, 17, 18, 19, 25, 27, 30, 31,
33, 34, 35]. Наиболее популярными численными методами решения задачи
Коши являются методы Рунге – Кутты (РК), которые основаны на разложении
решения в ряд Тейлора. Однако, решение можно разложить в ряд по степеням
некоторой функции, зависящей от шага метода. Эту задачу можно эффективно решить с помощью разложения Лагранжа – Бюрмана (ЛБ) [5]. Использование нестандартных разложений позволяет получить увеличенную область
устойчивости метода и проводить вычисления с бо́ льшим шагом.
В данной работе построены новые численные методы оптимизации выпуклых функций с использованием методов РК на основе разложения ЛБ,
проведено теоретическое исследование методов, а также приведены результаты их применения к задачам из различных областей и проведено сравнение
3с другими известными методами.
Целью работы является разработка и анализ новых численных методов
минимизации выпуклых функций с использованием методов РК на основе
разложения ЛБ. Для достижения поставленной цели необходимо решить следующие задачи:
- построение новых градиентных методов,
- получение условий сходимости,
- программная реализация и решение тестовых задач,
- сравнение построенных методов с другими известными методами оптимизации.
Глава 1 посвящена обзору литературы. Рассмотрена аналогия между
градиентным спуском и задачей Коши, а также осуществлен обзор статей,
связанных с тематикой работы. Представлено семейство методов РК и методы, основанные на разложении ЛБ. Сформулированы цель и задачи работы.
В Главе 2 приводится построение и анализ новых градиентных методов минимизации, сформулированы и доказаны теоремы о сходимости для
случая квадратичной и возмущенной квадратичной функции.
В Главе 3 проводится сравнение построенных методов с другими известными методами оптимизации. Рассматриваются задачи из различных областей: краевые задачи для уравнения Пуассона в двумерном и трехмерном
случаях; задача минимизации интегрального функционала; краевая задача
для нелинейного интегро-дифференциального уравнения и задача логистической регрессии с регуляризацией. По результатам расчетов показано, что
построенные методы могут сходиться быстрее, чем широко используемые
методы минимизации выпуклых функций.
В представленной работе были проведены построение и анализ методов на основе метода РК с разложением ЛБ. Сформулированы и доказаны теоремы о сходимости построенных методов. Получены выражения для параметров, обеспечивающие оптимальную скорость сходимости. Проведено сравнение построенных методов с другими известными методами минимизации выпуклых функций при решении тестовых задач из различных областей.
В ходе работы были получены следующие результаты:
1. Построены методы спуска на основе двухэтапного метода Рунге - Кутты с разложением Лагранжа - Бюрмана.
2. Получены условия сходимости для случая квадратичной и возмущенной квадратичной функции.
3. Проведены вычислительные эксперименты по сравнению предложенных методов с известными методами минимизации при решении двумерных и трехмерных задач для уравнений эллиптического типа, задачи вариационного исчисления, задачи для нелинейного интегро-дифференциального уравнения и задачи логистической регрессии.
Из полученных результатов можно сделать следующие выводы:
1. В выражении для шага (2.14) за счет выбора параметра у можно влиять на скорость сходимости и шаг численного метода. За счет этого, при про-ведении практических расчетов можно производить вычисления с высокой эффективностью, экономя вычислительные ресурсы.
2. При решении задач из разных областей показано, что построенные методы могут сходиться быстрее, чем известные методы минимизации выпуклых функций.
Перспективной для дальнейшего исследования можно назвать задачу распространения методов на основе метода РК с разложением ЛБ на случай произвольной гладкой выпуклой функции. В частности, можно рассмотреть по строение квазиньютоновских методов и их применение к задачам машинного обучения, обработки изображений и теории управления.
