[SciPy-Dev] optimize.fmin_ncg bug

Ralf Gommers ralf.gommers@googlemail....
Sat Jul 3 23:58:46 CDT 2010


On Sat, Jul 3, 2010 at 4:41 PM, Ralf Gommers <ralf.gommers@googlemail.com>wrote:

> There has been an intermittent test failure in scipy.optimize for a long
> time, only on Windows:
>
> ======================================================================
> ERROR: line-search Newton conjugate gradient optimization routine
> ----------------------------------------------------------------------
> Traceback (most recent call last):
>   File
> "C:\Python26\lib\site-packages\scipy\optimize\tests\test_optimize.py", line
> 115, in test_ncg
>     retall=False)
>   File "C:\Python26\lib\site-packages\scipy\optimize\optimize.py", line
> 1096, in fmin_ncg
>     alphak, fc, gc, old_fval = line_search_BFGS(f,xk,pk,gfk,old_fval)
>   File "C:\Python26\lib\site-packages\scipy\optimize\optimize.py", line
> 600, in line_search_BFGS
>     phi_a2 = f(*((xk+alpha2*pk,)+args))
>   File "C:\Python26\lib\site-packages\scipy\optimize\optimize.py", line
> 103, in function_wrapper
>     return function(x, *args)
>   File
> "C:\Python26\lib\site-packages\scipy\optimize\tests\test_optimize.py", line
> 41, in func
>     raise RuntimeError, "too many iterations in optimization routine"
> RuntimeError: too many iterations in optimization routine
>
> ----------------------------------------------------------------------
>
> I finally managed to track it down to line 1076 of optimize.py:
>     if curv == 0.0:
>
> This should be replaced with "if curv < eps:" with eps a suitably small
> number. Now my question is, how small is suitably small? 1e-10 seems to
> work, but maybe someone who known what the algorithm does can suggest a
> number that's not just a wild guess.
>
> Looking at the rest of optimize.py, there's quite a bit of comparing with
> zero going on which doesn't look right. Sometimes even with a comment like
> "maybe this slipped below machine precision". Comparing floating point
> numbers with zero like that is just a bad idea and should be fixed.
>
>
OK, looked at it in some more detail. I propose to change the comparison
with 0.0 to:
    if 0 <= curv <= 3*numpy.finfo(numpy.float64).eps:


By printing the value of 'curv' at each iteration before line 1076 we see
the problem, the code only checks for exactly 0.0 or <0.0 while the loop
approaches 0.0 to about +2*float64.eps and then runs away till we get
Inf/Nans in 'pk':
.......................0.00399999953806
1.25810055332e-05
1.3020931042e-07
1.98642696237e-10
6.89328152584e-12
3.75054053064e-16
1.17020918838e-15
3.65518790716e-15
1.522193813e-14
3.49498275889e-14
1.00753995671e-13
8.85621735118e-14
6.45602832318e-13
7.71651859561e-13
1.26993734725e-12
1.99182104181e-12
3.589092817e-12
3.31289828857e-12
7.33740017942e-12
1.1035546662e-11
1.41992354262e-11
3.51353735966e-11
4.29576509375e-11
6.83301887956e-11
1.10152323757e-10
2.02779978823e-10
2.58793635812e-10
4.28945979394e-10
7.10409808322e-10
1.17270345986e-09
1.92876849893e-09
3.53828040702e-09
4.92294232525e-09
7.1957586196e-09
1.18388196318e-08
1.70747389794e-08
3.72806974206e-08
5.35293003171e-08
9.33825403925e-08
1.22352272763e-07
2.12909037336e-07
3.07803338116e-07
4.02456362066e-07
7.00986627566e-07
9.6196850915e-07
1.36818301207e-06
2.13258348427e-06
3.28792400662e-06
5.01214989681e-06
7.55113686018e-06
1.12377188955e-05
1.72677931327e-05
2.32111890424e-05
3.3315332674e-05
4.71713470554e-05
6.59126173456e-05
9.09613197183e-05
0.000124130248531
0.000174603954122
0.000220134787641
0.000294134065199
0.000391904614904
0.000521995990713
0.000642371889147
0.000979855604735
0.00131625176769
0.00184480132165
0.00236723563377
0.00336587176004
0.00405386458411
0.00641503610926
0.00829947277392
0.0131341969672
0.0195918691409
0.0246436359513
0.0347262025799
0.0506396319829
0.0699390838321
0.0967920110714
0.129810713109
0.190348188533
0.238461606854
0.392229499575
0.524126282795
0.784084315019
0.931385310094
1.46067729788
2.03440185395
2.82231409859
4.01402864384
4.9533933324
7.49622545276
10.4700586476
13.5314471454
18.1905146597
24.3003828933
32.2523989905
42.5248543154
55.6998127601
72.4850733504
96.2032800258
106.571255441
161.149692744
215.008049236
272.723774241
310.370850848
431.849384449
377.245150044
611.993566609
478.678751989
2454.80128358
921.429944883
4068.83043858
-1503.78719623
E.............


With the fix the result is:
.......................0.00399999953806
1.25810055332e-05
1.3020931042e-07
1.98642696237e-10
6.89328152584e-12
3.75054053064e-16
..............


It's ticket http://projects.scipy.org/scipy/ticket/1150

I will commit this today in the 0.8.x branch unless someone disagrees.

Cheers,
Ralf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/scipy-dev/attachments/20100704/7a412b21/attachment.html 


More information about the SciPy-Dev mailing list