Метод градиентного спуска — это один из базовых численных подходов для нахождения минимума функции нескольких переменных. Его часто используют тогда, когда нужно постепенно приближаться к точке, в которой значение функции становится меньше. В этой статье рассмотрим основную идею метода, запишем итерационную формулу, объясним роль длины шага и покажем, как можно вычислять градиент, если частные производные не заданы явно.
Метод Градиентного Спуска: Основная Идея Минимизации
Рассмотрим функцию нескольких переменных
\[ 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) \), затем значение функции последовательно уменьшалось, а процесс завершился тогда, когда расстояние между двумя соседними приближениями стало меньше заданной точности.
Что Рассмотреть Дальше: Полезные Темы для Продолжения
Метод градиентного спуска хорошо показывает базовую идею движения к минимуму с помощью градиента. Но в численной оптимизации есть и другие подходы. Именно они помогают лучше сравнить разные способы минимизации функций нескольких переменных.
- Метод покоординатного спуска: Минимизация шаг за шагом — В этой статье речь пойдет о поиске минимума через последовательное изменение отдельных координат функции нескольких переменных.
- Метод Ньютона: Минимизация функции многих переменных — Материал покажет, как в минимизации используют не только градиент, но и информацию о кривизне функции.
- Метод Ньютона с параметром: Управляемое движение к минимуму — В статье будет рассмотрено, как параметр шага помогает сделать метод Ньютона более управляемым во время минимизации.
Метод Градиентного Спуска в Коде: От Схемы до Собственной Программы
После теории и практического примера стоит сделать еще один полезный шаг — попробовать реализовать метод самостоятельно. Готовая блок-схема из этого раздела поможет превратить математическую идею в понятный программный алгоритм для поиска минимального значения функции нескольких переменных методом градиентного спуска. Вы можете взять ее за основу и написать небольшую программу на любимом языке программирования. Так вы не только проверите результат вычислений, но и лучше увидите, как выбор начальной точки, шага и условия остановки влияет на работу метода.
