Метод наискорейшего спуска: формула шага и зигзаг

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

Идея метода и направление спуска

Пусть нужно минимизировать гладкую функцию $f(\mathbf{x})$ нескольких переменных. В каждой точке градиент $\nabla f(\mathbf{x})$ указывает направление наибыстрейшего роста функции, поэтому антиградиент $-\nabla f(\mathbf{x})$ задаёт направление наибыстрейшего убывания. Общая схема итерации такова:

$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \, \nabla f(\mathbf{x}_k),$

где $\alpha_k > 0$ - длина шага на $k$-й итерации. В обычном градиентном спуске $\alpha_k$ берут постоянной или подбирают по эвристике. В методе наискорейшего спуска шаг определяется строго: мы фиксируем направление $-\nabla f(\mathbf{x}_k)$ и ищем такое $\alpha_k$, при котором функция вдоль этого направления минимальна. Это и есть точный линейный поиск.

Рассчитать для своей задачи

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

Формула оптимального шага

Чтобы найти $\alpha_k$, рассмотрим функцию одной переменной $\varphi(\alpha) = f(\mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k))$ и приравняем её производную к нулю. Для квадратичной функции это даёт замкнутую формулу. Возьмём модельную задачу, на которой строят почти все учебные примеры:

$f(x, y) = \tfrac{1}{2}\left(a x^2 + b y^2\right), \qquad \nabla f = (a x,\; b y).$

Здесь матрица вторых производных (гессиан) постоянна и равна $H = \mathrm{diag}(a, b)$. Подставив шаг в $\varphi(\alpha)$ и взяв производную, получаем оптимальную длину шага:

$\alpha_k = \frac{\mathbf{g}^{\mathsf T}\mathbf{g}}{\mathbf{g}^{\mathsf T} H\, \mathbf{g}}, \qquad \mathbf{g} = \nabla f(\mathbf{x}_k).$

Числитель - квадрат нормы градиента, знаменатель учитывает кривизну функции в направлении градиента. Чем сильнее кривизна вдоль $\mathbf{g}$, тем короче шаг, и наоборот. Эта формула точна для любой квадратичной функции; для произвольной гладкой функции тот же шаг находят численно (например, дроблением шага или методом золотого сечения по $\alpha$).

Рассчитать для своей задачи

На карте линий уровня хорошо видно ключевое свойство: каждый шаг останавливается в точке касания эллипса, а соседние звенья ломаной перпендикулярны. Калькулятор выше строит ровно эту картину для $f(x, y) = \tfrac12(x^2 + b y^2)$ из стартовой точки $(9, 1)$.

Почему траектория идёт зигзагом

Зигзаг - не дефект реализации, а математическое следствие точного линейного поиска. В точке минимума вдоль направления производная $\varphi'(\alpha_k) = 0$, а она равна скалярному произведению нового градиента на старое направление. Значит, $\nabla f(\mathbf{x}_{k+1}) \perp \nabla f(\mathbf{x}_k)$: каждый следующий градиент ортогонален предыдущему. Для функции двух переменных это означает, что все шаги чередуют два взаимно перпендикулярных направления, и ломаная зигзагит между двумя «стенками» оврага.

Чем сильнее вытянуты линии уровня, тем уже этот овраг и тем мельче становятся полезные шаги: метод тратит итерации на метание поперёк оврага вместо движения вдоль него к минимуму. Передвиньте в калькуляторе ползунок кривизны $b$ - при $b$ около единицы линии уровня почти круглые и спуск идёт почти по прямой, а при больших $b$ зигзаг становится частым и заметным.

Число обусловленности и скорость сходимости

Степень вытянутости линий уровня измеряет число обусловленности гессиана - отношение наибольшего собственного значения к наименьшему:

$\kappa = \frac{\lambda_{\max}}{\lambda_{\min}} = \frac{\max(a, b)}{\min(a, b)}.$

Для нашей модельной функции с $a = 1$ и $b = 10$ получаем $\kappa = 10$. Скорость сходимости метода наискорейшего спуска линейная (геометрическая), и её множитель выражается именно через $\kappa$:

$f(\mathbf{x}_{k+1}) - f^{*} \;\le\; \left(\frac{\kappa - 1}{\kappa + 1}\right)^{2}\bigl(f(\mathbf{x}_k) - f^{*}\bigr).$

При $\kappa = 10$ множитель $(\kappa-1)/(\kappa+1) = 0{,}818$, а его квадрат около $0{,}67$: за итерацию значение функции в среднем падает менее чем вдвое. При $\kappa = 1$ (идеально круглые линии уровня) множитель равен нулю - спуск попадает в минимум за один шаг. А при $\kappa \to \infty$ множитель стремится к единице, и метод почти останавливается. Это главный практический вывод: наискорейший спуск страдает от плохо обусловленных задач, и именно поэтому на смену ему приходят метод сопряжённых градиентов и метод Ньютона.

