A. 约束优化方法与无约束方法在步长的选取上有何不同
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具有更好的数值稳定性。
B. 无约束最优化方法中凸函数的次梯度是什么
如果函数不可微的时候，就用次梯度来代替梯度进行计算