您的位置: 首页  >  文章  >  优化算法 - 牛顿法 and 拟牛顿法

优化算法 - 牛顿法 and 拟牛顿法

分类: 文章 • 2024-03-13 17:17:45

优化算法 - 牛顿法 and 拟牛顿法

预备知识

  • 无约束优化问题

    我们以前聊过约束优化方法，将带有约束的优化问题（例如 SVM 中间隔的间隔要大于 1）通过 拉格朗日乘子法转化为凸优化问题，再对各参数求偏导从而求的最优解。

    那么对于无约束的优化问题呢？我们通常使用跟梯度有关的算法。例如 梯度下降法，在 Logistic回归 中以及神经网络中都有应用。而关于梯度的无约束优化算法还有牛顿法系列。

    在介绍牛顿法前我们先来了解两个基础知识，Hesse 矩阵以及 泰勒展开式。

  • Hesse 矩阵

    简单来说，Hesse 矩阵就是某一矩阵对于其中各元素的偏导（二阶）。

    例如有矩阵：A=[x1x1x1x2x2x1x2x2]A=\begin{bmatrix} x_1x_1 & x_1x_2\\ x_2x_1 & x_2x_2\\ \end{bmatrix}

    则，H(x)=[∂2f∂x12∂2f∂x1∂x2∂2f∂x2∂x1∂2f∂x22]H(x)=\begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} \\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} \\ \end{bmatrix}

    Hesse矩阵的通用表达式为：H(x)=[∂2f∂xi∂xj]n∗nH(x)=[\frac{\partial^2 f}{\partial x_i \partial x_j}]_{n*n}

  • 泰勒展开式

    高数中的经典公式，将一个函数，在某一点处，利用各阶导数计算原函数值。这里以二阶展开举例，省略高阶无穷小的余项。

    将 f(x)f(x) 在 x0 处的二阶展开：

    f(x)=f(x0)+f′(x0)(x−x0)+12f′′(x0)(x−x0)2f(x)=f(x_0)+f'(x_0)(x-x_0)+\frac{1}{2}f''(x_0)(x-x_0)^2

    对于 x 为矩阵来讲，令 g(x)g(x) 表示一阶导，H(x)H(x) 表示二阶导：

    f(x)=f(x0)+f′(x0)(x−x0)+12f′′(x0)(x−x0)2=f(x0)+gT(x0)(x−x0)+12(x−x0)TH(x0)(x−x0)\begin{aligned}f(x)=&f(x_0)+f'(x_0)(x-x_0)+\frac{1}{2}f''(x_0)(x-x_0)^2\\ =&f(x_0)+g^T(x_0)(x-x_0)+\frac{1}{2}(x-x_0)^TH(x_0)(x-x_0) \end{aligned}

牛顿法

