Метод Градиентного Спуска: Как Шаг за Шагом Уменьшать Значение Функции

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

Метод Градиентного Спуска: Основная Идея Минимизации

Рассмотрим функцию нескольких переменных

\[
f(\bar{x})=f(x_1,x_2,\dots,x_n),
\]

где \( \bar{x} \) — это вектор переменных.

Минимизировать такую функцию означает найти такую точку \( \bar{x} \), в которой значение \( f(\bar{x}) \) будет наименьшим или хотя бы локально наименьшим в некоторой области. Само слово «локально» здесь важно. Ведь метод градиентного спуска в общем случае не всегда находит глобальный минимум. Обычно он приводит к локальному минимуму, который зависит от начальной точки и свойств функции.

Чтобы понять, куда двигаться, используют градиент функции. Для функции нескольких переменных он имеет вид

\[
\nabla f(\bar{x})=
\left(
\frac{\partial f}{\partial x_1},
\frac{\partial f}{\partial x_2},
\dots,
\frac{\partial f}{\partial x_n}
\right).
\]

Каждый элемент этого вектора является частной производной. То есть он показывает, как изменяется функция, если менять одну переменную, а все остальные оставить постоянными.

Градиент указывает направление самого быстрого возрастания функции. А нам нужно уменьшать значение функции, не так ли? Поэтому двигаться нужно в противоположном направлении: \( -\nabla f(\bar{x}) \). Это направление называют антиградиентным. Именно оно показывает, в какую сторону нужно сделать шаг, чтобы значение функции уменьшалось быстрее всего вблизи текущей точки.

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

Начальное Приближение: Как Строится Итерационный Процесс

Теперь перейдем от идеи к алгоритму. Сначала нужно выбрать начальное приближение:

\[
\bar{x}^{(0)}=
\left(
x_1^{(0)},
x_2^{(0)},
\dots,
x_n^{(0)}
\right).
\]

Это стартовая точка, с которой начинаются вычисления. Выбор этой точки имеет значение. Если функция сложная и имеет несколько локальных минимумов, то разные начальные точки могут привести к разным результатам.

После выбора \( \bar{x}^{(0)} \) вычисляют градиент в этой точке: \( \nabla f(\bar{x}^{(0)}) \). Далее выполняют первый шаг в направлении антиградиента:

\[
\bar{x}^{(1)}
=
\bar{x}^{(0)}-\alpha\cdot \nabla f(\bar{x}^{(0)}),
\qquad \alpha>0.
\]

Здесь \( \alpha \) — текущая длина шага. Она показывает, насколько далеко мы переходим от начальной точки в направлении убывания функции.

После этого получаем новую точку

\[
\bar{x}^{(1)}=
\left(
x_1^{(1)},
x_2^{(1)},
\dots,
x_n^{(1)}
\right).
\]

На следующей итерации уже работаем не с начальной точкой, а с новым приближением. Поэтому снова вычисляем градиент, но уже в точке \( \bar{x}^{(1)} \), и переходим к точке \( \bar{x}^{(2)} \):

\[
\bar{x}^{(2)}
=
\bar{x}^{(1)}-\alpha\cdot \nabla f(\bar{x}^{(1)}),
\qquad \alpha>0.
\]

Таким образом, шаг за шагом строится последовательность приближений. В общем виде ее можно записать так:

\[
\bar{x}^{(k+1)}
=
\bar{x}^{(k)}-\alpha\cdot \nabla f(\bar{x}^{(k)}),
\qquad k=0,1,2,\dots
\]

где \( \alpha \) — текущая длина шага, которая используется при переходе от \( \bar{x}^{(k)} \) к \( \bar{x}^{(k+1)} \).

Эта формула является основой метода. Она показывает, как из текущей точки \( \bar{x}^{(k)} \) перейти к следующей точке \( \bar{x}^{(k+1)} \). При этом каждый переход выполняется с учетом направления убывания функции.

Длина Шага: Как Избежать Неудачного Перехода

После записи итерационной формулы возникает важный практический вопрос: как выбрать длину шага \( \alpha \)? Ведь именно она определяет, насколько сильно мы сместимся в антиградиентном направлении.

Если шаг слишком мал, метод может двигаться очень медленно. Если же шаг слишком большой, можно перейти слишком далеко и получить не меньшее, а большее значение функции. Поэтому после каждого перехода желательно проверять, действительно ли функция уменьшилась:

\[
f(\bar{x}^{(k+1)})<f(\bar{x}^{(k)}).
\]

Если это условие выполняется, то новую точку можно принять. В таком случае текущее значение \( \alpha \) можно оставить для следующей итерации.

