Метод градиентного спуска

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
Строка 3: Строка 3:
{{eqno|1}}
{{eqno|1}}
::<tex>f(x) \to \min_{x \in \mathbb{R}^n}</tex>
::<tex>f(x) \to \min_{x \in \mathbb{R}^n}</tex>
 +
 +
Пусть функция <tex>f(x)</tex> такова, что можно вычислить ее градиент.
== Метод градиентного спуска ==
== Метод градиентного спуска ==
Строка 8: Строка 10:
=== Идея метода ===
=== Идея метода ===
-
Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом <tex>-\nabla f</tex>:
+
Основная идея метода заключается в том, чтобы осуществлять оптимизацию в направлении наискорейшего спуска, а это направление задаётся антиградиентом <tex>-\nabla f</tex>:
<tex>x^{[j+1]}=x^{[j]}-\lambda^{[j]}\nabla f(x^{[j]}) </tex>
<tex>x^{[j+1]}=x^{[j]}-\lambda^{[j]}\nabla f(x^{[j]}) </tex>
Строка 15: Строка 17:
*постоянной, в этом случае метод может расходиться;
*постоянной, в этом случае метод может расходиться;
*дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
*дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
-
*наискорейшим спуском: <tex>\lambda^{[j]}=\arg \min_{\lambda} \,f(x^{[j]}-\lambda\nabla f(x^{[j]})) \!</tex>
+
*наискорейшим спуском: <tex>\lambda^{[j]}=\arg \min_{\lambda} \,f(x^{[j]}-\lambda\nabla f(x^{[j]})) </tex>
=== Алгоритм ===
=== Алгоритм ===
Строка 23: Строка 25:
# Повторять:
# Повторять:
-
# <tex>x^{[j+1]}=x^{[j]}-\lambda^{[j]}\nabla f(x^{[j]}) </tex>, где <tex>\lambda^{[j]}=\arg\min_{\lambda} \,f(x^{[j]}-\lambda \nabla f(x^{[j]})) </tex> или другой метод выбора <tex>\lambda^{[j]}</tex>
+
# <tex>x^{[j+1]}=x^{[j]}-\lambda^{[j]}\nabla f(x^{[j]}) </tex>, где <tex>\lambda^{[j]}</tex> выбирается одним из описанных выше способов
# если выполен критерий останова, то возвращаем текущее значение <tex>x^{[j+1]}</tex>
# если выполен критерий останова, то возвращаем текущее значение <tex>x^{[j+1]}</tex>
Строка 36: Строка 38:
===Сходимость метода===
===Сходимость метода===
 +
'''Теорема 1 о сходимости метода градиентного спуска спуска с постоянным шагом.'''
 +
Пусть <tex>\lambda^{[k]}=\lambda=const</tex>, функция <tex>f</tex> дифференцируема, ограничена снизу. Пусть выполняется условие Липшица для градиента <tex>f'(x)</tex>:
 +
<tex>||f'(x)-f'(y)|| \leq L ||x-y||</tex>.
 +
Пусть <tex>0<\lambda<2/L</tex>.
 +
 +
Тогда <tex>\lim_{k \to \infty}f'(x^{[k]}) = 0, \; f(x^{[k+1]})<f(x^{[k]}) </tex> при любом выборе начального приближения.
 +
 +
В условиях теоремы градиентный метод обеспечивает сходимость <tex>\{ x^{[k]} \}</tex> либо к точной нижней грани <tex>\inf_x f(x)</tex> (если функция <tex>f(x)</tex> не имеет минимума) либо к значению <tex>f(x*): \;\lim_{k \to \infty}x^{[k]} = x*,\; f'(x*)=0.</tex> Существуют примеры, когда в точке <tex>x*</tex> реализуется седло, а не минимум. Тем не менее, на практике методы градиентного спуска обычно обходят седловые точки и находят локальные минимумы целевой функции.
 +
 +
'''Определение.''' Дифференцируемая функция <tex>f</tex> называется сильно выпуклой (с константой <tex>l>0</tex>), если для любых <tex>x</tex> и <tex>y</tex> из <tex>\mathbb{R}^n</tex> справедливо
 +
 +
::<tex>f(x+y)\geq f(x)+ \langle f'(x) ,y \rangle + l||y||^2/2 .</tex>
 +
 +
'''Теорема 2 о сходимости метода градиентного спуска спуска с постоянным шагом.'''
 +
 +
Пусть функция <tex>f</tex> дифференцируема, сильно выпукла. Пусть выполняется условие Липшица для градиента <tex>f'(x)</tex>:
 +
<tex>||f'(x)-f'(y)|| \leq L ||x-y||</tex>.
 +
Пусть <tex>0<\lambda<2/L</tex>.
 +
 +