Рассчитать для своей задачи

Пример решения типовой задачи

Разберём стандартную постановку: минимизировать $f(x, y) = \tfrac12(x^2 + 10 y^2)$ методом наискорейшего спуска из точки $(x_0, y_0) = (9, 1)$. Градиент здесь $\nabla f = (x,\; 10 y)$, гессиан $H = \mathrm{diag}(1, 10)$.

В стартовой точке градиент $\mathbf{g}_0 = (9,\; 10)$, его квадрат нормы $\mathbf{g}_0^{\mathsf T}\mathbf{g}_0 = 81 + 100 = 181$. Знаменатель шага $\mathbf{g}_0^{\mathsf T} H \mathbf{g}_0 = 1\cdot 81 + 10\cdot 100 = 1081$. Отсюда оптимальный шаг:

$\alpha_0 = \frac{181}{1081} \approx 0{,}167.$

Делаем шаг и получаем новую точку:

$x_1 = 9 - 0{,}167\cdot 9 \approx 7{,}49, \qquad y_1 = 1 - 0{,}167\cdot 10 \approx -0{,}67.$

Значение функции упало с $f(\mathbf{x}_0) = 45{,}5$ до $f(\mathbf{x}_1) \approx 30{,}3$. Проверка ортогональности: новый градиент $\mathbf{g}_1 = (7{,}49;\; -6{,}74)$, а старое направление было $(9; 10)$. Их скалярное произведение $9\cdot 7{,}49 + 10\cdot(-6{,}74) \approx 0$ - шаги действительно перпендикулярны, как и требует теория. Дальше итерации повторяются, и за каждый шаг функция убывает примерно в полтора раза, что согласуется с множителем $0{,}67$ при $\kappa = 10$. Калькулятор выше собирает ровно эту цепочку, оставляя вам контроль над формулами и числами.

Частые ошибки

• Фиксированный шаг вместо линейного поиска. Метод наискорейшего спуска по определению выбирает $\alpha_k$ точной минимизацией вдоль направления. Если взять постоянный $\alpha$, это уже обычный градиентный спуск, и при неверном выборе он либо расходится, либо ползёт.
• Движение по градиенту, а не против. Спускаемся в направлении $-\nabla f$. Знак минус в формуле $\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla f$ обязателен, иначе вы будете подниматься в максимум.
• Путаница в формуле шага. В числителе $\alpha_k$ стоит $\mathbf{g}^{\mathsf T}\mathbf{g}$, в знаменателе $\mathbf{g}^{\mathsf T} H \mathbf{g}$ с гессианом. Если перепутать местами или забыть $H$, шаг получится неверной длины.
• Ожидание быстрой сходимости при большом $\kappa$. При вытянутых линиях уровня метод честно зигзагит и сходится медленно. Это не ошибка кода, а свойство метода - для таких задач берут сопряжённые градиенты.
• Неверный критерий остановки. Останавливаться надо по малости нормы градиента $\lVert \nabla f \rVert < \varepsilon$, а не по числу шагов наугад: иначе либо недосчитаете, либо потратите лишние итерации.

FAQ

Чем метод наискорейшего спуска отличается от обычного градиентного спуска? Направление у них одно и то же - антиградиент. Разница в длине шага: в наискорейшем спуске $\alpha_k$ выбирается точной одномерной минимизацией вдоль направления, тогда как в обычном градиентном спуске шаг фиксированный или подбирается грубой эвристикой.

Почему соседние шаги перпендикулярны? Потому что шаг останавливается в минимуме функции вдоль направления, а там производная по шагу равна нулю. Эта производная равна скалярному произведению нового градиента на старое направление, значит, новый градиент ортогонален предыдущему шагу.

Почему метод медленно сходится на овражных функциях? Овражная функция имеет большое число обусловленности $\kappa$: линии уровня сильно вытянуты. Множитель сходимости $(\kappa-1)/(\kappa+1)$ при больших $\kappa$ близок к единице, поэтому за итерацию функция убывает совсем немного, а траектория зигзагит поперёк оврага.

Коротко

Метод наискорейшего спуска движется против градиента, выбирая на каждом шаге оптимальную длину $\alpha_k = (\mathbf{g}^{\mathsf T}\mathbf{g})/(\mathbf{g}^{\mathsf T} H \mathbf{g})$ точным линейным поиском. Из условия минимума вдоль направления следует ортогональность соседних шагов, отсюда характерный зигзаг. Скорость сходимости линейна с множителем $(\kappa-1)/(\kappa+1)$ по числу обусловленности $\kappa$: круглые линии уровня дают спуск за один шаг, вытянутые овраги резко его замедляют.