Если же значение функции не уменьшилось или даже увеличилось, тогда длину шага нужно уменьшить. Один из простых способов — разделить шаг пополам:

\[
\alpha \leftarrow \frac{\alpha}{2}.
\]

После этого новую точку вычисляют еще раз, но уже с меньшим шагом:

\[
\bar{x}^{(k+1)}
=
\bar{x}^{(k)}-\alpha\cdot \nabla f(\bar{x}^{(k)}).
\]

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

Однако рано или поздно изменения становятся очень малыми. Поэтому нужно иметь условие остановки. Например, можно завершить вычисления, если норма градиента стала меньше заданной точности:

\[
\|\nabla f(\bar{x}^{(k)})\|<\varepsilon.
\]

Также можно использовать условие близости двух соседних приближений:

\[
\|\bar{x}^{(k+1)}-\bar{x}^{(k)}\|<\varepsilon.
\]

Или условие малого изменения значения функции:

\[
|f(\bar{x}^{(k+1)})-f(\bar{x}^{(k)})|<\varepsilon.
\]

Здесь \( \varepsilon \) — заданная точность вычислений.

С теоретической точки зрения, если локальный минимум достигается внутри области, то в этой точке выполняется условие

\[
\nabla f(\bar{x})=0.
\]

Однако важно помнить: это условие является необходимым, но не всегда достаточным. Точка с нулевым градиентом может быть не только точкой минимума, но и точкой максимума или седловой точкой. Поэтому результат нужно оценивать с учетом свойств функции.

Вычисление Градиента: Что Делать Без Явных Производных

В простых учебных примерах частные производные часто находят аналитически. То есть мы берем заданную функцию, дифференцируем ее по каждой переменной и получаем готовую формулу для градиента.

Но что делать, если частные производные найти сложно? Или если функция задана так, что ее значение можно вычислить, но явный вид производных неудобен? В таком случае элементы градиента можно приближенно вычислять численно.

Для переменной \( x_i \) можно использовать формулу односторонней разности:

\[
\frac{\partial f}{\partial x_i}\approx
\frac{
f(x_1,\dots,x_i+\Delta x_i,\dots,x_n)-
f(x_1,\dots,x_i,\dots,x_n)
}{
\Delta x_i
},
\qquad i=1,2,\dots,n.
\]

Здесь \( \Delta x_i \) — малое приращение переменной \( x_i \). Идея простая: мы немного изменяем одну переменную, оставляем остальные без изменений и смотрим, как изменилось значение функции.

Для большей точности иногда используют центральную разность:

\[
\frac{\partial f}{\partial x_i}\approx
\frac{
f(x_1,\dots,x_i+\Delta x_i,\dots,x_n)-
f(x_1,\dots,x_i-\Delta x_i,\dots,x_n)
}{
2\Delta x_i
}.
\]

Эта формула обычно дает более точное приближение, но требует больше вычислений значений функции. Поэтому на практике выбор способа зависит от того, что важнее: скорость или точность.

Итак, метод градиентного спуска можно применять не только тогда, когда градиент задан явно. Его можно использовать и в численной форме, если мы умеем вычислять значение самой функции.

Практическая Часть: Метод Градиентного Спуска Для Функции Двух Переменных

Теперь рассмотрим, как метод градиентного спуска работает на конкретной функции двух переменных. В таком примере уже нужно не просто записать формулу, а последовательно вычислять градиент, новые приближения и проверять условие остановки. Так наглядно видно, как теоретическая схема превращается в реальный вычислительный процесс.

Пример 1. Найти минимальное значение функции \( f(x_1,x_2)=(x_1-1)^2+(x_2+2)^2 \) с точностью \( \varepsilon=0.05 \) методом градиентного спуска

Рассмотрим функцию:

\[
f(x_1,x_2)=(x_1-1)^2+(x_2+2)^2.
\]

Это функция двух переменных \( x_1 \) и \( x_2 \). Она имеет простой аналитический вид, поэтому с ее помощью удобно показать, как шаг за шагом применяется метод градиентного спуска.

Возьмем начальное приближение

\[
\bar{x}^{(0)}=(3,2).
\]

Также выберем текущую длину шага \( \alpha=0.25 \). Условие остановки будем проверять по правилу

\[
\|\bar{x}^{(k+1)}-\bar{x}^{(k)}\|<0.05.
\]

Для метода градиентного спуска используем формулу

\[
\bar{x}^{(k+1)}
=
\bar{x}^{(k)}
-\alpha\cdot \nabla f(\bar{x}^{(k)}).
\]

Сначала найдем градиент заданной функции. Для этого вычислим частные производные:

