Математика / Начала анализа

Градиентный спуск с постоянным шагом: условие убывания

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

Опубликовано: 22 октября 2026 г.Обновлено: 22 октября 2026 г.

Оптимизация и исследование операций Численные методы Математический анализ Страницы с задачами и решениями Есть историческая справка

Формула

x_{k+1}=x_k-\alpha\nabla f(x_k),\quad 0<\alpha<2/L,\quad f(x_{k+1})\le f(x_k)-\alpha(1-L\alpha/2)\|\nabla f(x_k)\|^2

Схема Спуск по двум координатам

В жёсткой координате y движение завершилось за шаг; x продолжает уменьшаться.

Обозначения

$x_k$: вектор текущих координат, безразмерно
$α$: положительная длина шага по градиенту, единица координаты / единица градиента
$∇f$: градиент целевой функции, единица функции / единица координаты
$L$: константа Липшица градиента, единица функции / квадрат единицы координаты

Условия применения

Функция дифференцируема, её градиент L-липшицев на области, содержащей каждый рассматриваемый отрезок шага. Координаты согласованно масштабированы, направление не ограничено внешними условиями. Для строгого убывания при ненулевом градиенте достаточно 0 < α < 2/L.

Ограничения

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

Подробное объяснение

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

Для L-липшицева градиента квадратичная верхняя оценка имеет вид f(x+s) ≤ f(x)+∇f(x)·s+(L/2)‖s‖². Подставляя s = −α∇f(x), получаем приведённое неравенство убывания. Его коэффициент положителен ровно при α между нулём и 2/L.

Особенно наглядно поведение квадрата f(x) = qx²/2. Итерация превращается в xₖ₊₁ = (1−αq)xₖ. Сходимость к нулю требует |1−αq| < 1. Малый шаг медленно уменьшает координату, шаг между 1/q и 2/q меняет её знак, а шаг выше 2/q увеличивает модуль.

Для симметричной положительно определённой квадратичной формы роль q играют собственные значения матрицы. Наибольшее задаёт безопасный предел, а наименьшее определяет медленный режим. Предварительное масштабирование координат может заметно улучшить этот баланс.

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

Как пользоваться формулой

Запишите функцию в согласованных координатах, вычислите её градиент и обоснуйте верхнюю границу L на нужной области.
Выберите положительный шаг меньше 2/L; значение 1/L даёт простой безопасный вариант при верной оценке гладкости.
Вычислите все компоненты градиента в прежней точке и одновременно обновите координаты по выбранному направлению.
Контролируйте фактическое убывание и норму градиента; при нарушении прогноза пересмотрите L, масштаб или подбор шага.

Историческая справка

Градиентные методы входят в вычислительную традицию последовательного улучшения приближения по локальной информации о функции. Во второй половине XX века анализ шага и скорости сходимости стал центральной частью численной оптимизации. Работа Ларри Армихо 1966 года рассматривает градиентные схемы для функций с липшицевыми первыми производными и допускает переменный шаг. Современные курсы отделяют простую формулу направления от выбора длины: в лекциях Райана Тибширани показаны как медленное движение при малом шаге, так и расходимость при большом. Приведённый постоянный шаг — учебная форма этого семейства, а не утверждение, что вся градиентная оптимизация была создана одним автором или в одной публикации.

Историческая линия формулы

Градиентный спуск — семейство методов, различающихся правилом шага, нормой и условиями задачи. Здесь используется евклидово направление и постоянный скалярный шаг. Статья Армихо служит источником контекста анализа гладкости, а не заявлением о его авторстве всей идеи спуска.

Пример

Рассмотрим f(x,y) = (x²+4y²)/2, начальную точку (2,1) и α = 0,25. Градиент равен (x,4y), а L = 4 — наибольшее собственное значение диагональной матрицы. Условие 0 < 0,25 < 0,5 выполнено. Первый градиент (2,4), поэтому новая точка (2−0,25·2; 1−0,25·4) = (1,5;0). Значение уменьшилось с 4 до 1,125. Следующая точка (1,125;0), значение 0,6328125. Верхняя оценка первого шага даёт f₁ ≤ 4−0,25·(1−4·0,25/2)·20 = 1,5; фактическое 1,125 ниже этой границы. Все координаты безразмерны. Быстрое обнуление y здесь связано с выбранным шагом и не означает завершения оптимизации по x.

Частая ошибка

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

Практика

Задачи с решением

Осцилляция

Условие. Для f(x)=x²/2, x₀=2, α=1,5 найдите x₁ и x₂.

Решение. Итерация xₖ₊₁ = −0,5xₖ даёт x₁ = −1 и x₂ = 0,5. Модуль убывает, хотя знак меняется.

Ответ. −1; 0,5.

Слишком большой шаг

Условие. Для той же функции возьмите α=3 и x₀=1. Найдите первые две точки.

Решение. Множитель равен 1−3 = −2. Получаем −2 и 4; значения функции растут с 0,5 до 2 и 8.

Ответ. x₁ = −2, x₂ = 4; расходимость.

Дополнительные источники

https://stat.cmu.edu/~ryantibs/statcomp-F15/lectures/optimization.html
https://train.rse.ox.ac.uk/material/HPCu/scientific_computing/optimisation/02-line-search-methods
https://msp.org/pjm/1966/16-1/pjm-v16-n1-p01-s.pdf

Связанные формулы

Математика

Метод золотого сечения: сужение интервала минимума

$\tau=\frac{\sqrt5-1}{2},\quad u=a+(1-\tau)(b-a),\quad v=a+\tau(b-a),\quad L_n=\tau^nL_0$

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

Математика

Тернарный поиск минимума непрерывной унимодальной функции

$u=a+\frac{b-a}{3},\quad v=b-\frac{b-a}{3},\quad [a,b]\leftarrow\begin{cases}\left[u,b\right],&f(u)>f(v),\\\left[a,v\right],&f(u)\le f(v),\end{cases}\quad L_n=(2/3)^nL_0$

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

Математика

Параболическая интерполяция для поиска минимума функции

$A=\frac{(f_3-f_2)/(x_3-x_2)-(f_2-f_1)/(x_2-x_1)}{x_3-x_1},\quad B=\frac{f_2-f_1}{x_2-x_1}-A(x_1+x_2),\quad x_p=-\frac{B}{2A}$

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

Математика

Правило Армихо: обратный поиск длины шага спуска

$f(x+\alpha p)\le f(x)+c\alpha\nabla f(x)^Tp,\quad \nabla f(x)^Tp<0,\quad \alpha\leftarrow\beta\alpha,\quad 0<c<1,\ 0<\beta<1$

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