最优化方法
就是给一个初点,找到一个收敛点列,迭代式即
其中
为常数且大于0
GD
假设f(x)连续可微,并且导数在处不为0,我们有一阶Taylor展开
这里我们需要让x随着k增大函数值减小即
然而负数有很多,我们取最小的那个,由Cauchy-Schwarts
当且仅当
时成立,因此GD推导公式为
Newton
设二阶Taylor展开
同GD我们求后两项和最小值,求导有
假设Hessian矩阵
这玩意儿正定,极值点为
显然f(x)如果是二次凸函数一次迭代就到位,而对于非二次函数,牛顿法并不能保证经过有限次迭代就可以求得最优解,有一点是在极小点附近目标函数接近于二次函数,因此其收敛速度很快。对于Newton法可以加系数成为阻尼牛顿法即
上面的两个算法都是往梯度下降最大的方向走,如果每次路线正交也可以收敛,比如CG
CG(共轭梯度)
对于任意n维向量,
有
则称
,
关于G共轭。虽然梯度下降法的每一步都是朝着局部最优的方向前进的,但是它在不同的迭代轮数中会选择非常近似的方向,说明这个方向的误差并没通过一次更新方向和步长更新完,在这个方向上还存在误差,因此参数更新的轨迹是锯齿状。共轭梯度法的思想是,选择一个优化方向后,本次选择的步长能够将这个方向的误差更新完,在以后的优化更新过程中不再需要朝这个方向更新了。当然这玩意儿明显理想状态,现实是我们并不知道极小点在哪里,所以不可能找到准确的正交向量,否则其实可以直接求出,也就是说
我们希望
方向上不再进行修正,因此有
但是明显
是未知的,因而
是求不粗来的,我们引入正交基为d的矩阵G并使得
解得
而
可迭代获得
,另一方面由Gram-Schmidt正交化对线性无关向量
有
因此
故
这玩意儿可以求。总迭代n次即收敛
Quasi-Newton
Newton法每次存Hessian矩阵大,且那玩意儿不一定正定,所以不一定可逆,设
求导有
代入
我们变换一下有
设
如果
为n阶正定,我们构造
使得
也为正定矩阵。DFP算子
这样每次就不用存每个Hessian矩阵,另外在BFGS中令
有
再逆回来有BFGS算子
因此
即有迭代式,因此只需要
和一堆的
即可算出最终结果,大幅度减少内存