Golden Section Search

This documentation was generated with the assistance of AI. Please report any inaccuracies.

Golden section search is the simplest reliable method for minimizing a function of one variable: it needs only function evaluations (no derivatives), and its worst-case behavior is well understood and guaranteed. It is described in Press et al., 2007, Sections 10.1 (page 490, bracketing a minimum) and 10.2 (page 492, golden section search), and implemented as GoldenSingleOptimizer in the com.irurueta.numerical.optimization package. Bracketing itself is implemented in the BracketedSingleOptimizer base class shared by every single-variable optimizer in this package (see also Brent’s Method and Brent’s Method with Derivatives).

Bracketing a minimum

A root is bracketed by two points where a function has opposite sign; a minimum is bracketed only by a triplet such that is less than both and — this guarantees (for a smooth function) that a minimum lies somewhere in . Every optimizer in this package treats establishing such a bracket as an essential first step, rather than an optional convenience.

Given two distinct starting points, the shared bracketing routine searches downhill (swapping the two points first if needed, so the downhill direction runs from the first toward the second) and keeps stepping further in that direction — using parabolic extrapolation through the three most recent points when it helps, and a fixed magnification factor (the golden ratio, ) otherwise — until it finds a third point where the function value has turned back uphill:

flowchart TD A["Evaluate f at two starting points; swap them\nif needed so the downhill direction runs a -> b"] --> B["c = b + GOLD * (b - a) (first guess)"] B --> C{"f(b) > f(c) ?"} C -->|"yes: not yet bracketed"| D["Try a parabolic-extrapolation step;\nfall back to a fixed golden-ratio step\nif the parabolic step is unusable or too far"] D --> E["Shift a, b, c forward by one position"] E --> C C -->|"no: f(b) is a local minimum\nrelative to f(a), f(c)"| F["Bracket (a, b, c) found"]

Golden section search

Once bracketed, golden section search narrows the triplet the same way bisection narrows a root bracket: try a new interior point, and keep whichever of the two resulting sub-triplets still brackets a lower center point. The only real question is where, within the larger of the two segments, to place that next trial point.

Writing the middle point as a fraction of the way from to , and the next trial point as a further fraction beyond :

Minimizing the worst-case new segment length — and requiring the same optimal placement strategy to be self-similar from one stage to the next — gives the quadratic equation , whose relevant root is:

This is the golden section: the optimal bracketing triplet has its middle point a fractional distance from one end and from the other, and each new trial point should be placed at that same fractional position within the larger of the two current segments. Because this ratio is self-replicating, starting from any bracket quickly converges to it regardless of the triplet’s initial proportions.

Successive bracketing of a minimum: starting from the triplet 1, 3, 2, each new trial point 4, 5, 6 replaces whichever outer point no longer helps, shrinking the bracket until it tightly encloses the minimum

Every new function evaluation shrinks the bracket by a fixed factor of — reliable, but only linearly convergent (each new significant figure costs a comparable number of further evaluations), unlike the superlinear convergence of Brent’s Method.

flowchart TD A["Bracket (a, b, c); track 4 running points x0..x3"] --> B["Place new trial point at fraction 0.38197\ninto the larger of the two current segments"] B --> C["Evaluate f there"] C --> D{"Is the new point's neighbor\nstill the lower of the pair?"} D -->|"yes"| E["Keep that as the new bracket triplet"] D -->|"no"| F["Keep the other new bracket triplet"] E --> G{"|x3 - x0| <= tolerance * (|x1| + |x2|) ?"} F --> G G -->|"no"| B G -->|"yes"| H["Return whichever of the two center\npoints has the lower function value"]

Library implementation

GoldenSingleOptimizer extends BracketedSingleOptimizer and adds a single tunable parameter:

getTolerance() / setTolerance(double) — the fractional precision to isolate the minimum to; default 3e-8.

BracketedSingleOptimizer itself provides computeBracket(minEvalPoint, middleEvalPoint) (and overloads defaulting the middle point, or the whole range) to run the downhill bracketing search described above, plus setBracket(a, b, c) to supply an already-known bracket directly instead. After minimize() completes, getResult() and getEvaluationAtResult() return the minimizing point and the function value there.

Press et al., 2007 recommends golden section search specifically for functions whose second (or lower) derivative is discontinuous — in that case Brent’s Method's parabolic interpolation offers no real advantage, and the simpler, more predictable golden section search is just as good a choice.

Requesting a tolerance smaller than the square root of the machine’s floating-point precision is generally pointless: near the minimum , the function is well approximated by , so the correction term becomes indistinguishable from roundoff once drops below roughly .

Example

final var listener = new SingleDimensionFunctionEvaluatorListener() {
    @Override
    public double evaluate(final double point) {
        return (point - 2.0) * (point - 2.0);
    }
};

final var optimizer = new GoldenSingleOptimizer();
optimizer.setListener(listener);
optimizer.computeBracket(0.0, 1.0);
optimizer.minimize();

final var xmin = optimizer.getResult();          // approximately 2.0
final var fmin = optimizer.getEvaluationAtResult(); // approximately 0.0