minimization using the Brent algorithm (brent.c)

Fabrice Rossi rossi@ufrmd.dauphine.fr
Mon Mar 17 18:43:00 GMT 2003


Z F wrote:

> Hello Brian
>
> Sorry for my rudness, but I think that it is not prudent to require
> a "test" point inside the interval. (I know that standard libraries
> require that). The test F(a)>F(x)F(a) or F(y)>F(b) so the test is
> useless and only requires an extra computation of F() which might be
> time consuming.

The purpose of requiring F(a)>F(x)<F(b) is not only a protection against 
stupid mistake.

First of all, it guarantees that there is actually a minimum in the open 
interval ]a,b[ (as long as F is continuous). The whole rationnal of 
Brent algorithm is to take an input interval on which the studied 
function has a minimum (strictly inside the interval) and to produce 
(after a given number of steps or up to a given precision) a smaller 
interval, included into ]a,b[ that satisfies the same requirement.

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).

Moreover, evaluation of F(x) is required for the Brent algorithm (or the 
golden section search), so there is no useless evaluation.

Fabrice Rossi



More information about the Gsl-discuss mailing list