findLocalMin

Find a real minimum of a real function f(x) via bracketing. Given a function f and a range (ax..bx), returns the value of x in the range which is closest to a minimum of f(x). f is never evaluted at the endpoints of ax and bx. If f(x) has more than one minimum in the range, one will be chosen arbitrarily. If f(x) returns NaN or -Infinity, (x, f(x), NaN) will be returned; otherwise, this algorithm is guaranteed to succeed.

Tuple!(T, "x", Unqual!(ReturnType!DF), "y", T, "error")
findLocalMin
(
T
DF
)
(
scope DF f
,
in T ax
,
in T bx
,
in T relTolerance = T.epsilon^^0.25
,
in T absTolerance = sqrt(T.epsilon)
)
if (
isFloatingPoint!T
)
in { assert (isFinite(ax) && isFinite(bx), "ax and bx shall be finite reals"); assert (isNormal(absTolerance) && absTolerance >= T.epsilon * 2, "absTolerance shall be normal positive real no less then $(D T.epsilon*2)"); assert (isNormal(relTolerance) && relTolerance > 0, "relTolerance shall be normal positive real"); }
out (result) { assert (isFinite(result.x)); }

Parameters

f
Type: DF

Function to be analyzed

ax
Type: T

Left bound of initial range of f known to contain the minimum.

bx
Type: T

Right bound of initial range of f known to contain the minimum.

relTolerance
Type: T

Relative tolerance.

absTolerance
Type: T

Absolute tolerance.

Preconditions: ax and bx shall be finite reals.
relTolerance shall be normal positive real.
absTolerance shall be normal positive real no less then T.epsilon*2.

Return Value

Type: Tuple!(T, "x", Unqual!(ReturnType!DF), "y", T, "error")

A tuple consisting of x, y = f(x) and error = 3 * (absTolerance * fabs(x) + relTolerance).

The method used is a combination of golden section search and successive parabolic interpolation. Convergence is never much slower than that for a Fibonacci search.

References: "Algorithms for Minimization without Derivatives", Richard Brent, Prentice-Hall, Inc. (1973)

Examples

auto ret = findLocalMin((double x) => (x-4)^^2, -1e9, 1e9);
assert(ret.x.approxEqual(4.0));
assert(ret.y.approxEqual(0.0));

See Also

Meta