数学基础01-最优化(梯度下降法、牛顿法、拟牛顿法等)

1、最优化问题分类

按照约束条件分，可以分为：无约束优化问题、有不等式优化问题、有不等式优化问题。

按照是否线性，可以分为线性优化问题(目标函数和约束均线性)、非线性优化问题(目标函数和约束中任意部分非线性)。

按是否凸，可以分为凸优化问题、非凸优化问题。

对于有约束优化问题，常见的做法是转换到无约束问题上：对于只有等式约束的问题，通过拉格朗日乘子转换；对于有不等式约束的问题，通过KKT条件进行转换。

对于凸优化问题来说，只有一个全局最优点，没有局部最优点；对于非凸问题来说，有多个局部最优点。

对于最优化问题的求解，可以分为两大类算法：

1、基于梯度的精确搜索算法

2、基于经验的启发式算法(或者叫智能算法)

前者包含梯度下降法、牛顿法、拟牛顿法等；后者包含爬山法、遗传算法、模拟退火算法、粒子群算法、蚁群算法等。

以下内容主要介绍前者。

2、梯度下降法

2.1、梯度下降法

基于梯度的迭代算法思路是：再当前迭代位置上，找到一个使目标函数值变小的方向，并且在这个方向上移动一定距离，找到下一个迭代位置。

梯度下降法的做法最为简单，直接以梯度方向的方向为下降方向，人工设定步长，完成迭代。公式如下：

$w_k+1 = w_k - alpha * abla_w f(x_k)$

2.2、梯度下降法为什么work

前面说过，基于梯度的迭代算法的思路是找到一个使目标函数值减小的方向，在这个方向上移动。那么梯度的负方向为什么可以满足这个条件呢？

考虑当前迭代位置$x_k$，下一个迭代位置为$x_k+ alpha d$。其中$alpha$为搜索步长，$d$为搜索方向向量，其长度为单位向量。由泰勒公式可知:

$f(x_k + alpha d) = f(x_k) + abla_w f(x_k) * alpha d + o( abla d)$

$simeq f(x_k) + alpha abla_w f(x_k) * d$

$= f(x_k) + alpha left| abla_w f(x_k) ight| left| d ight| * cos heta$

可知，当$d$与$ abla_w f(x_k)$反向时，$f(x_k + alpha d) $能取得极小值。

2.3、次梯度下降法

梯度下降法的计算中使用了梯度，也就是潜在要求目标函数在迭代位置可导。

但是实际上目标函数不一定满足此要求，比如目标函数为分段函数，或者$max$函数。此时需要使用次梯度下降法。

具体内容参考：http://www.hanlongfei.com/convex/2015/10/02/cmu-10725-subgradidient/

3、深度学习中的梯度下降法变体

3.1、梯度下降法的缺点

总地来说，梯度下降算法有如下缺点：

1、局部位置的梯度方向可能并不是全局最速下降方向，这样就会导致收敛缓慢

2、迭代步长不好设置，大步长可能导致震荡，小步长可能导致收敛缓慢；步长是全局的，对于所有维度一致，但是不同维度的数据分布不一致，不应该有同等的下降速度

3、对于非凸问题，梯度下降可能进入局部最优无法跳出

3.2、深度学习中的优化算法总览

对于以上问题，一系列梯度下降算法的变体被提出以解决问题。大致可以分为两个方向：

1、优化下降方向，包括Momentum算法、NAG算法等；

2、优化每个维度上下降的步长，包括AdaGrad算法、RMSProp算法、AdaDelta算法等。

目前最常用的算法，是结合以上两者优点的Adam算法和Nadam算法。

如下图所示（这里的公式和以上公式和上面公式符号不一致，因为以下公式是从别的地方拷贝的，公式输入太累了，偷懒一下）：

3.3、Momentum算法

Momentum算法的出发点是：如果梯度比较扭曲(前一个梯度和后一个梯度差别较大)，那么梯度下降就会走折线，来回震荡。如果在梯度下降过程可以加入惯性，利用之前的动量继续往山下滚，这样就可以减少震荡。这里的惯性，就是加权后的历史梯度值，这里用$V_t$表示。其更新公式如下：

