yukamu 发表于 2022-1-2 15:02

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

专栏文章汇总


本文结构如下
1：梯度下降法

[*]1.1 梯度
[*]1.2 梯度下降的直观解释
[*]1.3 梯度下降算法法
[*]1.4 梯度下降的算法调优
[*]1.5 梯度下降法大家族（BGD，SGD，MBGD）
[*]    1.5.1 批量梯度下降法（Batch Gradient Descent）
[*]    1.5.2 随机梯度下降法（Stochastic Gradient Descent）
[*]    1.5.3 小批量梯度下降法（Mini-batch Gradient Descent）
[*]1.6 批量梯度下降法python实现
[*]1.7 梯度下降法和最小二乘法
2： 牛顿法

[*]2.1 求解方程
[*]2.2 最优化
[*]2.3 牛顿法与梯度下降法
3： 拟牛顿法的思路
4： DFP(Davidon-Fletcher-Powell)算法(DFP algorithm)
5： BFGS(Broyden-Fletcher-Goldfard-Shano)算法(BFGS algorithm)
6： Broyden类算法(Broyden's algorithm)
7： 参考文献
<hr/>1： 梯度下降法

1.1 梯度
导数我们都非常熟悉，既可以表示某点的切线斜率，也可以表示某点变化率，公式如下表示：
https://www.zhihu.com/equation?tex=f%27%28x%29%3D%5Cunderset%7B%5CDelta+x%5Crightarrow+0%7D%7Blim%7D%5Cfrac%7B%5CDelta+y%7D%7B%5CDelta+x%7D%3D%5Cunderset%7B%5CDelta+x%5Crightarrow+0%7D%7Blim%7D%5Cfrac%7Bf%28x%2B%5CDelta+x%29-f%28x%29%7D%7B%5CDelta+x%7D%5C%5C
当函数是多元时，倒数就变成了偏导数： https://www.zhihu.com/equation?tex=f_x%28x%2Cy%29 表示当不变时，沿着轴的变化变化率； https://www.zhihu.com/equation?tex=f_y%28x%2Cy%29 表示当不变时，沿着轴的变化变化率。
但是多元函数是一个平面，方向有很多，轴轴只是其中两个方向而已，假如我们需要其他方向的变化率怎么办呢？因此方向导数就有用了，顾名思义，方向导数可以表示任意方向的倒数。
假如二次函数，方向 https://www.zhihu.com/equation?tex=u%3Dcos%5Ctheta+~i%2Bsin%5Ctheta+~j （为单位向量）的方向导数公式如下： https://www.zhihu.com/equation?tex=%5Cunderset%7Bt%5Crightarrow+0%7D%7Blim%7D%5Cfrac%7Bf%28x%2Bt~cos%5Ctheta%2Cy%2Bt~sin%5Ctheta%29-f%28x%29%7D%7Bt%7D ，记为。其中 https://www.zhihu.com/equation?tex=D_uf%3Df_x%28x%2Cy%29cos%5Ctheta%2Bf_y%28x%2Cy%29sin%5Ctheta%3D%5Cbegin%7Bbmatrix%7Df_x%28x%2Cy%29%26f_y%28x%2Cy%29%5Cend%7Bbmatrix%7D%5Cbegin%7Bbmatrix%7Dcos%5Ctheta%5C%5C+sin%5Ctheta%5Cend%7Bbmatrix%7D 。我们记为： https://www.zhihu.com/equation?tex=D_uf%3D%5Cmathbf%7BA%7D%5Ctimes+%5Cmathbf%7BI%7D%3D%5Cbegin%7Bvmatrix%7D%5Cmathbf%7BA%7D+%5Cend%7Bvmatrix%7D%5Cbegin%7Bvmatrix%7D%5Cmathbf%7BI%7D+%5Cend%7Bvmatrix%7Dcos%5Calpha ，其中是两向量的夹角。我们可以知道，当为0时，方向导数达到最大，此时的方向导数即为梯度。
更多的关于梯度的知识点可以看里面的回答：如何直观形象的理解方向导数与梯度以及它们之间的关系？
从几何意义上来说，梯度向量就是函数变化增加最快的地方。具体来说，对于函数,在点 https://www.zhihu.com/equation?tex=%28x_0%2Cy_0%29 ，沿着梯度向量的方向就是 https://www.zhihu.com/equation?tex=%5Cbegin%7Bbmatrix%7D%5Cfrac%7B%5Cpartial+f%7D%7B%5Cpartial+x_0%7D%5C%5C+%5Cfrac%7B%5Cpartial+f%7D%7B%5Cpartial+y_0%7D%5Cend%7Bbmatrix%7D 的方向是增加最快的地方（还记得梯度怎么来的吗？方向导数的最大值，粗暴点，就是导数最大值）。或者说，沿着梯度向量的方向，更加容易找到函数的最大值。反过来说，沿着梯度向量相反的方向（去负号），则就是更加容易找到函数的最小值。

1.2 梯度下降的直观解释
比如我们在一座大山上的某处位置，由于我们不知道怎么下山，于是决定走一步算一步，也就是在每走到一个位置的时候，求解当前位置的梯度，沿着梯度的负方向，也就是当前最陡峭的位置向下走一步，然后继续求解当前位置梯度，向这一步所在位置沿着最陡峭最易下山的位置走一步。这样一步步的走下去，一直走到觉得我们已经到了山脚。当然这样走下去，有可能我们不能走到山脚，而是到了某一个局部的山峰低处（局部最小值）。
从上面的解释可以看出，梯度下降不一定能够找到全局的最优解，有可能是一个局部最优解。当然，如果损失函数是凸函数，梯度下降法得到的解就一定是全局最优解。



1.3 梯度下降算法法
梯度下降法(Gradient descent)或最速下降法(steepest descent)是求解无约束最优化问题的一种常用的、实现简单的方法。
假设是 https://www.zhihu.com/equation?tex=R%5E%7Bn%7D 上具有一阶连续偏导数的函数。求解
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C+%26+%5Cmin_%7Bx+%5Cin+R%5E%7Bn%7D%7D+f+%5Cleft%28+x+%5Cright%29+%5Cend%7Balign%2A%7D+%5C%5C
无约束最优化问题。 https://www.zhihu.com/equation?tex=f%5E%7B%2A%7D 表示目标函数的极小点。
梯度下降法是一种迭代算法。选取适当的初值 https://www.zhihu.com/equation?tex=x%5E%7B%280%29%7D ，不断迭代，更新的值，进行目标函数的极小化，直到收敛。由于负梯度方向是使函数下降最快的的方向，在迭代的每一步，以负梯度方向更新的值，从而达到减少函数值的目的。
第 https://www.zhihu.com/equation?tex=k%2B1 次迭代值
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C+%26+x%5E%7B%5Cleft%28+k%2B1+%5Cright%29%7D+%5Cleftarrow+x%5E%7B%5Cleft%28+k+%5Cright%29%7D+%2B+%5Clambda_%7Bk%7D+p_%7Bk%7D+%5Cend%7Balign%2A%7D+%5C%5C
其中，是搜索方向，取负梯度方向 https://www.zhihu.com/equation?tex=p_%7Bk%7D%3D+-+%5Cnabla+f+%5Cleft%28+x%5E%7B%5Cleft%28k%5Cright%29%7D+%5Cright%29%EF%BC%8C%5Clambda_%7Bk%7D 是步长，由一维搜索确定，即使得

梯度下降算法：
输入：目标函数 https://www.zhihu.com/equation?tex=f+%5Cleft%28+x+%5Cright%29 ，梯度函数 https://www.zhihu.com/equation?tex=g%5Cleft%28+x%5E%7B%5Cleft%28k%5Cright%29%7D+%5Cright%29%3D%5Cnabla+f+%5Cleft%28+x%5E%7B%5Cleft%28k%5Cright%29%7D%5Cright%29 ，计算精度
输出： https://www.zhihu.com/equation?tex=f+%5Cleft%28+x+%5Cright%29+ 的极小点
1. 取初值 https://www.zhihu.com/equation?tex=x%5E%7B%5Cleft%280%5Cright%29%7D+%5Cin+R%5E%7Bn%7D ，置
2. 计算 https://www.zhihu.com/equation?tex=f+%5Cleft%28+x%5E%7B%5Cleft%28k%5Cright%29%7D%5Cright%29
3. 计算梯度 https://www.zhihu.com/equation?tex=g_%7Bk%7D%3Dg%5Cleft%28+x%5E%7B%5Cleft%28k%5Cright%29%7D+%5Cright%29 ，当 https://www.zhihu.com/equation?tex=%5C%7C+g_%7Bk%7D+%5C%7C+%3C+%5Cvarepsilon+ 时，停止迭代，令；否则，令 https://www.zhihu.com/equation?tex=p_%7Bk%7D%3D-g%5Cleft%28x%5E%7B%5Cleft%28k%5Cright%29%7D%5Cright%29 ，求，使

4. 置 https://www.zhihu.com/equation?tex=x%5E%7B%5Cleft%28k%2B1%5Cright%29%7D%3D+x%5E%7B%5Cleft%28k%5Cright%29%7D%2B%5Clambda_%7Bk%7Dp_%7Bk%7D ，计算 https://www.zhihu.com/equation?tex=f+%5Cleft%28+x%5E%7B%5Cleft%28k%EF%BC%8B1%5Cright%29%7D+%5Cright%29
当 https://www.zhihu.com/equation?tex=%5C%7C+f+%5Cleft%28+x%5E%7B%5Cleft%28k%EF%BC%8B1%5Cright%29%7D+%5Cright%29+-+f+%5Cleft%28+x%5E%7B%5Cleft%28k%5Cright%29%7D+%5Cright%29+%5C%7C+%3C+%5Cvarepsilon+ 或 https://www.zhihu.com/equation?tex=%5C%7C+x%5E%7B%5Cleft%28k%EF%BC%8B1%5Cright%29%7D+-+x%5E%7B%5Cleft%28k%5Cright%29%7D+%5C%7C+%3C+%5Cvarepsilon+ 时，停止迭代，令 https://www.zhihu.com/equation?tex=x%5E%7B%2A%7D%3Dx%5E%7Bk%2B1%7D
5. 否则，置，转3.
1.4 梯度下降的算法调优
在使用梯度下降时，需要进行调优。哪些地方需要调优呢？

[*]算法的步长选择。步长取值取决于数据样本，可以多取一些值，从大到小，分别运行算法，看看迭代效果，如果损失函数在变小，说明取值有效，否则要增大步长。步长太大，会导致迭代过快，甚至有可能错过最优解。步长太小，迭代速度太慢，很长时间算法都不能结束。所以算法的步长需要多次运行后才能得到一个较为优的值。
[*]算法参数的初始值选择。初始值不同，获得的最小值也有可能不同，因此梯度下降求得的只是局部最小值；当然如果损失函数是凸函数则一定是最优解。由于有局部最优解的风险，需要多次用不同初始值运行算法，关键损失函数的最小值，选择损失函数最小化的初值。
[*]归一化。由于样本不同特征的取值范围不一样，可能导致迭代很慢，为了减少特征取值的影响，可以对特征数据归一化。

1.5 梯度下降法大家族（BGD，SGD，MBGD）
1.5.1 批量梯度下降法（Batch Gradient Descent）
批量梯度下降法，是梯度下降法最常用的形式，具体做法也就是在更新参数时使用所有的样本来进行更新。

1.5.2 随机梯度下降法（Stochastic Gradient Descent）
随机梯度下降法，其实和批量梯度下降法原理类似，区别在与求梯度时没有用所有的样本的数据，而是仅仅选取一个样本来求梯度。
随机梯度下降法，和批量梯度下降法是两个极端，一个采用所有数据来梯度下降，一个用一个样本来梯度下降。自然各自的优缺点都非常突出。对于训练速度来说，随机梯度下降法由于每次仅仅采用一个样本来迭代，训练速度很快，而批量梯度下降法在样本量很大的时候，训练速度不能让人满意。对于准确度来说，随机梯度下降法用于仅仅用一个样本决定梯度方向，导致解很有可能不是最优。对于收敛速度来说，由于随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。

1.5.3 小批量梯度下降法（Mini-batch Gradient Descent）
小批量梯度下降法是批量梯度下降法和随机梯度下降法的折衷，也就是对于 https://www.zhihu.com/equation?tex=m 个样本，我们采用个样子来迭代， https://www.zhihu.com/equation?tex=1%3Cx%3Cm 。一般可以取 https://www.zhihu.com/equation?tex=x%3D16%2C32%2C64... ，当然根据样本的数据，可以调整这个的值。上述三种方法得到局部最优解的过程如下：



1.6 批量梯度下降法python实现
def train(X, y, W, B, alpha, max_iters):
    '''
    使用了所有的样本进行梯度下降
    X: 训练集,
    y: 标签,
    W: 权重向量,
    B: bias,
    alpha: 学习率,
    max_iters: 最大迭代次数.
    '''
    dW = 0 # 权重梯度收集器
    dB = 0 # Bias梯度的收集器
    m = X.shape # 样本数
    for i in range(max_iters):
      dW = 0 # 每次迭代重置
      dB = 0
      for j in range(m):
            # 1. 迭代所有的样本
            # 2. 计算权重和bias的梯度保存在w_grad和b_grad,
            # 3. 通过增加w_grad和b_grad来更新dW和dB
            W = W - alpha * (dW / m) # 更新权重
            B = B - alpha * (dB / m) # 更新bias

    return W, B

1.7 梯度下降法和最小二乘法
梯度下降法和最小二乘法相比，梯度下降法需要选择步长，而最小二乘法不需要。梯度下降法是迭代求解，最小二乘法是计算解析解。如果样本量不算很大，且存在解析解，最小二乘法比起梯度下降法要有优势，计算速度很快。但是如果样本量很大，用最小二乘法由于需要求一个超级大的逆矩阵，这时就很难或者很慢才能求解解析解了，使用迭代的梯度下降法比较有优势。
<hr/>2： 牛顿法

一般来说，牛顿法主要应用在两个方面，1：求方程的根；2：最优化。

2.1 求解方程
并不是所有的方程都有求根公式，或者求根公式很复杂，导致求解困难。利用牛顿法，可以迭代求解。
原理是利用泰勒公式，在 https://www.zhihu.com/equation?tex=x_0 处展开，且展开到一阶, 即。求解方程，等价于 https://www.zhihu.com/equation?tex=f%28x_0%29%2Bf%27%28x_0%29%28x-x_0%29%3D0 ，求解 https://www.zhihu.com/equation?tex=x%3Dx_1%3Dx_0-f%28x_0%29%2Ff%27%28x_0%29 。因为这是利用泰勒公式的一阶展开，处并不是完全相等，而是近似相等，这里求得的 https://www.zhihu.com/equation?tex=x_1 并不能让，只能说 https://www.zhihu.com/equation?tex=f%28x_1%29 的值比 https://www.zhihu.com/equation?tex=f%28x_0%29 的值更接近于0，于是迭代的想法就很自然了，可以进而推出 https://www.zhihu.com/equation?tex=x_%7Bn%2B1%7D%3Dx_%7Bn%7D-f%28x_n%29%2Ff%27%28x_%7Bn%7D%29 ，通过迭代，这个式子必然在 https://www.zhihu.com/equation?tex=f%28x%5E%2A%29%3D0 的时候收敛。整个过程如下：




2.2 最优化
无约束最优化问题
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+%5Cmin_%7Bx+%5Cin+R%5E%7Bn%7D%7D+f%5Cleft%28x%5Cright%29%5Cend%7Balign%2A%7D+%5C%5C
其中为目标函数的极小点。
设具有二阶连续偏导数，若第 https://www.zhihu.com/equation?tex=k 次迭代值为，则可将在附近进行二阶泰勒展开
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+f%5Cleft%28x%5Cright%29+%3D+f%5Cleft%28x%5E%7B%5Cleft%28k%5Cright%29%7D%5Cright%29%2Bg_%7Bk%7D%5E%7BT%7D%5Cleft%28x-x%5E%7B%5Cleft%28k%5Cright%29%7D%5Cright%29%2B%5Cdfrac%7B1%7D%7B2%7D%5Cleft%28x-x%5E%7B%5Cleft%28k%5Cright%29%7D%5Cright%29%5E%7BT%7D+H%5Cleft%28x%5E%7B%5Cleft%28k%5Cright%29%7D%5Cright%29%5Cleft%28x-x%5E%7B%5Cleft%28x%5Cright%29%7D%5Cright%29%5Cend%7Balign%2A%7D+%5C%5C
其中， https://www.zhihu.com/equation?tex=g_%7Bk%7D%3Dg%5Cleft%28x%5E%7B%5Cleft%28k%5Cright%29%7D%5Cright%29%3D%5Cnabla+f%5Cleft%28x%5E%7B%5Cleft%28k%5Cright%29%7D%5Cright%29 是的梯度向量在点的值，是的海赛矩阵
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+H%5Cleft%28x%5Cright%29%3D%5Cleft%5B%5Cdfrac%7B%5Cpartial%5E%7B2%7Df%7D%7B%5Cpartial+x_%7Bi%7D+%5Cpartial+x_%7Bj%7D%7D%5Cright%5D_%7Bn+%5Ctimes+n%7D%5Cend%7Balign%2A%7D+%5C%5C
在点的值。
函数有极值的必要条件是在极值点处一阶导数为0，即梯度向量为0。特别的当是正定矩阵时，函数的极值为极小值。
我们为了得到一阶导数为0的点，可以用到2.1里的求解方程方法。根据二阶泰勒展开，对 https://www.zhihu.com/equation?tex=%5Cnabla+f%28x%29 在进行展开得（也可以对上述泰勒公式再进行求导）

其中，，则
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+g_%7Bk%7D%2BH_%7Bk%7D%5Cleft%28x%5E%7B%5Cleft%28k%2B1%5Cright%29%7D-x%5E%7B%5Cleft%28k%5Cright%29%7D%5Cright%29%3D0+%5C%5C+%26+x%5E%7B%5Cleft%28k%2B1%5Cright%29%7D%3Dx%5E%7B%5Cleft%28k%5Cright%29%7D-H_%7Bk%7D%5E%7B-1%7Dg_%7Bk%7D%5Cend%7Balign%2A%7D+%5C%5C
我们令
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+H_%7Bk%7Dp_%7Bk%7D%3D-g_%7Bk%7D%5Cend%7Balign%2A%7D+%5C%5C
则得到迭代公式
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+x%5E%7B%5Cleft%28k%2B1%5Cright%29%7D%3Dx%5E%7B%5Cleft%28k%5Cright%29%7D%2Bp_%7Bk%7D%5Cend%7Balign%2A%7D+%5C%5C
最终可在 https://www.zhihu.com/equation?tex=%5Cnabla+f%28x%5E%2A%29%3D0 收敛。
牛顿法：
输入：目标函数，梯度，海赛矩阵 https://www.zhihu.com/equation?tex=H%5Cleft%28x%5Cright%29 ，精度要求
输出：的极小点
1. 取初始点，置
2. 计算
3. 若则停止计算，得近似解
4. 计算，并求
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+H_%7Bk%7Dp_%7Bk%7D%3D-g_%7Bk%7D%5Cend%7Balign%2A%7D%5C%5C
5. 置 https://www.zhihu.com/equation?tex=x%5E%7B%5Cleft%28k%2B1%5Cright%29%7D%3Dx%5E%7B%5Cleft%28k%5Cright%29%7D%2Bp_%7Bk%7D
6. 置，转2.
2.3： 牛顿法与梯度下降法
梯度下降法和牛顿法相比，两者都是迭代求解，不过梯度下降法是梯度求解，而牛顿法是用二阶的海森矩阵的逆矩阵求解。相对而言，使用牛顿法收敛更快（迭代更少次数）。但是每次迭代的时间比梯度下降法长。
梯度下降法： https://www.zhihu.com/equation?tex=x%5E%7B%28k%2B1%29%7D%3Dx%5E%7B%28k%29%7D-%5Clambda+%5Cnabla+f%28x%5E%7Bk%7D%29
牛顿法： https://www.zhihu.com/equation?tex=x%5E%7B%28k%2B1%29%7D%3Dx%5E%7B%28k%29%7D-%5Clambda+%28H%5E%7B%28k%29%7D%29%5E%7B-1%7D+%5Cnabla+f%28x%5E%7Bk%7D%29
如下图是一个最小化一个目标方程的例子，红色曲线是利用牛顿法迭代求解，绿色曲线是利用梯度下降法求解。



至于为什么牛顿法收敛更快，通俗来说梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。更多的可见：最优化问题中，牛顿法为什么比梯度下降法求解需要的迭代次数更少？
<hr/>3： 拟牛顿法的思路

在牛顿法的迭代中，需要计算海森矩阵的逆矩阵 https://www.zhihu.com/equation?tex=H%5E%7B-1%7D ，这一计算比较复杂，考虑用一个阶矩阵 https://www.zhihu.com/equation?tex=G_k%3DG%28x%5E%7B%28k%29%7D%29 来近似代替 https://www.zhihu.com/equation?tex=H_k%5E%7B-1%7D%3DH%5E%7B-1%7D%28x%5E%7B%28k%29%7D%29 。这就是拟牛顿法的基本想法。
要找到近似的替代矩阵，必定要和有类似的性质。先看下牛顿法迭代中海森矩阵满足的条件。首先满足以下关系：
取 https://www.zhihu.com/equation?tex=x%3Dx%5E%7B%5Cleft%28k-1%5Cright%29%7D ，由

得
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+g_%7Bk-1%7D-g_%7Bk%7D%3DH_%7Bk%7D%5Cleft%28x%5E%7B%5Cleft%28k-1%5Cright%29%7D-x%5E%7B%5Cleft%28k%5Cright%29%7D%5Cright%29%5Cend%7Balign%2A%7D+%5C%5C
记 https://www.zhihu.com/equation?tex=y_%7Bk%7D%3Dg_%7Bk%7D-g_%7Bk-1%7D%EF%BC%8C%5Cdelta_%7Bk%7D%3Dx%5E%7B%5Cleft%28k%5Cright%29%7D-x%5E%7B%5Cleft%28k-1%5Cright%29%7D ，则
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+y_%7Bk-1%7D%3DH_%7Bk%7D%5Cdelta_%7Bk-1%7D+%5C%5C+%26+H_%7Bk%7D%5E%7B-1%7Dy_%7Bk-1%7D%3D%5Cdelta_%7Bk-1%7D%5Cend%7Balign%2A%7D+%5C%5C
称为拟牛顿条件(Secant equation)。

注：在李航老师《统计机器学习》附录B中，取的是 https://www.zhihu.com/equation?tex=x%3Dx%5E%7B%28k%2B1%29%7D ，得到的拟牛顿条件是 https://www.zhihu.com/equation?tex=H_%7Bk%7D%5E%7B-1%7Dy_%7Bk%7D%3D%5Cdelta_%7Bk%7D ，但是用 https://www.zhihu.com/equation?tex=x%3Dx%5E%7B%28k-1%29%7D 的到的拟牛顿条件和下面推导吻合，但还没找到原因，还望高手指教。

其次，如果是正定的（也是正定的），那么保证牛顿法的搜索方向 https://www.zhihu.com/equation?tex=p_k 是下降方向。这是因为搜索方向是 https://www.zhihu.com/equation?tex=p_k%3D-H_k%5E%7B-1%7Dg_k ，
由
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+x%5E%7B%5Cleft%28k%2B1%5Cright%29%7D%3Dx%5E%7B%5Cleft%28k%5Cright%29%7D-H_%7Bk%7D%5E%7B-1%7Dg_%7Bk%7D+%5Cend%7Balign%2A%7D+%5C%5C
有
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+x%3Dx%5E%7B%5Cleft%28k%5Cright%29%7D-%5Clambda+H_%7Bk%7D%5E%7B-1%7D+g_%7Bk%7D%3Dx%5E%7B%5Cleft%28k%5Cright%29%7D%2B%5Clambda+p_%7Bk%7D+%5Cend%7Balign%2A%7D%5C%5C
则在的泰勒展开可近似为
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+f%5Cleft%28x%5Cright%29%3Df%5Cleft%28x%5E%7B%5Cleft%28k%5Cright%29%7D%5Cright%29-%5Clambda+g_%7Bk%7D%5E%7BT%7D+H_%7Bk%7D%5E%7B-1%7D+g_%7Bk%7D%5Cend%7Balign%2A%7D%5C%5C
由于正定，故 https://www.zhihu.com/equation?tex=g_%7Bk%7D%5E%7BT%7D+H_%7Bk%7D%5E%7B-1%7D+g_%7Bk%7D+%3E+0 。当 https://www.zhihu.com/equation?tex=%5Clambda 为一个充分小的正数时，有 https://www.zhihu.com/equation?tex=f%5Cleft%28x%5Cright%29+%3C+f%5Cleft%28x%5E%7B%5Cleft%28x%5Cright%29%7D%5Cright%29 ，即搜索方向是下降方向。
因此拟牛顿法将作为近似。要求满足同样的条件。首先，每次迭代矩阵是正定的。同时，满足下面的拟牛顿条件：
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26G_%7Bk%2B1%7Dy_k%3D%5Cdelta_k%5Cend%7Balign%2A%7D+%5C%5C
按照拟牛顿条件，在每次迭代中可以选择更新矩阵：
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26G_%7Bk%2B1%7D%3DG_k%2B%5CDelta+G_k%5Cend%7Balign%2A%7D+%5C%5C
这种选择有一定的灵活性，因此有很多具体的实现方法，下面介绍Broyden类拟牛顿法。
<hr/>4： DFP(Davidon-Fletcher-Powell)算法(DFP algorithm)

DFP算法中选择作为的近似，假设每一步迭代中矩阵是由加上两个附加项构成，即
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+G_%7Bk%2B1%7D%3DG_%7Bk%7D%2BP_%7Bk%7D%2BQ_%7Bk%7D%5Cend%7Balign%2A%7D%5C%5C
其中，与是待定矩阵。则
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+G_%7Bk%2B1%7Dy_%7Bk%7D%3DG_%7Bk%7Dy_%7Bk%7D%2BP_%7Bk%7Dy_%7Bk%7D%2BQ_%7Bk%7Dy_%7Bk%7D%5Cend%7Balign%2A%7D%5C%5C
为使满足拟牛顿条件，可使与满足
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+P_%7Bk%7Dy_%7Bk%7D%3D%5Cdelta_%7Bk%7D+%5C%5C+%26+Q_%7Bk%7Dy_%7Bk%7D%3D-G_%7Bk%7Dy_%7Bk%7D%5Cend%7Balign%2A%7D%5C%5C
可取
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+P_%7Bk%7D%3D+%5Cdfrac%7B%5Cdelta_%7Bk%7D+%5Cdelta_%7Bk%7D%5E%7BT%7D%7D%7B%5Cdelta_%7Bk%7D%5E%7BT%7D+y_%7Bk%7D%7D+%5C%5C+%26+Q_%7Bk%7D%3D-+%5Cdfrac%7BG_%7Bk%7Dy_%7Bk%7Dy_%7Bk%7D%5E%7BT%7DG_%7Bk%7D%7D%7By_%7Bk%7D%5E%7BT%7DG_%7Bk%7Dy_%7Bk%7D%7D%5Cend%7Balign%2A%7D%5C%5C
可得矩阵的迭代公式

可以证明，如果初始矩阵是正定的，则迭代过程中的每个矩阵都是正定的。
DFP算法：
输入：目标函数，梯度，精度要求
输出：的极小点
1. 取初始点，取为正定矩阵，置
2. 计算， 若则停止计算，得近似解；否则，转3.
3. 置 https://www.zhihu.com/equation?tex=p_%7Bk%7D%3D-G_%7Bk%7Dg_%7Bk%7D
4. 一维搜索，求使

5. 置
6. 计算，若则停止计算，近似解；否则，计算

7. 置，转3.
5： BFGS(Broyden-Fletcher-Goldfard-Shano)算法(BFGS algorithm)

DFP是用逼近海赛矩阵的逆矩阵，而BFGS算法中选择逼近海赛矩阵 https://www.zhihu.com/equation?tex=H_%7Bk%7D ，相应的拟牛顿条件
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+B_%7Bk%2B1%7D+%5Cdelta_%7Bk%7D+%3D+y_%7Bk%7D%5Cend%7Balign%2A%7D%5C%5C
假设每一步迭代中矩阵是由加上两个附加项构成，即
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+B_%7Bk%2B1%7D%3DB_%7Bk%7D%2BP_%7Bk%7D%2BQ_%7Bk%7D%5Cend%7Balign%2A%7D%5C%5C
其中，与是待定矩阵。则
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+B_%7Bk%2B1%7Dy_%7Bk%7D%3DB_%7Bk%7Dy_%7Bk%7D%2BP_%7Bk%7Dy_%7Bk%7D%2BQ_%7Bk%7Dy_%7Bk%7D%5Cend%7Balign%2A%7D%5C%5C
为使满足拟牛顿条件，可使与满足
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+P_%7Bk%7D%5Cdelta_%7Bk%7D%3Dy_%7Bk%7D+%5C%5C+%26+Q_%7Bk%7D%5Cdelta_%7Bk%7D%3D-B_%7Bk%7Dy_%7Bk%7D%5Cdelta_%7Bk%7D%5Cend%7Balign%2A%7D%5C%5C
可取
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+P_%7Bk%7D%3D+%5Cdfrac%7By_%7Bk%7Dy_%7Bk%7D%5E%7BT%7D%7D%7By_%7Bk%7D%5E%7BT%7D%5Cdelta_%7Bk%7D+%7D+%5C%5C+%26+Q_%7Bk%7D%3D-+%5Cdfrac%7BB_%7Bk%7D%5Cdelta_%7Bk%7D%5Cdelta_%7Bk%7D%5E%7BT%7DB_%7Bk%7D%7D%7B%5Cdelta_%7Bk%7D%5E%7BT%7DB_%7Bk%7D%5Cdelta_%7Bk%7D%7D%5Cend%7Balign%2A%7D%5C%5C
可得矩阵的迭代公式

可以证明，如果初始矩阵是正定的，则迭代过程中的每个矩阵都是正定的。
BFGS算法：
输入：目标函数，梯度，精度要求
输出：的极小点
1. 取初始点，取为正定矩阵，置
2. 计算   ，若则停止计算，得近似解；否则，转3.
3. 由 https://www.zhihu.com/equation?tex=B_%7Bk%7Dp_%7Bk%7D%3D-g_%7Bk%7D 求出
4. 一维搜索，求使

5. 置
6. 计算，若，则停止计算，近似解；否则，计算

7. 置，转3.<hr/>6： Broyden类算法(Broyden's algorithm)

我们可以从BFGS算法矩阵 https://www.zhihu.com/equation?tex=B_%7Bk%2B1%7D%EF%BC%9DB_%7Bk%7D%2B%5Cdfrac%7By_%7Bk%7Dy_%7Bk%7D%5E%7BT%7D%7D%7By_%7Bk%7D%5E%7BT%7D%5Cdelta_%7Bk%7D+%7D-+%5Cdfrac%7BB_%7Bk%7D%5Cdelta_%7Bk%7D%5Cdelta_%7Bk%7D%5E%7BT%7DB_%7Bk%7D%7D%7B%5Cdelta_%7Bk%7D%5E%7BT%7DB_%7Bk%7D%5Cdelta_%7Bk%7D%7D 的迭代公式得到BFGS算法关于的迭代公式。
记
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+G_%7Bk%7D%3DB_%7Bk%7D%5E%7B-1%7D%2C%5Cquad+G_%7Bk%2B1%7D%3DB_%7Bk%2B1%7D%5E%7B-1%7D%5Cend%7Balign%2A%7D%5C%5C
两次应用Sherman-Morrison公式，得
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+G_%7Bk%EF%BC%8B1%7D%3D%5Cleft%28I-+%5Cdfrac%7B%5Cdelta_%7Bk%7Dy_%7Bk%7D%5E%7BT%7D%7D%7B%5Cdelta_%7Bk%7D%5E%7BT%7Dy_%7Bk%7D%7D%5Cright%29G_%7Bk%7D%5Cleft%28I-%5Cdfrac%7B%5Cdelta_%7Bk%7Dy_%7Bk%7D%5E%7BT%7D%7D%7B%5Cdelta_%7Bk%7D%5E%7BT%7Dy_%7Bk%7D%7D%5Cright%29%5E%7BT%7D%2B%5Cdfrac%7B%5Cdelta_%7Bk%7D%5Cdelta_%7Bk%7D%5E%7BT%7D%7D%7B%5Cdelta_%7Bk%7D%5E%7BT%7Dy_%7Bk%7D%7D%5Cend%7Balign%2A%7D%5C%5C
称为BFGS算法关于的迭代公式。
其中Sherman-Morrison公式：假设 https://www.zhihu.com/equation?tex=A 是阶可逆矩阵， https://www.zhihu.com/equation?tex=u%2Cv 是维向量，且 https://www.zhihu.com/equation?tex=A%2Buv%5ET 也是可逆矩阵，则：
https://www.zhihu.com/equation?tex=%28A%2Buv%5ET%29%5E%7B-1%7D%3DA%5E%7B-1%7D-%5Cfrac%7BA%5E%7B-1%7Duv%5ETA%5E%7B-1%7D%7D%7B1%2Bv%5ETA%5E%7B-1%7Du%7D%5C%5C
令由DFP算法的迭代公式得到的记作，由BFGS算法的迭代公式得到的记作，由于和均满足拟牛顿条件，则两者的线性组合
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%5C%5C%26+G_%7Bk%2B1%7D%3D%5Calpha+G%5E%7BDFP%7D%2B%5Cleft%281-%5Calpha%5Cright%29+G%5E%7BBFGS%7D%5Cend%7Balign%2A%7D%5C%5C
也满足拟牛顿条件，而且是正定的。其中， https://www.zhihu.com/equation?tex=0+%5Cleq+%5Calpha+%5Cleq+1 。该类算法称为Broyden类算法。
<hr/>7： 参考文献

李航：《统计学习方法》，清华大学出版社
Jacobian矩阵和Hessian矩阵
梯度下降（Gradient Descent）小结
https://hackernoon.com/gradient-descent-aynk-7cbe95a778da
牛顿法与拟牛顿法学习笔记

BlaXuan 发表于 2022-1-2 15:03

quasi newton的BFGS method的想法，主要是：在最后两次迭代中，f的梯度与近似函数m的梯度相同（m是将f在当前迭代点处进行一阶taylor展开得到的），导出secant equation，因此你那里写得个方程实际上是一样的。

c0d3n4m 发表于 2022-1-2 15:06

好文

yukamu 发表于 2022-1-2 15:11

总结的很好

APSchmidt 发表于 2022-1-2 15:11

5的公式错了吧？Bk+1δk吧

xiangtingsl 发表于 2022-1-2 15:11

已赞赏感谢

unityloverz 发表于 2022-1-2 15:18

尝试回答注的问题：按我理解，我们统一此刻的x为x{k}，那么根据步长和搜索方向的乘积得到下一时刻即k+1时刻的x_{k+1}，在求解下降方向p_{k}和λ时用的是目标函数值极小化进行求解，此时带入目标函数的是：x_{k+1}，所以才能展开为x_{k}+λ*p_{k}，才能进行后续的计算，所以此处的牛顿法或者拟牛顿条件的海森阵H才能根据x_{k}进行计算，不好求才有了拟牛顿方法用G去代替；至于为什么取x_{k-1}可以，因为等号左右的负号抵消得到的形式与前面一样，差别在于此处不该是H_{k}，而应该是H_{k-1}。

LiteralliJeff 发表于 2022-1-2 15:23

请问最后一法的Gk是替换的海塞矩阵还是海塞矩阵的逆

yukamu 发表于 2022-1-2 15:25

2.3： 牛顿法与梯度下降法中牛顿法的公式 写错了吧，没有 系数

xiangtingsl 发表于 2022-1-2 15:31

问下，为什么能直接带入在k+1处的导数等于零，那前面不等于零怎么办
页: [1] 2 3
查看完整版本: 梯度下降法、牛顿法和拟牛顿法