Re: [Gretl-devel] testcases and pet projects
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(a)univpm.it
http://www.econ.univpm.it/lucchetti