【最优化】简单线搜索（黄金分割法，斐波那契法......）

黄金分割法（Golden Section Method）和斐波那契法（Fibonacci Method）极为相似，唯一的区别就是试探点的公式不一样而已。相比较，斐波那契法更为灵活更为强大。斐波那契法介于二分搜索和黄金分割法之间。

Fibonacci数列：1，1，2，3，5，8，13，21，34，55，89，144......

可见，相邻两项的比值从0.5渐渐变为0.618并趋近于0.618。

黄金分割法的算法如下：

斐波那契法算法如下：

Python程序：

所用函数如下：

f(x)=min{x/2, 2-(x-3)^2, 2-x/2}

# -*- coding: utf-8 -*-
# @Author : ZhaoKe
# @Time : 2022-10-09 15:29
import numpy as np

def fun(x):
    f1 = x / 2
    f2 = 2-(x-3)**2
    f3 = 2-x/2
    f = np.vstack((f1, f2, f3))
    # print(f)
    return -np.min(f, axis=0)
def golden_section(f, left, right, eps):
    print("===========Golden Section Search==========")
    lam = left + 0.382*(right-left)
    mu = left + 0.618*(right-left)
    k = 1
    tol = right - left
    flam, fmu = 0, 0
    while tol > eps and k < 100000:
        flam = f(lam)
        fmu = f(mu)
        if flam > fmu:
            left = lam
            lam = mu
            mu = left + 0.618*(right-left)
        else:
            right = mu
            mu = lam
            lam = left + 0.382*(right-left)
        k = k + 1
        tol = np.abs(right-left)
    if k == 100000:
        print("找不到最小值")
        x = None
        minf = None
        return
    x = (left + right) / 2
    min_f = f(x)
    print("极值点：", x, "，函数值: ", min_f)


def fibonacci_search(f, left, right, eps):
    print("===========Fibonacci Search==========")
    N = (right-left) / eps
    n = 1
    Fib = [1, 1]
    c = Fib[1] - N
    flam, fmu = 0, 0
    while c < 0:
        n += 1
        Fib.append(Fib[n-1] + Fib[n-2])
        c = Fib[n] - N
    print(Fib[0:12])
    lam = left + Fib[n-2]/Fib[n] * (right - left)
    mu = left + Fib[n-1]/Fib[n] * (right - left)
    k = 1
    while k < n-3:
        flam = fun(lam)
        fmu = fun(mu)
        if flam > fmu:
            left = lam
            lam = mu
            mu = left + Fib[n-1-k]/Fib[n-k] * (right-left)
        else:
            right = mu
            mu = lam
            lam = left + Fib[n-2-k]/Fib[n-k] * (right-left)
        k += 1
    x = (left + right) / 2
    min_f = f(x)
    print("极值点：", x, "，函数值: ", min_f)


if __name__ == '__main__':
    golden_section(fun, 0, 8, 0.05)
    fibonacci_search(fun, 0, 8, 0.03)

计算结果：

===========Golden Section Search==========
极值点： 2.013992448832476 ，函数值:  [-0.99300378]
===========Fibonacci Search==========
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
极值点： 2.0053050397877983 ，函数值:  [-0.99734748]

显然两个算法所得结果都与真实值极为相近（见上图。）