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

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

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

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

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

Формула

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

Схема Правило Армихо: отклонить и сократить

Проверяется доля линейного прогноза, а не только знак изменения.

Обозначения

$x$: текущая точка, безразмерно
$p$: фиксированное направление спуска, единица координаты
$α$: множитель направления, безразмерно
$c$: доля линейно предсказанного уменьшения, безразмерно
$β$: коэффициент уменьшения пробного шага, безразмерно
$∇f(x)^Tp$: производная вдоль направления, единица функции

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

Направление p фиксировано на время поиска и удовлетворяет ∇f(x)ᵀp < 0. Функция непрерывно дифференцируема в окрестности x, а пробные точки лежат в области определения. Параметры c и β находятся между нулём и единицей; начальный пробный шаг положителен.

Ограничения

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

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

Линейная модель предсказывает изменение α∇f(x)ᵀp, которое отрицательно для направления спуска. Условие Армихо требует получить хотя бы долю c этого прогнозируемого уменьшения. Правая часть меньше f(x), поэтому принятый ненулевой шаг действительно снижает функцию.

Начинают с пробного α₀, часто с единицы в подходящем масштабе. Если условие не выполнено, шаг умножают на β. Направление и градиент в исходной точке при этом не пересчитывают: меняется только длина движения. Новый градиент понадобится после принятия точки внешним алгоритмом.

Дифференцируемость даёт f(x+αp) = f(x)+α∇f(x)ᵀp+o(α). Так как c < 1 и направленная производная отрицательна, достаточно малый шаг удовлетворит проверке. Это локальное объяснение конечного завершения при точных вычислениях и допустимых пробных точках.

Параметр c задаёт строгость требования, а β — скорость сокращения. Близкое к единице β перебирает более густую сетку длин, но требует больше вызовов функции. Малое β быстро отступает от неудачной пробы, иногда принимая существенно более короткий шаг, чем необходимо.

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

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

Найдите направление p и скалярное произведение градиента с ним; продолжайте только при строго отрицательном результате.
Задайте начальную длину α₀ и параметры c, β между нулём и единицей; сохраните функцию и градиент исходной точки.
Проверьте допустимость новой точки и неравенство Армихо; при отказе уменьшите α в β раз, сохраняя направление.
Примите первый прошедший шаг и лишь затем обновите точку и градиент; запишите число сокращений для диагностики.

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

Ларри Армихо опубликовал в Pacific Journal of Mathematics в 1966 году работу о минимизации функций с липшицевыми непрерывными первыми частными производными. Она рассматривает сходимость градиентных схем и модификации с переменным шагом. В современной терминологии имя Армихо закрепилось за условием достаточного уменьшения, которое сравнивает фактическую функцию с долей линейного прогноза. Университетские курсы обычно сочетают это условие с обратным поиском: начинают с пробной длины и последовательно сокращают её. Важно различать историческую теорему с её предпосылками, современную форму неравенства и отдельное правило перебора шагов. Само имя условия не отменяет проверки направления и допущений конкретного алгоритма.

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

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

Пример

Пусть f(x) = x², текущая точка x = 1, направление p = −f′(1) = −2. Возьмём c = 0,1, β = 0,5 и α₀ = 1. Направленная производная равна 2·(−2) = −4. При α = 1 новая точка −1, значение f = 1, а правая часть условия равна 1−0,1·4 = 0,6. Проверка 1 ≤ 0,6 неверна. Сокращаем шаг до 0,5: новая точка 0, значение 0, правая часть 1−0,1·0,5·4 = 0,8. Условие 0 ≤ 0,8 выполнено, шаг принимается. Функция уменьшилась с 1 до 0 после одного сокращения. Величины безразмерны; в общей задаче начальный шаг зависит от масштаба направления, поэтому число 1 не имеет универсального физического смысла.

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

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

Практика

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

Проверка короткой пробы

Условие. Для примера с x=1, p=−2, c=0,1 проверьте α=0,25.

Решение. Новая точка 0,5, функция 0,25. Правая часть равна 1−0,1·0,25·4 = 0,9, поэтому проба проходит.

Ответ. Проходит: 0,25 ≤ 0,9.

Неверное направление

Условие. При f(x)=x², x=1 выбран p=1. Допустим ли запуск стандартного обратного поиска спуска?

Решение. Произведение градиента на направление равно 2·1 = 2 > 0. Условие направления спуска нарушено; его нужно изменить до поиска длины.

Ответ. Нет: направление повышает функцию в первом порядке.

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

https://msp.org/pjm/1966/16-1/pjm-v16-n1-p01-s.pdf
https://optimization.cbe.cornell.edu/index.php?title=Line_search_methods
https://stat.cmu.edu/~ryantibs/statcomp-F15/lectures/optimization.html

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

Математика

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

$\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}$

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

Математика

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

$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$

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