一维搜索方法
# 0x1.问题
目标函数为一元单值函数𝑓: ℝ→ℝ的最小优化问题。 利用迭代求解的方式。 记为一维搜索方法。
# 0x2.黄金分割法
前提: 目标函数在[𝑎~0~,𝑏~0~ ]上是==单峰的==,即存在唯一的局部极小点。
总体思路 利用迭代的方式,不断压缩含解区间,直到满足求解的精度。
黄金分割法𝜌为固定值。 考虑每次迭代使用不同的参数𝜌,即$𝜌_1,𝜌_2,…, 𝜌_𝑘,…$ 参数满足条件 $𝜌_{𝑘+1}=\frac{1−2𝜌_𝑘}{1−𝜌_𝑘 }=1−\frac{𝜌_𝑘}{1−𝜌_𝑘}$
计算精度方法:
$\frac12(b_0-a_0)(1-𝜌)^n \le \epsilon$
步骤:
取a~0~,b~0~区间
按照𝜌分隔,得到a1和b1点
判断a1和b1大小,如果a1较小,说明最小值在(a0,b1)区间,作为(a1,b1),则原a1作为新的区间的b2,再算出新的a2,继续求解;反之类似,原b1作为新的区间的a2。
不断迭代,达到精度值。。。
效果:
总压缩比:
$(1-𝜌)^n$
# 0x3.斐波那契数列法
$𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 (1−𝜌_1 )(1−𝜌_2 )…(1−𝜌_𝑁)$
$Subject\ to\ 𝜌_{𝑘+1}=1−\frac{𝜌_𝑘}{1−𝜌_𝑘 },𝑘=1,…,𝑁−1$ $0≤𝜌_𝑘≤\frac12,𝑘=1,2,…,𝑁$
具体方法
F1 F2 F3 F4 F5 F6 F7 F8
1 2 3 5 8 13 21 34
2
$𝜌_1=1−\frac{𝐹_𝑁}{𝐹_{𝑁+1}}$
$𝜌_2=1−\frac{𝐹_{𝑁-1}}{𝐹_{𝑁}}$
…
$𝜌_N=1−\frac{𝐹_1}{𝐹_2}$
其中$1-2𝜌_k=(1-𝜌_k)𝜌_{k+1}$
计算精度方法:
$\frac12(b_0-a_0)\frac {F_1}{F_{N+1}} \le \epsilon$
步骤:
取a~0~,b~0~区间
按照𝜌1分隔,每次的𝜌依次取斐波那契数列中值,得到a1和b1点
判断a1和b1大小,如果a1较小,说明最小值在(a0,b1)区间,作为(a1,b1),则原a1作为新的区间的b2,再算出新的a2,继续求解;反之类似,原b1作为新的区间的a2。
不断迭代,达到精度值。。。
效果:
总压缩比为:
$(1−𝜌_1 )(1−𝜌_2 )…(1−𝜌_𝑁)=\frac1{F_{N+1}}$
# 0x4.二分法
计算一个点的导数值 压缩比为1/2, 比斐波那契数列法的压缩比还要高。
# 0x5.牛顿法
找二次插值多项式,满足函数值、一阶导和二阶导条件
步骤:
$𝑞(𝑥)=𝑓(𝑥^{(𝑘)} )+𝑓′ (𝑥^{(𝑘)} )(𝑥−𝑥^{(𝑘)} )+1/2 𝑓′′ (𝑥^{(𝑘)} ) (𝑥−𝑥^{(𝑘)} )^2$ $𝑞^′ (𝑥)=0$
$𝑥^{(𝑘+1)}=𝑥^{(𝑘)}−\frac{𝑓′ (𝑥^{(𝑘)} )}{𝑓′′ (𝑥^{(𝑘)} ) }$
•上面的牛顿迭代公式,实际上搜索到f′(x)=0的解。
牛顿迭代公式,用于解方程𝑔(𝑥)=0 $𝑥^{(𝑘+1)}=𝑥^{(𝑘)}−\frac{g′ (𝑥^{(𝑘)} )}{g′′ (𝑥^{(𝑘)} ) }$
前提:
𝑓′′ (𝑥)>0时,牛顿法运行正常。
问题:
- 可能收敛到极大点
- 牛顿法的收敛性和初始值的选取有关,有可能不收敛。
# 0x6.割线法
利用割线的斜率代替切线的斜率
步骤:
迭代公式:
# 0x7.划界法
找到三点𝑎,𝑐,𝑏满足 𝑓(𝑐)<𝑓(𝑎) 𝑓(𝑐)<𝑓(𝑏)
# 0x8.多维优化问题中的一维搜索
$𝑥^{(𝑘+1)}=𝑥^{(𝑘)}+𝑎_𝑘 𝑑^{(𝑘)} \𝜙(𝑎)=𝑓(𝑥^{(𝑘)}+𝑎_𝑘 𝑑^{(𝑘)}) \𝜙′ (𝑎)=𝑑^{(𝑘)⊺} 𝛻𝑓(𝑥^{(𝑘)}+𝑎_𝑘 𝑑^{(𝑘)})$