黄金分割法

发表于 | 分类于 |
字数统计: 363字

黄金分割法(0.618法)适用于任何单峰值函数𝜙(𝑡)求极小点的问题，甚至对函数可以不要求连续。

单峰函数
设𝜙 : [𝑎, 𝑏] ⊂ R → R，𝑡⋆是在[𝑎, 𝑏]上的全局极小点，如果对于[𝑎, 𝑏]上的任意两点𝑡1, 𝑡2，且𝑡1 < 𝑡2都有
𝜙(t1) > 𝜙(t2), if t2 < t*
𝜙(t1) < 𝜙(t2), if t1 > t*
那么称𝜙(𝑡)是区间[𝑎, 𝑏]上的单峰函数。若𝑡1 < 𝑡⋆ < 𝑡2，称[𝑡1, 𝑡2]为搜索区间。

算法步骤：
步骤1 确定𝜙(𝑡)的初始搜索区间[𝑎, 𝑏]。
步骤2 计算𝑡2 = 𝑎 + 𝛽(𝑏 − 𝑎)，𝜙2 = 𝜙(𝑡2)。
步骤3 计算𝑡1 = 𝑎 + 𝛼(𝑏 − 𝑎)，𝜙1 = 𝜙(𝑡1)，。
步骤4 若𝑡2-𝑡1≤ 𝜀，停机；否则，转步骤5。
步骤5 若𝜙(𝑡1) ≤ 𝜙(𝑡2)，则𝑏 = 𝑡2, 𝑡2 = 𝑡1, 𝜙(𝑡2) = 𝜙(𝑡1), 𝑡1 = 𝑎 + 𝛼(𝑏 − 𝑎), 𝜙1 = 𝜙(𝑡1);
否则，𝑎 = 𝑡1, 𝑡1 = 𝑡2, 𝜙(𝑡1) = 𝜙(𝑡2), 𝑡2 = 𝑎 + 𝛽(𝑏 − 𝑎), 𝜙2 = 𝜙(𝑡2).然后转步骤4。

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
import math
from scipy.optimize import fmin,fminbound
# one dimension golden search
def f ( x ):
    L = math.exp(-x)+x**2
    return L
def golden(f ,*args):
    if not('a' in dir()):
        a=[]
        b=[]
    a.append(args[0])
    b.append(args[1])
    L=1e-16  # tolrence for convergence
    n=80   # max steps for iteration
    #a,b is the region containing opt point
    lambda1=a[0]+0.382*(b[0]-a[0])
    miu1=a[0]+0.618*(b[0]-a[0])
    #lambda1 miu1 is the test point of golden search method
    for k in range(0,n):
        if abs(b[k]-a[k])<=L:
            solve=(a[k]+b[k])/2
            break
        f_lambda1=f(lambda1)
        f_miu1=f(miu1)
        if f_lambda1>f_miu1:
            a.append(lambda1)
            b.append(b[k])
            lambda2=miu1
            miu2=a[k+1]+0.618*(b[k+1]-a[k+1])
        else:
            a.append(a[k])
            b.append(miu1)
            miu2=lambda1
            lambda2=a[k+1]+0.382*(b[k+1]-a[k+1])
        lambda1=lambda2
        miu1=miu2
    print('optimum point  is ：',solve)
    return solve
print(golden(f,0,1))