$egin{align*} Vg_t & gets abla J(Vtheta_{t-1}) \ Vv_t & gets gamma Vv_{t-1} + eta Vg_t\ Vtheta_t & gets Vtheta_{t-1} - Vv_t end{align*}$

Momentum算法可以理解为用来解决梯度下降算法的第1个缺点。

3.4、NAG算法

对于梯度下降的第3个问题，迭代陷入局部的问题。NAG(Nesterov accelerated gradient)算法可能有助于缓解。NAG在Momentum的基础上，在计算当前梯度的时候，不是站在当前位置上看，而是继续向前跑了当前动量那么长的距离。这样跑的远也就看得远。其更新公式如下：

$egin{align*} Vg_t & gets abla J(Vtheta_{t-1} - gamma Vv_{t-1}) \ Vv_t & gets gamma Vv_{t-1} + eta Vg_t\ Vtheta_t &gets Vtheta_{t-1} - Vv_t end{align*}$

3.5、AdaGrad算法

对于梯度下降的第2个问题，一种可行的思路是：经常更新的参数，我们已经积累了大量关于它的知识，不希望被单个样本影响太大，希望学习速率慢一些；对于偶尔更新的参数，我们了解的信息太少，希望能从每个偶然出现的样本身上多学一些，即学习速率大一些。这也就是AdaGrad算法的思路。其更新公式如下：

$egin{align*} Vg_t & gets abla J(Vtheta_{t-1}) \ G_t &gets G_t + Vg_t odot Vg_t \ Vtheta_t & gets Vtheta_{t-1} - frac{eta}{sqrt{G_t + epsilon}} odot Vg_t end{align*}$

这里可以看出$G_t$是递增的，而且可能是比较快的递增，然后就会导致后续的步长很小趋向于0，最后$theta$就不会更新了。

3.6、RMSProp算法

基于以上问题，RMSProp算法被提出来：通过折扣系数，降低历史更新带来的影响，从而解决后续步长趋向于0的问题。其更新公式是：

$egin{align*} Vg_t & gets abla J(Vtheta_{t-1}) \ G_t &gets gamma G_t + (1-gamma) Vg_t odot Vg_t \ Vtheta_t & gets Vtheta_{t-1} - frac{eta}{sqrt{G_t + epsilon}} odot Vg_t end{align*}$

3.7、AdaDelta算法

类似于RMSProp的AdaDelta算法更新公式如下：

$egin{align*} Vg_t & gets abla J(Vtheta_{t-1}) \ G_t & gets gamma G_t + (1-gamma) Vg_t odot Vg_t \ Delta Vtheta_t & gets - frac{sqrt{Delta_{t-1} + epsilon}}{sqrt{G_t + epsilon}} odot Vg_t \ Vtheta_t & gets Vtheta_{t-1} + Delta Vtheta_t \ Delta_t & gets gamma Delta_{t-1} + (1-gamma) DeltaVtheta_t odot Delta Vtheta_t end{align*}$

3.8、Adam算法

在出现了以上算法以后，结合以上算法优点的算法就自然地被提了出来。Adam算法结合了Momentum和RMSProp算法，其更新公式如下：

$egin{align*} Vg_t &gets abla J(Vtheta_{t-1}) \ Vm_t & gets eta_1 Vm_{t-1} + (1-eta_1) Vg_t \ G_t & gets gamma G_t + (1-gamma) Vg_t odot Vg_t \ alpha & gets eta frac{sqrt{1-gamma^t}}{1-eta^t} \ Vtheta_t & gets Vtheta_{t-1} - alpha frac{Vm_t}{sqrt{G_t + epsilon}} end{align*}$

类似地，还有结合了NAG和RMSProp的优点的Nadam。

3.9、优化算法的再说明

贴一个以上算法(缺Adam)的一个实验效果图：

目前来看，Adam俨然是最优的梯度下降算法了，但是据很多大神说，对于Adam的批评也很多。观其原因，大概是因为对于具体数据集，细致调参的梯度下降算法，其结果可能优于Adam。

3、牛顿法

