python最优化方法之一维搜索（黄金分割法+斐波那契法）

文章目录 1.概念2.遍历搜索3.优化算法3.1.一维搜索原则3.2.黄金分割法Code Block 3.3.斐波拉契法Code Block

1.概念

qquad 一维搜索是最优化方法最简单的一种，即求一个在(a,b)内，连续下单峰函数 f ( x ) f(x) f(x)的极小值。所谓下单峰函数就是只有一个极小值的函数。

2.遍历搜索

qquad 这个问题看似简单，我们只需要指定步长，从区间左端点搜索到右端点，每次根据步长新产生一个值，比对它和前两个值的大小。记录三个值从左到由依次为 x 1 x_1 x1​, x 2 x_2 x2​, x 3 x_3 x3​，若出现 x 1 > x 2 < x 3 x_1>x_2x2​Fn​}的定义如下： F 1 = F 2 = 1 , F n + 2 = F n + 1 + F n F_1=F_2=1,F_{n+2}=F_{n+1}+F_{n} F1​=F2​=1,Fn+2​=Fn+1​+Fn​ 取分点时， x 1 = a + F n − 2 F n ( b − a ) , x 2 = a + F n − 1 F n ( b − a ) x_1=a+frac{F_{n-2}}{F_n}(b-a),x_2=a+frac{F_{n-1}}{F_n}(b-a) x1​=a+Fn​Fn−2​​(b−a),x2​=a+Fn​Fn−1​​(b−a) { x 1 − a = F n − 2 F n ( b − a ) x 2 − a = F n − 1 F n ( b − a ) x 2 − x 1 = F n − 1 − F n − 2 F n ( b − a ) = F n − 3 F n ( b − a ) b − x 2 = F n − F n − 1 F n ( b − a ) = F n − 2 F n ( b − a ) egin{cases} x_1-a=frac{F_{n-2}}{F_n}(b-a) \x_2-a=frac{F_{n-1}}{F_n}(b-a) \x_2-x_1=frac{F_{n-1}-F_{n-2}}{F_n}(b-a)=frac{F_{n-3}}{F_n}(b-a) \b-x_2=frac{F_{n}-F_{n-1}}{F_n}(b-a)=frac{F_{n-2}}{F_n}(b-a) end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​x1​−a=Fn​Fn−2​​(b−a)x2​−a=Fn​Fn−1​​(b−a)x2​−x1​=Fn​Fn−1​−Fn−2​​(b−a)=Fn​Fn−3​​(b−a)b−x2​=Fn​Fn​−Fn−1​​(b−a)=Fn​Fn−2​​(b−a)​

1.若 x 1 ＜ x 2 x_1＜x_2 x1​＜x2​，则取新区间为 [ a , x 2 ] [a,x_2] [a,x2​]，则 D E ‾ = F n − 3 F n ( b − a ) ， I J ‾ = F n − 1 F n ( b − a ) , C D ‾ = F n − 2 F n ( b − a ) , C D I J = F n − 2 F n − 1 ， 因 此 D 相 当 于 I J 中 的 x 2 的 位 置 只 需 要 再 取 x 1 = a + F n − 3 F n − 1 ( b − a ) 即 可 overline{DE}=frac{F_{n-3}}{F_n}(b-a)，overline{IJ}=frac{F_{n-1}}{F_n}(b-a),overline{CD}=frac{F_{n-2}}{F_n}(b-a), \ frac{CD}{IJ}=frac{F_{n-2}}{F_{n-1}}，因此D相当于IJ中的x_2的位置\只需要再取x_1=a+frac{F_{n-3}}{F_{n-1}}(b-a)即可 DE=Fn​Fn−3​​(b−a)，IJ=Fn​Fn−1​​(b−a),CD=Fn​Fn−2​​(b−a),IJCD​=Fn−1​Fn−2​​，因此D相当于IJ中的x2​的位置只需要再取x1​=a+Fn−1​Fn−3​​(b−a)即可

2.若 x 1 > x 2 x_1>x_2 x1​>x2​，则取新区间为 [ x 1 , b ] [x_1,b] [x1​,b]，则 D E ‾ = F n − 3 F n ( b − a ) ， G H ‾ = F n − 1 F n ( b − a ) , C D ‾ = F n − 2 F n ( b − a ) , D E G H = F n − 3 F n − 1 ， 因 此 D 相 当 于 G H 中 的 x 1 的 位 置 只 需 要 再 取 x 2 = a + F n − 2 F n − 1 ( b − a ) 即 可 overline{DE}=frac{F_{n-3}}{F_n}(b-a)，overline{GH}=frac{F_{n-1}}{F_n}(b-a),overline{CD}=frac{F_{n-2}}{F_n}(b-a), \ frac{DE}{GH}=frac{F_{n-3}}{F_{n-1}}，因此D相当于GH中的x_1的位置\只需要再取x_2=a+frac{F_{n-2}}{F_{n-1}}(b-a)即可 DE=Fn​Fn−3​​(b−a)，GH=Fn​Fn−1​​(b−a),CD=Fn​Fn−2​​(b−a),GHDE​=Fn−1​Fn−3​​，因此D相当于GH中的x1​的位置只需要再取x2​=a+Fn−1​Fn−2​​(b−a)即可

对于要求精度esp，取压缩比 C = b − a e s p ， F n = m i n { x ∣ x ≥ C , x ∈ N + } C=frac{b-a}{esp}，F_n=minlbrace x|x≥C,x∈N^+ brace C=espb−a​，Fn​=min{x∣x≥C,x∈N+}，按照上述方法迭代至分母为 F 2 F_2 F2​为止，最后按照以下方法进行：

Code Block

首先我们需要一个生产斐波那契数列（Fabonaci）的函数：

# 在本案例中，使用一次性生成斐波拉契列表的方法算法复杂度更低# 生成的斐波拉契数列F(0)=0,F(1)=F(2)=1,剩余项和普通斐波拉契数列类似def Fab_list(Fmax): a,b=0,1 Fablist = [a,b] # 返回一个列表 while Fablist[-1]