Possible infinite loop in bisect

[marius311]

One other minor thing, with a sufficiently poorly conditioned problem, it seems its possible to get stuck in an infinite loop in bisect here (at least it happened to me).

I can try and get a MWE if needed, let me know, but perhaps a simple fix is to add a maxiter type argument there as well, or simply use the same one from the HagerZhangLineSearch ?

[Jutho]

Bisect should not be able to go into an infinite loop, as every time the distance between the two end points of the interval decreases by a factor of two. However, what I have also experienced is that it goes into
b.α - a.α < eps()
which should then trigger the warning. This happens in particular if gradients (and function values) are only computed up to some precision which is less accurate than machine precision.

Is that what you are seeing, or is there another error behaviour that I am missing. I am certainly also experiencing cases where the line search fails (which I think are due to function values and gradients depending on the solution of large scale eigenvalue problems and linear problems, which are solved using Krylov methods which sometimes don't converge or produce a less accurate result).

However, it is certainly also possible that the linesearch implementation still has bugs.

And even if that is not the case, I agree that a better strategy should exist to nonetheless recover from linesearch failures without erroring and just continuing as is, taking the hit of an increased function value if there is no other way.

[marius311]

Ah thanks that helped, I think I see what's happening. My problem is a Float32 eltype so b.α - a.α :: Float32 but eps() is by default for Float64, so I think it should be eps(typeof(a.α)) or something like that. Indeed, my loop was getting stuck at b.α - a.α = 1.8189894f-12 and eps(Float32)=7.275958f-12 so the warning would have been triggered.

I agree it would be nice to have a little more control over when to terminate the the linesearch. Anecdotally I often find its often not worth the effort of getting the step size to super high precision as compared to just taking more steps.

[Jutho]

Yes, good catch. I will fix that. Normally the line search should not try to get super high precision, it just tries to find a feasible point that satisfies the criteria laid out in the Hager-Zhang papers. But if there is some inaccuracy in either function values or gradients, it might become impossible to satisfy those criteria and that's when trouble sets in (at least, that's definitely a cause, but maybe there are other issues as well).