梯度下降法只使用了一阶梯度信息，导致其下降方向可能并非全局最优。牛顿法利用二阶梯度信息，得到一个收敛更快的方向方法。

根据泰勒展开有：

$f(x_k+1 - x_k) = f(x_k) + g_k^T*(x_{k+1} - x_k) + frac{1}{2} (x_{k+1} - x_k)^T H(x_k)(x_{k+1} - x_k) $

其中，$g_k$表示$f(x_k)$在当前位置的一阶导；H表示海森矩阵。以上公式省略了高阶无穷小项。

对以上公式，左右求导，并令两边等于0(在导数为0处取最小值)，可以得到：

$0 = g_k + H_k(x_{x+1}-x_k)$

于是得到牛顿法的一次迭代步骤：

$x_{k+1} = x_k - H_k^{-1}g_k$

4、拟牛顿法

在牛顿法中，需要计算海森矩阵的逆矩阵$H^{-1}$，这里有两个问题：

1、逆矩阵计算量太大，$o(n^3)$，其中$n$为维度；

2、逆矩阵可能非正定，这样更新方向可能并不会让目标函数值变小。

为了解决以上问题，出现了拟牛顿法。拟牛顿法的思路是，用一个满足更新条件的正定矩阵，去替换逆矩阵，从而减少计算量，并保证更新正常。

这里的更新条件是：

$H_k （x_{k+1} - x_k） = g_{k+1}-g_k$

令

$x_{k+1} - x_k = abla x_k, g_{k+1} - g_k = abla g_k$

得

$H_k abla x_k = abla g_k$ (1)

或

$H_k^{-1} abla g_k = abla x_k $ (2)

4.1、DFP算法

DFP中，考虑$G_k$作为(1)中$H_k^{-1}$的近似，把$G_{k+1}$拆解成:

$G_{k+1} = G_{k} + P_k + Q_k$

其中，初始值${G_0}$为正定矩阵，${P_k}$为正定矩阵，$Q_k$为正定矩阵。

有:

$G_{k+1} abla g_k = G_{k} abla g_k + P_k abla g_k + Q_k abla g_k$

只要:

$P_k abla g_k = abla x_k$

$Q_k abla g_k = -G_{k} abla g_k$

就有:

$G_{k+1} abla g_k= abla x_k$

可以取:

$P_k = frac{ abla x_k abla x_k^T}{ abla x_k^T abla x_k} $

$Q_K = - frac{G_k abla g_k abla g_k^T G_k^T} { abla g_k^T G_k^T abla g_k}$

满足条件。

4.2、BFGS算法

BFGS中，考虑$B_k$作为(2)中$H_k$的近似，同样地把$B_{k+1}$拆解成:

$B_{k+1} = B_{k} + P_k + Q_k$

类似于以上分析，可以取:

$P_k = frac{ abla g_k abla g_k^T}{ abla g_k^T abla g_k}$

$Q_K = - frac{G_k abla x_k abla x_k^T G_k^T} { abla x_k^T G_k^T abla x_k}$

满足条件。

5、共轭梯度法

共轭梯度法是介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数信息，既克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点。共轭梯度法优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。

具体的实现步骤请参加wiki百科共轭梯度法。

下图为共轭梯度法和梯度下降法搜索最优解的路径对比示意图：

注：绿色为梯度下降法，红色代表共轭梯度法

6、信赖域算法

这个算法在强化学习中被用到了，也就是所谓的TRPO算法。

其思想是在每次迭代中给出一个信赖域，这个信赖域一般是当前迭代点的一个小邻域。

然后，在这个邻域内求解一个子问题，得到试探步长，接着用某一评价函数来决定是否接受该试探步以及确定下一次迭代的信赖域。

新的信赖域的大小取决于试探步的好坏。如果试探步较好，在下一步信赖域扩大或者保持不变，否则减小信赖域。

7、启发式算法

启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。

其特点是在解决问题时，利用过去的经验，选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。

启发式优化算法包括爬山法、模拟退火方法、遗传算法、蚁群算法以及粒子群算法等。

如果发现文中有问题，敬请联系作者批评指正，真诚欢迎您的指教，谢谢！

微信: legelsr0808

邮箱: legelsr0808@163.com