梯度下降法、牛顿法、拟牛顿法

发表于   |   更新于 | 分类于

1 梯度下降法

1.1 目的

求解无约束最优化问题的极小值

1.2 方法

通过不断的迭代，进行目标函数的极小化，直到收敛

1.3 泰勒一阶展开

1.4 思想

极小化 $f(x)$ ，则 $x-x_0 = -f’(x_0) * \lambda$ ，其中 $\lambda > 0 $

1.5 结论

$ x = x_0 - \lambda * f’(x_0)$ ，其中学习率 $\lambda > 0 $

1.6 应用

  • 数学问题中，求解极小值
  • 机器学习中，求解目标函数最优解

2 牛顿法

2.1 简介

牛顿法，又称牛顿迭代法，主要是迭代的方法用于求解方程的根。后应用于无约束问题的最优化。

2.2 解方程

利用泰勒公式一阶展开，$f(x) = f(x_0) + (x-x_0) f’(x_0)$

求解方程 $f(x) = 0$， 则 $f(x_0) + (x-x_0) f’(x_0) = 0$

推出，$x = x_0 - \frac{f(x_0)}{f’(x_0)}$

算法流程：

不断迭代 $x_{k+1} = x_k - \frac{f(x_k)}{f’(x_k)}$，

直至 $f(x_{k+1}) = 0$

举例如下：

求解$\sqrt2$ ， 保留 5位小数
思路：设计 $y = f(x)$， 将$x = \sqrt2$ 代入，$y = 0$， 故 $f(x) = x^2 -2$

1
2
3
4
5
6
7
8
9
10
class Solution:
    def mySqrt(self, x: int) -> int:
        num_pre = x
        num_cur = (num_pre * num_pre + x) / (2 * num_pre)

        while abs(num_pre-num_cur) > 0.0001:
            num_pre = num_cur
            num_cur = (num_pre * num_pre + x) / (2 * num_pre)
        
        return num_cur

2.3 求解无约束最优化问题

利用泰勒公式二阶展开

函数$f(x)$ 在 $x_0$有极值的必要条件是 $f’(x_0) = 0$

2.4 最优化问题应用至高维

引入Hessian矩阵

其中，$g_k$ 是一阶导（梯度），$H_k$ 是Hessian矩阵

3 拟牛顿法

避免每次都要计算Hessian矩阵，采用正定矩阵近似方法实现

4 结论

4.1 速记

  • 梯度下降时，迭代 $ x = x_0 - \lambda * f’(x_0)$ 直至收敛，其中学习率 $\lambda > 0 $
  • 牛顿法解方程时，迭代 $ x = x_0 - \frac{f(x_0)}{f’(x_0)} $，直至收敛
  • 牛顿法最优化时，迭代 $ x = x_0 - \frac{ f’(x_0)}{ f’’(x_0)}$ 直至收敛

4.2 对比

  • 梯度下降法靠近极小值，收敛速度慢；通过步长控制，极值点震荡
  • 牛顿法是二阶收敛，梯度下降法是一阶收敛，牛顿法收敛速度快
  • 牛顿法容易陷入局部最优
  • 牛顿法要同时求出梯度和Hessian矩阵，计算量大且不好计算；当输入向量维度$N$较大时，Hessian矩阵的大小时 $N*N$，需要内存和显存非常大
Donate comment here