-
Notifications
You must be signed in to change notification settings - Fork 15
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
New line searches #1
Comments
Hey there. I gave implementing the zoom line search algorithm a try, as I find it to be a generally well-working method. At least for some of the problems I have tackled in the past. The main obstacle (apart from getting used to the JAX control flow for nested if-expressions) is how to retrieve the descent information needed to evaluate the decrease and curvature conditions as well as interpolate the step sizes. In the current implementation of the search and descent interfaces there seems to be no general way to retrieve the descent direction after the descent step is made. Also, the descent methods currently have no common naming scheme regarding the descent direction, if it's even calculated explicitly (I get that this may not alway be necessary), which further complicates things. My understanding is that one would have to divide the current step by the step size to (re-)evaluate the descent direction, which may generally be a bad idea for a value that is supposed to decrease with further convergence. Or am I missing something obvious? If not, my proposal would be to modify the interface of the descent methods in a way that allows to retrieve the current descent direction in a unified way. Also, I think the abstract line search step method should have an additional argument for the descent direction or even the descent state, as this is most likely required by complex line search methods in one way or another. On a side note, I'm also working on implementing the L-BFGS algorithm (kind of finished, at least from a methodological point of view), which also relies on common interfaces for descents. Looking forward to further discuss this topic! |
Hello! Thanks for the interest in implementing some new line searches. Just to be clear, for a minimisation problem of a function
As for technical details of implementing the Wolfe conditions, there should be no issues here. The classic Wolfe conditions for current iterate Does this clear things up? |
Thank you for taking the time to write down the general line search problem and current implementation in such detail. This actually helps a lot to clarify the problem I'm currently facing. First, you are totally right about the Wolfe conditions. I understood that the descent information is computed by substracting
Evaluating the sufficient decrease condition with The problem still persisting is the computation of new trial step sizes They propose computing new trial step sizes
with
This requires explicit computation of the derivative
of
which requires computation of the descent direction Please let me know if you have any suggestions. Maybe I'm once again misleaded by the usual notation. Edit: fixed some typos in equations |
Yep, this looks like it may require a more significant rewrite. As you pointed out, the issue is how to get The most obvious solution to this may be to pass the descent @HeSchatz I've already left you in the dark on this for way too long, my apologies. While determining how much of a rewrite this will need, a clunky option which at least gets the autodiff issue out of your way would be to use finite difference. You should be able to compute and store |
I think I'm happy with a breaking change. We're still early in this project's lifecycle, and this is already an advanced API. |
c.f. also zoom.
The text was updated successfully, but these errors were encountered: