最速下降法步长,最速下降法步长 _生活百科

2、牛顿法和最速下降法只能求解无约束优化，有约束的非线性规划有哪些求解方法？

文章插图
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 。一般目标函数在最优点附近呈现为二次函数，于是可以想像最优点附近用牛顿迭代法收敛是比较快的。而在开始搜索的几步，我们用梯度下降法收敛是比较快的。将两个方法融合起来可以达到满意的效果。
收敛快是牛顿迭代法最大的优点，但也有致命的缺点：Hesse矩阵及其逆的求解计算量大，更何况在某个迭代点Xk处Hesse矩阵的逆可能根本就不存在（即Hesse矩阵奇异），这样无法求得Xk+1 。
拟牛顿法
Hesse矩阵在拟牛顿法中是不计算的，拟牛顿法是构造与Hesse矩阵相似的正定矩阵，这个构造方法，使用了目标函数的梯度（一阶导数）信息和两个点的“位移”（Xk-Xk-1）来实现。有人会说，是不是用Hesse矩阵的近似矩阵来代替Hesse矩阵，会导致求解效果变差呢？事实上，效果反而通常会变好。

最速下降法步长,最速下降法 步长

最速下降法步长,最速下降法步长