Участник:Margarita/Градиентный спуск

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

Рассмотрим задачу поиска минимума функции [math]\displaystyle{ f(x)\colon \mathbb{R}^n \to \mathbb{R} }[/math]

[math]\displaystyle{ \begin{align} f(x) \rightarrow \min_{x \in \mathbb{R}^n} \end{align} }[/math]

Будем считать, что функция [math]\displaystyle{ f(x) }[/math] такова, что можно вычислить её градиент.

Общее описание алгоритма

Наискорейший спуск — это вариант градиентного спуска: метода нахождения локального экстремума функции с помощью движения вдоль направления градиента.

Математическое описание алгоритма

Основная идея метода состоит в том, чтобы идти в направлении [math]\displaystyle{ -\nabla f }[/math], то есть в направлении, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки:

[math]\displaystyle{ \begin{align} x^{k+1} = x^{k} - \lambda^{k}(\nabla f), \end{align} }[/math]

где выбирается [math]\displaystyle{ \lambda^{k} }[/math]по следующему правилу: [math]\displaystyle{ \lambda^{k} = \operatorname{arg}\min_{\lambda} f(x^{k} - \lambda^{k}(\nabla f)) }[/math].