Bisections

Bisections work by moving an interval until we observe a sign change (either in the function or its derivative).

Example

We consider the same example as we had when demonstrating backtracking line search:

ls_obj = linesearch_problem(s)

Bracketing

Performing bisections requires providing an initial interval. If we are only given a single point instead of an interval we have to perform bracketing. For bracketing [3] we move an interval successively and simultaneously increase it in the hope that we observe a local minimum (see bracket_minimum).

α₀ = 0.0
(a, c) = bracket_minimum(alpha -> ls_obj.F(alpha, params), α₀)

(1.28, 5.12)

We then use this interval to start the bisection algorithm.

Potential Problem with Backtracking

We here illustrate a potential issue with backtracking. For this consider the following function:

f2(α::T) where {T <: Number} = α^2 - one(T)
α₀ = -10.0
(a, c) = bracket_root(f2, α₀)

(-7.44, 0.23999999999999932)

And when we plot this we find:

If the interval would contain $r_1$ and $r_2$ then we get an error:

bracket_root(f2, 30.)

MethodError: Cannot `convert` an object of type Nothing to an object of type Tuple{Float64, Float64}
The function `convert` exists, but no method is defined for this combination of argument types.

Closest candidates are:
  (::Type{T})(::Any) where T<:Tuple
   @ Base tuple.jl:454
  convert(::Type{T}, !Matched::T) where T<:Tuple
   @ Base essentials.jl:600
  convert(::Type{T}, !Matched::NTuple{N, Any}) where {N, T<:Tuple}
   @ Base essentials.jl:601
  ...