A demonstration of the golden section search algorithm

goldensection.py

from math import sqrt
phi = (1 + sqrt(5))/2
resphi = 2 - phi
 
# a and b are the current bounds; the minimum is between them.
# c is the center pointer pushed slightly left towards a
def goldenSectionSearch(f, a, c, b, absolutePrecision):
    if abs(a - b) < absolutePrecision:
        return (a + b)/2
    # Create a new possible center, in the area between c and b, pushed against c
    d = c + resphi*(b - c)
    if f(d) < f(c):
        return goldenSectionSearch(f, c, d, b, absolutePrecision)
    else:
        return goldenSectionSearch(f, d, c, a, absolutePrecision)

f = lambda x: x**2

def test_search():
    assert abs(goldenSectionSearch(f, -1, (-1 + resphi*2), 1, 1e-10)) < 1e-10
    print "OK!"

if __name__ == '__main__':
    test_search()