[SciPy-Dev] Proposal to add two new linesearch strategies to scipy.optimize

[Ihno Schrot]

Hi all,

I would like to propose to add two new linesearch strategies to 
scipy.optimize(.linesearch.py), namely the "Restrictive Monotonicity 
Test" (RMT) [1] and the "Backward Step Control" (BSC) [2].

It is well known that Newton-type methods for rootfinding or 
optimization problems can be forced to converge globally in a domain 
where the Jacobian or Hessian, respectively, is nonsingular. However, 
with linesearch strategies which are based on descent arguments with 
classical merit functions one usually has to pay the price of taking 
unnecessarily small stepsizes even in the domain where full steps would 
lead to convergence. This is also the case for the existing linesearch 
strategies in SciPy.

The suggested linesearch strategies were developed to achieve global 
convergence of Newton-type methods while avoiding too small step sizes. 
The RMT already has shown good performance in many practical 
applications. The BSC is a rather novel strategy but the numerical 
results available so far are promising and the BSC is proven to enable 
global convergence under reasonable assumptions. Moreover, I have done 
extensive numerical tests of both linesearch strategies in my master 
thesis. Although the tests have been focussed on comparing the two 
strategies, I also compared them to SciPys linesearch strategy that is 
based on the Wolfe condition and found that the RMT and BSC can 
outperform SciPys linesearch strategy in terms of the number of 
benchmark problems that can be solved.

Therefore, I believe that adding the BSC and the RMT to SciPy benefits a 
wide range of users by providing modern powerful linesearch strategies. 
Especially, users would have two more linesearch strategies to apply to 
their problems, which can be helpful given that it is problem dependent 
which linesearch strategy works the best.

If the community thinks that adding those two strategies is an useful 
enhancement, colleagues and I are happy to improve and eventually add 
our code to SciPy. Of course, we are also happy to answer any questions 
from the community regarding this proposal.

Greetings from Heidelberg,
Ihno

[1] https://doi.org/10.1007/978-0-387-35514-6_3
[2] https://doi.org/10.1137/140968586

-- 
Ihno Schrot
Institute for Applied Mathematics
Heidelberg University
E-Mail: ihno.schrot at uni-heidelberg.de

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.python.org/pipermail/scipy-dev/attachments/20201103/577b73bb/attachment.html>