一维搜索方法

文章目录

  • 一维搜索方法+多维牛顿法
    • 黄金分割法
    • 二分法
    • 牛顿法(用于求解方程)
    • 割线法
    • 牛顿法(高维——用于最优化)
      • 算法过程

一维搜索方法+多维牛顿法

​ 寻找一元函数的极值点的迭代求解方法。迭代算法从初始搜索点 x ( 0 ) x^{(0)} x(0)出发,产生一个迭代序列 x ( 1 ) x^{(1)} x(1) x ( 2 ) x^{(2)} x(2),…。通过当前迭代点 x ( k ) x^{(k)} x(k)和目标函数 f f f构建下一个迭代点 x ( k + 1 ) x^{(k+1)} x(k+1)

黄金分割法

迭代过程中压缩比例不变,只使用目标函数值 f f f

适用范围:黄金分割法适用于 [ a , b ] [a,b] [a,b]区间上任何单谷函数求极小值(存在唯一的局部极小点)问题。

思想:按照固定比例0.618取点,不断压缩极小点所在的区间,知道达到足够的精度水平。

算法搜索过程:

  1. 给出初始搜索区间 [ a , b ] [a,b] [a,b],以及收敛精度;
  2. 按照公式计算下一个迭代点及函数值;
  3. 根据函数值确定压缩后的新区间;
  4. 检查新区间是否满足收敛精度。

计算迭代点公式:
a 1 = a + 0.382 ( b − a ) a_1=a+0.382(b-a) a1=a+0.382(ba)

b 1 = a + 0.618 ( b − a ) b_1=a+0.618(b-a) b1=a+0.618(ba)

计算函数值,确定压缩后的新区间:
f ( a 1 ) < f ( b 1 ) − > [ a , b 1 ] f(a_1)<f(b_1)->[a,b_1] f(a1)<f(b1)>[a,b1]

f ( a 1 ) > = f ( b 1 ) − > [ a 1 , b ] f(a_1)>=f(b_1)->[a_1,b] f(a1)>=f(b1)>[a1,b]

压缩区间选中某一迭代点如 b 1 b_1 b1,未选中的迭代点 a 1 a_1 a1作为被选中迭代点 b 1 b_1 b1的下一个迭代点 b 2 b_2 b2,根据新区间 [ a , b 1 ] [a,b_1] [a,b1]计算 a 1 a_1 a1的下一个迭代点 a 2 a_2 a2,直到区间满足收敛精度。

二分法

要求函数在 [ a , b ] [a,b] [a,b]上连续可微,即一阶可导。

思想:利用一阶导数来连续压缩区间。

算法搜索过程:

  1. 确定初始区间的中点: x ( 0 ) = a + b 2 ​ x^{(0)}=\frac{a+b}{2}​ x(0)=2a+b
  2. 计算函数 f ​ f​ f x ( 0 ) ​ x^{(0)}​ x(0)处的一阶导数 f ‘ ( x ( 0 ) ) ​ f^`(x^{(0)})​ f(x(0))
  3. 如果 f ‘ ( x ( 0 ) ) > 0 f^`(x^{(0)})>0 f(x(0))>0,说明极小点在 x ( 0 ) x^{(0)} x(0)左侧,极小点的区间被压缩为 [ a , x ( 0 ) ] [a,x^{(0)}] [a,x(0)];如果 f ‘ ( x ( 0 ) ) < 0 f^`(x^{(0)})<0 f(x(0))<0,说明极小点在 x ( 0 ) x^{(0)} x(0)右侧,极小点的区间被压缩为 [ x ( 0 ) , b ] [x^{(0)},b] [x(0),b];如果 f ‘ ( x ( 0 ) ) = 0 f^`(x^{(0)})=0 f(x(0))=0,说明 x ( 0 ) x^{(0)} x(0)就是极小点,搜索结束。

在每次迭代中,区间的压缩比为 1 2 \frac{1}{2} 21,经过N次迭代后,整个区间的压缩比为 ( 1 2 ) N (\frac{1}{2})^N (21)N

