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

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

Data Mining

无约束最优化方法

梯度的方向与等值面垂直，并且指向函数值提升的方向。

二次收敛是指一个算法用于具有正定二次型函数时，在有限步可达到它的极小点。二次收敛与二阶收敛没有尽然联系，更不是一回事，二次收敛往往具有超线性以上的收敛性。一阶收敛不一定是线性收敛。

解释一下什么叫正定二次型函数：

n阶实对称矩阵Q，对于任意的非0向量X，如果有XTQX>0，则称Q是正定矩阵。

对称矩阵Q为正定的充要条件是：Q的特征值全为正。

二次函数，若Q是正定的，则称f(X)为正定二次函数。

黄金分割法

黄金分割法适用于任何单峰函数求极小值问题。

求函数在[a,b]上的极小点，我们在[a,b]内取两点c,d，使得a<c<d<b。并且有

1）如果f(c)<f(d)，则最小点出现在[a,d]上，因此[a,d]成为下一次的搜索区间。

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矩阵，会导致求解效果变差呢？事实上，效果反而通常会变好。

拟牛顿法与牛顿法的迭代过程一样，仅仅是各个Hesse矩阵的求解方法不一样。

在远离极小值点处，Hesse矩阵一般不能保证正定，使得目标函数值不降反升。而拟牛顿法可以使目标函数值沿下降方向走下去，并且到了最后，在极小值点附近，可使构造出来的矩阵与Hesse矩阵“很像”了，这样，拟牛顿法也会具有牛顿法的二阶收敛性。

对目标函数f(X)做二阶泰勒展开：

两边对X求导

当X=Xi时，有

这里我们用Hi来代表在点Xi处的Hesse矩阵的逆，则

(5)式就是拟牛顿方程。

下面给出拟牛顿法中的一种--DFP法。

令

我们希望Hi+1在Hi的基础上加一个修正来得到：

给定Ei的一种形式：

m和n均为实数，v和w均为N维向量。

(6)(7)联合起来代入(5)可得：

下面再给一种拟牛顿法--BFGS算法。

(8)式中黑色的部分就是DFP算法，红色部分是BFGS比DFP多出来的部分。

BFGS算法不仅具有二次收敛性，而且只有初始矩阵对称正定，则BFGS修正公式所产生的矩阵Hk也是对称正定的，且Hk不易变为奇异，因此BFGS比DFP具有更好的数值稳定性。