优化算法知识点整理

几种优化算法，梯度下降的种类
考虑无约束优化问题

m i n_{x} f (x)

梯度下降

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

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

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

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

根据泰勒一阶展开：

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

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

$Δ x = - γ \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)})^{T} H (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)}

，即

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

记

y_{k} = g_{k + 1} - g_{k}, δ_{k} = (x^{(k + 1)} - x^{(k)})

，则拟牛顿条件表示为：

y_{k} = H_{k} δ_{k}

或者

{H_{k}}^{- 1} y_{k} = δ_{k}

用一个n阶的矩阵

G_{k} = G (x^{(k)})

来近似代替

H (x^{(k)})^{- 1}

，则

G_{k}

也满足拟牛顿条件

G_{k + 1} y_{k} = δ_{k}

每次更新：

G_{k + 1} = G_{k} + Δ G_{k}

(1) DFP算法
DFP算法选择用

G_{k + 1}

的方法是，假设每一步迭代中矩阵

G_{k + 1}

是由

G_{k}

加上两个附加项构成的，即

G_{k + 1} = G_{k} + P_{k} + Q_{k}

其中

P_{k}, Q_{k}

是待定矩阵，两边同时右乘

y_{k}

G_{k + 1} y_{k} = G_{k} y_{k} + P_{k} y_{k} + Q_{k} y_{k}

为使

G_{k + 1}

满足拟牛顿条件，可使

P_{k} ， Q_{k}

满足：

P_{k} y_{k} = δ_{k} Q_{k} y_{k} = - G_{k} y_{k}

取：

P_{k} = \frac{δ_{k} {δ_{k}}^{T}}{{δ_{k}}^{T} y_{k}} Q_{k} = - \frac{G_{k} y_{k} {y_{k}}^{T} G_{k}}{{y_{k}}^{T} G_{k} y_{k}}

(2)BFGS算法

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

$B_{k + 1} δ_{k} = y_{k}$

首先令

B_{k + 1} = B_{k} + P_{k} + Q_{k} B_{k + 1} δ_{k} = B_{k} δ_{k} + P_{k} δ_{k} + Q_{k} δ_{k}

考虑使

P_{k}

和

Q_{k}

满足：

P_{k} δ_{k} = y_{k} Q_{k} δ_{k} = - B_{k} δ_{k}

找出合适条件的

P_{k}

和

Q_{k}

，得到BFGS算法矩阵

B_{k + 1}

的迭代公式：

B_{k + 1} = B_{k} + \frac{y_{k} {y_{k}}^{T}}{{y_{k}}^{T} δ_{k}} - \frac{B_{k} δ_{k} {δ_{k}}^{T} B_{k}}{{δ_{k}}^{k} B_{k} δ_{k}}

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

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

文字内容来源大萍的博客

优化算法知识点整理

相关推荐