Quasi Newton Method

abstract type
    DescentMethod
end

mutable struct BFGS <: DescentMethod
    Q
end

function bracket_minimum(f, x=0; s=1e-2, k=2.0)
    a, ya = x, f(x)
    b, yb = a + s, f(a + s)
    if yb > ya
        a, b = b, a
        ya, yb = yb, ya
        s = -s
    end
    while true
        c, yc = b + s, f(b + s)
        if yc > yb
            return a < c ? (a, c) : (c, a)
        end
        a, ya, b, yb = b, yb, c, yc
        s *= k
    end
end

function minimize(f, a, b)
    a = convert(Float64, a)
    b = convert(Float64, b)
    return Optim.optimize(f, a, b).minimizer
end

function line_search(f, x, d)
    objective = α -> f(x .+ α*vec(d))
    a, b = bracket_minimum(objective)
    α = minimize(objective, a, b)
    return x + α*d
end

function init!(M::BFGS, f, ∇f, x)
    m = length(x)
    M.Q = Matrix(1.0I, m, m)
    return M
end

function step!(M::BFGS, f, ∇f, x)
    Q, g = M.Q, ∇f(x)
    x′ = line_search(f, x, - Q*g)
    g′ = ∇f(x′)
    δ = x′ - x
    γ = g′ - g
    Q[:] = Q - (δ*γ'*Q + Q*γ*δ')/(δ'*γ) + (1 + (γ'*Q*γ)/(δ'*γ))[1]*(δ*δ')/(δ'*γ)
    return x′
end

function quasi_method(f, g, x0)
    xʼ = x0
    Q = 0.0005
    n = 10000
    QN = BFGS(Q)
    init!(QN, f, g, xʼ)

    i = 0
    prev = 0
    while i <= n
        i += 1
        xʼ = step!(QN, f, g, xʼ)
        if prev == xʼ
            break
        else
            prev = xʼ
        end
    end
    return xʼ,f(xʼ),i
end

k(x) = x .^ 2 + 15*x
l(x) = ForwardDiff.jacobian(k, x)
res = quasi_method(k, l, [-5.0, -2.0])