牛顿法的Hessian修正策略与信赖域dogleg方法

在优化问题中，我们常使用牛顿法来寻找函数的极小点。其核心思想是利用函数在当前点的二次模型（一个抛物面）来逼近原函数，并通过求解这个二次模型的极小点来确定下一步的迭代方向。这个二次模型由梯度（一阶导数）和Hessian矩阵（二阶导数矩阵）共同决定。

然而，直接应用牛顿法存在两个关键问题：Hessian矩阵可能不是正定的（导致模型的极小点不存在或方向错误），以及当初始点离目标极值点太远时，步长可能过大，导致算法不收敛甚至发散。本指南将手把手教你如何通过修正Hessian矩阵和使用信赖域dogleg方法来解决这两个问题，让优化过程更稳定、更可靠。

1. 基础：标准牛顿法及其问题

标准牛顿法的迭代步骤如下：

1. 计算梯度：在当前点 $\mathbf{x}_k$，计算目标函数 $f$ 的梯度向量 $\mathbf{g}_k = \nabla f(\mathbf{x}_k)$。
2. 计算Hessian矩阵：在当前点 $\mathbf{x}_k$，计算Hessian矩阵 $\mathbf{H}_k = \nabla^2 f(\mathbf{x}_k)$。这个矩阵描述了函数在各个方向上的弯曲程度（曲率）。
3. 求解牛顿方程：求解 线性方程组 $\mathbf{H}_k \mathbf{p}_k = -\mathbf{g}_k$，得到牛顿步 $\mathbf{p}_k$。
4. 更新迭代点：设置 下一个点 $\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{p}_k$。

当Hessian矩阵 $\mathbf{H}_k$ 是正定的时候，牛顿步 $\mathbf{p}_k$ 会直接指向二次模型的唯一极小点，通常能带来快速的收敛。

核心问题：如果 $\mathbf{H}_k$ 不是正定的（比如它有负特征值或零特征值），那么由它定义的二次模型就没有极小点（可能是个鞍点或极大点），求解出来的 $\mathbf{p}_k$ 可能是一个让函数值上升的方向。此外，即使 $\mathbf{H}_k$ 正定，但在远离最优解的区域，二次模型可能无法很好地近似原函数，导致取的步长 $\mathbf{p}_k$ 过大，使得 $f(\mathbf{x}_k + \mathbf{p}_k) > f(\mathbf{x}_k)$，算法反而“跑飞了”。

2. 进阶策略一：修正Hessian以确保正定性

为了解决Hessian不正定的问题，一个直接的策略是构造一个修正矩阵 $\mathbf{B}_k$，使其与 $\mathbf{H}_k$ 接近，但保证是正定的。最常用的方法如下。

1. 执行特征值分解：计算 Hessian矩阵 $\mathbf{H}_k$ 的特征值分解。设其特征值为 $\lambda_1, \lambda_2, \dots, \lambda_n$。正定要求所有特征值都大于零。
2. 设置阈值：定义 一个小的正数 $\tau$（例如 1e-6），作为保证正定性的最小特征值下限。
3. 修正特征值：检查 每一个特征值 $\lambda_i$。如果 $\lambda_i < \tau$，则将其替换为 $\tau$（或一个稍大的值，如 $|\lambda_i| + \tau$，这取决于具体实现策略）。修正后的特征值记为 $\tilde{\lambda}_i$。
4. 重构Hessian矩阵：利用 修正后的特征值和原始的特征向量，重新组合 成修正后的Hessian矩阵：
   $$ \mathbf{B}_k = \mathbf{Q} \, \text{diag}(\tilde{\lambda}_1, \tilde{\lambda}_2, \dots, \tilde{\lambda}_n) \, \mathbf{Q}^T $$
   其中 $\mathbf{Q}$ 是由特征向量组成的正交矩阵。
5. 使用修正矩阵：用 修正后的正定矩阵 $\mathbf{B}_k$ 替代 原始的 $\mathbf{H}_k$ 来求解牛顿方程 $\mathbf{B}_k \mathbf{p}_k = -\mathbf{g}_k$。

这个过程确保了你总是在用一个“曲面弯曲方向合理”的模型来求解下一步，避免了向错误的方向（如上坡方向）搜索。

3. 进阶策略二：通过信赖域框架控制步长

修正Hessian解决了“方向错误”的问题，但没有解决“步长过大”的问题。信赖域方法通过引入一个“安全圈”来解决后者。

核心思想：不直接信任二次模型在整个空间都有效，而是只相信它在当前点 $\mathbf{x}_k$ 附近的一个邻域（信赖域）内是准确的。我们只在这个邻域内寻找使二次模型最小的点。

操作步骤：

1. 设定信赖域半径：初始化 或更新 一个正数 $\Delta_k > 0$，它定义了当前信赖域的大小。可以想象以 $\mathbf{x}_k$ 为圆心，$\Delta_k$ 为半径的一个球体。
2. 构建并求解子问题：求解 如下的带约束优化子问题，以确定试探步长 $\mathbf{s}_k$：
   $$ \min_{\mathbf{s}} \quad m_k(\mathbf{s}) = f(\mathbf{x}_k) + \mathbf{g}_k^T \mathbf{s} + \frac{1}{2} \mathbf{s}^T \mathbf{B}_k \mathbf{s} $$
   $$ \text{subject to} \quad \|\mathbf{s}\| \leq \Delta_k $$
   其中 $m_k(\mathbf{s})$ 是我们的二次模型函数。问题的含义是：在信赖域（球）内，找到使模型下降最多的点。
