FYI: fminbnd added + a question about tolerances

[Jaroslav Hajek]

hi all,

by this changeset
http://hg.savannah.gnu.org/hgweb/octave/rev/035ac548a67e
I implemented fminbnd for Octave, using the state-of-the-art Brent's
method (in contrast to the old OctaveForge version, which only does a
golden section search).
The reference implementation is on Netlib. The interface should be
mostly Matlab-compatible.

One thing I'd like to discuss with anyone interested is the stopping tolerance.
The Netlib implementation transforms the supplied tolerance using
tol = sqrt (eps) * abs (x) + tolx / 3
and something like this seems to be also done by Matlab 2007. The
sqrt(eps) is given by theory - it's the best precision to be expected
from the inverse parabolic steps.
It is *not*, however, the best precision expectable from the golden
section steps, which are well capable to bracket the minimum to a much
higher accuracy.
So, using sqrt(eps) here makes it impossible to go closer to the
minimum/root even though the algorithm is well capable of it.
For instance, in Matlab 2007a:

>> fminbnd (@(x) (x-0.3)^4, 0, 1, optimset ('TolX', 0)) - 0.3

ans =

  -1.2589e-09

OTOH, Octave can now do much better:

octave:4> fminbnd (@(x) (x-0.3)^4, 0, 1, optimset ('TolX', 0)) - 0.3
ans = 0

I believe the Matlab algorithm is capable of going this close as well,
it's just implicitly disallowed.

Based on this reasoning, I believe it's wrong to impose the sqrt(eps)
threshold, and I used 2*eps instead (this was already done in fzero).
Another question is the default tolerance, TolX. I'm setting it to
sqrt(eps) by default. Matlab seems to use higher values.
I believe, however, that the fzero/fminbnd functions are so efficient
that the user will most typically far prefer accuracy to performance,
so I think Octave's defaults are more reasonable. But I'm open to
discussion.

enjoy!

-- 
RNDr. Jaroslav Hajek, PhD
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz