NumericalOptimization/univariate/elimination/golden_section.py

numerical_optimization_univariate_elimination_golden_section.py

#-*- coding: utf-8 -*-
import math

def _verbose(a, b, x1, x2, f1, f2):
    print 'a=%.5f, b=%.5f, x1=%.5f, f(x1)=%.5f, x2=%.5f, f(x2)=%.5f'%(a, b, x1, f1, x2, f2)

def minimize(function, a, b, epsilon=1e-5, verbose=False, golden_ratio=(-1.0+math.sqrt(5.0))/2.0):
    L = b-a
    while L > epsilon:
        L = abs(b-a)
        _ = [a + (golden_ratio * L), b - (golden_ratio * L)]
        x1 = min(_)
        x2 = max(_)
        f1 = function(x1)
        f2 = function(x2)
        if verbose: _verbose(a, b, x1, x2, f1, f2)
        if f1 > f2:
            a = x1
        else:
            b = x2
    return x1

numerical_optimization_univariate_elimination_golden_section_execute.py

>>> minimize( lambda x: abs(x-0.3), 0.0, 1.0 )
0.29999647723245804
>>> minimize( lambda x: abs(x-0.3), 0.0, 1.0, epsilon=1e-3, verbose=True )
a=0.00000, b=1.00000, x1=0.38197, f(x1)=0.08197, x2=0.61803, f(x2)=0.31803
a=0.00000, b=0.61803, x1=0.23607, f(x1)=0.06393, x2=0.38197, f(x2)=0.08197
a=0.00000, b=0.38197, x1=0.14590, f(x1)=0.15410, x2=0.23607, f(x2)=0.06393
a=0.14590, b=0.38197, x1=0.23607, f(x1)=0.06393, x2=0.29180, f(x2)=0.00820
a=0.23607, b=0.38197, x1=0.29180, f(x1)=0.00820, x2=0.32624, f(x2)=0.02624
a=0.23607, b=0.32624, x1=0.27051, f(x1)=0.02949, x2=0.29180, f(x2)=0.00820
a=0.27051, b=0.32624, x1=0.29180, f(x1)=0.00820, x2=0.30495, f(x2)=0.00495
a=0.29180, b=0.32624, x1=0.30495, f(x1)=0.00495, x2=0.31308, f(x2)=0.01308
a=0.29180, b=0.31308, x1=0.29993, f(x1)=0.00007, x2=0.30495, f(x2)=0.00495
a=0.29180, b=0.30495, x1=0.29682, f(x1)=0.00318, x2=0.29993, f(x2)=0.00007
a=0.29682, b=0.30495, x1=0.29993, f(x1)=0.00007, x2=0.30185, f(x2)=0.00185
a=0.29682, b=0.30185, x1=0.29874, f(x1)=0.00126, x2=0.29993, f(x2)=0.00007
a=0.29874, b=0.30185, x1=0.29993, f(x1)=0.00007, x2=0.30066, f(x2)=0.00066
a=0.29874, b=0.30066, x1=0.29947, f(x1)=0.00053, x2=0.29993, f(x2)=0.00007
a=0.29947, b=0.30066, x1=0.29993, f(x1)=0.00007, x2=0.30021, f(x2)=0.00021
a=0.29947, b=0.30021, x1=0.29975, f(x1)=0.00025, x2=0.29993, f(x2)=0.00007
0.299753615984702