search

yuki-koyama / mathtoolbox

Mathematical tools (interpolation, dimensionality reduction, optimization, etc.) written in C++11 with Eigen
https://yuki-koyama.github.io/mathtoolbox/
MIT License
255 stars 35 forks source link

Line search in BFGS and L-BFGS sometimes fail #46

Open yuki-koyama opened 5 years ago

yuki-koyama commented 5 years ago

I've just found that the demo of GPR sometimes fails to optimize hyperparameters using BFGS or L-BFGS in this library; it throws run-time exceptions during line search. This needs to be examined carefully.

yuki-koyama commented 4 years ago

This is probably not a bug but a correct behavior.

This document, https://dl.acm.org/citation.cfm?id=279236, said

If the line search is unable to find a point with a sufficiently lower value of the objective after 20 evaluations of the objective function, [...]

which indicates that it is possible to fail the line search to find a solution that satisfies the necessary conditions. This document also said

In this case all correction vectors [...] are discarded and the iteration is restarted along the steepest descent direction.

So it may be better to follow this restarting strategy. Anyway, this issue needs to be examined still.