\[
\frac{\partial f}{\partial x_1}=2\cdot (x_1-1),
\qquad
\frac{\partial f}{\partial x_2}=2\cdot (x_2+2).
\]

Следовательно,

\[
\nabla f(x_1,x_2)=
\left(
2\cdot (x_1-1),
2\cdot (x_2+2)
\right).
\]

Начинаем первую итерацию. В начальной точке \( \bar{x}^{(0)}=(3,2) \) градиент равен

\[
\nabla f(3,2)=
\left(
2\cdot (3-1),
2\cdot (2+2)
\right)
=
(4,8).
\]

Тогда новое приближение вычисляем так:

\[
\bar{x}^{(1)}
=
(3,2)-0.25\cdot(4,8).
\]

Отсюда

\[
\bar{x}^{(1)}
=
(3,2)-(1,2)=(2,0).
\]

Проверим, уменьшилось ли значение функции. В начальной точке получаем

\[
f(3,2)=(3-1)^2+(2+2)^2=20.
\]

В новой точке имеем

\[
f(2,0)=(2-1)^2+(0+2)^2=5.
\]

Поскольку

\[
5<20,
\]

переход выполнен успешно. Следовательно, текущее значение \( \alpha=0.25 \) можно оставить для следующей итерации.

Теперь проверим условие точности:

\[
\|\bar{x}^{(1)}-\bar{x}^{(0)}\|
=
\sqrt{(2-3)^2+(0-2)^2}.
\]

Поэтому

\[
\|\bar{x}^{(1)}-\bar{x}^{(0)}\|
=\sqrt{1+4}
=\sqrt{5}
\approx 2.236.
\]

Поскольку

\[
2.236>0.05,
\]

вычисления продолжаем.

Переходим ко второй итерации. Берем точку

\[
\bar{x}^{(1)}=(2,0).
\]

Вычисляем градиент в этой точке:

\[
\nabla f(2,0)=
\left(
2\cdot (2-1),
2\cdot (0+2)
\right)
=
(2,4).
\]

Тогда

\[
\bar{x}^{(2)}
=
(2,0)-0.25\cdot(2,4).
\]

Следовательно,

\[
\bar{x}^{(2)}
=
(2,0)-(0.5,1)=(1.5,-1).
\]

Значение функции в этой точке равно

\[
f(1.5,-1)=(1.5-1)^2+(-1+2)^2.
\]

Получаем

\[
f(1.5,-1)=0.5^2+1^2=1.25.
\]

Поскольку

\[
1.250<5,
\]

второй шаг также является успешным. В этом примере после каждого выполненного перехода значение функции уменьшается, поэтому уменьшать шаг \( \alpha \) не нужно.

Проверим точность:

\[
\|\bar{x}^{(2)}-\bar{x}^{(1)}\|
=
\sqrt{(1.5-2)^2+(-1-0)^2}
\approx 1.118.
\]

Поскольку

\[
1.118>0.05,
\]

переходим к следующей итерации.

Продолжение итерационного процесса

Для третьей итерации имеем

\[
\bar{x}^{(2)}=(1.5,-1).
\]

Вычисляем градиент:

\[
\nabla f(1.5,-1)=
\left(
2\cdot (1.5-1),
2\cdot (-1+2)
\right)
=
(1,2).
\]

Тогда

\[
\bar{x}^{(3)}
=
(1.5,-1)-0.25\cdot(1,2).
\]

Отсюда

\[
\bar{x}^{(3)}
=
(1.5,-1)-(0.25,0.5)=(1.25,-1.5).
\]

Вычислим значение функции:

\[
f(1.25,-1.5)=(1.25-1)^2+(-1.5+2)^2.
\]

Поэтому

\[
f(1.25,-1.5)=0.25^2+0.5^2=0.313.
\]

Получаем

\[
0.313<1.25.
\]

Следовательно, значение функции снова уменьшилось.

Теперь проверим условие точности:

\[
\|\bar{x}^{(3)}-\bar{x}^{(2)}\|
=
\sqrt{(1.25-1.5)^2+(-1.5+1)^2}
\approx 0.559.
\]

Поскольку

\[
0.559>0.05,
\]

вычисления продолжаем.

Для четвертой итерации берем

\[
\bar{x}^{(3)}=(1.25,-1.5).
\]

Находим градиент:

\[
\nabla f(1.25,-1.5)=
\left(
2\cdot (1.25-1),
2\cdot (-1.5+2)
\right)
=
(0.5,1).
\]

Тогда

\[
\bar{x}^{(4)}
=
(1.25,-1.5)-0.25\cdot(0.5,1).
\]

