brent-local-min-generator v1.0.1
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-generatorUsage
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), andlocal_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 functionfvalue 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.