最优化——线搜索-斐波那契数列法

斐波那契数列法

斐波那契数列法与二分法相比没有太大的区别，只是nuk与lambdak的更新方式不一样，如下。


其中F为斐波那契数列，k为迭代次数，n为数组大小。

---

Python代码：

def FibonacciArray(size):
    fibonacciArray = [1,1]
    for i in range(2,size):
        fibonacciArray.append(fibonacciArray[i-1] + fibonacciArray[i-2])
    return fibonacciArray

fibonacciArray = FibonacciArray(50)
def FibonacciMethod(a0, b0,):
    epsilon = 0.0001
    ak = a0
    bk = b0
    k = 0
    n = len(fibonacciArray) - 1
    while True:
        if bk -ak < epsilon:
            xstar = (bk + ak) / 2
            fstar = calFx(xstar)
            return xstar, fstar
        else:
            k = k + 1
            lambdaK = ak + (fibonacciArray[n - k - 1] / fibonacciArray[n - k + 1]) * (bk - ak)
            muK= ak + (fibonacciArray[n - k] / fibonacciArray[n - k + 1]) * (bk - ak)
            fLambdaK = calFx(lambdaK)
            fMuK = calFx(muK)
            if fLambdaK > fMuK:
                ak = lambdaK
                continue
            else:
                bk = muK
                continue
xstar, fstar = FibonacciMethod(-3,5)
print("FibonacciMethod xstar is %s" % xstar)
print("FibonacciMethod fstar is %s" % fstar)