Does it require derivatives?

No; it uses comparisons of function values.

Why not choose two entirely new points each time?

Golden spacing permits reuse, reducing the number of fresh evaluations needed to continue the search.

Can it find the global minimum of any function?

No. The interval-retention argument relies on unimodality and reliable comparisons.

AI Glossary / Mathematics and optimization / Advanced

Golden-section search

Definition

Golden-section search is a derivative-free method for locating a minimum of a unimodal function on an interval. It compares function values at two interior points and repeatedly discards a portion of the interval, using golden-ratio spacing to reuse one previous evaluation at each step.

What it means

The method suits a one-variable problem whose objective decreases toward a minimum and increases afterward within the chosen interval. It needs function values rather than derivatives, which is useful when derivatives are unavailable or inconvenient to calculate.

Its reliability depends on the shape assumption and trustworthy comparisons. An arbitrary function with several valleys is not covered by the same guarantee. Narrowing an interval is only meaningful if the retained interval continues to contain the minimum being sought.

How it works

Let rho = (square root of 5 − 1) / 2, approximately 0.618034. For an interval [a, b], place c = b − rho(b − a) and d = a + rho(b − a), so c is left of d.

If f(c) is smaller than f(d), retain [a, d]. If f(d) is smaller, retain [c, b]. Under strict unimodality, equality permits retaining the middle interval, or a compatible standard tie-handling rule. The special spacing allows one old interior point and its function value to serve in the next comparison.

The standard one-sided reductions multiply interval width by rho. Continue until the retained width meets a suitable positional tolerance or an evaluation limit is reached. Numerical implementations must also account for rounding, indistinguishable function values and any noise in the objective.

Three practical examples

1. Deterministic simulation: tune one continuous parameter over a range where the modeled cost has a single valley. Reusing evaluations is valuable when each simulation is expensive.

2. Line search: minimize an objective along a selected direction after identifying an appropriate one-dimensional interval. The full multidimensional problem is not solved by that single line search.

3. Engineering calibration: select one setting that minimizes a deterministic mismatch measure. Establish the shape and allowed range before assuming an interval-based search will find the desired setting.

Think of it this way

Imagine searching for the bottom of a valley using height measurements at carefully placed checkpoints. Each comparison rules out one outer stretch. The checkpoint spacing is chosen so that one surviving measurement can be reused after the search area shrinks, reducing the need for new measurements.

Worked example

Consider an original teaching objective f(x) = (x − 1.3) squared + 2 on [0, 4]. Its minimum is known analytically at x = 1.3, which lets us check the search. In a real derivative-free application, that answer would usually be unknown.

The first interior points are approximately c = 1.527864 and d = 2.472136. Their function values are 2.051922 and 3.373903. Because the left value is smaller, retain [0, 2.472136]. Its width is about 0.618034 times the original width.

Reuse 1.527864 and evaluate the new left point 0.944272, where f is approximately 2.126542. The right interior value is now smaller, so retain [0.944272, 2.472136]. The true minimizer remains inside.

Next compare the reused point 1.527864 with the new right point 1.888544, whose objective is approximately 2.346384. Retain [0.944272, 1.888544]. A further new evaluation at 1.304952 gives approximately 2.000025, so the fourth reduction retains [0.944272, 1.527864].

After four reductions the width is about 0.583592, equal to 4 times rho to the fourth power. Although a tested point is already close to 1.3, the interval still supplies only a relatively loose position guarantee.

Suppose the required absolute error is at most 0.01 and we will report the retained interval's midpoint. A width no greater than 0.02 is sufficient. Eleven standard reductions leave width about 0.020100, slightly too wide; twelve leave about 0.012422. The midpoint then has a worst-case positional error at most about 0.006211, assuming every comparison preserved the minimizer.

That is a location bound, not automatically a bound on objective error for an arbitrary function. The distinction matters when the objective is steep or poorly scaled.

Illustrative case study

In a fictional production simulation, a team searches for the best continuous cooling setting. Initial deterministic runs suggest a single cost valley over the permitted range. Golden-section search reduces the number of new simulations by reusing a surviving evaluation after each interval update.

Later, engineers introduce random variation into the simulation. Two nearly equal settings now sometimes reverse order when rerun. The team recognizes that the original interval guarantee depended on reliable comparisons and evaluates a method designed for uncertain observations before using the noisy results operationally.

The lesson is that a sound search rule does not remove uncertainty from the function being measured. Evaluation quality and the shape assumption remain part of the problem.

Common misconceptions and mistakes

A unique global minimum alone does not establish unimodality. A function can have one best minimum while containing other local valleys and peaks.

The golden ratio does not confer a universal speed advantage. The benefit here is systematic interval reduction with evaluation reuse under specific assumptions.

Golden-section search minimizes a function; it is not ordinary bisection for finding a sign-changing root. Nor does it directly handle discrete parameters merely by rounding every proposed point.

A tiny interval does not validate an incorrect initial bracket or unreliable comparisons. Always distinguish the requested tolerance from what the evaluations can actually support.

Business use

The method can be useful for a single continuous decision variable when evaluations are costly, reproducible and suitably unimodal over the allowed range. Define the practical accuracy requirement before spending evaluations on progressively smaller differences.

Track the interval, function evaluations and stopping reason. For simulations or empirical measurements, investigate noise and multiple local minima before interpreting the returned point as the best feasible business decision.

Check your understanding

Which interval remains after the first comparison in the example?

Answer: Approximately [0, 2.472136].

What factor describes a standard width reduction?

Answer: Approximately 0.618034.

Why does width 0.02 suffice for midpoint error 0.01?

Answer: Any point inside the interval lies no farther than half its width from the midpoint.

Related terms

Derivative-free optimization
Line search
Unimodality
interval bracketing
Fibonacci search
Brent's minimization method
stopping tolerance

Learn next

Reproduce the interval updates while caching reused function values. Then test a function with several local minima and identify exactly where the unimodal interval-retention argument fails.

Sources

Charles Van Loan, Introduction to Scientific Computing, Chapter 8, Section 8.2.2, Cornell-hosted text on golden-section search: https://www.cs.cornell.edu/courses/cs4220/2014sp/CVLBook/chap8.pdf

The quadratic calculations and production-simulation case are original illustrations.

Previous: Golden response Next: Goldfeld - Quandt test