Тогда <tex>\lim_{k \to \infty}x^{[k]} = x*, \; ||x^{[k]}-x*||\leq Cq^k, \; 0<q<1</tex> при любом выборе начального приближения.
== Числовые примеры ==
== Числовые примеры ==
== Рекомендации программисту ==
== Рекомендации программисту ==
Строка 47: Строка 69:
* ''Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков.''&nbsp; Численные методы. Лаборатория Базовых Знаний, 2003.
* ''Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков.''&nbsp; Численные методы. Лаборатория Базовых Знаний, 2003.
* ''Н.Н.Калиткин.''&nbsp; Численные методы. Москва «Наука», 1978.
* ''Н.Н.Калиткин.''&nbsp; Численные методы. Москва «Наука», 1978.
 +
* ''Н.И.Глебов, Ю.А.Кочетов, А.В.Плясунов.''&nbsp;Методы оптимизации. 2000.
 +
 +
{{stub}}
{{stub}}
[[Категория:Учебные задачи]]
[[Категория:Учебные задачи]]

Версия 11:52, 20 ноября 2008

Содержание

Постановка задачи

Рассмотрим задачу поиска минимума функции f(x): \mathbb{R}^n \to \mathbb{R} , записываемую в виде:

(1)
f(x) \to \min_{x \in \mathbb{R}^n}

Пусть функция f(x) такова, что можно вычислить ее градиент.

Метод градиентного спуска

Идея метода

Основная идея метода заключается в том, чтобы осуществлять оптимизацию в направлении наискорейшего спуска, а это направление задаётся антиградиентом -\nabla f:

x^{[j+1]}=x^{[j]}-\lambda^{[j]}\nabla f(x^{[j]})

где \lambda^{[j]} выбирается

  • постоянной, в этом случае метод может расходиться;
  • дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
  • наискорейшим спуском: \lambda^{[j]}=\arg \min_{\lambda} \,f(x^{[j]}-\lambda\nabla f(x^{[j]}))

Алгоритм

Вход: функция f: \mathbb{R}^n \to \mathbb{R}

Выход: найденная точка оптимума x

  1. Повторять:
  2. x^{[j+1]}=x^{[j]}-\lambda^{[j]}\nabla f(x^{[j]}) , где \lambda^{[j]} выбирается одним из описанных выше способов
  3. если выполен критерий останова, то возвращаем текущее значение x^{[j+1]}

Критерий останова

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

  1. ||x^{[k+1]}-x^{[k]}||\leq\eps
  2. ||f(x^{[k+1]})-f(x^{[k]})||\leq\eps

Здеcь x^{[k]} \in \mathbb{R}^n - значение, полученное после k-го шага оптимизации. \eps - наперед заданное положительное число.

Сходимость метода

Теорема 1 о сходимости метода градиентного спуска спуска с постоянным шагом.

Пусть \lambda^{[k]}=\lambda=const, функция f дифференцируема, ограничена снизу. Пусть выполняется условие Липшица для градиента f'(x): ||f'(x)-f'(y)|| \leq L ||x-y||. Пусть 0<\lambda<2/L.

Тогда \lim_{k \to \infty}f'(x^{[k]}) = 0, \; f(x^{[k+1]})<f(x^{[k]}) при любом выборе начального приближения.

В условиях теоремы градиентный метод обеспечивает сходимость \{ x^{[k]} \} либо к точной нижней грани \inf_x f(x) (если функция f(x) не имеет минимума) либо к значению f(x*): \;\lim_{k \to \infty}x^{[k]} = x*,\; f'(x*)=0. Существуют примеры, когда в точке x* реализуется седло, а не минимум. Тем не менее, на практике методы градиентного спуска обычно обходят седловые точки и находят локальные минимумы целевой функции.

Определение. Дифференцируемая функция f называется сильно выпуклой (с константой l>0), если для любых x и y из \mathbb{R}^n справедливо

f(x+y)\geq f(x)+ \langle f'(x) ,y \rangle + l||y||^2/2 .

Теорема 2 о сходимости метода градиентного спуска спуска с постоянным шагом.

Пусть функция f дифференцируема, сильно выпукла. Пусть выполняется условие Липшица для градиента f'(x): ||f'(x)-f'(y)|| \leq L ||x-y||. Пусть 0<\lambda<2/L.

Тогда \lim_{k \to \infty}x^{[k]} = x*, \; ||x^{[k]}-x*||\leq Cq^k, \; 0<q<1 при любом выборе начального приближения.

Числовые примеры

Рекомендации программисту

Заключение

Ссылки

Список литературы

  • А.А.Самарский, А.В.Гулин.  Численные методы. Москва «Наука», 1989.
  • Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков.  Численные методы. Лаборатория Базовых Знаний, 2003.
  • Н.Н.Калиткин.  Численные методы. Москва «Наука», 1978.
  • Н.И.Глебов, Ю.А.Кочетов, А.В.Плясунов. Методы оптимизации. 2000.


Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0»
Личные инструменты