This is the mail archive of the gsl-discuss@sources.redhat.com mailing list for the GSL project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


Dear Fabrice Rossi and gsl-ers..

First of all let me ask the question: Which problem is being solved?

The answer (i.e the formulation of the problem) which I see is the
following:

On an open interval (a,b) find such a point x0 inside (a,b) that
F(x0) is minimal. (from this it follows that F(a)>F(x0)<F(b).)

Numerically, exact x0 can never be found so it is acceted that the
output is the best approximation x to x0 and/or the interval (a',b')
on which the correct x0 lies.

Thus, the input to the problem is the open interval (a,b) and the
function F(x). Nothing more, there is no "first' guess here...
How the method proceeds is up to the method.

It is a common misconseption, in my opinion, that a method (golden rule
or Brent) start with a triplet, quartet or sixtet or N-tet...

The algorithm itself should construct N-tet and make calculations.

The motivation for the golden section or for brent is that for any
given stage of calculation given the search interval (a_n,b_n)
a new approximation x_n for x0 is found (according to the rules of the
method) and the following should be true F(a_n)>F(x_n)<F(b_n).
If on any stage this inequality is false, the golden/Brent is in deep
trouble. Note that x_n is not given by the user, it is obtained within 
the algorithm.

Thus, the scenario should be the following:

Given the interval (a,b) and F(x) each method should find the first 
iteration x_1 and test the inequality above if the algorithm requires
it. If the test is required and not satisfied and the method can not
proceed -- abort, if the test is satisfied or not required and the
method can proceed, a new interval (a_1,b_1) is constructed and the
problem returns to the initial one of finding extremum on (a_1,b_1)
given F(x).

There is no need for a "third" point supplied by the user in the
initial step.

The use of "user" points only worsens(does not improve) convergence of
the algorithm without any other effect. Unfotunately, the common
partice is to use that useless "initial" guess making the user to
execute the first stage of the algorithm or face the loss of one
function evaluation or even convergence.

This is my opinion.

Lazar

__________________________________________________
Do you Yahoo!?
Yahoo! Platinum - Watch CBS' NCAA March Madness, live on your desktop!
http://platinum.yahoo.com


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]