[Gretl-devel] testcases and pet projects

[Riccardo (Jack) Lucchetti]

On Mon, 6 Jul 2009, chris wrote:

> Hi,
>
> Riccardo (Jack) Lucchetti wrote:
>> On Mon, 6 Jul 2009, Riccardo (Jack) Lucchetti wrote:
>> 
>> Ok, I think I've got it. The reason why line 548 in gretl_bgfs.c reads
>>
>>      crit_ok = !na(f) && (f >= fmax + d);
>> 
>> instead of
>>
>>      crit_ok = !na(f) && (f >= fmax);
>> 
>> is that, in normal circumstances, we want to avoid jumping from one place 
>> to another if the jump doesn't yield a *significant* improvement in the 
>> objective function. Here d is the threshold, which, in turn, is computed as
>> 
>> d = sumgrad * steplen * acctol;
>> 
>> acctol is a hand-tweaked small number, steplen is between 0 and 1, so what 
>> really makes the difference here is sumgrad.
>> 
> I've checked with BFGS_DEBUG on and it seems that d is always negative. So if 
> i understand correctly, gretl doesn't look for a significant improvement, but 
> is happy even if f decreased by abs(d)

Hm, you got me thinking on this one. In fact, I suspect that this is a bug 
that's been there for more than 2 years. Allin, please check if what I'm 
saying makes sense to you. Our original BFGS implementation was ripped 
from somewhere else (I believe it was R, but I may be wrong) and it was 
conceived as a _minimiser_ rather than a _maximiser_. Then, we decided to 
flip the sign, so to speak: you can see this by comparing versions 1.181 
and 1.182 of lib/src/nls.c, where BFGS was at the time. The "d" check, 
however, stayed the same. So, if my analysis is right, the "right" patch 
would be

Index: lib/src/gretl_bfgs.c
===================================================================
RCS file: /cvsroot/gretl/gretl/lib/src/gretl_bfgs.c,v
retrieving revision 1.7
diff -u -r1.7 gretl_bfgs.c
--- lib/src/gretl_bfgs.c        6 Jul 2009 04:24:02 -0000       1.7
+++ lib/src/gretl_bfgs.c        6 Jul 2009 12:14:13 -0000
@@ -543,7 +543,7 @@
                 }
                 if (ndelta > 0) {
                     f = cfunc(b, data);
-                   d = sumgrad * steplen * acctol;
+                   d = - sumgrad * steplen * acctol;
                     fcount++;
                     crit_ok = !na(f) && (f >= fmax + d);
  #if BFGS_DEBUG

However, I believe my earlier argument about the matrix H is still 
correct at least in part, so we may want to change the above to

   d = (iter>0) ? -sumgrad * steplen * acctol : 0;

although in this case, we'd make the algorithm more lenient, not stricter 
(which may be undesirable).

Chris' test script runs fine with the above patch applied. I also ran a 
few other tests and nothing wrong appeared. Before committing, though, I'd 
like to hear Allin's opinion.


Riccardo (Jack) Lucchetti
Dipartimento di Economia
Università Politecnica delle Marche

r.lucchetti at univpm.it
http://www.econ.univpm.it/lucchetti