Как я могу использовать модуль Linesearches.jl в Julia независимо от Optim.jl? - PullRequest
Новая
       6

Как я могу использовать модуль Linesearches.jl в Julia независимо от Optim.jl?

0 голосов
/ 13 мая 2018

У меня есть реализация L-BFGS, и я хотел бы вызвать поиск строки из LineSearches.jl для сравнения. Однако документация довольно скудная и фокусируется только на использовании Linesearches.jl в контексте Optim.jl. Я не могу найти примеры того, как использовать Linesearches.jl самостоятельно.

1 Ответ

0 голосов
/ 04 июня 2018

Я создал пример использования алгоритмов LineSearches с пользовательским оптимизатором в документации latest .

Обратите внимание, чтов настоящее время для примера требуется LineSearches master, но он должен быть доступен в v6.0.0 в ближайшее время.

Вот полный пример на случай разрыва ссылок: ( EDIT : обновлено с новым примером кодаэто упрощает процесс.)

Использование LineSearches без Optim / NLsolve

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

function gdoptimize(f, g!, fg!, x0::AbstractArray{T}, linesearch,
                    maxiter::Int = 10000,
                    g_rtol::T = sqrt(eps(T)), g_atol::T = eps(T)) where T <: Number
    x = copy(x0)
    gvec = similar(x)
    g!(gvec, x)
    fx = f(x)

    gnorm = norm(gvec)
    gtol = max(g_rtol*gnorm, g_atol)

    # Univariate line search functions
    ϕ(α) = f(x .+ α.*s)
    function dϕ(α)
        g!(gvec, x .+ α.*s)
        return vecdot(gvec, s)
    end
    function ϕdϕ(α)
        phi = fg!(gvec, x .+ α.*s)
        dphi = vecdot(gvec, s)
        return (phi, dphi)
    end

    s = similar(gvec) # Step direction

    iter = 0
    while iter < maxiter && gnorm > gtol
        iter += 1
        s .= -gvec

        dϕ_0 = dot(s, gvec)
        α, fx = linesearch(ϕ, dϕ, ϕdϕ, 1.0, fx, dϕ_0)

        @. x = x + α*s
        g!(gvec, x)
        gnorm = norm(gvec)
    end

    return (fx, x, iter)
end

Обратите внимание, что существует множество алгоритмов оптимизации и поиска линий, которые позволяют пользователю одновременно оценивать как цель, так и градиент по соображениям вычислительной эффективности.Мы включили эту функциональность в алгоритм в качестве входной функции fg!, и даже если алгоритм градиентного спуска не использует ее явно, многие алгоритмы LineSearches используют.

метод градиентного спуска gdoptimize выбираетнаправление спуска и вызывает алгоритм поиска линии linesearch, который возвращает длину шага α и значение цели fx = f(x + α*s).

Функции ϕ и dϕ представляют одномерную цель и ее производную, которая используетсяалгоритмами поиска строки.Чтобы использовать вызов функции fg! в оптимизаторе, для некоторых операций поиска строки требуется функция ϕdϕ, которая возвращает одномерную цель и производную одновременно.

Оптимизация Розенброка

Здесьпример, показывающий, как мы можем комбинировать gdoptimize и LineSearches для минимизации функции Розенброка, которая определяется как 

f(x) = (1.0 - x[1])^2 + 100.0 * (x[2] - x[1]^2)^2

function g!(gvec, x)
    gvec[1] = -2.0 * (1.0 - x[1]) - 400.0 * (x[2] - x[1]^2) * x[1]
    gvec[2] = 200.0 * (x[2] - x[1]^2)
    gvec
end

function fg!(gvec, x)
    g!(gvec, x)
    f(x)
end

Теперь мы можем использовать gdoptimize с BackTracking для оптимизации функции Розенброкаиз заданного начального условия x0. 

x0 = [-1., 1.0]

using LineSearches
ls = BackTracking(order=3)
fx_bt3, x_bt3, iter_bt3 = gdoptimize(f, g!, fg!, x0, ls)

Интересно, что поиск строки StrongWolfe сходится за одну итерацию, тогда как все остальные алгоритмы занимают тысячи итераций.Это просто удача из-за конкретного выбора начального условия 

ls = StrongWolfe()
fx_sw, x_sw, iter_sw = gdoptimize(f, g!, fg!, x0, ls)
...