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

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

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

$\begin{align} f(x) \rightarrow \min_{x \in \mathbb{R}^n} \end{align}$

Будем считать, что у функции $f(x)$ существуют частные производные.

Если в задаче требуется найти максимум, вместо $f(x)$ следует брать $-f(x)$.

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

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

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

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

Основная идея метода состоит в том, чтобы идти в направлении антиградиента $-\nabla f$ (отсюда название метода), то есть в направлении, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки:

$\begin{align} x_{k+1} = x_{k} - \alpha_{k}\nabla f(x_{k}), \end{align}$

где $\alpha_{k}$ выбирается по одному из следующих правил:

• постоянной, в таком случае метод может не сходиться;
• дробным шагом, то есть во время итерации длина шага делится на некоторое число;
• наискорейшим спуском, где $\alpha_{k} = \operatorname{arg}\min_{\alpha} f(x_{k} - \alpha_{k}\nabla f(x_{k}))$.

1.5 Схема реализации последовательного алгоритма

Алгоритм:

1. Выбираем начальную точку $x_{0}, \varepsilon$.
2. Вычисляем $x_{k+1} = x_{k} - \alpha_{k}\nabla f(x_{k})$, где $\alpha_{k}$ выбирается одним из описанных выше способом.
3. Если выполнено условие останова, то возвращаем $x_{k+1}$, иначе переходим к шагу 2.

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

• $\| x_{k+1} - x_{k} \| \lt \varepsilon$;
• $\| f(x_{k+1}) - f(x_{k}) \| \lt \varepsilon$;
• $\| \nabla f(x_{k+1}) \| \lt \varepsilon$;