More-Thuente Linesearch Algorithm Questions

[itrumper]

I have been using the More-Thuente linesearch with a L-BFGS solver on an optimization problem. The convergence is typically very efficient (in my opinion), however I often encounter the error, MoreThuenteLineSearch: Search direction must be a descent direction. I have looked at the code for L-BFGS, and it initializes the search direction on this line.

The code in MoreThuenteLineSearch then evaluates whether the search direction is within 90 degrees of the descent direction on this line.

I'm curious if anyone can help me understand why the L-BFGS algorithm may be providing a search direction that violates this condition? Looking at the optimization state prior to this error being thrown I don't see anything in the gradient or cost functions that stand out to me, it seems like everything is progressing along smoothly.

I have also attempted to adjust the bounds and Wolfe condition parameters, but those do not seem to ever completely remove this behavior, although I am not very experienced with this realm of mathematics, so my investigation has been purely experimental.

It also seems that the check in MoreThuenteLineSesarch could be improved so that if the search direction is more anti-parallel to the descent direction, we could flip the search direction's sign to align. In the case of perpendicular, I agree, an error should be thrown.

Thank you in advance for any help and suggestions!

[stefan-k]

Thanks a lot for reporting this and apologies for the very late reply! We've had this reported before (#132), but nothing came out of this issue. Unfortunately I currently don't have time to look at this in detail, but I suspect numerical issues. Have you tried printing self.dginit over the course of the optimization? I suspect that it is 0 < self.dginit <= EPS when this issue happens. Even if this is the case, I'm not sure how to handle this properly.

It also seems that the check in MoreThuenteLineSesarch could be improved so that if the search direction is more anti-parallel to the descent direction, we could flip the search direction's sign to align. In the case of perpendicular, I agree, an error should be thrown.

I think this would violate certain assumptions and will cause issues down the line. The More-Thuente line search assumes that you provide a downhill search direction, it is therefore the responsibility of the caller to ensure that this is the case.

Thanks again for this report. I consider this a bug and would therefore suggest to convert this to an issue. What do you think?

[itrumper]

This discussion has been migrated over to the issue #400