minimization using the Brent algorithm (brent.c)

[Faheem Mitha <faheem at email dot unc dot edu>]

Dear GSL People,

My version of gsl is 1.3 (on Debian).

I need to use a one-dimensional global minimization algorithm (to minimize
a function on an interval). However, this algorithm is embedded inside a
larger framework, and needs to be called many times without user
intervention. I discovered that an implementation of this algorithm was in
GSL, so I decided to use it.

However, I ran into an problem. The first time I ran my algorithm, I got
the following

gsl: fsolver.c:126: ERROR: endpoints do not enclose a minimum
Default GSL error handler invoked.

I checked, and this was triggered by the following two lines in
min/fsolver.c

 if (f_minimum >= f_lower || f_minimum >= f_upper)
    {
      GSL_ERROR ("endpoints do not enclose a minimum", GSL_EINVAL);
    }

In other words, if the function value at the initial value happens to be
larger than the function value at the endpoints, an error is triggered.

However, if you look at the actual discussion of the Brent algorithm on on
72-75 of "Algorithms for Minimization without Derivatives", you can see
this should not be an issue. In fact, Brent automatically takes the
initial value to be v = a + (3 - \sqrt(5)/2)*(b-a), and it is not an
problem if f(v) happens to be greater than f(a) or f(b).

The GSL version of the algorithm requires user input for the initial
value, but in fact I'd say one of the strengths of this algorithm is that
it does *not* require user input.

Yes, I now see that your manual says

"The minimization algorithms begin with a bounded region known to contain
a minimum.  The region is described by an lower bound a and an upper bound
b, with an estimate of the location of the minimum x.

The value of the function at x must be less than the value of the
function at the ends of the interval,

     f(a) > f(x) < f(b)

This condition guarantees that a minimum is contained somewhere within
the interval."

However, this makes the algorithm much less useful for cases where you
don't know whether the maximum occurs at the interior or the end
points.

If my understanding of the Brent algorithm is correct, in the case
when the function has a local minimum on the interval, Brent will
return to me some value close to where the local minimum occurs, and
in cases where there is no local minimum it will return to me one of
the end points.

So if I choose the value that gives the smallest function value from
the set containing the output of Brent and the two end points I should
always get the absolute minimum. Correct? It seems to me this would be
a more useful way for the algorithm to be implemented. Or, at least
don't make it impossible for people to use Brent to search for a local
minimum which may not be a global minimum.

In conclusion, it seems to me that your error criterion is too
restrictive.

In any case, can you suggest a workaround for the error message? If I
don't hear anything I will simply comment out these two lines, and
recompile, since I don't have plans to use any of the other
minimization algorithms in GSL at the moment. If you can think of
anything better, I'd be happy to hear of it.

If I missed something, and my understanding above is deficient, please
let me know.

                                                        Faheem.