Re: multimin question

[Fabrice Rossi <rossi at ufrmd dot dauphine dot fr>]

Dave Morrison wrote:
> I'm not sure I grok Fabrice's diagnosis - if this is related to a cut on
> the norm of the gradient, it's not obvious to me why shifting the
> function by a constant offset would matter.

My diagnosis is only an explanation for the error messages, which display a
bug (now fixed) in my part of GSL. The incorrect behavior you're talking about
was only a way to show this bug. Basically, my bracketing code based on
extended precision registers assumed that a given value was different from
another one. So it ended with a GSL_SUCCESS and passed values to Brian's one
dim minimizer. But the values lost their extended precision during the
transmission and where discovered equal in Brian's code, triggering an error.
This is now fixed by a volatile declaration and commited to the CVS.

Now your problem is more complex and related also (but in a different way) to
numerical precision. We know that we cannot find a one dimensional minimum
with a better precision that sqrt(e) where e is the relative precision of the
floating point model used. This is because near a minimum, the function behave
quadratically. But in multidim there is an interaction with the gradient (more
precisely with the descent direction). For each iteration we have to minimize
g(u)=f(x+ud), where d is the descent direction. Around a minimum, f behave
quadratically with ud. That means (u|d|)^2 cannot be smaller than e. So the
localisation of the minimum cannot be better than something that depends on
the norm of the descent direction. If we assume that the descent direction has
a norm that is approximately equal to the gradient norm (this depends on the
algorithm but is at least true for steepest descent) this means that we should
give to one dim algorithm a precision that depends on the norm of the
gradient, or at least keep the gradient norm within reasonnable bounds. In my
test code, I quit the main loop when the gradient norm is below sqrt(e), which
means that the one dim minimum cannot be located...

What is the link with having or not a zero minimum? Well, it seems that the
requested small norm for the gradient cannot been reached. The program is
trying to locate a minimum based on differences between values of the
objective function. I guess that even if the movement on x is so small that
the calculation is not exact, you obtain very small non zero values that are
different if the minimum is 0. If the minimum is 1 for instance, around you
really must move from sqrt(e) in order to obtain a real difference. I know I'm
not very clear so look at this: if you compute x^2 for x=10e-20 and 10e-21,
you obtain different values. If you compute x^2+1, you don't.

I guess that the solution is to use a clever stopping criterion, for instance
something based on the length of the last move or on the last function change.
I will check in the CVS new stopping criterion next week. Suggestions are
welcome.

Fabrice