errors in fmin_bfgs and some improvements (Trac #734)

[scipy-gitbot]

Original ticket http://projects.scipy.org/scipy/ticket/734 on 2008-09-03 by trac user jgarcke, assigned to @cournape.

There are a couple of issues with fmin_bfgs in optimize.py.

I'll attach a patch against optimize.py from Revision 4683, but that file / fmin_bfgs hasn't really changed much anyway recently.

• the second linesearch can't return an alpha_k != None because it gets 'wrong' old_fval,old_old_fval. These get changed on the return from the first linesearch. These return values should be stored temporarily and only be used of the first linesearch returns an useable alpha_k
• a more stable way to compute sk

The following are changes to achieve a more robust behaviour

• an additional stopping criteria tracking very small changes
• a different way to handle possible div by zero

[scipy-gitbot]

Attachment added by trac user jgarcke on 2008-09-03: optimize.py.diff

[scipy-gitbot]

Milestone changed to 0.7.1 by @cournape on 2009-05-02

[scipy-gitbot]

trac user jgarcke wrote on 2010-11-11

parts of this appearing here (and were fixed)
http://projects.scipy.org/scipy/ticket/1158

[scipy-gitbot]

@rgommers wrote on 2010-11-13

The parts that are still relevant are here: rgommers@c5b0f4af.

The change to compute sk is straightforward. The change in handling div-by-zero looks fine too.

Two questions for the extra stopping criterion:

1. How did you choose the 1e-6 number? I couldn't find that in the reference you supplied.
2. Do you have a test for this?

[scipy-gitbot]

trac user jgarcke wrote on 2010-11-15

I took 1e-6 since it is the default option here:
http://www2.imm.dtu.dk/~hbn/Software/quasi_newton.m

default value : opts(1:6) = [2 2 1 1e-4*||g(x0)||_inf 1e-6 100]
the fifth one is relevant here.

But then, it probably should be an option in the function call with the default set to 1e-6.

Test as in a numerical example that this works ? And works better with this change ?

Not really, I had problems with this inside a programm I had and didn't go down to a simple example because there it often enough works in the current form. And I can't easily extract the part where the minimisation happens since it depends on the whole part of the software.

And I later used a different algorithm anyway:

ALGORITHM 611, COLLECTED ALGORITHMS FROM ACM.
ALGORITHM APPEARED IN ACM-TRANS. MATH. SOFTWARE, VOL.9, NO. 4,
DEC., 1983, P. 503-524.

http://calgo.acm.org/611.gz

where I used f2py and a wrapper routine in python.

That one was more robust and faster than the python one.

If interested I can give my python wrapper for that one.

[scipy-gitbot]

Attachment added by @rgommers on 2010-11-28: ticket-734.patch

[scipy-gitbot]

@nilswagner01 wrote on 2011-04-13

Different optimizers expect different types of arrays, e.g. bfgs expects 1-d array for the initial guess, func and fprime. fmin_ncg works well with 0-d arrays. Is is possible to fix this inconsistent behaviour ?

[scipy-gitbot]

Attachment added by trac user rfc on 2011-05-07: ticket-734-tweaks.patch

[scipy-gitbot]

trac user rfc wrote on 2011-05-07

Hello all,

I suggest a few small changes to rgommers' patch (see above patch):

1. Exposed tolerance for new stopping condition as new fmin_bfgs parameter xtol, default value 1e-6. I don't know what would make a good default tolerance. Perhaps using a smaller one would be safer.
2. The BFGS update to Hk matrix should not be performed if yksk is non-positive, as this would break positive-definiteness of the matrix Hk. rgommers' patch ensured abs(yksk) was sufficiently large. I suggest removing the abs() and just ensuring yksk itself is large enough.
3. If the update to the Hk matrix is not performed, this should not terminate iteration with failure, instead simply continue iterating without updating Hk.

Changes 2. and 3. follow the advice from the notes on Unconstrained Optimization located here: http://www2.imm.dtu.dk/documents/ftp/publlec.html

On a related note, I think the scalar_search_wolfe1 function from linesearch could use a bit of work. A more rugged line search would further improve the robustness of fmin_bfgs and fmin_cg. This function wraps minpack's dcsrch routine but I think scalar_search_wolfe1 could be improved to avoid calling dcsrch with invalid inputs. Another possible change could be to raise errors when dcsrch fails (containing the detailed error message from dcsrch, for example) instead of hiding the errors and returning None. I'd like to submit a patch for this when I can find the time.

[scipy-gitbot]

@rgommers wrote on 2011-05-09

That all sounds reasonable. J. Garcke (who supplied the original patch, I just updated it) and you are working from the same reference it seems. @jgarcke: could you review the proposed changes? It would be good to wrap this up.

Improvements to scalar_search_wolfe1 are also very welcome.

[scipy-gitbot]

Milestone changed to 0.10.0 by @rgommers on 2011-05-09

[scipy-gitbot]

trac user jgarcke wrote on 2011-05-10

The latest patch looks good.

Thanks.

[scipy-gitbot]

@rgommers wrote on 2011-06-04

@rfc: I made one small change to your patch, see https://github.com/rgommers/scipy/tree/ticket-734-fmin_bfg. A new keyword argument (xtol) should always be added at the end. Otherwise it breaks backwards compatibility when keyword args are supplied as positional args.

The xtol addition should have a test that exercises it. Do you have an example that can be turned into a test?

[scipy-gitbot]

@rgommers wrote on 2011-08-27

Sorry, that link is broken, should be https://github.com/rgommers/scipy/tree/ticket-734-fmin_bfgs.

[scipy-gitbot]

Milestone changed to Unscheduled by @rgommers on 2011-08-27

[scipy-gitbot]

@pv wrote on 2012-05-19

According to Wright & Nocedal (p. 201), skipping the update is not so good, and a better alternative is to use a damped BFGS update (p. 538). They don't give a direct formula for the update for H, so one needs a think a little bit here first.

The xtol part of the patch seems OK to me.

[andyfaff]

@pv, @rgommers , is there enough information in this issue still to justify keeping it open? I tried following all the links and couldn't access any of them.

[rgommers]

This link still works: master...rgommers:ticket-734-fmin_bfgs

I can't remember the details, so no opinion on whether that's still applicable.

[jgarcke]

The xtol part of the change is still valid and useful.

And likely it could still be interesting to look at the above algorithm 611 and bind that into scipy. But I have no idea about the process involved for that.

[WillTirone]

Going through old issues to attempt to summarize and evaluate next steps to possibly close them, please let me know if anyone has suggestions on other things I need to consider :)

