Possible inefficiency with step size in Newton method + backtracking linesearch about optim.jl HOT 17 CLOSED

@sebastien-villemot, I didn't contribute to the Newton code, but this seems off. From the literature I've read, the line search step size should be reset to 1 each time.

from optim.jl.

In my problem, NLsolve returns the error "Too many iterations in backtracking_linesearch!". So it does not seem like the best choice in all cases.

from optim.jl.

PRs accepted

from optim.jl.

Arguably we should remove backtracking_linesearch since it never works well in my experience.

from optim.jl.

Any progress on this?

from optim.jl.

Should we perhaps deprecate backtracking_linesearch?

from optim.jl.

I think we should benchmark the change before doing anything, but resetting to 1.0 seems like the right thing to do. I have other stuff to finish, and limited time, but if no one else grabs it, I'll have a look at some point.

from optim.jl.

please don't remove backtracking line search; I am just in the process of rewriting it. On my first tests, I actually beat HZ and MT line search with LBFGS.

from optim.jl.

Btw, I just notices that the same 1.0 problem is also in LBFGS.

from optim.jl.

Personally, I always use an extrapolation step, which defaults to 1.0 if it ends up near 1.0. This is my current implementation; just as a quick hack to try it out:

        if iteration > 1
           alphaguess = 2.0 * (f_x - f_x_previous) / dphi0
           alphaguess = max(alphaguess, alpha/4.0)
           alphaguess = min(alphaguess, 1.0)
           if alphaguess > 0.75
               alphaguess = 1.0
           end
        else
            alphaguess = 1.0
        end

On Rosenbrock example:

linesearch : F-evals / G-evals
HZ : 60 / 81
MT : 76 / 76
new BT : 45 / 72

(HZ is for ConjugateGradients, the rest for LBFGS)

from optim.jl.

some variant of this might even fix #166

from optim.jl.

@cortner where are we on this, was this fixed somewhere?

from optim.jl.

An improvement to backtracking was introduced as a non-default option here: JuliaNLSolvers/LineSearches.jl#7.
Further updates that change default behaviour of backtracking will be merged with JuliaNLSolvers/LineSearches.jl#20.

The Newton algorithm still seems to be lacking the resetting state.alpha = 1.0 step, which is the best default in the "good" regions for Newton.

from optim.jl.

But this is now a LineSearches.jl issue right? Or do you need something from optim ?

from optim.jl.

No - it is more complicated. What Linesearches.jl really needs is a refactoring to make linesearches tyoes rather than functions: this will definitely affect Optim.

from optim.jl.

See #294 and JuliaNLSolvers/LineSearches.jl#9

from optim.jl.

closed by #328

from optim.jl.