牛顿法(用于求解方程)

要求函数二阶可导。

思想:构造一个经过点 ( x ( k ) , f ( x ( k ) ) ) (x^{(k)},f(x^{(k)})) (x(k),f(x(k)))处的二次函数,该函数在 x ( k ) x^{(k)} x(k)的一阶和二阶导数分别为 f ‘ ( x ( k ) ) f`(x^{(k)}) f(x(k)) f ‘ ‘ ( x ( k ) ) f``(x^{(k)}) f(x(k)),如下所示:
q ( x ) = f ( x ( k ) ) + f ‘ ( x ( k ) ) ( x − x ( k ) ) + 1 2 f ‘ ‘ ( x ( k ) ) ( x − x ( k ) ) 2 q(x)=f(x^{(k)})+f`(x^{(k)})(x-x^{(k)})+\frac{1}{2}f``(x^{(k)})(x-x^{(k)})^2 q(x)=f(x(k))+f(x(k))(xx(k))+21f(x(k))(xx(k))2
可以得到:
q ( x ( k ) ) = f ( x ( k ) ) q(x^{(k)})=f(x^{(k)}) q(x(k))=f(x(k))

q ‘ ( x ( k ) ) = f ‘ ( x ( k ) ) q`(x^{(k)})=f`(x^{(k)}) q(x(k))=f(x(k))

q ‘ ‘ ( x ( k ) ) = f ‘ ‘ ( x ( k ) ) q``(x^{(k)})=f``(x^{(k)}) q(x(k))=f(x(k))

q ( x ) q(x) q(x)即可认为是 f ( x ) f(x) f(x)的近似,因此求函数 f f f的极小点可近似于求解 q q q的极小点。

