julianlsolvers / linesearches.jl Goto Github PK

Include tests for Travis when we get Optim 1.0

Morethuente, hagerzhang and strongwolfe all evaluate df.g! or df.fg!, and should thus report return any step that will give g(x+alpha*p) within tolerance from Optim, NLsolve etc.

In static.jl:

• Delete DeprecatedStatic and the Static(;kwargs...) function
• Replace string NewStatic with Static

Ref #97

All the linesearches take an argument g::Array or similar, which was previously used to store the gradient. With the use of NLSolversBase and *gradient!, this seems unnecessary?

I'll remove it, if nobody has an objection @cortner @pkofod

Optim doesn't really use LineSearchResults for much, and neither does LineSearches. Maybe we should just get rid of it?

One con that I can think of.

1. LineSearchResults works sort-of like the store_trace does in Optim, and may be valuable (if we bother using it)

If we move on with this remake, we should also fully embrace value_gradient! etc. from NLSolversBase. This must somehow be done in conjunction with a way to communicate the slope of the function \phi(\alpha) = f(x + \alpha * s), which now is calculated using vecdot(s, gradient(f)). So maybe this is the time to fully move onwards and redefine to work with phi(\alpha) instead of f and gradient(f)?

We should create documentation, or at the very least explain the input and output structure for the linesearch algorithms.

Hello, tests in NLsolve now fail (since 1-2 months ago) when upgrading some deps and fixing some deprecation warnings. https://github.com/EconForge/NLsolve.jl. The tests uses backtracking! so has there been any changes to the backtracking! line search that could cuase the tests to fail?

• Counter: Find a situation where all the (non-trivial) linesearches require at least two evals (e.g. Himmelblau above?)
• Optim usage: This should be covered by the "other package", and not in LineSearches.

from #59

It would be good to have an optimal linesearch, mostly for testing purposes (it somewhat reduces the noise in comparing two methods). I took a stab at implementing this using Optim.jl, but ran into the following circular dependency problem :
https://discourse.julialang.org/t/circular-modules-and-precompilation-errors/3855/2
(optim uses linesearches which uses optim)
Ideas for bypassing this welcome!

@antoine-levitt has suggested that we require all the line search algorithms to have the same required arguments.

(ls::LineSearch)(ϕ, dϕ, ϕdϕ,alpha0::T, ϕ_0, dϕ_0) where T

That way, we don't need a perform_linesearch wrapper like the one I added to the custom optimizer example.

The README examples are inconsistent in their printing of the Optim optimization results (different versions).

        if iterfinite >= iterfinitemax
            return T(0), true
            #             error("Failed to achieve finite test value; alphatest = ", alphatest)
        end

at initialguess.jl:234 returns Float64, Bool, where it should return Float64. Not sure what the right fix is here, so passing it to @pkofod ;-)

Deprecations on types and g-storage were introduced in LineSearches v2. We're now on v3, so it's time to remove them.

If I understand correctly, ia here should be 1 as per the paper which initializes the bracket to be [0, c_j].

• Test linesearch behaviour when alpha = NaN, Inf or negative
• Add counter tests (we can create OnceDifferentiable objects using NLSolversBase)

There is one of the cases where StrongWolfe returns ϕdϕ instead of ϕ in the following line:

In HagerZhang and MoreThuente we throw errors if the step direction is not a descent direction (that is, d\phi(0) \geq 0).

No tests are made in BackTracking and StrongWolfe, and it seems like they just return the given step length. I think the algorithms assume a descent direction, so we should probably be consistent here and throw an error.

I think we should leave Static alone, as my intention with it is for more "advanced" optimizers to decide exactly what the step should be (as long as it produces finite function values).

Ref: #91

If I try to use LineSearches.hz_linesearch! instead of Optim.hz_linesearch! then I get the following error:

LoadError: MethodError: no method matching hz_linesearch!(::Optim.DifferentiableFunction, ::Array{Float64,1}, ::Array{Float64,1}, ::Array{Float64,1}, ::Array{Float64,1}, ::Optim.LineSearchResults{Float64}, ::Float64, ::Bool)
Closest candidates are:
  hz_linesearch!{T}(!Matched::LineSearches.AbstractDifferentiableFunction, ::Array{T,N}, ::Array{T,N}, ::Array{T,N}, ::Array{T,N}, !Matched::LineSearches.LineSearchResults{T}, ::Real, ::Bool) at /Users/ortner/.julia/v0.5/LineSearches/src/hz_linesearch.jl:75

Is there maybe a specific branch of Optim that I should use?

Hi,

Sorry to create another issue with an easy question, but I was wondering if there is a way to display each iteration of a line search algorithm.

The basic example on show the results but I'd like to see every step of the process.

Thank you very much!

Hey, I'm the author of MultiFloats.jl, a new Julia package for extended precision arithmetic. I'd like to make my MultiFloat{T,N} type compatible with Optim.jl, but unfortunately I don't have an implementation of log2(::MultiFloat) yet, which trips up this one line in hagerzhang.jl:

iterfinitemax::Int = ceil(Int, -log2(eps(T)))

Is there any reason that this couldn't be replaced with precision(T)-1 or -exponent(eps(T)), to allow floating-point types that don't have log2 implemented? Of course I'm also working on implementing transcendental functions in MultiFloat.jl, but for the simple task of getting the exponent of epsilon, I figure a call to a transcendental function is unnecessary anyway.

like

if vecnorm(s) == 0
    Base.error("Step direction is zero.")
end

The linesearches communicates the step length back to the caller, but not the objective value.
We should pass the objective value back as well to stop unnecessary calls of the objective function in Optim and NLOpt NLSolve

