Re: golden section search fails when minimum is on the edge of the interval

[Christian Krüger]

The minimizers in GSL require an estimate x \in [a, b] of the location 
of the minimum to be supplied during initialisation; and this estimate 
has to fulfill f(a) > f(x) < f(b).

Effectively, this means that GSL can find minima only in the open 
interval (a, b), and in contrast to, e.g., the root finder algorithms 
which only need the interval boundaries a and b, you also need to supply 
a reasonable guess of the minimum that satisfies above mentioned 
condition. You'll get the same error message that you quoted if your 
estimate is "bad".

In this way, the implementation of GSL is not wrong or buggy. But one 
has to keep in mind the subtlety that a minimum at the ends of the 
interval cannot be found with these methods (unfortunately).



Am 14.07.22 um 15:22 schrieb Peter Rockett:
> I am using GS search embedded inside another optimiser and 
> occasionally the minimum of the function ends up on the edge of the 
> interval, i.e. when searching over [a..b], the minimum is at exactly 
> at either a or b. In this situation, the GSL routine fails with: "gsl: 
> fsolver.c:126: ERROR: endpoints do not enclose a minimum". As far as I 
> understand, GS search should cope with this situation, hence its 
> specification in terms of finding a minimum in the closed (cf open) 
> interval [a..b]. Therefore, I suspect this is a bug.
>
> An MWE (effectively copied from the manual example but with a modified 
> fn1 fucntion)  is attached.
>
> FWIW: The brent solver fails with exactly the same error.
>
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <math.h>
>
> #include <gsl/gsl_errno.h>
> #include <gsl/gsl_math.h>
> #include <gsl/gsl_min.h>
>
> double fn1(double x, void* params)
>     {
>     (void)(params); /* avoid unused parameter warning */
>     return x;
>     }
>
> int main(void)
>     {
>     int status;
>     int iter = 0, max_iter = 100;
>     const gsl_min_fminimizer_type* T;
>     gsl_min_fminimizer* s;
>
>     double m = 0.5;
>     double a = 0.0, b = 1.0;
>
>     gsl_function F;
>     F.function = &fn1;
>     F.params = 0;
>     T = gsl_min_fminimizer_goldensection;
>     s = gsl_min_fminimizer_alloc(T);
>     gsl_min_fminimizer_set(s, &F, m, a, b);
>     printf("using %s method\n", gsl_min_fminimizer_name(s));
>     printf("%5s [%9s, %9s] %9s %10s %9s\n", "iter", "lower", "upper", 
> "min", "err");
>     printf("%5d [%.7f , %.7f ] %.7f %.7f \n", iter, a, b, m, b - a);
>     do
>         {
>         iter++;
>         status = gsl_min_fminimizer_iterate(s);
>         m = gsl_min_fminimizer_x_minimum(s);
>         a = gsl_min_fminimizer_x_lower(s);
>         b = gsl_min_fminimizer_x_upper(s);
>         status = gsl_min_test_interval(a, b, 0.001, 0.0);
>         if(status == GSL_SUCCESS)
>             printf("Converged:\n");
>         printf("%5d [%.7f , %.7f ] " "%.7f %+.7f \n", iter, a, b, m, b 
> - a);
>         }
>     while(status == GSL_CONTINUE && iter < max_iter);
>
>     gsl_min_fminimizer_free(s);
>
>     return status;
>     }