Метод градиентного спуска
Рассмотрение идеи метода, его алгоритма. Определение критерия останова. Оценка сходимости градиентного спуска с постоянным шагом. Выбор оптимального шага. Характеристика градиентного метода с дроблением шага. Разработка рекомендаций программисту.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | реферат |
Язык | русский |
Дата добавления | 25.12.2018 |
Размер файла | 405,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
КЫРГЫЗСКОЙ РЕСПУБЛИКИ
КЫРГЫЗСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ
ИМ. Ж.БАЛАСАГЫНА
Факультет: Математики и информатики
СРС
На тему: «Метод градиентного спуска»
По дисциплине: «Методы оптимизации»
Выполнила: ст. гр. «ПМиИбк-15»
Султанова Б.Т.
Проверила: ст. пр. Саркелова Ж.Ж.
Оглавление
Введение
1. Метод градиентного спуска
1.1 Идея метода
1.2 Алгоритм
1.3 Критерий останова
1.4 Сходимость градиентного спуска с постоянным шагом
1.5 Выбор оптимального шага
1.6 Градиентный метод с дроблением шага
1.7 Метод наискорейшего спуска
2. Числовые примеры
2.1 Метод градиентного спуска с постоянным шагом
2.2 Градиентный метод с дроблением шага
2.3 Метод наискорейшего спуска
3. Рекомендации программисту
Заключение
градиентный спуск шаг программист
Введение
В работе рассматривается задача поиска минимума функции , записываемая в виде:
(1)
Пусть функция такова, что можно вычислить ее градиент. Тогда можно применить метод градиентного спуска, описанный в данной статье.
В статье приведены теоремы сходимости метода градиентного спуска, а также рассмотрена его варианты:
Метод градиентного спуска с постоянным шагом
Метод градиентного спуска с дроблением шага
Метод наискорейшего спуска
1. Метод градиентного спуска
Рис.1 Геометрическая интерпретация метода градиентного спуска с постоянным шагом. На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в раз".
1.1 Идея метода
Основная идея метода заключается в том, чтобы осуществлять оптимизацию в направлении наискорейшего спуска, а это направление задаётся антиградиентом :
где выбирается постоянной, в этом случае метод может расходиться;
дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
наискорейшим спуском:
1.2 Алгоритм
Вход: функция
Выход: найденная точка оптимума
Повторять:
,
где выбирается одним из описанных выше способов если выполен критерий останова, то возвращаем текущее значение
1.3 Критерий останова
Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях. Некоторые из них:
Здесь - значение, полученное после -го шага оптимизации. - наперед заданное положительное число.
1.4 Сходимость градиентного спуска с постоянным шагом
Теорема 1 о сходимости метода градиентного спуска с постоянным шагом.
Пусть , функция дифференцируема, ограничена снизу. Пусть выполняется условие Липшица для градиента : . Пусть .
Тогда при любом выборе начального приближения.
В условиях теоремы градиентный метод обеспечивает сходимость либо к точной нижней грани (если функция не имеет минимума) либо к значению Существуют примеры, когда в точке реализуется седло, а не минимум. Тем не менее, на практике методы градиентного спуска обычно обходят седловые точки и находят локальные минимумы целевой функции.
Определение. Дифференцируемая функция называется сильно выпуклой (с константой ), если для любых и из справедливо
Теорема 2 о сходимости метода градиентного спуска спуска с постоянным шагом.
Пусть функция дифференцируема, сильно выпукла с константой . Пусть выполняется условие Липшица для градиента : . Пусть .
Тогда при любом выборе начального приближения.
1.5 Выбор оптимального шага
Рис.2 Ситуация, когда метод гардиентного спуска сходится плохо.
Константа , фигурирующая в теореме 2 и характеризующая скорость сходимости метода, зависит от шага . Нетрудно видеть, что величина минимальна, если шаг выбирается из условия , т. е. если .
При таком выборе шага оценка сходимости будет наилучшей и будет характеризоваться величиной:
.
В качестве и могут выступать равномерные по x оценки сверху и снизу собственных значений оператора . Если , то и метод сходится очень медленно. Геометрически случай соответствует функциям с сильно вытянутыми линиями уровня (см. рис. 2). Простейшим примером такой функции может служить функция на , задаваемая формулой:
Поведение итераций градиентного метода для этой функции изображено на рис. 2 -- они, быстро спустившись на "дно оврага", затем медленно "зигзагообразно" приближаются к точке минимума. Число (характеризующее, грубо говоря, разброс собственных значений оператора ) называют числом обусловленности функции . Если , то функции называют плохо обусловленными или овражными. Для таких функций градиентный метод сходится медленно.
Но даже для хорошо обусловленных функций проблема выбора шага нетривиальна в силу отсутствия априорной информации о минимизируемой функции. Если шаг выбирается малым (чтобы гарантировать сходимость), то метод сходится медленно. Увеличение же шага (с целью ускорения сходимости) может привести к расходимости метода. Далее будут описаны два алгоритма автоматического выбора шага, позволяющие частично обойти указанные трудности.
1.6 Градиентный метод с дроблением шага
В этом варианте градиентного метода величина шага на каждой итерации выбирается из условия выполнения неравенства
,(2)
где - некоторая заранее выбранная константа.
Процедуру нахождения такого обычно оформляют так. Выбирается число и некоторый начальный шаг . Теперь для каждого k полагают и делают шаг градиентного метода. Если с таким условие (2) выполняется, то переходят к следующему k. Если же (2) не выполняется, то умножают на ("дробят шаг") и повторяют эту процедуру до тех пор пока неравенство (2) не будет выполняться. В условиях теоремы 1 эта процедура для каждого k за конечное число шагов приводит к нужному .
Можно показать, что в условиях теоремы 2 градиентный метод с дроблением шага линейно сходится. Описанный алгоритм избавляет нас от проблемы выбора на каждом шаге, заменяя ее на проблему выбора параметров и , к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.
1.7 Метод наискорейшего спуска
Рис.3 Геометрическая интерпретация метода наискорейшего спуска. На каждом шаге выбирается так, чтобы следующая итерация была точкой минимума функции на луче L.
Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче
:
.
Другими словами, выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. рис. 3). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, кстати, что в этом методе направления соседних шагов ортогональны.
Метод наискорейшего спуска требует решения на каждом шаге задачи одномерной оптимизации. Практика показывает, что этот метод часто требует меньшего числа операций, чем градиентный метод с постоянным шагом.
В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.
2. Числовые примеры
2.1 Метод градиентного спуска с постоянным шагом
Для исследования сходимости метода градиентного спуска с постоянным шагом была выбрана функция:
.
Начальное приближение - точка (10,10). Использован критерий останова:
Результаты эксперимента отражены в таблице:
Значение шага |
Достигнутая точность |
Количество итераций |
|
0.1 |
метод расходится |
||
0.01 |
2e-4 |
320 |
|
0.001 |
2e-3 |
2648 |
|
0.0001 |
1e-2 |
20734 |
Из полученных результатов можно сделать вывод, что при слишком большом чаге метод расходится, при слишком малом сходится медленно и точность хуже. Надо выбирать шаг наибольшим из тех, при которых метод сходится.
2.2 Градиентный метод с дроблением шага
Для исследования сходимости метода градиентного спуска с дроблением шага (2) была выбрана функция:
.
Начальное приближение - точка (10,10). Использован критерий останова:
Результаты эксперимента отражены в таблице:
Значение параметра |
Значение параметра |
Значение параметра |
Достигнутая точность |
Количество итераций |
|
0.95 |
0.95 |
1 |
5e-4 |
629 |
|
0.1 |
0.95 |
1 |
1e-5 |
41 |
|
0.1 |
0.1 |
1 |
2e-4 |
320 |
|
0.1 |
0.95 |
0.01 |
2e-4 |
320 |
Из полученных результатов можно сделать вывод об оптимальном выборе параметров: , хотя метод не сильно чувствителен к выбору параметров.
2.3 Метод наискорейшего спуска
Для исследования сходимости метода наискорейшего спуска была выбрана функция:
.
Начальное приближение - точка (10,10). Использован критерий останова:
Для решения одномерных задач оптимизации использован метод золотого сечения. Метод получил точность 6e-8 за 9 итераций.
Отсюда можно сделать вывод, что метод наискорейшего спуска сходится быстрее, чем градиентный метод с дроблением шага и метод градиентного спуска с постоянным шагом. Недостатком методом наискорейшего спуска является необходимость решать одномерную задачу оптимизации.
3. Рекомендации программисту
При программировании методов градиентного спуска следует аккуратно относится к выбору параметров, а именно
Метод градиентного спуска с постоянным шагом: шаг следует выбирать меньше 0.01, иначе метод расходится (метод может расходится и при таком шаге в зависимости от исследуемой функции).
Градиентный метод с дроблением шага не очень чувствителен к выбору параметров. Один из вариантов выбора параметров:
Метод наискорейшего спуска: в качестве метода одномерной оптимизации можно использовать метод золотого сечения (когда он применим).
Заключение
Методы градиентного спуска являются достаточно мощным инструментом решения задач оптимизации. Главным недостатком методов является ограниченная область применимости.
Размещено на Allbest.ru
Подобные документы
Назначение и классификация методов поисковой оптимизации. Эффективность поискового метода. Методы поиска нулевого порядка: исходные данные, условия, недостатки и применение. Структура градиентного метода поиска. Основная идея метода наискорейшего спуска.
лекция [137,8 K], добавлен 04.03.2009Особенности метода неопределенных множителей Лагранжа, градиентного метода и метода перебора и динамического программирования. Конструирование алгоритма решения задачи. Структурная схема алгоритма сценария диалога и описание его программной реализации.
курсовая работа [1010,4 K], добавлен 10.08.2014Необходимые условия экстремума. Разработка машинного алгоритма и программы многомерной оптимизации для градиентного метода с использованием метода равномерного поиска. Проверка необходимых и достаточных условий экстремума для найденной точки минимума.
курсовая работа [249,8 K], добавлен 25.09.2013Обучение простейшей и многослойной искусственной нейронной сети. Метод обучения перцептрона по принципу градиентного спуска по поверхности ошибки. Реализация в программном продукте NeuroPro 0.25. Использование алгоритма обратного распространения ошибки.
курсовая работа [1019,5 K], добавлен 05.05.2015Оптимизация решения задачи с помощью алгоритма отжига. Анализ теории оптимизации как целевой функции. Метод градиентного спуска. Переменные и описание алгоритма отжига. Представление задачи коммивояжера через граф. Сведение задачи к переменным и решение.
курсовая работа [784,0 K], добавлен 21.05.2015Программная реализация приложения для вычисления заданных функций. Процедура поиска минимума функции. Применение методов Хука-Дживса и градиентного спуска для решения задачи. Исследование функции в окрестности базисной точки, определение ее координат.
контрольная работа [767,1 K], добавлен 02.02.2014Решение задачи на тему максимизации функций многих переменных. Описание метода дихотомии, его применение для решения нелинейных уравнений. Решение данной задачи с использованием метода покоординатного спуска. Составление алгоритмов, листинг программы.
курсовая работа [138,5 K], добавлен 01.10.2009Метод численного интегрирования. Использование метода половинного деления для решения нелинейного уравнения. Определение отрезка неопределенности для метода половинного деления. Получение формулы Симпсона. Уменьшение шага интегрирования и погрешности.
курсовая работа [3,0 M], добавлен 21.05.2013Решение задачи минимизации среднеквадратичной интенсивности управления. Использование формулы Коши и приращения критерия качества. Применение программы конечного двойственного метода линейно квадратичного программирования. Выбор метода корректировки.
курсовая работа [262,0 K], добавлен 23.02.2016Преобразование формулы и решение ее с помощью Метода Эйлера. Моделирование метода оптимизации с функцией Розенброка. Поиск модели зашумленного сигнала. Нахождение минимума заданной целевой функции методом покоординатного спуска нулевого порядка.
курсовая работа [1,2 M], добавлен 21.12.2013