Re: minimization using the Brent algorithm (brent.c)

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

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