q q q的极小点应满足一阶必要条件:
0 = q ‘ ( x ) = f ‘ ( x ( k ) ) + f ‘ ‘ ( x ( k ) ) ( x − x ( k ) ) 0=q`(x)=f`(x^{(k)})+f``(x^{(k)})(x-x^{(k)}) 0=q(x)=f(x(k))+f(x(k))(xx(k))
x = x ( k + 1 ) x=x^{(k+1)} x=x(k+1),可得:
x ( k + 1 ) = x ( k ) − f ‘ ( x ( k ) ) f ‘ ‘ ( x ( k ) ) x^{(k+1)}=x^{(k)}-\frac{f`(x^{(k)})}{f``(x^{(k)})} x(k+1)=x(k)f(x(k))f(x(k))
上式(10)即为牛顿法的迭代公式。当 f ‘ ‘ ( x ) > 0 f``(x)>0 f(x)>0时,对于区间内的 x x x都成立,牛顿法正常;反之当 f ‘ ‘ ( x ) < 0 f``(x)<0 f(x)<0时,牛顿法可能收敛到极大值点。

可用于求解方程 g ( x ) = 0 g(x)=0 g(x)=0,用 g ( x ) g(x) g(x)替代 f ‘ ( x ) f`(x) f(x) g ‘ ( x ) g`(x) g(x)替代 f ‘ ‘ ( x ) ​ f``(x)​ f(x)

割线法

当牛顿法中函数二阶不可导时的方法。

二阶导数不存在,使用一阶导数对其近似得到:
f ‘ ‘ ( x ( k ) ) = f ‘ ( x ( k ) ) − f ‘ ( x ( k − 1 ) ) x ( k ) − x ( k − 1 ) f``(x^{(k)})=\frac{f`(x^{(k)})-f`(x^{(k-1)})}{x^{(k)}-x^{(k-1)}} f(x(k))=x(k)x(k1)f(x(k))f(x(k1))
将上式(11)代入牛顿法迭代公式(10),可得到新的迭代公式:
x ( k + 1 ) = x ( k ) − x ( k ) − x ( k − 1 ) f ‘ ( x ( k ) ) − f ‘ ( x ( k − 1 ) ) f ‘ ( x ( k ) ) x^{(k+1)}=x^{(k)}-\frac{x^{(k)}-x^{(k-1)}}{f`(x^{(k)})-f`(x^{(k-1)})}f`(x^{(k)}) x(k+1)=x(k)f(x(k))f(x(k1))x(k)x(k1)f(x(k))
可用于求解方程 g ( x ) = 0 ​ g(x)=0​ g(x)=0,用 g ( x ) ​ g(x)​ g(x)替代 f ‘ ( x ) ​ f`(x)​ f(x)

牛顿法(高维——用于最优化)

假设任务是优化一个目标函数 f ( x ) f(x) f(x),求函数 f ( x ) f(x) f(x)的极大极小问题,可以转化为求解函数 f ( x ) f(x) f(x)的导数 f ‘ ( x ) = 0 f`(x)=0 f(x)=0的问题。

将函数 f ( x ) f(x) f(x)在点 x ( k ) x^{(k)} x(k)处进行泰勒展开,忽略三次以上的项,可得到二次型近似函数:
f ( x ) ≈ f ( x ( k ) ) + ( x − x ( k ) ) T g ( k ) + 1 2 ( x − x ( k ) ) T F ( x ( k ) ) ( x − x ( k ) ) ≜ q ( x ) f(x)\thickapprox f(x^{(k)})+(x-x^{(k)})^Tg^{(k)}+\frac{1}{2}(x-x^{(k)})^TF(x^{(k)})(x-x^{(k)})\triangleq q(x) f(x)f(x(k))+(xx(k))Tg(k)+21(xx(k))TF(x(k))(xx(k))q(x)
为了简化描述,令 g ( k ) = ∇ f ( x ( k ) ) g^{(k)}=\nabla f(x^{(k)}) g(k)=f(x(k)),将局部极小点的一阶必要条件应用到函数 q q q,可得:
0 = ∇ q ( x ) = g ( k ) + F ( x ( k ) ) ( x − x ( k ) ) 0=\nabla q(x)=g^{(k)}+F(x^{(k)})(x-x^{(k)}) 0=q(x)=g(k)+F(x(k))(xx(k))
F ( x ( k ) ) > 0 F(x^{(k)})>0 F(x(k))>0,函数 q q q的极小点为:
x ( k + 1 ) = x ( k ) − F ( x ( k ) ) − 1 g ( k ) x^{(k+1)}=x^{(k)}-F(x^{(k)})^{-1}g^{(k)} x(k+1)=x(k)F(x(k))1g(k)
式(15)就是牛顿法的迭代公式

算法过程

  1. 计算梯度 ∇ f ( x ) \nabla f(x) f(x),即 g ( x ) g(x) g(x);计算黑塞矩阵 F ( x ) F(x) F(x);
  2. 计算 g ( k ) , F ( x ( k ) ) , F ( x ( k ) ) − 1 , F ( x ( k ) ) − 1 g ( k ) g^{(k)},F(x^{(k)}),F(x^{(k)})^{-1},F(x^{(k)})^{-1}g^{(k)} g(k),F(x(k)),F(x(k))1,F(x(k))1g(k)
  3. 确定下一迭代点 x ( k + 1 ) = x ( k ) − F ( x ( k ) ) − 1 g ( k ) x^{(k+1)}=x^{(k)}-F(x^{(k)})^{-1}g^{(k)} x(k+1)=x(k)F(x(k))1g(k)

同:

  1. 计算 F ( x ( k ) ) F(x^{(k)}) F(x(k))
  2. 求解 F ( x ( k ) ) d ( k ) = − g ( k ) F(x^{(k)})d^{(k)}=-g^{(k)} F(x(k))d(k)=g(k),得到 d ( k ) d^{(k)} d(k)
  3. 确定下一迭代点 x ( k + 1 ) = x ( k ) + d ( k ) x^{(k+1)}=x^{(k)}+d^{(k)} x(k+1)=x(k)+d(k)

你可能感兴趣的