Получаем

\[
\bar{x}^{(4)}
=
(1.25,-1.5)-(0.125,0.25)=(1.125,-1.75).
\]

Значение функции равно

\[
f(1.125,-1.75)=(1.125-1)^2+(-1.75+2)^2.
\]

После вычисления имеем

\[
f(1.125,-1.75)=0.125^2+0.25^2=0.078.
\]

Поскольку

\[
0.078<0.313,
\]

переход принимаем.

Проверяем точность:

\[
\|\bar{x}^{(4)}-\bar{x}^{(3)}\|
=
\sqrt{(1.125-1.25)^2+(-1.75+1.5)^2}
\approx 0.280.
\]

Поскольку

\[
0.280>0.05,
\]

нужно выполнить еще одну итерацию.

Для пятой итерации имеем

\[
\bar{x}^{(4)}=(1.125,-1.75).
\]

Вычисляем градиент:

\[
\nabla f(1.125,-1.75)=
\left(
2\cdot (1.125-1),
2\cdot (-1.75+2)
\right)
=
(0.25,0.5).
\]

Тогда

\[
\bar{x}^{(5)}
=
(1.125,-1.75)-0.25\cdot(0.25,0.5).
\]

Отсюда

\[
\bar{x}^{(5)}
=
(1.125,-1.75)-(0.063,0.125)=(1.063,-1.875).
\]

Значение функции в этой точке:

\[
f(1.063,-1.875)=(1.063-1)^2+(-1.875+2)^2.
\]

Следовательно,

\[
f(1.063,-1.875)
\approx 0.063^2+0.125^2
\approx 0.02.
\]

Получаем

\[
0.02<0.078,
\]

поэтому точку \( \bar{x}^{(5)} \) принимаем.

Проверяем условие остановки:

\[
\|\bar{x}^{(5)}-\bar{x}^{(4)}\|
=
\sqrt{(1.063-1.125)^2+(-1.875+1.75)^2}
\approx 0.14.
\]

Поскольку

\[
0.14>0.05,
\]

итерационный процесс пока не завершаем.

Далее выполним еще две итерации в той же последовательности: вычисляем градиент, делаем шаг в направлении антиградиента, проверяем уменьшение функции и условие точности.

Для шестой итерации берем

\[
\bar{x}^{(5)}=(1.063,-1.875).
\]

Градиент в этой точке равен

\[
\nabla f(1.063,-1.875)
\approx
\left(
2\cdot (1.063-1),
2\cdot (-1.875+2)
\right)
=
(0.125,0.25).
\]

Тогда

\[
\bar{x}^{(6)}
=
(1.063,-1.875)-0.25\cdot(0.125,0.25).
\]

Получаем

\[
\bar{x}^{(6)}
=
(1.063,-1.875)-(0.031,0.063)
=
(1.031,-1.938).
\]

Значение функции:

\[
f(1.031,-1.938)
=
(1.031-1)^2+(-1.938+2)^2
\approx 0.005.
\]

Снова видим уменьшение значения функции:

\[
0.005<0.02.
\]

Теперь проверим точность:

\[
\|\bar{x}^{(6)}-\bar{x}^{(5)}\|
=
\sqrt{(1.031-1.063)^2+(-1.938+1.875)^2}
\approx 0.07.
\]

Поскольку

\[
0.07>0.05,
\]

выполняем еще одну итерацию.

Для седьмой итерации имеем

\[
\bar{x}^{(6)}=(1.031,-1.938).
\]

Вычисляем градиент:

\[
\nabla f(1.031,-1.938)
\approx
\left(
2\cdot (1.031-1),
2\cdot (-1.938+2)
\right)
=
(0.063,0.125).
\]

Тогда

\[
\bar{x}^{(7)}
=
(1.031,-1.938)-0.25\cdot(0.063,0.125).
\]

Отсюда

\[
\bar{x}^{(7)}
=
(1.031,-1.938)-(0.016,0.031)
=
(1.016,-1.969).
\]

Вычислим значение функции:

\[
f(1.016,-1.969)
=
(1.016-1)^2+(-1.969+2)^2
\approx 0.001.
\]

Поскольку

\[
0.001<0.005,
\]

последний переход также уменьшил значение функции.

Теперь снова проверяем условие точности:

\[
\|\bar{x}^{(7)}-\bar{x}^{(6)}\|
=
\sqrt{(1.016-1.031)^2+(-1.969+1.938)^2}
\approx 0.035.
\]

Поскольку

\[
0.035<0.05,
\]

итерационный процесс можно завершить.

Последним найденным приближением является

