Поиск вдоль направления

10.2. Поиск вдоль направления#

Пусть на шаге алгоритма оптимизации текущее приближение минимума равняется \(\mathbf{x}_k\) и выбрано направление убывания функции \(\mathbf{d}_k\). Построим скалярную функцию \(\phi(\alpha): \real \to \real\)

(10.3)#\[\phi(\alpha) = f(\mathbf{x}_k + \alpha \mathbf{d}_k).\]

Логично подбирать амплитуду шага \(\alpha\) такой, которая в точности минимизирует \(\phi(\alpha)\)

\[\alpha^{*} = \argmin_{\alpha > 0} \phi(\alpha),\]

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

\[\alpha^{*} \approx \argmin_{\alpha > 0} \phi(\alpha).\]

Для решения этой задачи применяют поиск вдоль направления (line search). Поиск должен с неплохой точностью находить шаг \(\alpha^{*}\) за приемлемое время. Чтобы построить оптимальный по точности и быстродействию алгоритм, используются условия Вольфе.

10.2.1. Условия Вольфе#

Первое условие Вольфе (также условие достаточного убывания, sufficient decrease) требует уменьшения функции

(10.4)#\[f(\mathbf{x}_k + \alpha\mathbf{d}_k) \le f(\mathbf{x}_k) + \beta \alpha \nabla f(\mathbf{x}_k)^\top \mathbf{d}_k,\]

где \(\beta\) – параметр оптимизации, выбираемый в диапазоне \(\beta\in(0,1)\), обычно \(\beta = 10^{-4}\). В правой части (10.4) фактически записано разложение Тейлора \(f\) в точке \(\mathbf{x}_k\).

Приведём также запись условия (10.4) в терминах \(\phi(\alpha)\). Поскольку

\[\phi'(\alpha) = \nabla f(\mathbf{x}_k + \alpha \mathbf{d}_k)^\top \mathbf{d}_k,\]

то условие (10.4) запишется следующим образом

\[\phi(\alpha) \le \phi(0) + \beta \alpha \phi'(0).\]

Отметим также, что справа в выражении стоит прямая \(l(\alpha)\) с отрицательным наклоном \(\beta\phi'(0) < 0\).

Второе (слабое) условие Вольфе (или условие на кривизну, curvature condition) требует увеличения производной вдоль направления \(\mathbf{d}_k\) в новой точке

(10.5)#\[\nabla f(\mathbf{x}_k + \alpha \mathbf{d}_k)^\top \mathbf{d}_k \ge \sigma \nabla f(\mathbf{x}_k)^\top \mathbf{d}_k,\]

или

\[\phi'(\alpha) \ge \sigma \phi'(0).\]

где \(\sigma \in (\beta, 1)\) – параметр оптимизации. Для метода сопряжённых градиентов обычно берут \(\sigma = 0.1\), а для метода Ньютона \(0.9\).

Условие (10.5) допускает большие положительные производные. Используется также его альтернатива – второе сильное условие Вольфе

(10.6)#\[|\nabla f(\mathbf{x}_k + \alpha \mathbf{d}_k)^\top \mathbf{d}_k| \le -\sigma \nabla f(\mathbf{x}_k)^\top \mathbf{d}_k,\]

или

\[|\phi'(\alpha)| \le -\sigma \phi'(0).\]

Сильное условие Вольфе (10.6) выделяет небольшие окрестности по \(\alpha\) около локальных минимумов, максимумов и стационарных точек. Размер окрестностей контролирует параметр \(\sigma\).

Итак набор условий (10.4) и (10.5) называют слабыми условиями Вольфе, а набор (10.4) и (10.6) называют сильными условиями Вольфе.

10.2.2. Поиск вдоль направления назад#

Поиск вдоль направления назад строится лишь на первом условии Вольфе (10.4).

Алгоритм 10.8 (Поиск вдоль направления назад)

Входные данные

  • функция \(f\),

  • её градиаент \(\nabla f\),

  • направление убывания \(\mathbf{d}\),

  • начальный вектор \(\mathbf{x}_0\),

  • максимальное значение \(\alpha_0\) (например, для метода Ньютона \(1\)),

  • шаг масштабирования \(0 < q < 1\).

Алгоритм

  1. Подсчитать значение функции и градиент в начальной точке \(f(\mathbf{x}_0\)), \(\nabla f(\mathbf{x}_0)\).

  2. Проставить \(\alpha \lto \alpha_0\).

  3. Проверить удовлетворение первого условия Вольфе (10.4). Если условие удовлетворено, \(\alpha\) найдено.

  4. Уменьшить \(\alpha\): \(\alpha \lto q \alpha\). Перейти на шаг 3.

Поиск называется «поиском назад» (backtracking), поскольку начинает с крупного \(\alpha\), которое в последствии итеративно уменьшается.

10.2.3. Сильный поиск вдоль направления#

Сильный поиск вдоль направления (strong backtracking) учитывает сильные условия Вольфе и требует более сложного алгоритма.

Поиск делится на фазы локализации (bracketing) и уточнения (zoom).

В фазе локализации происходит поиск интервала \((\alpha_\text{lo}, \alpha_\text{hi})\), в котором гарантируется наличие шагов \(\alpha\), для которых сильные условия Вольфе удовлетворятся. Этот интервал можно обнаружить, если одно из следующих условий выполнено

\[\begin{split}\begin{align} f(\mathbf{x} + \alpha \mathbf{d}) &\ge f(\mathbf{x}),\\ f(\mathbf{x} + \alpha\mathbf{d}) &> f(\mathbf{x}) + \beta \alpha \nabla f(\mathbf{x})^\top \mathbf{d},\\ \nabla f(\mathbf{x} + \alpha \mathbf{d})^\top \mathbf{d} &\ge 0. \end{align}\end{split}\]

Первое условие показывает, что выбранное \(\alpha\) приводит к увеличению функции, второе условие является обратным к первому условию Вольфе (10.4), а последнее показывает, что выбранный шаг приводит к точке, где \(\phi(\alpha)\) возрастающая.

В фазе уточнения происходит поиск \(\alpha\) в интервале \((\alpha_\text{lo}, \alpha_\text{hi})\), удовлетворяющее сильным условиям Вольфе. Это можно производить по-разному, самый простой поиск – бинарный, по знаку производной \(\phi'(0)\). Более сложные поиски используют, например, параболическую или кубическую интерполяцию функции \(\phi(\alpha)\) по известным значениям функции \(\phi\) и её производной \(\phi'\), затем в качестве нового приближения \(\alpha\) выбирают минимум интерполяционной модели.

Ниже приводится модифицированная версия сильного линейного поиска назад (Kochenderfer & Wheeler, 2019, стр. 62).

Функция 10.9 (strong_backtracking)

Сильный поиск вдоль направления

"""
    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
Содержание