Hi,

I am trying to do the simple example provided, but it doesn't work.

using Optim
using LineSearches
prob = Optim.UnconstrainedProblems.examples["Rosenbrock"]

all works fine but when I do
algo_hz = Newton(linesearch = hagerzhang!)

I get the following error:
WARNING: both LineSearches and Optim export "hagerzhang!"; uses of it in module Main must be qualified
ERROR: UndefVarError: hagerzhang! not defined

Why is that?

Thanks for your help!

I'd like to see a flexible logging / tracing functionality here.

Currently there is little info provided when things go wrong inside the linesearches. Finiteness tests such as #101 should (optionally) warn the user that something is wrong.

Whenever Optim starts using LineSearches

ref changes in #80

• Don't allocate vectors. We might as well have them as scalars to avoid allocations
• We should also free the deepest layer of df, although we could in theory still provide simple wrappers.
• Add an argument to specify a largest \alpha. This is to accommodate Fminbox and other simple constrained optimizers not evaluating outside of constraints. Of course, some constrained optimizers will need more specialized line searches (or use trust regions of course).
• We should return \alpha, \phi(\alpha) to avoid recalculation of \phi if packages other than Optim and NLsolve want to use these functions. We can still call value_gradient! outside, as we're checking if it's the same point anyway.
  ... more?

Currently these don't work together with the Inf values in our @with_kw structs.

This can be fixed with JuliaMath/DoubleFloats.jl#18, and if so we should re-enable the DoubleFloats tests in arbitrary_precision.jl. Otherwise, we'll have to think of something new here

At the moment all linesearchoptions (e.g. C1, C2) are passed via arguments. This makes it a bit of a pain for the user to set those arguments given how the line search functions are passed to Optim. I suggest to either move to a LineSearchOptions type or to keyword arguments.

Here's a reproduction along with the error message: https://gist.github.com/samuela/d53088b8aa7403a77ec5b6e51166c0f3

The tag name "3.3.0" is not of the appropriate SemVer form (vX.Y.Z).
cc: @pkofod

I suggest to replace hz_linesearch! by hagerzhang!, mt_linesearch! by morethuente!, backtracking_linesearch!bybacktrackingand so forth. Then they could be called viaLineSearches.backtracking!`, etc.

In the paper, the divisor is norm(gr)^2

I have a few questions/concerns about the initialization of HagerZhang:

1. If we start at or close to the minimizer, dphi0 will be close to 0, so it is possible this will error

   LineSearches.jl/src/initialguess.jl

   Line 252 in 1f40bf3

   if alpha == 0

   .
2. In the paper, the quadratic stepping is optional and when it fails, the algorithm falls back on using an initial guess that is a multiple of the previous step size. Isn't this a more reasonable thing to do rather than error above?
3. If I understand correctly, this line

   LineSearches.jl/src/initialguess.jl

   Line 266 in 1f40bf3

   if phitest > phi_0

   is not in the original paper.
4. While I understand the rationale behind the while loop in

   LineSearches.jl/src/initialguess.jl

   Line 228 in 1f40bf3

   while !isfinite(phitest)

   which was used to ensure that phitest is finite, possibly a concern with log-barrier methods, but this guarantee is gone in

   LineSearches.jl/src/initialguess.jl

   Line 268 in 1f40bf3

   else

   . Maybe do a similar loop here?

We should start throwing LineSearchExceptions with information that can be useful for external packages. See e.g. JuliaNLSolvers/Optim.jl#263

The tag name "5.2.0" is not of the appropriate SemVer form (vX.Y.Z).
cc: @anriseth

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

We should redo the backtracking algorithm, and let the user choose between quadratic and cubic interpolation.

The "standard" case with no interpolation does not work very well, so I say we scrap that.

Follow "Numerical Optimization" by Nocedal and Wright, page 56, and/or
"Numerical Methods for Unconstrained Optimization and Nonlinear Equations" by Dennis and Schnabel, page 325.

• Move alphaguess from Optim.
• Make it a type chosen by the user.
• Default all of them to alpha = 1 (Optim change. Except Accelerated and Momentum GD)

Initial ones to implement:

• Set alpha = 1
• Keep the previous alpha
• Extrapolation of the form from L-BFGS
• Converg alphatry

Check if there is something wrong with the backtracking_linesearch! implementation, it fails tests at the moment.

Can be useful for example with Newton's method in the quadratic regime.

Similar to
https://www.mcs.anl.gov/petsc/petsc-current/docs/manualpages/SNES/SNESLINESEARCHBASIC.html

This should also help #24

Add references to the algorithms that have been implemented.
As a first, just add them to the README.

If we ever write a documentation, we can move them there.

Ref: #7 (comment)

Some of the linesearch algorithms calls the objective unnecessarily when calculating the value at the initial x.

JuliaNLSolvers/Optim.jl#802

Hi,

I am running LBFGS optimization algorithm with MoreThuente linesearch algorithm.
I track the execution of the algorithm by damping the output of the trace into the terminal.

In some cases (which are, fortunately, rare), the optimization just gets stuck: there are no new messages in the trace.
My guess is that LineSearch algorithm gets stuck for some reason.

Could someone provide advice on how to better debug such cases where the LineSearch is stuck?
May be you have some ideas what the problem might be?

Specifically, all the links on this page link to https://github.com/JuliaLang/julia/blob/0d713926f85dfa3e4e0962215b909b8e47e94f48/base/#L0-L12 with the last bit changing occasionally. I clicked on Edit on GitHub, but it appears the docs were created with some sort of automation.

The above line should have an absolute tolerance in light of https://discourse.julialang.org/t/approximate-equality/8952/4.

Ref #118