本章主要讨论一维函数的最小化问题算法 一维搜索的重要性:

• 一维搜索是高位搜索的特例, 一维搜索能启发高维搜索方法.

• 一维搜索算法时高维搜索算法的一部分(用于决定步长).

定义1 (单峰函数) 若一维函数 在定义 上有唯一局部极小值点 则 在 在 上是单峰函数(unimodal function).

黄金分割法

黄金分割法用到的是单峰函数一个简单的性质:

若选择 满足 且 则 ; 若 则

这实际上就提供了一种简单的找出最小值的方法, 即在 中任意选择 比较 利用上述性质更新区间, 在更新后的区间再选择 重复进行下去直到达到我们想要的精度(区间压缩到一定的长度).

我们需要关注的是点的选择方式. 一种朴素的想法是等比压缩, 选择点后得到的左右两个区间与原区间的比值相等且恒定, 即若第 次更新后的区间为 则在第 次选择的点 满足 且 用语言描述就是:

那么根据性质极值点应该在区间 或者区间 中, 新的区间的长度是原来的区间的 倍, 故为等比压缩.

这种方式每次需要计算两个点的函数值, 现欲减少运算量. 假设现在的新区间为 在该区间内上一步求出的 的函数值是已知的, 我们可以利用这一函数值. 即如果有合适的 使得在选择 时, 有 或者 那么我们每次只需要计算一个点. 经过计算, 当 时解得 不符合题意舍去; 当 时有 解得 且此时有 选择 后, 每次迭代只需计算一次函数 的值. 此时能够使得短区间 ( 或 ) 与长区间 长度的比值等于长区间与整个区间 的比值, 这是黄金分割最经典的模型, 这也是其名字的由来.

同理, 若新区间为 令 或者 仍然能得到与上面相同的结果.

进行 次后 所在的区间的长度变为原来的 这是最终的压缩比例, 称为总压缩比.

Python实现

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

import math

def f(x):
    return math.pow(x,2)+4*math.cos(x)#函数

l=float(input())
r=float(input()) #初始化区间
rho=(3-math.sqrt(5))/2
e=float(input()) #精度
a=l
b=r
k=1 #迭代次数
a=l+(r-l)*rho
b=r-(r-l)*rho
while(math.fabs(l-r)>e):
    print("Iterations:",k)
    print("a=%.4f" % a)
    print("b=%.4f" % b)
    print("f(a)=%.4f" % f(a))
    print("f(b)=%.4f" % f(b))
    if f(a)>f(b):
        l=a
        a=b
        b=r-(r-l)*rho
    else:
        r=b
        b=a
        a=l+(r-l)*rho
    print("The new section is","[","%.4f" % l ,",","%.4f" % r,"]")
    k+=1

上面是目标函数为 初始区间为 且精度 的例子，输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Iterations: 1
a=1.3820
b=1.6180
f(a)=2.6607
f(b)=2.4292
The new section is [ 1.3820 , 2.0000 ]
Iterations: 2
a=1.6180
b=1.7639
f(a)=2.4292
f(b)=2.3437
The new section is [ 1.6180 , 2.0000 ]
Iterations: 3
a=1.7639
b=1.8541
f(a)=2.3437
f(b)=2.3196
The new section is [ 1.7639 , 2.0000 ]
Iterations: 4
a=1.8541
b=1.9098
f(a)=2.3196
f(b)=2.3171
The new section is [ 1.8541 , 2.0000 ]

MATLAB实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

%从左到右依次为函数,变量,区间左端点,区间右端点,精度,返回极值点所在的区间
function [a,b]=GoldenCut(f,var,left,right,eps)
rho=(3-sqrt(5))/2;
k=1;
L=right-left;
a=left+L*rho;
b=right-L*rho;
while abs(right-left)>eps
    f_a=subs(f,var,a);
    f_b=subs(f,var,b);
    if f_a>f_b
        left=a;
        a=b;
        b=right-(right-left)*rho;
    else
        right=b;
        b=a;
        a=left+(right-left)*rho;
    end
    k=k+1;
end
a=left;
b=right;

斐波那契法

我们的目标是找到极小值点 在用算法逼近极小值点的时候, 精度越高越好, 这表现在我们利用算法求出的 所在的区间的长度上. 在黄金分割法中最终区间的长度为 其中 为初始区间长度, 于是为了改进算法我们希望降低总压缩比, 提高 的精度.

在黄金分割法中我们令比例 恒定不变, 为了降低总压缩比, 现令每一次取点的 都不同, 记第 次取点的比例为 区间长度为 则有 得到 假设进行了 次迭代, 那么总压缩比为 我们想要解决的就是如下的优化问题: 可以证明数列 是上述优化问题的最优解, 其中 是斐波那契数列, 这样可以得到总压缩比为

需要注意的是在第 次迭代时有 这意味着第 次选择点时两个点会重合. 为了避免这一情况的发生, 在第 次选择点修正 为 其中 是任意小的正数. 修正后的总压缩比为

因为斐波那契数列相邻两项之比在 的极限是 所以斐波那契法最终的压缩比实际上与黄金分割法变化不大. 因此黄金分割法比斐波那契法用得更多.

Python实现

确定 时使用的不等式为

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

import math

def g(x):
    return math.pow(x,2)+4*math.cos(x)

l=float(input())
r=float(input()) #初始化区间
e=float(input()) #精度
epsilon=float(input()) #微扰
F=[1,1]
N=1
while True: #确定迭代次数N
    F.append(F[N]+F[N-1])
    if F[N+1]>=(2*epsilon+1)*(r-l)/e:
        break
    N+=1
print("N=",N)
rho=1-F[N]/F[N+1]
a=l+(r-l)*rho
b=r-(r-l)*rho
for i in range(N):
    print("Iterations:",i+1)
    print("rho=%.4f" % rho)
    print("a=%.4f" % a)
    print("b=%.4f" % b)
    print("f(a)=%.4f" % g(a))
    print("f(b)=%.4f" % g(b))
    if i==N-2:#下一次的rho
        rho=0.5-epsilon
    else:
        rho=1-F[N-i-1]/F[N-i]
    if g(a)>g(b):
        l=a
        a=b
        b=r-(r-l)*rho
    else :
        r=b
        b=a
        a=l+(r-l)*rho
    print("The new section is","[","%.4f" % l ,",","%.4f" % r,"]")

仍然以目标函数 初始区间为 且精度 为例，附加 经计算输出：

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

N= 4
Iterations: 1
rho=0.3750
a=1.3750
b=1.6250
f(a)=2.6688
f(b)=2.4239
The new section is [ 1.3750 , 2.0000 ]
Iterations: 2
rho=0.4000
a=1.6250
b=1.7500
f(a)=2.4239
f(b)=2.3495
The new section is [ 1.6250 , 2.0000 ]
Iterations: 3
rho=0.3333
a=1.7500
b=1.8750
f(a)=2.3495
f(b)=2.3175
The new section is [ 1.7500 , 2.0000 ]
Iterations: 4
rho=0.4500
a=1.8750
b=1.8875
f(a)=2.3175
f(b)=2.3169
The new section is [ 1.8750 , 2.0000 ]

二分法

二分法要求目标函数可导. 并根据极小值点的导数为零这一条件用二分法找出导函数的零点.实际上是零点存在性定理. 每次选择中点, 每次的压缩比为 迭代 次的总压缩比为 这比黄金分割法与斐波那契法的压缩比更优秀.

平方根倒数速算法

待补充.

多维优化问题中的一维优化

待补充。