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 [2] 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.)

Unable to bracket f starting at x = 30.0.