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

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

Перейти к: навигация, поиск

Содержание

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

Рассмотрим задачу поиска минимума функции 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»
Личные инструменты