The simplest optimization method is a golden section method. It has guaranteed linear convergence independent of the function whose minimum is to be found. An interval is divided into 2 parts, and on each step the algorithm chooses the left or right interval without taking into account the behavior of the function. Independently of the value of function obtained, if we select left interval, we'll calculate the following function value in a point A, otherwise, the next point will be B.

Besides, we can take into account that in the neighborhood of the minimum function it could be described by a parabola. The most obvious solution is to build a parabola by three known values, and find its minimum. Then we select three more points near the extremum found, and build a new parabola, having the next interpolation.

The convergence of such method is quadratic, but this method isn't applicable. First, it is only the smooth function that can be described by a parabola in the neighborhood of minimum, but the method can fail when working with non-smooth functions. Second, we must have a rather small initial interval containing the minimum. Outside of such an interval the function behavior is arbitrary, and we could converge to the maximum instead of the minimum, or get outside of the search domain while finding a minimum of the recurrent parabola.

The Brent method combines some lines of a golden section method and some of a parabolic interpolation method, which is proposed above. This method is characterized by quadratic convergence in case of smooth functions and guaranteed linear convergence in case of nonsmooth or sophisticated functions.

Few words about the principles of work. The algorithm keeps in memory five points: points a and b limit interval [a, b], where the minimum is localised, and three points with the best-case value of f(x) are kept in points x, w, v. On the basis of these points, the recurrent parabola is formulated. The next value of the function is calculated in the point of the minimum of this parabola. If the assumed minimum is outside of the interval [a, b] or if some conditions are fulfilled, the next step is performed on the basis of the golden section method. These conditions are: the presence of signs of nonsmoothness or a rather big distance to extremum.

Subroutine description

The algorithm finds a local minimum of F(X) function in the interval [a,b].

Input parameters:

• a - the left boundary of an interval to search minimum in
• b - the right boundary
• Epsilon - absolute error of the value of the function minimum.

Output parameters:

• XMin - point of minimum.

The result: function value at the point of minimum.

Report a bug

C#

C# 1.0 source.
brentopt.csharp.zip - Brent's method

C++

C++ source.
brentopt.cpp.zip - Brent's method
ablas.zip - optimized basic linear algebra subroutines with SSE2 support (for C++ sources only)

Delphi

Delphi source.
Can be compiled under FPC (in Delphi compatibility mode).
brentopt.delphi.zip - Brent's method

Visual Basic 6

Visual Basic 6 source.
brentopt.vb6.zip - Brent's method

Zonnon ^beta

Zonnon source.
Zonnon is an experimental language developed at ETH Zurich.
See www.zonnon.ethz.ch for more information.
brentopt.zonnon.zip - Brent's method