本文共 3376 字，大约阅读时间需要 11 分钟。

几种优化算法，梯度下降的种类

考虑无约束优化问题

$$min_x f(x)$$

1. 梯度下降

梯度下降法是一种常用的一阶优化方法，是求解无约束优化问题最简单、最经典的方法之一。

其中，f(x)连续可微。若能构造一个序列$x^0,x^1, x^2,...$满足

$$f(x^{t+1}) <f(x^t), t=0,1,2...$$

则不断执行该过程即可收敛到局部极小点。

根据泰勒一阶展开：

$$f(x+\Delta{x})\approx f(x)+\Delta x^T\nabla f(x)$$

要满足$f(x+\Delta x)<f(x)$, 可选择：

$\Delta x = - \gamma \nabla f(x)$

选择合适的步长，就能通过梯度下降法收敛到局部最小

(1) 批梯度下降

原始的梯度下降算法

(2) 随机梯度下降

每次梯度计算只使用一个样本：

• 避免在类似样本上计算梯度造成的冗余计算
• 增加了跳出当前的局部最小值的潜力
• 在逐渐缩小学习率的情况下，有与批梯度下降法类似的收敛速度

(3) 小批量梯度下降

每次梯度计算使用一个小批量的样本：

• 梯度计算比单样本更加稳定
• 可以很好的利用现成的高度优化的矩阵运算工具

.

2. 牛顿法

若f(x)二阶连续可微，则f(x)的二阶泰勒展开：

$$f(x)=f(x^{(k)})+{g_k}^T(x-x^{(k)}) + \frac {1}{2}(x-x^{(k)})^TH(x^{(k)})(x-x^{(k)})$$

其中

$g_k=g(x^{(k)})=\nabla f(x^{(k)})$

上式表示f(x)的梯度向量在点$x^{(k)}$处的值

定义海塞矩阵

$$H(x)=[\frac {\partial ^2 f}{\partial x_i\partial x_j}]_{n\times n}$$

$H(x^{(k)})$为海塞矩阵在$x^{(k)}$处的值

牛顿法利用极小点的必要条件$\nabla f(x)= 0$，每次迭代中从点$x^{(k)}$开始，求目标函数的极小点，作为第k+1次迭代值$x^{(k+1)}$。

假设$x^{(k+1)}$满足$\nabla f(x^{(k+1)})= 0$

对f(x)的二阶泰勒展开求一阶偏导数

$$\nabla f(x) = g_k + H(x^{(k)})(x-x^{(k)})$$

令上式为0即可求$x^{(k+1)}$

$$x^{(k+1)}=-x^{(k)}- H(x^{(k)})^{-1} g_k$$

• 牛顿法的优缺点总结：

优点：二阶收敛，收敛速度快；

缺点：

• 牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂；
• 使用小批量的情形下，牛顿法对于二阶导数的估计噪音太大
• 在目标函数非凸时，牛顿法更容易受到暗点甚至最大值点的吸引
  .

3.拟牛顿

在牛顿迭代中，需要计算海塞矩阵的逆矩阵$H^{-1}$，这一计算比较复杂，考虑使用一个n阶的矩阵$G_k=G(x^{(k)})$来近似代替$H(x^{(k)})^{-1}$。这就是拟牛顿法的基本想法。 - 拟牛顿条件 由海塞矩阵H_k满足的条件：

$$\nabla f(x) = g_k + H(x^{(k)})(x-x^{(k)})$$ 令 x=x(k+1) x = x ( k + 1 ) $x = x^{(k+1)}$，即 $$g_{k+1} = g_k + H(x^{(k)})(x^{(k+1)}-x^{(k)})$$ 记 yk=gk+1−gk,δk=(x(k+1)−x(k)) y k = g k + 1 − g k , δ k = ( x ( k + 1 ) − x ( k ) ) $y_k = g_{k+1} - g_k, \delta_k=(x^{(k+1)}-x^{(k)})$，则拟牛顿条件表示为： yk=Hkδk y k = H k δ k $y_k= H_k \delta_k$ 或者 Hk−1yk=δk H k − 1 y k = δ k ${H_k}^{-1}y_k=\delta_k$ 用一个n阶的矩阵 Gk=G(x(k)) G k = G ( x ( k ) ) $G_k=G(x^{(k)})$来近似代替 H(x(k))−1 H ( x ( k ) ) − 1 $H(x^{(k)})^{-1}$，则 Gk G k $G_k$也满足拟牛顿条件 $$G_{k+1}y_k=\delta_k$$ 每次更新： Gk+1=Gk+ΔGk G k + 1 = G k + Δ G k $G_{k+1}=G_k+\Delta G_k$ (1) DFP算法 DFP算法选择用 Gk+1 G k + 1 $G_{k+1}$的方法是，假设每一步迭代中矩阵 Gk+1 G k + 1 $G_{k+1}$是由 Gk G k $G_{k}$加上两个附加项构成的，即 $$G_{k+1}=G_k+P_k+Q_k$$ 其中 Pk,Qk P k , Q k $P_k,Q_k$是待定矩阵，两边同时右乘 yk y k $y_k$ $$G_{k+1}y_k=G_ky_k + P_ky_k+Q_ky_k$$ 为使 Gk+1 G k + 1 $G_{k+1}$满足拟牛顿条件，可使 Pk，Qk P k ， Q k $P_k，Q_k$满足： $$P_ky_k=\delta_k \\Q_ky_k=-G_ky_k$$ 取： $$P_k=\frac{\delta_k{\delta_k}^T}{{\delta_k}^Ty_k} \\Q_k=-\frac{G_ky_k{y_k}^TG_k}{{y_k}^TG_ky_k}$$ (2)BFGS算法

最流行的拟牛顿算法，考虑使用B_k逼近海塞矩阵H，这时，相应的拟牛顿条件是

$B_{k+1}\delta_k=y_k$

首先令

$$B_{k+1}=B_k+P_k+Q_k \B_{k+1}\delta_k=B_k\delta_k+P_k\delta_k+Q_k\delta_k$$ 考虑使 Pk P k $P_k$和 Qk Q k $Q_k$满足： $$P_k\delta_k=y_k \Q_k\delta_k = -B_k\delta_k$$ 找出合适条件的 Pk P k $P_k$和 Qk Q k $Q_k$，得到BFGS算法矩阵 Bk+1 B k + 1 $B_{k+1}$的迭代公式： $$B_{k+1}=B_k + \frac{y_k{y_k}^T}{{y_k}^T\delta_k}-\frac{B_k\delta_k{\delta_k}^TB_k}{{\delta_k}^kB_k\delta_k}$$

4 三种求解无约束优化问题的方法的比较

• 梯度下降法并不是下降最快的方向，它只是目标函数在当前的点的切面上下降最快的方向；牛顿法下降的方向一般被认为是下降最快的方向。
• 梯度下降不一定能够找到全局最优解，也有可能只是一个局部最优解。如果损失函数是凸函数，梯度下降法得到的解就一定是全局最优解。
• 从收敛速度上看 ，牛顿法是二阶收敛，梯度下降是一阶收敛，前者牛顿法收敛速度更快。但牛顿法仍然是局部算法，只是在局部上看的更细致，梯度法仅考虑方向，牛顿法不但考虑了方向还兼顾了步子的大小，其对步长的估计使用的是二阶逼近。
• 根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。

文字内容来源