Performance Zone is brought to you in partnership with:
DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Optimization - Minimum - Search And Golden Rule

06.15.2008
| 6014 views |
  • submit to reddit
        
from math import sin
def f(x):
    return ((x**4))

def optMinSearch(f, xi, h, t=1.0e-9):
    ssx = xi
    x = xi
    fx = f(x)
    sx = x
    x += h
    fxn = f(x)
    n = 0

    while abs(fxn-fx) > t :
        while fx > fxn:
            n += 1
            fx = fxn
            ssx = sx
            sx = x
            x += h
            fxn = f(x)
    
        xx = x
        h = h / 2
        x = ssx
        fx = f(x)
        sx = x
        x += h
        fxn = f(x)
        n += 1
    
    
    return x, fxn, n, sx, xx


    

def optMinGold(f, xi, xf, t=1.0e-9):
    # constants
    A = 0.6180339887
    
    n = 0
    
    x1 = xi
    x2 = xf

    x3 = x1 + A * (x2-x1)
    x4 = x2 - A * (x2-x1)
    
    fx3 = f(x3)
    fx4 = f(x4)
    
    while abs(x2-x1) > t:
        #print n, x1, x2, abs(x2-x1)
        n+=1
        if fx3 < fx4:
        # fx4 > fx3
            x1 = x4
            x4 = x3
            x3 = x1 + A * (x2-x1)
        else:
         # fx4 < fx3
            x2 = x3
            x3 = x4
            x4 = x2 - A * (x2-x1)
        
        fx3 = f(x3)
        fx4 = f(x4)
        
    return (x1,x2,n)


xmin, fmin, n, sx, xx = optMinSearch(f, -2.0, 0.1)
print xmin
print fmin
print n
print "-----"


(x1,x2,n) = optMinGold(f, -2.0, 2.0)
print x1
print f(x1)
print x2
print f(x2)
print n