minimization using the Brent algorithm (brent.c)
Fabrice Rossi
rossi@ufrmd.dauphine.fr
Mon Mar 17 20:39:00 GMT 2003
Z F wrote:
> >The fact that there might be a point y such that F(y)>F(a) or
> >F(y)>F(b)
> >is quite irrelevent and cannot be rule out by an efficient algorithm
> >unless you make stronger assumption on F (in which case using
> >derivatives might be a good idea).
>
>
> This is the answer. The existance of the point y is irrelevant, but
> the function will fail if y is used as the first guess of the extremum.
> This is what I meant, it is a useless test. If the test is passed, you
> know that a minimum exists, if the test is failed you have not learned
> anything. So why complain? The function complains that it could not
> check that the root exists not that it does not exist. If you like the
> test so much, there should be a way to force the algorithm to proceed
> even it the test is failed since it does not tell you anything.
>
>
>
> >Moreover, evaluation of F(x) is required for the Brent algorithm (or
> >the
> >golden section search), so there is no useless evaluation.
>
>
> The x, required for golden/Brent is not just any x, it is a particular
> place inside the interval (a;b). So the function call is useless.
I'm not sure to understand your answer.
First, a LOCAL minimization algorithm (such as Brent or Golden section
algorithm) must give its answer as a bracketing triple, that is an
interval ]a,b[ and a point x in ]a,b[ such that F(a)>F(x) and F(b)>F(x).
I will not argue about global minimization algorithm, as I'm far from an
expert in this area. The only simple way to start such a local
minimization algorithm is to provide it a starting bracketing triple.
The Golden section search is based on the fact you start it with a
bracketing triple. If it is not the case, that is when you have
F(x)>F(a) (for instance), you are in trouble. Assume for instance your
next try is y, between a and x and you have F(y)<F(x), F(y)>F(a) and
F(y)>F(b). What is your next estimate? Do you prefer ]a,x[, for which
you have now a bracketing triple, or ]y,b[ for which you have a
candidate (b) that is currently the lowest? I'm quite sure that the
Golden section search can be modified to take into account such cases,
but your proposal (drop the test and proceed) does not seem to fit in.
Last point, the first guess (i.e., x) does not have to be the golden
one. You can start the golden section with whatever internal point you
want. Asymptoticaly, newly evaluated point will be "golden" one's. The
convergence rate is not changed by starting from an arbitrary point. For
the Brent algorithm, you must have three starting points, which can be
basically arbitrary as you are fitting a quadratic function through
those point (of course, as you fall back to a golden section step when
numerical problems occurs, you must have a bracketing interval). So
there is no such thing as a "brent point". Of course, in both cases, the
next evaluation point (y) is not arbitrary, but we are talking about the
initial bracket, aren't we?
Fabrice Rossi
More information about the Gsl-discuss
mailing list