10.2. Поиск вдоль направления#
Пусть на шаге алгоритма оптимизации текущее приближение минимума равняется \(\mathbf{x}_k\) и выбрано направление убывания функции \(\mathbf{d}_k\). Построим скалярную функцию \(\phi(\alpha): \real \to \real\)
Логично подбирать амплитуду шага \(\alpha\) такой, которая в точности минимизирует \(\phi(\alpha)\)
однако данный подход вычислительно трудоёмок. Поэтому на практике шаг \(\alpha\) находят приближённо, т.е. решают задачу
Для решения этой задачи применяют поиск вдоль направления (line search). Поиск должен с неплохой точностью находить шаг \(\alpha^{*}\) за приемлемое время. Чтобы построить оптимальный по точности и быстродействию алгоритм, используются условия Вольфе.
10.2.1. Условия Вольфе#
Первое условие Вольфе (также условие достаточного убывания, sufficient decrease) требует уменьшения функции
где \(\beta\) – параметр оптимизации, выбираемый в диапазоне \(\beta\in(0,1)\), обычно \(\beta = 10^{-4}\). В правой части (10.4) фактически записано разложение Тейлора \(f\) в точке \(\mathbf{x}_k\).
Приведём также запись условия (10.4) в терминах \(\phi(\alpha)\). Поскольку
то условие (10.4) запишется следующим образом
Отметим также, что справа в выражении стоит прямая \(l(\alpha)\) с отрицательным наклоном \(\beta\phi'(0) < 0\).
Второе (слабое) условие Вольфе (или условие на кривизну, curvature condition) требует увеличения производной вдоль направления \(\mathbf{d}_k\) в новой точке
или
где \(\sigma \in (\beta, 1)\) – параметр оптимизации. Для метода сопряжённых градиентов обычно берут \(\sigma = 0.1\), а для метода Ньютона \(0.9\).
Условие (10.5) допускает большие положительные производные. Используется также его альтернатива – второе сильное условие Вольфе
или
Сильное условие Вольфе (10.6) выделяет небольшие окрестности по \(\alpha\) около локальных минимумов, максимумов и стационарных точек. Размер окрестностей контролирует параметр \(\sigma\).
Итак набор условий (10.4) и (10.5) называют слабыми условиями Вольфе, а набор (10.4) и (10.6) называют сильными условиями Вольфе.
10.2.2. Поиск вдоль направления назад#
Поиск вдоль направления назад строится лишь на первом условии Вольфе (10.4).
Входные данные
функция \(f\),
её градиаент \(\nabla f\),
направление убывания \(\mathbf{d}\),
начальный вектор \(\mathbf{x}_0\),
максимальное значение \(\alpha_0\) (например, для метода Ньютона \(1\)),
шаг масштабирования \(0 < q < 1\).
Алгоритм
Подсчитать значение функции и градиент в начальной точке \(f(\mathbf{x}_0\)), \(\nabla f(\mathbf{x}_0)\).
Проставить \(\alpha \lto \alpha_0\).
Проверить удовлетворение первого условия Вольфе (10.4). Если условие удовлетворено, \(\alpha\) найдено.
Уменьшить \(\alpha\): \(\alpha \lto q \alpha\). Перейти на шаг 3.
Поиск называется «поиском назад» (backtracking), поскольку начинает с крупного \(\alpha\), которое в последствии итеративно уменьшается.
10.2.3. Сильный поиск вдоль направления#
Сильный поиск вдоль направления (strong backtracking) учитывает сильные условия Вольфе и требует более сложного алгоритма.
Поиск делится на фазы локализации (bracketing) и уточнения (zoom).
В фазе локализации происходит поиск интервала \((\alpha_\text{lo}, \alpha_\text{hi})\), в котором гарантируется наличие шагов \(\alpha\), для которых сильные условия Вольфе удовлетворятся. Этот интервал можно обнаружить, если одно из следующих условий выполнено
Первое условие показывает, что выбранное \(\alpha\) приводит к увеличению функции, второе условие является обратным к первому условию Вольфе (10.4), а последнее показывает, что выбранный шаг приводит к точке, где \(\phi(\alpha)\) возрастающая.
В фазе уточнения происходит поиск \(\alpha\) в интервале \((\alpha_\text{lo}, \alpha_\text{hi})\), удовлетворяющее сильным условиям Вольфе. Это можно производить по-разному, самый простой поиск – бинарный, по знаку производной \(\phi'(0)\). Более сложные поиски используют, например, параболическую или кубическую интерполяцию функции \(\phi(\alpha)\) по известным значениям функции \(\phi\) и её производной \(\phi'\), затем в качестве нового приближения \(\alpha\) выбирают минимум интерполяционной модели.
Ниже приводится модифицированная версия сильного линейного поиска назад (Kochenderfer & Wheeler, 2019, стр. 62).
Сильный поиск вдоль направления
"""
strong_backtracking(f, ∇f, x0, d[; α0=1.0, αmax=Inf, β=1e-4, σ=0.9])
Сильный поиск вдоль направления значения α вдоль направления `d`, при котором для функции `f`
выполнятся сильные условия Вольфе в точке `x0 + α*d`.
`∇f` - функция градиента.
Опционально задаётся начальное значение α `α0`, и параметры условий Вольфе:
`β` на первое условие и `σ` - на второе.
(Kochenderfer & Wheeler, Algorithms for Optimization, 2019, стр. 62)
"""
function strong_backtracking(f, ∇f, x0, d; α0=1.0, β=1e-4, σ=0.9)
y0, g0 = f(x0), ∇f(x0)⋅d
@assert g0 < 0 "Направление d не убывающее"
α = α0
yprev, αprev = y0, 0.0
αlo = αhi = NaN
# bracketing phase
# поиск интервала (`αlo`, `αhi`), в котором существует α,
# удовлетворяющее строгим условиям Вольфе
for i in 1:100
y = f(x0 + α*d)
# первое условие Вольфе нарушено или функция увеличилась
if y > y0 + β*α*g0 || y ≥ yprev
αlo, αhi = αprev, α
break
end
g = ∇f(x0 + α*d)⋅d
if abs(g) ≤ -σ*g0 # 2ое условие Вольфе выполнено, `α` найдено
return α
elseif g ≥ 0
αlo, αhi = αprev, α
break
end
yprev, αprev, α = y, α, 2α
end
# zoom phase
# поиск α, для которого выполняются условия Вольфе
ylo = f(x0 + αlo*d)
for i in 1:100
# бинарный поиск, но может быть и интерполяция
α = (αlo + αhi)/2
y = f(x0 + α*d)
if y > y0 + β*α*g0 || y ≥ ylo # `αhi` слишком большое
αhi = α
else
g = ∇f(x0 + α*d)⋅d
# 2ое условие Вольфе удовлетворено, `α` найдено
abs(g) ≤ -σ*g0 && return α
# обновление границ по бинарному поиску на производную
if g ≥ 0
αhi = α
else
αlo = α
end
end
end
@error "Ошибка в линейном поиске, α не найдено"
return NaN
end