接下来进入正题，对于无约束优化问题来讲，无法直接求解，所以需要类似梯度下降一样一步一步的迭代。牛顿法也同样基于这个理念。

  • 形象化解释

    首先来看一个形象化的解释：

    ∙\bullet 目标：求 f(x)=0f(x)=0 的解 x∗x^*

    ∙\bullet 初始选择一个接近函数 f(x)f(x) 零点的 x0x_0，计算相应的 f(x0)f(x_0) 和切线斜率 f′(x0)f'(x_0)。

    ∙\bullet 利用“两点式”计算经过点 (x0,f(x0))(x_0, f(x_0)) 且斜率为 f′(x0)f'(x_0) 的直线，与 xx 轴的交点 (x1,0)(x_1,0).

    f′(x0)=f(x0)−f(x1)x0−x1=f(x0)x0−x1f'(x_0)=\frac{f(x_0)-f(x_1)}{x_0-x_1}=\frac{f(x_0)}{x_0-x_1}

    x1=x0−f(x0)f′(x0)x_1=x_0-\frac{f(x_0)}{f'(x_0)}，x1x_1 则为下一次迭代的点，

    牛顿法又称为切线法，如图所示： 优化算法 - 牛顿法 and 拟牛顿法
    （图片来自 https://www.cnblogs.com/shixiangwan/p/7532830.html）

    以上步骤是求解能使 f(x)=0f(x)=0 时的解 x∗x^*，但我们现在要求的是能使 f′(x)=0f'(x)=0 的解，所以，我们的目标变为：

    f′′(x0)=f′(x0)−f′(x1)x0−x1f''(x_0)=\frac{f'(x_0)-f'(x_1)}{x_0-x_1}

    得到：

    x1=x0−f′(x0)f′′(x0)⟹  kxk+1=xk−f′(xk)f′′(xk)x_1=x_0-\frac{f'(x_0)}{f''(x_0)} \mathop{}_{\Longrightarrow}^{~~k}x_{k+1}=x_k-\frac{f'(x_k)}{f''(x_k)}

    这便是我们牛顿法的迭代更新过程。

  • 公式化解释

    对于函数 g(x)g(x)，其导数 H(x)H(x)，对 g(x)g(x) 在点 xkx_k 出使用泰勒二阶展开，得：

    g(x)=g(xk)+H(xk)(x−xk)g(x)=g(x_k)+H(x_k)(x-x_k)

    令 x=xk+1，gk=g(xk)，Hk=H(xk)x=x_{k+1}，g_k=g(x_k)，H_k=H(x_k)，则更新迭代公式为：

    xk+1=xk+Hk−1(gk+1−gk)x_{k+1}=x_k+H_k^{-1}(g_{k+1}-g_k)

    （gk+1=0 时则与之前所推等价g_{k+1}=0~时则与之前所推等价）

  • 算法过程
    1. 确定精度要求ε，初始化x0，置k=0确定精度要求 ε，初始化 x_0，置k=0
    2. 计算gk=g(xk)，若∣∣g(xk)∣∣≤ε则停止计算，求得近似解x∗=xk；否则转第 3 步计算 g_k=g(x_k)，若||g(x_k)||\leε 则停止计算，求得近似解 x^*=x_k；否则转第~3~步
    3. 计算Hk=H(xk)，以及其逆矩阵Hk−1计算 H_k=H(x_k)，以及其逆矩阵 H_k^{-1}
    4. 计算xk+1=xk−Hk−1gk，令k=k+1，转第 2 步计算 x_{k+1}=x_k-H_k^{-1}g_k，令k=k+1，转第~2~步

    我们可以看到，在迭代过程中，需要求 Hk的逆矩阵Hk−1H_k的逆矩阵 H_k^{-1}，这个计算比较复杂，效率很低，所以就产生了拟牛顿法。

拟牛顿法

拟牛顿法的思想是与牛顿法一样的，但由于求逆矩阵复杂，多以拟牛顿法寻找一个矩阵用来近似替代 Hk−1H_k^{-1}

  • 拟牛顿条件

    想找替代矩阵可不是随便找的，需要满足一个条件（两点式），即：

    xk+1−xk=Hk−1(gk+1−gk)x_{k+1}-x_k=H_k^{-1}(g_{k+1}-g_k)

    此条件被称为“拟牛顿条件”。

    拟牛顿法则是使用 GkG_k 作为 Hk−1H_k^{-1} 的近似，要求 GkG_k 为正定矩阵，且满足拟牛顿条件。根据拟牛顿条件的不同，选取的正定矩阵也不一样：

    如果选择 GkG_k 作为 Hk−1H_k^{-1} 的近似，就成为 DFP 算法；
    如果选择 BkB_k 作为 HkH_k 的近似，就成为 BFGS 算法。

    按照拟牛顿条件，在每次迭代中可以选择更新替代矩阵：

    Gk+1=Gk+ΔGkG_{k+1}=G_k+ΔG_k

    为什么要求 Gk或BkG_k或B_k 为正定矩阵呢？那是因为只有它们为正定矩阵时，x 的搜索方向才是 f(x)f(x) 下降的方向。

    具体的，根据迭代更新公式：xk+1=xk−Hk−1gkx_{k+1}=x_k-H_k^{-1}g_k，

    引入参数 λλ，定义 pk=−Hk−1gkp_k=-H_k^{-1}g_k

    迭代更新公式变为：xk+1−xk=λPkx_{k+1}-x_k=λP_k

    f(xk+1)f(x_{k+1}) 在 xkx_k 处的泰勒一阶展开：f(xk+1)=f(xk)+gkT(xk+1−xk)f(x_{k+1})=f(x_k)+g_k^T(x_{k+1}-x_k)

    将迭代更新公式代入，得：

    f(xk+1)=f(xk)−λgkTHk−1gkf(x_{k+1})=f(x_k)-λg_k^TH_k^{-1}g_k

    因为 HkH_k 是正定的（Hk−1H_k^{-1} 也是正定的），所以有 gkTHk−1gk>0g_k^TH_k^{-1}g_k>0，当 λλ 为充分小的正数时，总有 f(xk+1)<f(xk)f(x_{k+1})<f(x_k)，就意味着 f(x)f(x) 在迭代中逐步逼近最小值，也就是说 pkp_k 的方向是函数下降方向。

  • DFP (Davidon-Fletcher-Powell)
    • 算法推导

      DFP 算法选择 GkG_k 作为 Hk−1H_k^{-1} 的近似，假设每一步迭代中矩阵 Gk+1G_{k+1} 是由 GkG_k 加上两个附加矩阵构成的，即：

      Gk+1=Gk+Pk+QkG_{k+1}=G_k+P_k+Q_k，其中 Pk，QkP_k，Q_k 为待定矩阵，令 yk=gk+1−gky_k=g_{k+1}-g_k，δk=xk+1−xkδ_k=x_{k+1}-x_k

      这时 ，Gk+1yk=Gkyk+Pk+QkykG_{k+1}y_k=G_ky_k+P_k+Q_ky_k

      为使 Gk+1G_{k+1} 满足拟牛顿条件，可使 Pk，QkP_k，Q_k 满足：

      Pkyk=δkP_ky_k=δ_k，可以找到 Pk=δkδkTδkTykP_k=\frac{δ_kδ_k^T}{δ_k^Ty_k}

      Qkyk=−GkykQ_ky_k=-G_ky_k，可以找到 Qk=−GkykykTGkykTGkykQ_k=-\frac{G_ky_ky_k^TG_k}{y_k^TG_ky_k}

      由以上得到矩阵 Gk+1G_{k+1} 的迭代公式：

      Gk+1=Gk+δkδkTδkTyk−GkykykTGkykTGkykG_{k+1}=G_k+\frac{δ_kδ_k^T}{δ_k^Ty_k}-\frac{G_ky_ky_k^TG_k}{y_k^TG_ky_k} （公式 G）

      可以证明，如果初始矩阵 G0G_0 是正定的，则迭代过程中的每个矩阵 GkG_k 都是正定的。

    • 算法过程
      1. 确定精度要求ε，初始化x0、G0为正定对称矩阵，置k=0确定精度要求 ε，初始化 x_0、G_0为正定对称矩阵，置k=0
      2. 计算gk=g(xk)，若∣∣g(xk)∣∣≤ε则停止计算，求得近似解x∗=xk；否则转第 3 步计算 g_k=g(x_k)，若||g(x_k)||\leε 则停止计算，求得近似解 x^*=x_k；否则转第~3~步
      3. 计算pk=Gkgk计算 p_k=G_kg_k
      4. 一维搜索：λk=   λ≥0argminf(xk+λpk)一维搜索：λ_k=\mathop{}_{~~~λ\ge0}^{argmin}f(x_k+λp_k)
      5. 计算xk+1=xk+λkpk计算 x_{k+1}=x_k+λ_kp_k
      6. 计算gk+1=g(xk+1)，若∣∣g(xk)∣∣≤ε则停止计算，求得近似解x∗=xk；否则，按（公式G）计算Gk+1，置k=k+1计算g_{k+1}=g(x_{k+1})，若||g(x_k)||\leε 则停止计算，求得近似解 x^*=x_k；否则，按（公式G）计算 G_{k+1}，置 k=k+1
  • BFGS (Broyden-Fletcher-Goldfarb-Shanno)

    BFGS 与 DFP 类似，不同的是选取的替代矩阵不同：

    Bk+1=Bk+ykδyTykTδk−BkδkδkTBkδkTBkδkB_{k+1}=B_k+\frac{y_kδ_y^T}{y_k^Tδ_k}-\frac{B_kδ_kδ_k^TB_k}{δ_k^TB_kδ_k}

总结

对于牛顿法与拟牛顿法的计算过程的区别：

牛顿法：

通过泰勒展开式近似原函数，每次迭代以计算 Hesse 的逆矩阵为核心，从而逼近 原函数的最小值。

拟牛顿法：

通过初始化 (G0或B0)(G_0或B_0) ，一维搜索 λkλ_k，以及替代矩阵(Gk+1或Bk+1)(G_{k+1}或B_{k+1})的迭代计算，代替了 Hesse 逆矩阵的计算。

从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法的收敛速度更快。更通俗地说，如果想找一条最短的路径走到一个山的最底部，梯度下降法每次只从当前所处位置选一个坡度最大的方向走一步，而牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑在走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）

相关推荐