Golden-section search
Golden-section search is a technique for finding the extremum (minimum or maximum) of a strictly unimodal function by successively narrowing the range of values inside which the extremum is known to exist. By leveraging the golden ratio (phi = (sqrt(5) – 1) / 2 approximately equal to 0.61803398875), the algorithm maintains invariant sub-interval proportions such that only one new function evaluation is required per iteration.
HOW-TO IMPLEMENT & CONFIGURE
- Modern runtime environment (Python 3.8+ or C++17/Rust 1.60+)
- Floating-point unit (FPU) adhering to IEEE 754 double-precision standard
- Strictly unimodal objective function over the closed interval [a, b]
Step 1
Define the mathematical constants and initialize the precision thresholds. Ensure floating-point tolerances (epsilon) prevent infinite iteration due to machine precision limits.
import math
# Define the golden ratio conjugate
PHI = (math.sqrt(5.0) - 1.0) / 2.0
# Tolerance for convergence
EPSILON = 1e-9Step 2
Implement the iterative golden-section search loop. Maintain interior points x1 and x2 based on the golden ratio proportional splits, updating bounds until the interval size is within tolerance.
def golden_section_search(func, a, b, tol=1e-9):
"""
Finds the minimum of a unimodal function `func` on the interval [a, b].
"""
phi = (math.sqrt(5.0) - 1.0) / 2.0
# Create initial interior points
x1 = b - phi * (b - a)
x2 = a + phi * (b - a)
f1 = func(x1)
f2 = func(x2)
while (b - a) > tol:
if f1 < f2:
# Minimum is to the left of x2
b = x2
x2 = x1
f2 = f1
x1 = b - phi * (b - a)
f1 = func(x1)
else:
# Minimum is to the right of x1
a = x1
x1 = x2
f1 = f2
x2 = a + phi * (b - a)
f2 = func(x2)
return (a + b) / 2.0Step 3
Write rigorous unit tests using well-known convex test functions like the parabolas or shifted absolute value functions to guarantee correctness.
def test_golden_section():
# Test function: f(x) = (x - 2.5)^2 + 1
# Expected minimum at x = 2.5
objective = lambda x: (x - 2.5)**2 + 1.0
min_x = golden_section_search(objective, 0.0, 5.0)
assert abs(min_x - 2.5) < 1e-6, f"Expected 2.5, got {min_x}"
print("Golden-section search unit test passed successfully.")
if __name__ == '__main__':
test_golden_search()Step 4
Add guards against non-unimodal inputs, NaN or infinite function evaluations, and catastrophic cancellation during interval updates.
def hardened_golden_section(func, a, b, max_iter=1000, tol=1e-9):
if a >= b:
raise ValueError("Lower bound 'a' must be strictly less than upper bound 'b'")
phi = (math.sqrt(5.0) - 1.0) / 2.0
x1 = b - phi * (b - a)
x2 = a + phi * (b - a)
f1, f2 = func(x1), func(x2)
if math.isnan(f1) or math.isnan(f2) or math.isinf(f1) or math.isinf(f2):
raise RuntimeError("Objective function evaluated to NaN or Inf.")
for _ in range(max_iter):
if (b - a) < tol:
break
if f1 < f2:
b = x2
x2 = x1
f2 = f1
x1 = b - phi * (b - a)
f1 = func(x1)
else:
a = x1
x1 = x2
f1 = f2
x2 = a + phi * (b - a)
f2 = func(x2)
else:
raise TimeoutError("Maximum iterations reached without convergence.")
return (a + b) / 2.0Mathematical Foundation & Invariant Preservation
Golden-section search relies on the property of the golden ratio where the ratio of the whole interval to the larger segment equals the ratio of the larger segment to the smaller segment. Specifically, given an interval [a, b] with interior points x1 and x2, when an endpoint is discarded, the surviving interior point automatically serves as one of the interior points for the next iteration. This property ensures that exactly one function evaluation is carried out per cycle, minimizing expensive black-box evaluations.
Complexity Analysis
The worst-case and average-case time complexity is O(log((b – a) / tolerance)), as the search interval length shrinks by a factor of roughly 0.618033 per iteration, matching the asymptotic efficiency of bisection search while requiring fewer function evaluations in practice than standard ternary search. The space complexity is strictly O(1), requiring only a constant number of scalar registers to store bounds and evaluation outputs.
Architectural Anti-Patterns & Edge Cases
A primary pitfall in engineering implementations is deploying golden-section search on multimodal functions. If the objective function contains local minima outside the global basin of attraction, the algorithm converges to a sub-optimal local extremum. Additionally, developers must guard against floating-point underflow when intervals become extremely narrow, ensuring that (b – a) does not prematurely reach machine epsilon.
📚 STANDARDS & ACADEMIC RFC CITATIONS
- Kiefer, J. (1953). Sequential minimax search for a maximum. Proceedings of the American Mathematical Society, 4(3), 502-506.
- Press, W. H., Teukolsky, S. A., Vetterling, W. T., & Flannery, B. P. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press.
