Условия Армихо

Материал из MachineLearning.

Версия от 20:26, 18 июля 2026; Kamilia Gibadullina (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Перейти к: навигация, поиск

Содержание

1 Условие Армихо

Условие Армихо

Во многих методах оптимизации новое приближение строится по правилу

$x_{k+1}=x_k+\alpha p_k,$

где $x_k$ — текущая точка, $p_k$ — выбранное направление движения, а $\alpha$ — длина шага.

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

Условие Армихо — это простой способ проверить, обеспечивает ли выбранный шаг достаточное уменьшение целевой функции. Оно лежит в основе многих вариантов поиска шага с возвратом и было предложено Ларри Армихо в работе 1966 года.

Основная идея

Пусть требуется минимизировать функцию $f(x)$ . В текущей точке $x_k$ выбирается направление спуска $p_k$ . Для него выполняется условие

$\nabla f(x_k)^{T}p_k \lt 0$

Здесь $\nabla f(x_k)$ — градиент функции, а выражение $\nabla f(x_k)^T p_k$ показывает, как функция изменяется при движении в направлении $p_k$ . Отрицательное значение означает, что при достаточно маленьком шаге функция будет уменьшаться.

Условие Армихо имеет вид

$f(x_k+\alpha p_k)\leq f(x_k)+c\alpha\nabla f(x_k)^T p_k.$

Левая часть — значение функции после пробного шага. Правая часть задаёт уровень уменьшения, который считается достаточным. Поскольку направление является направлением спуска, выражение $\nabla f(x_k)^T p_k$ отрицательно. Поэтому правая часть меньше текущего значения $f(x_k)$ .

Параметр $c$ выбирается между нулём и единицей:

$0 \lt c \lt 1$

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

Поиск шага с возвратом

На практике условие Армихо часто применяется в алгоритме поиска шага с возвратом. Сначала проверяется достаточно большой шаг. Если он не подходит, его постепенно уменьшают.

Алгоритм можно описать следующим образом:

Выбирается начальная длина шага $\alpha_0$ .
Выполняется пробный переход из точки $x_k$ в точку $x_k+\alpha p_k$ .
Для пробной точки проверяется условие Армихо.
Если условие не выполнено, шаг уменьшается по правилу $\alpha=\beta\alpha$ .
Проверка повторяется до тех пор, пока не будет найден подходящий шаг.

Параметр $\beta$ также находится между нулём и единицей. Например, при $\beta=0{,}5$ длина шага после каждой неудачной проверки уменьшается в два раза.

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

Пример

Рассмотрим функцию одной переменной

$f(x)=x^2.$

Пусть текущая точка равна $x_k=1$ . Производная функции имеет вид $f'(x)=2x$ , поэтому в этой точке $f'(1)=2$ . Выберем направление антиградиента:

$p_k=-2.$

Пусть начальный шаг равен $\alpha=1$ , а параметр условия Армихо равен $c=0{,}25$ . После пробного шага получаем

$x_k+\alpha p_k=1+1\cdot(-2)=-1.$

В новой точке значение функции равно $f(-1)=1$ . Правая часть условия Армихо равна

$1+0{,}25\cdot1\cdot2\cdot(-2)=0.$

Неравенство $1\leq0$ неверно, поэтому шаг слишком большой.

Уменьшим его в два раза и возьмём $\alpha=0{,}5$ . Тогда новая точка равна нулю, а значение функции также равно нулю. Правая часть условия теперь равна $0{,}5$ . Неравенство $0\leq0{,}5$ выполняется, поэтому шаг принимается.

Выбор параметров

В поиске с возвратом обычно настраиваются три величины: начальный шаг $\alpha_0$ , параметр достаточного уменьшения $c$ и коэффициент сокращения $\beta$ .

Чем ближе $c$ к нулю, тем легче выполнить условие Армихо. При большем $c$ от шага требуется более заметное уменьшение функции.

Малое значение $\beta$ позволяет быстро сокращать неудачный шаг, но иногда приводит к слишком резкому уменьшению. Если $\beta$ близко к единице, шаг подбирается точнее, однако может потребоваться больше проверок функции.

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

Применение

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

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

Преимущества и ограничения

К преимуществам условия Армихо относятся:

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

У метода есть и ограничения:

иногда требуется несколько дополнительных вычислений функции;
найденный шаг не обязательно является наилучшим;
результат зависит от начального шага и параметров $c$ и $\beta$ ;
условие контролирует уменьшение функции, но не полностью оценивает качество шага;
может быть принят слишком маленький шаг, хотя более длинный шаг тоже был бы подходящим.

Связь с другими условиями выбора шага

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

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

См. также

Литература

Armijo L. Minimization of Functions Having Lipschitz Continuous First Partial Derivatives // Pacific Journal of Mathematics. — 1966. — Vol. 16, No. 1. — P. 1–3
Nocedal J., Wright S. J. Numerical Optimization. — 2nd ed. — New York: Springer, 2006
Boyd S., Vandenberghe L. Convex Optimization. — Cambridge: Cambridge University Press, 2004.
Bertsekas D. P. Nonlinear Programming. — 3rd ed. — Belmont: Athena Scientific, 2016.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%81%D0%BB%D0%BE%D0%B2%D0%B8%D1%8F_%D0%90%D1%80%D0%BC%D0%B8%D1%85%D0%BE»