1. 牛顿法
1.1 梯度下降法的缺点
对于无约束优化问题：
\[\min_{x \in \mathbb{R}^n} f(x) \]使用梯度下降法进行迭代：
\[x^{k + 1} = x^k - \alpha_k \nabla f(x^k) \]梯度下降的基本策略式沿着一阶导数的反方向（即最速下降方向）迭代。然而，当 \(\text{Hessian}\) 矩阵 \(\nabla ^2 f(x)\) 的条件数较多时，计算量较大，收敛的速度较为缓慢。
我们可以利用 \(f(x)\) 的 二阶信息 改进下降方向，从而加速算法的迭代。
1.2 牛顿法
对于二次可微函数 \(f(x)\)，考虑目标函数 \(f\) 在点 \(x^k\) 的 二阶泰勒近似：
\[f(x^{k + 1}) = f(x^k) + \nabla f(x^k)^T (x^{k + 1} - x^k) + \frac{1}{2}(x^{k + 1} - x^k)^T \nabla ^2 f(x^k)(x^{k + 1} - x^k) + o(||x^{k + 1} - x^k||^2) \]由 \(||x^{k + 1} - x^k|| \rightarrow 0\)，且 \(x^{k + 1} = x^k + d^k\)，忽略高阶项，得：
\[f(x^k + d^k) = f(x^k) + \nabla f(x^k)^T d^k + \frac{1}{2}(d^k)^T \nabla ^2 f(x^k)d^k \]将 \(d^k\) 视为参数，两边同时求梯度：
\[\nabla f(x^{k + 1}) = \nabla f(x^k) + \nabla ^2 f(x^k) d^k \]令导数为0，得：
\[\nabla ^2 f(x^k) d^k = - \nabla f(x^k) \]此方程称为 牛顿方程，由此可以得到牛顿法的搜索方向 \(d^k\)，被称为 牛顿方向。
若 \(\nabla ^2 f(x^k)\) 非奇异，那么可以得到 牛顿法的迭代格式：
\[x^{k + 1} = x^k - \alpha_k \nabla^2 f(x^k)^{-1} \nabla f(x^k) \]牛顿方向: \(d^k = \nabla^2 f(x^k)^{-1} \nabla f(x^k)\)
这就是 牛顿法 的迭代方程。一般情况下， 步长 \(\alpha_k = 1\) ，迭代格式也称为 经典牛顿法。即：
\[x^{k + 1} = x^k - \nabla^2 f(x^k)^{-1} \nabla f(x^k) \]
牛顿法和梯度法对比：
设基于梯度的迭代方程为 \(x^{k + 1} = x^k - H(x^{k}) \nabla f(x^k)\)，其中 \(x \in \mathbb{R}^n, \; H(x^k) \in \mathbb{R}^{n \times n}\)。
对于 梯度下降法，有：\(H(x^k) = \alpha I\)，其中 \(I\) 为单位阵；
对于 牛顿法，有：\(H(x^k) = \nabla ^2 f(x^k)^{-1}\)。
显然，牛顿法的 \(H(x^k)\) 是随着迭代点 \(x^k\) 不断变化的，相比于梯度下降法更加 灵活。
1.3 牛顿法过程
牛顿法是解决无约束优化问题的迭代算法之一。
牛顿法基本过程：
-
任选初始点 \(x^0 \in \mathbb{R}^n, \; k = 0\)
-
计算 \(\nabla f(x^k)\)，若目标函数满足终止条件 \(||\nabla f(x^k)|| < \varepsilon\) (或者其他终止条件)，则令 \(x^* = x^k\) 为最终解，结束整个算法
-
计算 \(\text{Hessian}\) 矩阵 \(\nabla^2 f(x^k)\)，
-
计算搜索方向 \(d^k = - \nabla^2 f(x^k)^{-1} \nabla f(x^k)\)
-
迭代更新：\(x^{k + 1} = x^k + d^k = x^k - \nabla^2 f(x^k)^{-1} \nabla(x^k)\)
2. 牛顿法收敛性
2.1 经典牛顿法的收敛性
假设 \(f\) 二阶连续可微，且存在 \(x^*\) 的一个邻域 \(N_{\delta}(x^*)\) 以及常数 \(L > 0\) 使得：
\[||\nabla ^2 f(x) - \nabla ^2 f(y)|| \le L||x - y||, \quad \forall \; x, y \in N_{\delta}(x^*) \]即函数 \(f\) 满足 \(\text{Hession}\) 矩阵利普希茨连续。
若 \(f(x)\) 满足 \(\nabla f(x^*) = 0, \; \nabla^2 f(x^*) \succ 0\)，则有：
-
若初始点 \(x^0\) 距离 \(x^*\) 足够近，则迭代点列 \(\{x^k\}\) 收敛到 \(x^*\) (局部收敛性)
-
\(\{x^k\}\) 二次收敛到 \(x^*\)
-
\(\{||\nabla f(x^k)||\}\) 二次收敛到 \(0\).
2.2 牛顿法收敛速度
牛顿法收敛速度 非常快，不会随着问题维度的增大而大幅增加所需的迭代次数，且不需要通过线搜确定迭代更新的步长。
但是，在实际使用中会存在一些 限制：
-
初始点 \(x^0\) 需要距离最优解 \(x^*\) 充分近(局部收敛性)。往往 先用梯度下降法 逼近得到较低精度的解，后用牛顿法 加速。
-
\(\text{Hessian}\) 矩阵 \(\nabla^2 f(x^*)\) 需 正定，如果是 半正定，可能会退化到 线性收敛。一般无法保证 \(\text{Hessian}\) 矩阵可逆，也不能保证是正定的。
-
\(\text{Hessian}\) 矩阵 \(\nabla^2 f(x^*)\) 条件数较多 时，求 \(\text{Hessian}\) 矩阵以及求其逆，需要很高的计算成本。故也对 初始点 \(x^0\) 的选取非常严格。
-
牛顿法的搜索方向下降 需要依赖于 \(\text{Hessian}\) 矩阵正定。
3. 修正牛顿法
3.1 修正角度
牛顿法（经典牛顿法） 优缺点非常明显，我们往往从以下两个缺点对牛顿法进行修正：
-
初始点 \(x^0\) 需要距离 \(x^*\) 足够近，否则，会导致迭代不稳定，进而导致算法 无法收敛。（局部收敛性）
-
牛顿法的搜索方向下降 需要依赖于 \(\text{Hessian}\) 矩阵正定，否则会导致牛顿方向不是下降的。
从以上的两个方面，可以分别考虑用以下方法完成修正：
-
加上 线搜索确定步长 \(\alpha\)，由此增加稳定性（精确解、直接搜索、\(\text{Wolfe, Goldstein, Armijo}\) 非精确准则等）
-
对 \(\nabla ^2 f(x^k)\) 进行修正，使其 一定正定 (即 \(\text{Hessian}\) 矩阵所有特征值均大于 \(0\))
对于第一点，下面提出了 阻尼牛顿法；对于第二点，下面提出了 L-M算法（Levenberg-Marquardt）。
3.2 阻尼牛顿法
由于不能保证 \(\text{Hessian}\) 矩阵 正定，故 牛顿方向 \(-\nabla ^2 f(x^k)^{-1} \nabla f(x^k)\) 不一定下降。所以，引入了 阻尼牛顿法，在 牛顿方向上加上线搜索，确定步长 \(\alpha\)，以此来保证搜索方向下降：
\[x^{k + 1} = x^k - \alpha_k \nabla^2f(x^k)^{-1} \nabla f(x^k) \]当 步长 \(\alpha\) 取固定值为 \(1\)，则退化为一般的 牛顿法（经典牛顿法）。
阻尼牛顿法基本过程：
-
任选初始点 \(x^0 \in \mathbb{R}^n, \; k = 0\)
-
计算 \(\nabla f(x^k)\)，若目标函数满足终止条件 \(||\nabla f(x^k)|| < \varepsilon\) (或者其他终止条件)，则令 \(x^* = x^k\) 为最终解，结束整个算法
-
计算 \(\text{Hessian}\) 矩阵 \(\nabla^2 f(x^k)\)，
-
计算搜索方向 \(d^k = - \nabla^2 f(x^k)^{-1} \nabla f(x^k)\)
-
沿着搜索方向 \(d^k\) 进行 线搜索，确定 步长 \(\alpha_k\)
-
迭代更新：\(x^{k + 1} = x^k + d^k = x^k - \alpha_k \nabla^2 f(x^k)^{-1} \nabla(x^k)\)
3.3 L-M算法
牛顿法中在迭代点 \(x^k\) 处的 \(\text{Hessian}\) 矩阵 \(\nabla^2 f(x^k)\) 可能是 奇异、非正定 等情况，无法保证 \(\text{Hessian}\) 矩阵可逆。
故可以为 \(\text{Hessian}\) 矩阵加上一个 \(\lambda I\) 来 强行让 \(\text{Hessian}\) 矩阵变得正定：
\[[\nabla^2 f(x^k) + \lambda I]d^k = -\nabla f(x^k) \]即使得 \([\nabla^2 f(x^k) + \lambda I]^{-1}\) 存在，所以有 \(\text{L-M}\) 算法下的牛顿方向：
\[d^k = - [\nabla^2 f(x^k) + \lambda I]^{-1}\nabla f(x^k) \]其中 \(\lambda \in \mathbb{R}^+\) 且 \(I\) 为单位阵。
在机器学习邻域的线性回归问题中，岭回归也是采用这种方法，使得协方差矩阵的逆一定存在。
在 \(\text{L-M}\) 算法中，只要 \(\lambda\) 足够大，一定可以使得 \(\text{Hessian}\) 矩阵 的所有特征值都大于 \(0\)，即 保证 \(\text{Hessian}\) 矩阵一定正定 。
参考
刘浩洋, 户将, 李勇锋, 文再文 《最优化：建模、算法与理论》
标签：迭代,text,nabla,牛顿,笔记,矩阵,最优化,Hessian From： https://www.cnblogs.com/MAKISE004/p/17904136.html