\[
\bar{x}^{(7)}=(1.016,-1.969).
\]

Поэтому приближенно точку минимума можно записать так:

\[
\bar{x}^{*}\approx(1.016,-1.969).
\]

Теперь найдем приближенное минимальное значение функции:

\[
f_{\min}\approx f(1.016,-1.969).
\]

Подставляем найденное приближение:

\[
f(1.016,-1.969)
=
(1.016-1)^2+(-1.969+2)^2.
\]

Следовательно,

\[
f(1.016,-1.969)
=
0.016^2+0.031^2
\approx 0.001.
\]

Таким образом, методом градиентного спуска получаем

\[
\bar{x}^{*}\approx(1.016,-1.969),
\qquad
f_{\min}\approx 0.001.
\]

Для удобства сведем основные результаты итераций в одну таблицу. Она хорошо показывает, как точка постепенно приближается к минимуму, а значение функции уменьшается.

\( k \)	\( \bar{x}^{(k)} \)	\( f(\bar{x}^{(k)}) \)	\( \|\bar{x}^{(k)}-\bar{x}^{(k-1)}\| \)
\( 0 \)	\( (3,2) \)	\( 20 \)	—
\( 1 \)	\( (2,0) \)	\( 5 \)	\( 2.236 \)
\( 2 \)	\( (1.5,-1) \)	\( 1.25 \)	\( 1.118 \)
\( 3 \)	\( (1.25,-1.5) \)	\( 0.313 \)	\( 0.559 \)
\( 4 \)	\( (1.125,-1.75) \)	\( 0.078 \)	\( 0.28 \)
\( 5 \)	\( (1.063,-1.875) \)	\( 0.02 \)	\( 0.14 \)
\( 6 \)	\( (1.031,-1.938) \)	\( 0.005 \)	\( 0.07 \)
\( 7 \)	\( (1.016,-1.969) \)	\( 0.001 \)	\( 0.035 \)

Сравнение с точным ответом

Проверим, как найденный результат согласуется с точным ответом. Для этого вернемся к самой функции:

\[
f(x_1,x_2)=(x_1-1)^2+(x_2+2)^2.
\]

Квадрат любого числа не может быть отрицательным. Поэтому значение функции будет наименьшим тогда, когда оба выражения в скобках будут равны нулю:

\[
x_1-1=0,
\qquad
x_2+2=0.
\]

Отсюда получаем

\[
x_1=1,
\qquad
x_2=-2.
\]

Следовательно, точная точка минимума имеет вид

\[
\bar{x}^{*}=(1,-2).
\]

Соответствующее минимальное значение функции равно

\[
f_{\min}=f(1,-2).
\]

Подставляем точные значения:

\[
f(1,-2)=(1-1)^2+(-2+2)^2=0.
\]

Следовательно,

\[
\bar{x}^{*}=(1,-2),
\qquad
f_{\min}=0.
\]

Полученное методом градиентного спуска приближение

\[
\bar{x}^{*}\approx(1.016,-1.969)
\]

близко к точной точке \( (1,-2) \). Поэтому результат вычислений хорошо согласуется с точным ответом. Вычисления начались с точки \( (3,2) \), затем значение функции последовательно уменьшалось, а процесс завершился тогда, когда расстояние между двумя соседними приближениями стало меньше заданной точности.

Что Рассмотреть Дальше: Полезные Темы для Продолжения

Метод градиентного спуска хорошо показывает базовую идею движения к минимуму с помощью градиента. Но в численной оптимизации есть и другие подходы. Именно они помогают лучше сравнить разные способы минимизации функций нескольких переменных.

1. Метод покоординатного спуска: Минимизация шаг за шагом — В этой статье речь пойдет о поиске минимума через последовательное изменение отдельных координат функции нескольких переменных.
2. Метод Ньютона: Минимизация функции многих переменных — Материал покажет, как в минимизации используют не только градиент, но и информацию о кривизне функции.
3. Метод Ньютона с параметром: Управляемое движение к минимуму — В статье будет рассмотрено, как параметр шага помогает сделать метод Ньютона более управляемым во время минимизации.

Метод Градиентного Спуска в Коде: От Схемы до Собственной Программы

После теории и практического примера стоит сделать еще один полезный шаг — попробовать реализовать метод самостоятельно. Готовая блок-схема из этого раздела поможет превратить математическую идею в понятный программный алгоритм для поиска минимального значения функции нескольких переменных методом градиентного спуска. Вы можете взять ее за основу и написать небольшую программу на любимом языке программирования. Так вы не только проверите результат вычислений, но и лучше увидите, как выбор начальной точки, шага и условия остановки влияет на работу метода.