Original Issue:

Original ticket http://projects.scipy.org/scipy/ticket/734 on 2008-09-03 by trac user jgarcke, assigned to @cournape.

There are a couple of issues with fmin_bfgs in optimize.py.

I'll attach a patch against optimize.py from Revision 4683, but that file / fmin_bfgs hasn't really changed much anyway recently.

* the second linesearch can't return an alpha_k != None because it gets 'wrong' old_fval,old_old_fval. These get changed on the return from the first linesearch. These return values should be stored temporarily and only be used of the first linesearch returns an useable alpha_k

* a more stable way to compute sk

The following are changes to achieve a more robust behaviour

* an additional stopping criteria tracking very small changes

* a different way to handle possible div by zero

Summary of above discussion:

• Most of the above links are broken, with the exception of this commit which was intended to close this issue.
• Community agreed that using xtol=1e-6 was a correct enhancement / approach
• NOTE: the minimization function is now stored in scipy._optimize._minimize_bfgs and scipy._optimize.fmin_bfgs rather than scipy.optimize.fmin_bfgs as it was in 2013.

Outstanding Items:

• It seems the commit was not merged into the main branch because consensus was not reach on the update of Hk:

@pv wrote on 2012-05-19

According to Wright & Nocedal (p. 201), skipping the update is not so good, and a better alternative is to use a damped BFGS update (p. 538). They don't give a direct formula for the update for H, so one needs a think a little bit here first.

The xtol part of the patch seems OK to me.

• A test was not written to check the new xtol argument, would need to add one
• A direct formula for the update was not given in the paper above so may need an expert opinion

Suggestion:

Decided whether or not the update to Hk is needed.

1. If not needed and this commit is still agreed upon, resubmit it (not sure how that would need to be redone since file structure has changed).
2. If update is needed to Hk, could break that out as a separate issue and accept the changes to the xtol argument and add a test.

Let me know if anyone has suggestions!

[mdhaber]

@WillTirone thanks for that summary. Could you submit a PR that merges this commit into main (even though that may mean ignoring git's automatic attempt to merge and manually applying the relevant changes to resolve the merge conflict)? Then we can review it like normal. We may or may not decide not to change the way Hk is updated, but I think a PR would help give this issue some attention. I'm willing to review; please ping me.

[WillTirone]

@mdhaber sure! I'll take a look at my summary and try what you suggested above, it may take a week or two.

[WillTirone]

(update that I'm still working on this, in my first semester of grad school so quite busy, but hopefully can get closed for closember)