Implement scipy.optimize's dcsrch (a modified version of Minpack2's code)

[rht]

While doing a benchmark for Julia vs Python in https://github.com/JuliaNLSolvers/Optim.jl/issues/922, I have found scipy.optimize's dcsrch (so I use PyCall to do scipy.optimize.minimize on a Julia model) to be faster than HagerZhang and BackTracking when the maximum linesearches is limited to 20.

While dcsrch is probably not a faster general purpose line search algorithm, I think having it implemented would ease the transition for people who are migrating their code from Python+SciPy to Julia+Optim.jl.

Some info about dcsrch:

c     This subroutine calls subroutine dcsrch from the Minpack2 library
c       to perform the line search.  Subroutine dscrch is safeguarded so
c       that all trial points lie within the feasible region.
c
c     Be mindful that the dcsrch subroutine being called is a copy in
c       this file (lbfgsb.f) and NOT in the Minpack2 copy distributed
c       by scipy.

Code implementation: https://github.com/scipy/scipy/blob/4ec6f29c0344ddce80845df0c2b8765fc8f27a72/scipy/optimize/lbfgsb_src/lbfgsb.f#L3326.

[Seelengrab]

I'm not 100% sure, but I think the original code (which, if I've followed it all correctly) is GPL licensed (https://software.sandia.gov/opt++/opt++2.4_doc/html/index.html, which I think covers the license for Minpack2 (https://software.sandia.gov/opt++/opt++2.4_doc/html/minpack2_8h.html this shows a header file! Be mindful when clicking)).

[rht]

According to https://github.com/scipy/scipy/blob/master/LICENSES_bundled.txt#L26, they use BSD-licensed code. The readme shows the website that hosts the source code: https://github.com/scipy/scipy/tree/master/scipy/optimize/lbfgsb_src. Does that mean the L-BFGS-B authors have incorrectly attributed the Minpack2 code?

[Seelengrab]

Does that mean the L-BFGS-B authors have incorrectly attributed the Minpack2 code?

Not necessarily, they may have implemented it from scratch/referenced a paper/done a clean-room implementation. I'm not a licensing expert, so I just wanted to chime in with what I found. Since LineSearches.jl is MIT though, it'd be a shame if such a useful addition would introduce GPL.

[longemen3000]

The implementation paper (algorithm 778: a L-Bfgs-B algorithm) says that the line search used is MoreThuente

[rht]

https://github.com/JuliaNLSolvers/LineSearches.jl/blob/master/src/morethuente.jl seems to be based on cvsrch, which is not dcsrch.