黄金分割法（0.618法）python实现

黄金分割法的python实现

在准备学优化方法期末考试的时候拿到习题没有答案,就想写一个程序然后和自己算出来的答案对一下就写了个程序,考完试了留着也没用索性写一篇出来造福学弟学妹，黄金分割法通俗的讲就是给一个区间给一个函数在这个区间里求函数的最小值

1.一维搜索黄金分割法

这里搬一下书上的概念书上的概念严谨但确实不好懂做两道例题就好了其实
考察一维搜索问题：

{ m i n φ ( λ ) s . t . a 1 ≤ λ ≤ b 1

$$egin{cases} min&varphi(lambda)\ s.t.&a_1lelambdale b_1 end{cases}$$ {mins.t.​φ(λ)a1​≤λ≤b1​​
其中$\phi (\lambda )$为凸函数

$1^{。}$设$\epsilon >0$为允许的搜索区间最后的长度令$\alpha$=0.618则黄金分割法计算步骤如下

$$\begin{gathered} {\lambda }_1=a_1+(1-\alpha )(b_1-a_1)\phi ({\lambda }_1) \\ {\mu }_1=a_1+\alpha (b_1-a_1)\phi ({\mu }_1) \end{gathered}$$
令$k=1$

$2^{。}$若$b_k-a_k<\epsilon$，则计算结束，最优解${\lambda }^{\ast }\in [a_k,b_k]$,可取 ${\lambda }^{\ast }\approx (1/2)(a_k+b_k)$;否则$\phi ({\lambda }_k)>\phi ({\mu }_k)$, 则转$3^{。}$;若$\phi ({\lambda }_k)\le \phi ({\mu }_k)$,则转$4^{。}$

$3^{。}$令$a_{k+1}={\lambda }_k,b_{k+1}=b_k$,再令${\lambda }_{k+1}={\mu }_k,{\mu }_{k+1}=a_{k+1}+\alpha (b_{k+1}-a_{k+1})$，计算$\phi ({\mu }_{k+1})$转$5^{。}$

$4^{。}$令$a_{k+1}=a_k,b_{k+1}={\mu }_k$,再令${\mu }_{k+1}={\lambda }_k,{\lambda }_{k+1}=a_{k+1}+(1-\alpha )(b_{k+1}-a_{k+1})$，计算$\phi ({\mu }_{k+1})$转$5^{。}$

$5^{。}$令$k=k+1$,返回$2^{。}$

2.python代码实现

例：求解$\min \phi (\lambda )={\lambda }^2+2\lambda ,s.t.-3\le \lambda \le 5$
取$\epsilon =0.2$取精度为0.001
取三位小数用python的round(x,3)实现

# 只需改如下四个参数即可
f = lambda x: x**2 + 2*x
# 定义变量
e = 0.2       # 终止线
a = -3           # 左边
b = 5          # 右边


# 黄金分割法计算法则
lanb = lambda a, b : a + 0.382* (b -a)
mui = lambda a, b : a + 0.618* (b -a)

Mui = round(mui(a, b),3)
Mui_value = round(f(Mui), 3)

Lamb = round(lanb(a, b) ,3)
Lamb_value= round(f(Lamb), 3)

print(f'a={a} b={b}')
print(f'lanb:{Lamb}')
print(f'mui:{Mui}')
print(f'f(lanb)= {Lamb_value}')
print(f'f(mui)= {Mui_value}')
print() #换行最后看着舒服

while b - a > e: #判断是否到达终止线
    if Lamb_value < Mui_value:
        print('f(lanb) < f(mui)')
        print()
        b = Mui
        Mui = Lamb
        Lamb = round(lanb(a, b), 3)
    else:
        print('f(mui) < f(lanb) ')
        print()
        a = Lamb
        Lamb = Mui
        Mui = round(mui(a, b), 3)

    Mui_value = round(f(Mui), 3)
    Lamb_value = round(f(Lamb), 3)
    print(f'a={a} b={b}')
    print(f'lanb:{Lamb}')
    print(f'mui:{Mui}')
    print(f'f(lanb)= {Lamb_value}')
    print(f'f(mui)= {Mui_value}')


print(f'b-a绝对值为{abs(b -a)} 小于终止线 算法停止')
print(f'X⭐包含于[{a}, {b}]')
print(f'X⭐ = {round((a + b)/ 2, 3)}')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

3.运行结果

a=-3 b=5
lanb:0.056
mui:1.944
f(lanb)= 0.115
f(mui)= 7.667
f(lanb) < f(mui)

a=-3 b=1.944
lanb:-1.111
mui:0.056
f(lanb)= -0.988
f(mui)= 0.115
f(lanb) < f(mui)

a=-3 b=0.056
lanb:-1.833
mui:-1.111
f(lanb)= -0.306
f(mui)= -0.988
f(mui) < f(lanb) 

a=-1.833 b=0.056
lanb:-1.111
mui:-0.666
f(lanb)= -0.988
f(mui)= -0.888
f(lanb) < f(mui)

a=-1.833 b=-0.666
lanb:-1.387
mui:-1.111
f(lanb)= -0.85
f(mui)= -0.988
f(mui) < f(lanb) 

a=-1.387 b=-0.666
lanb:-1.111
mui:-0.941
f(lanb)= -0.988
f(mui)= -0.997
f(mui) < f(lanb) 

a=-1.111 b=-0.666
lanb:-0.941
mui:-0.836
f(lanb)= -0.997
f(mui)= -0.973
f(lanb) < f(mui)

a=-1.111 b=-0.836
lanb:-1.006
mui:-0.941
f(lanb)= -1.0
f(mui)= -0.997
f(lanb) < f(mui)

a=-1.111 b=-0.941
lanb:-1.046
mui:-1.006
f(lanb)= -0.998
f(mui)= -1.0
b-a绝对值为0.17 小于终止线 算法停止
X⭐包含于[-1.111, -0.941]
X⭐ = -1.026

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

结束

用的书上的例子，书上的${\lambda }_2$算成-1.112算错了应该是-1.111所以后面的结果不一样