3. 评估并决定接受步长：计算 实际函数下降量 $\text{ared} = f(\mathbf{x}_k) - f(\mathbf{x}_k + \mathbf{s}_k)$ 和模型预测下降量 $\text{pred} = m_k(\mathbf{0}) - m_k(\mathbf{s}_k)$。
4. 计算比值：计算 比值 $\rho_k = \text{ared} / \text{pred}$。这个比值衡量了模型预测的准确性。
5. 更新迭代点与信赖域：
   • 若 $\rho_k$ 接近 1（例如 > 0.75），说明模型非常准确，接受 步长 $\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{s}_k$，并且在下一次迭代中扩大 信赖域半径 $\Delta_{k+1}$（例如 $\Delta_{k+1} = 2 \Delta_k$）。
   • 若 $\rho_k$ 为正但较小（例如介于 0.25 和 0.75 之间），说明模型有一定准确性但不完美，接受 步长 $\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{s}_k$，并保持 信赖域半径不变 $\Delta_{k+1} = \Delta_k$。
   • 若 $\rho_k$ 很小甚至为负（例如 < 0.25），说明模型预测失败，拒绝 这次步长（$\mathbf{x}_{k+1} = \mathbf{x}_k$），并缩小 信赖域半径 $\Delta_{k+1} = \Delta_k / 2$。

这个框架动态地调整搜索范围，确保迭代稳定进行。

4. 求解信赖域子问题的Dogleg路径法

现在最关键的问题变成了：如何高效地求解那个带约束的子问题 $\min m_k(\mathbf{s})$ s.t. $\|\mathbf{s}\| \leq \Delta_k$？Dogleg方法提供了一种近似但高效的几何解法。

它通过构造一条由两段直线组成的“狗腿”路径来逼近解。路径的两个端点有明确的定义：

1. 计算第一个端点（柯西点）：计算 最速下降步 $\mathbf{s}^C = -\frac{\mathbf{g}_k^T \mathbf{g}_k}{\mathbf{g}_k^T \mathbf{B}_k \mathbf{g}_k} \mathbf{g}_k$。这个点是在整个信赖域内沿最速下降方向使模型下降最多的点。如果 $\|\mathbf{s}^C\| \geq \Delta_k$，则解就位于最速下降方向上，取 $\mathbf{s}_k = -\frac{\Delta_k}{\|\mathbf{g}_k\|} \mathbf{g}_k$（即取最速下降方向上信赖域边界上的点）。
2. 计算第二个端点（牛顿点）：求解 无约束问题 $\min m_k(\mathbf{s})$，即求解 $\mathbf{B}_k \mathbf{s}^N = -\mathbf{g}_k$ 得到牛顿点 $\mathbf{s}^N$。如果 $\|\mathbf{s}^N\| \leq \Delta_k$，说明整个牛顿步都在信赖域内，直接取 $\mathbf{s}_k = \mathbf{s}^N$。
3. 构造并选择Dogleg路径上的点：如果柯西点在信赖域内，而牛顿点在信赖域外（即 $\|\mathbf{s}^C\| < \Delta_k < \|\mathbf{s}^N\|$），则解一定位于从柯西点到牛顿点的连线上。参数化 这条线段：$\mathbf{s}(\tau) = \mathbf{s}^C + (\tau - 1)(\mathbf{s}^N - \mathbf{s}^C)$，其中 $\tau \in [1, 2]$。
4. 求解一元方程：寻找 一个 $\tau \in [1, 2]$，使得 $\|\mathbf{s}(\tau)\| = \Delta_k$。这是一个关于 $\tau$ 的一元二次方程，可以直接解析求解。解出的 $\mathbf{s}(\tau)$ 就是本次迭代的试探步长 $\mathbf{s}_k$。

Dogleg方法的美妙之处在于，它巧妙地结合了最速下降法的稳定性和牛顿法的快速收敛性，同时严格遵守了信赖域的约束，计算成本很低。

5. 整合：完整的信赖域牛顿法流程

将以上策略整合，得到一个鲁棒的优化算法流程：

1. 初始化：选择 初始点 $\mathbf{x}_0$，初始信赖域半径 $\Delta_0 > 0$（例如 1.0），容差 tol。
2. 迭代开始：计算 当前点的梯度 $\mathbf{g}_k$。检查 收敛条件，例如 $\|\mathbf{g}_k\| < \text{tol}$，如果满足则停止。
3. 修正Hessian：计算 Hessian $\mathbf{H}_k$，并执行 第2节中的修正步骤，得到正定矩阵 $\mathbf{B}_k$。
4. 求解信赖域子问题：采用 Dogleg方法（第4节）求解带约束的子问题，得到试探步长 $\mathbf{s}_k$。
5. 评估与更新：计算 比值 $\rho_k$。根据 $\rho_k$ 的大小，决定 是否接受步长，并更新 信赖域半径 $\Delta_{k+1}$ 和迭代点 $\mathbf{x}_{k+1}$。
6. 循环：返回 步骤2继续下一次迭代。