brent-local-min-generator

This module implements Brent's algorithm to find a local minimum of a function f in an interval. This algorithm can also be used to find a maximum. If there is only a single minimum/maximum in the interval, that minimum/maximum will be found.

The algorithm is implemented as a generator function local_min_generator(). This not only allows an asynchronous function to be minimized using the algorithm, but also gives a lot of flexibility (see example below).

The module also provides a simple function local_min() to run the generator function to minimize synchronous functions, passed as a callback, and simplify its use.

Installation

Use the package manager to install the package brent-local-min-generator.

npm install brent-local-min-generator

Usage

The JavaScript code for the generator local_min_generator() follows Brent's original code of the Algol 60 procedure local_min() very closely.

Parameters

In the first comment in his code, Brent describes procedure local_min() as:

If the function f is defined on the interval (a, b), then local_min() finds an approximation x to the point at which f attains its minimum (or the appropriate limit point), and returns the value of f at x. t and eps define a tolerance tol = eps |x| + t, and f is never evaluated at two points closer together than tol.

|parameter | description |----------|------------ |f | the function f() for which the minimum is sought. Only for the utility function local_min(). |a | the finite lower bound of the interval in which to search the minimum |b | the finite upper bound of the interval in which to search the minimum |eps | the relative tolerance. eps should be no smaller than 2 * Number.EPSILON, and preferably not much less than Math.sqrt(Number.EPSILON). (optional, default: 2 * Number.EPSILON) |t | the absolute tolerance, should be positive. (optional, default: 0.0)

Functions

• local_min_generator(a, b, eps, t), and
• local_min(f, a, b, eps, t).

Both functions return an object with 2 properties:

• x: the x value for which the minimum was found,
• fx: the function f value in the minimum.

Examples

The examples assume the module has been loaded

const brents = require('brent-local-min-generator');

Consider the following function:

const f = x => x**3 + 1.5 * x**2 - 18 * x + 4;

]

Example 1: simple minimization

// minimize f(x) in the interval [0.5, 4]
console.log( brents.local_min(f, 0.5, 4) );
// expect:  {x: 2, fx: -18}

Example 2: simple maximization

// maximize f(x) in the interval [-5, -2]
const point = brents.local_min(x => -f(x), -5, -2);
point.fx *= -1;
console.log(point);
// expect {x: -3, fx: 44.5}.

Example 3: using the generator

// minimize f(x) in (0.5, 4)
const gen = brents.local_min_generator(0.5, 4);

let result = gen.next();
while ( ! result.done ) {
    const x = result.value;
    const y = f(x);

    result = gen.next(y)    
}

console.log( result.value );
// expect  {x: 2, fx: -18}

Example 4: customized minimum

Often implementations have an additional parameters for maximum number of iterations (max_iter). Brent's original code does not have this option, but using the generator function, they are easily implemented, as the following example function shows:

function myLocalMin(f, a, b, max_iter) {
    const gen = local_min_generator(a, b);

    let result = gen.next();
    for (let i=0; i<max_iter && ! result.done; ++i) {
        const x = result.value;
        const y = f(x);

        result = gen.next(y)    
    }

    return result.value;
}

Further Documentation

The ultimate documentation on this algorithm can be found on Emeritus Professor Richard P. Brent's homepage, and his page dedicated to his book Algorithms for Minimization Without Derivatives.

On the page for the book, not only the errata for the different editions of the book are available, but also scanned copy of the Prentice-Hall edition.

C, C++, Fortran77 and Fortran90 codes can be found on John Burkardt's homepage.

License

ISC