Exact Line Search Algorithm

Question

I am trying to implement a simple line-search algorithm in Julia. I am new to Julia programming, so I am learning it on the go. I'd like to ask for some help, if possible, to correct an error while running the code.

Source code.

using LinearAlgebra

function bracket_minimum(f, x = 0, s = 1e-2, k = 2.0)
    a, fa = x, f(x)
    b, fb = x + s, f(x + s)

    if(fb > fa)
        a, b = b, a
        fa, fb = fb, fa
        s = -s
    end

    while(true)
        c, fc = b + s, f(b + s)
        if(fb < fc)
            return a < c ? (a, c) : (c, a)
        else
            a, fa, b, fb = b, fb, c, fc
            s *= k
        end
    end
end

function bisection(f, a₀, b₀, ϵ)

    function D(f,a)
        # Approximate the first derivative using central differences
        h = 0.001
        return (f(a + h) - f(a - h))/(2 * h)
    end

    a = a₀
    b = b₀

    while((b - a) > ϵ)
        c = (a + b)/2.0

        if D(f,c) > 0
            b = c
        else
            a = c
        end
    end

    return (a,b)
end

function line_search(f::Function, x::Vector{Float64}, d::Vector{Float64})
    println("Hello")
    objective = α -> f(x + α*d)
    a, b = bracket_minimum(objective)
    α = bisection(objective, a, b, 1e-5)
    return α, x + α*d
end

f(x) = sin(x[1] * x[2]) + exp(x[2] + x[3]) - x[3]

x = [1,2,3]
d = [0, -1, -1]
α, x_min = line_search(f, x, d)

I am getting a Linear algebraic error, so I think I must not be passing vectors correctly or perhaps I am not doing scalar-vector multiplication correctly. But, I was having a hard-time figuring out. If I step through the code, it fails on the function call line_search(f,x,d) and does not even enter inside the function body.

Error description.

ERROR: MethodError: no method matching *(::Tuple{Float64,Float64}, ::Array{Int64,1})
Closest candidates are:
  *(::Any, ::Any, ::Any, ::Any...) at operators.jl:538
  *(::Adjoint{var"#s828",var"#s8281"} where var"#s8281"<:(AbstractArray{T,1} where T) where var"#s828"<:Number, ::AbstractArray{var"#s827",1} where var"#s827"<:Number) at C:\buildbot\worker\package_win64\build\usr\share\julia\stdlib\v1.5\LinearAlgebra\src\adjtrans.jl:283
  *(::Transpose{T,var"#s828"} where var"#s828"<:(AbstractArray{T,1} where T), ::AbstractArray{T,1}) where T<:Real at C:\buildbot\worker\package_win64\build\usr\share\julia\stdlib\v1.5\LinearAlgebra\src\adjtrans.jl:284

user_1269567 · Answer

Here is a fix in the code (I have cleaned up several stylistic things, but the key problem that your bisection returned a tuple not a value - I have changed it to return the center of the bracketing interval):

function bracket_minimum(f, x = 0.0, s = 1e-2, k = 2.0)
    a, fa = x, f(x)
    b, fb = x + s, f(x + s)

    if fb > fa
        a, b = b, a
        fa, fb = fb, fa
        s = -s
    end

    while true
        s *= k
        c, fc = b + s, f(b + s)
        if fb < fc
            return minmax(a, c)
        else
            a, fa, b, fb = b, fb, c, fc
        end
    end
end

function bisection(f, a₀, b₀, ϵ)

    function D(f, a)
        # Approximate the first derivative using central differences
        h = 0.001
        return (f(a + h) - f(a - h)) / (2 * h)
    end

    a = a₀
    b = b₀

    while (b - a) > ϵ
        c = (a + b) / 2.0

        if D(f, c) > 0
            b = c
        else
            a = c
        end
    end

    return (a + b) / 2 # this was changed
end

function line_search(f::Function, x::Vector{Float64}, d::Vector{Float64})
    @assert length(x) == length(d)
    objective(α) = f(x .+ α .* d)
    a, b = bracket_minimum(objective)
    α = bisection(objective, a, b, 1e-5)
    return α, x .+ α .* d
end

f(x) = sin(x[1] * x[2]) + exp(x[2] + x[3]) - x[3]

x = [1.0, 2.0, 3.0]
d = [0.0, -1.0, -1.0]
α, x_min = line_search(f, x, d)

I was not commenting on the algorithm, as I assume you are writing this as a programming exercise and you are not trying to write the fastest and most robust algorithm.

Exact Line Search Algorithm

1 Answers