Golden-section search in Python
Unimodal minimization that reuses one function evaluation per step by shrinking the interval by the golden ratio.
- File
golden_section_search.py, 34 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/golden-section-search/. The authors are listed in prov/ZDRDPS.jsonl.
import math
from typing import Callable
RHO = (math.sqrt(5) - 1) / 2 # 1/phi, about 0.618
def golden_section_min(f: Callable[[float], float], a: float, b: float, steps: int = 100) -> float:
"""Return a point near the minimum of a strictly unimodal f on [a, b].
It evaluates f exactly steps + 2 times. After the loop the minimum lies in
an interval of length (b - a) * RHO ** (steps + 1), whose midpoint is returned.
"""
rho = RHO # @line L1
c = b - rho * (b - a) # @line L2
d = a + rho * (b - a)
fc = f(c) # @line L3
fd = f(d)
for _ in range(steps): # @line L4
if fc < fd: # @line L5
b, d, fd = d, c, fc # @line L6
c = b - rho * (b - a)
fc = f(c)
else:
a, c, fc = c, d, fd # @line L7
d = a + rho * (b - a)
fd = f(d)
if fc < fd: # @line L8
b = d
else:
a = c
return a + (b - a) / 2 # @line L9
test_golden_section_search.py 60 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/golden-section-search/. The authors are listed in prov/ZDRDPS.jsonl.
import random
from golden_section_search import RHO, golden_section_min
class Counter:
def __init__(self, f):
self.f = f
self.calls = 0
def __call__(self, x):
self.calls += 1
return self.f(x)
def test_example() -> None:
x = golden_section_min(lambda t: (t - 2) ** 2, 0.0, 5.0)
assert abs(x - 2.0) < 1e-7
def test_example_eight_evaluations() -> None:
f = Counter(lambda t: (t - 2) ** 2)
x = golden_section_min(f, 0.0, 5.0, steps=6)
assert f.calls == 8
assert abs(x - 1.99590) < 1e-4
assert abs(x - 2.0) <= 5.0 * RHO ** 7 / 2
def test_evaluation_count() -> None:
for steps in range(0, 30):
f = Counter(lambda t: abs(t - 0.3))
golden_section_min(f, 0.0, 1.0, steps)
assert f.calls == steps + 2
def test_bracket_bound_random() -> None:
rng = random.Random(7)
for _ in range(2000):
a = rng.uniform(-100, 100)
b = a + rng.uniform(0.1, 100)
m = rng.uniform(a, b)
steps = rng.randrange(0, 40)
left = rng.uniform(0.1, 5)
right = rng.uniform(0.1, 5)
f = lambda t: left * (m - t) if t < m else right * (t - m)
x = golden_section_min(f, a, b, steps)
assert abs(x - m) <= (b - a) * RHO ** (steps + 1) / 2 + 1e-9 * (b - a)
def test_maximum_by_negation() -> None:
x = golden_section_min(lambda t: -(t * (4 - t)), 0.0, 4.0, 80)
assert abs(x - 2.0) < 1e-7
def test_minimum_at_an_end() -> None:
assert golden_section_min(lambda t: t, 0.0, 1.0) < 1e-12
assert golden_section_min(lambda t: -t, 0.0, 1.0) > 1 - 1e-12
What the next level needs
- the tests did not run in this build