一维搜索方法+多维牛顿法 股票黄金分割法迭代公式是什么

文章目录 一维搜索方法+多维牛顿法黄金分割法二分法牛顿法（用于求解方程）割线法牛顿法（高维——用于最优化）算法过程

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

​ 寻找一元函数的极值点的迭代求解方法。迭代算法从初始搜索点 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取点，不断压缩极小点所在的区间，知道达到足够的精度水平。

算法搜索过程：

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

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

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

计算函数值，确定压缩后的新区间： f ( a 1 ) < f ( b 1 ) − > [ a , b 1 ] f(a_1)[a,b_1] f(a1​)[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]上连续可微，即一阶可导。

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

算法搜索过程：

确定初始区间的中点： x ( 0 ) = a + b 2 ​ x^{(0)}=frac{a+b}{2}​ x(0)=2a+b​​；计算函数 f ​ f​ f​在 x ( 0 ) ​ x^{(0)}​ x(0)​处的一阶导数 f ‘ ( x ( 0 ) ) ​ f^`(x^{(0)})​ f‘(x(0))​；如果 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 x x都成立，牛顿法正常；反之当 f ‘ ‘ ( x ) < 0 f``(x)<0 f‘‘(x)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)就是牛顿法的迭代公式

算法过程 计算梯度 ∇ f ( x ) abla f(x) ∇f(x)，即 g ( x ) g(x) g(x)；计算黑塞矩阵 F ( x ) F(x) F(x);计算 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)；确定下一迭代点 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)。

同：

计算 F ( x ( k ) ) F(x^{(k)}) F(x(k))；求解 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)；确定下一迭代点 x ( k + 1 ) = x ( k ) + d ( k ) x^{(k+1)}=x^{(k)}+d^{(k)} x(k+1)=x(k)+d(k)。