牛顿法求最优步长,什么是最优步长 _生活百科

什么是最优步长

文章插图
有效计算时间最大,因此这个步长就称为最优步长.由于方法误差(离散化误差)和舍入误差随步长的这种反向变化关系,就导致了与量子力学中著名的Heisenberg测不准关系相类似的计算不确定性原理
约束优化方法与无约束方法在步长的选取上有何不同

文章插图
Data Mining
无约束最优化方法
梯度的方向与等值面垂直，并且指向函数值提升的方向。
二次收敛是指一个算法用于具有正定二次型函数时，在有限步可达到它的极小点。二次收敛与二阶收敛没有尽然联系，更不是一回事，二次收敛往往具有超线性以上的收敛性。一阶收敛不一定是线性收敛。
解释一下什么叫正定二次型函数：
n阶实对称矩阵Q ，对于任意的非0向量X ，如果有XTQX>0 ，则称Q是正定矩阵。
对称矩阵Q为正定的充要条件是：Q的特征值全为正。
二次函数，若Q是正定的，则称f(X)为正定二次函数。
黄金分割法
黄金分割法适用于任何单峰函数求极小值问题。
求函数在[a,b]上的极小点，我们在[a,b]内取两点c,d ，使得a 1）如果f(c) 2）如果f(c)>f(d) ，则[c,b]成为下一次的搜索区间。
假如确定了[a,d]是新的搜索区间，我们并不希望在[a,d]上重新找两个新的点使之满足(1)式，而是利用已经抗找到有c点，再找一个e点，使满足：
可以解得r=0.382 ，而黄金分割点是0.618 。
练习：求函数f(x)=x*x-10*x+36在[1,10]上的极小值。
+ View Code
最速下降法
泰勒级数告诉我们：
其中Δx可正可负，但必须充分接近于0 。
X沿D方向移动步长a后，变为X+aD 。由泰勒展开式：
目标函数：
a确定的情况下即最小化：
向量的内积何时最小？当然是两向量方向相反时。所以X移动的方向应该和梯度的方向相反。
接下来的问题是步长a应该怎么定才能使迭代的次数最少？
若f(X)具有二阶连续偏导，由泰勒展开式可得：
H是f(X)的Hesse矩阵。
可得最优步长：
g是f(X)的梯度矩阵。
此时：
可见最速下降法中最优步长不仅与梯度有关，而且与Hesse矩阵有关。
练习：求函数f(x1,x2)=x1*x1+4*x2*x2在极小点，以初始点X0=(1,1)T 。
+ View Code
梯度下降法开始的几步搜索，目标函数下降较快，但接近极值点时，收敛速度就比较慢了，特别是当椭圆比较扁平时，收敛速度就更慢了。
另外最速下降法是以函数的一次近似提出的，如果要考虑二次近似，就有牛顿迭代法。
牛顿迭代法
在点Xk处对目标函数按Taylar展开：
令
得
即
可见X的搜索方向是，函数值要在此方向上下降，就需要它与梯度的方向相反，即。所以要求在每一个迭代点上Hesse矩阵必须是正定的。
练习：求的极小点，初始点取X=(0,3) 。
+ View Code
牛顿法是二次收敛的，并且收敛阶数是2 。一般目标函数在最优点附近呈现为二次函数，于是可以想像最优点附近用牛顿迭代法收敛是比较快的。而在开始搜索的几步，我们用梯度下降法收敛是比较快的。将两个方法融合起来可以达到满意的效果。