信赖域方法

信赖域（TR）方法提供了一种与依赖线搜索的优化方法不同的策略。虽然许多优化技术，例如牛顿法和拟牛顿法（如BFGS和L-BFGS），通常先找到一个搜索方向（通常基于Hessian矩阵的近似值$B_k$），然后进行线搜索以找到沿该方向的合适步长，但TR方法则采用不同的策略。它们在当前迭代点$x_k$周围划定一个范围，在这个范围内，它们认为二次模型$m_k(p)$能够很好地近似真实目标函数$f(x_k + p)$。然后，它们通过在这个受信任的范围内最小化这个模型来找到候选步长$p_k$。

回顾之前介绍的二次模型：

$$m_k(p) = f(x_k) + \nabla f(x_k)^T p + \frac{1}{2} p^T B_k p$$

这里，$B_k$通常是精确的Hessian矩阵$\nabla^2 f(x_k)$，或者是BFGS或L-BFGS维护的拟牛顿近似。

信赖域子问题

在每次迭代$k$中，信赖域方法的核心是解决以下信赖域子问题：

$$\min_{p \in \mathbb{R}^n} m_k(p) \quad \text{受限于} \quad ||p|| \le \Delta_k$$

范围$||p|| \le \Delta_k$是信赖域，其中$\Delta_k > 0$是信赖域半径，范数$|| \cdot ||$通常是欧几里得（L2）范数。这个子问题寻求一个步长$p$，它能使模型$m_k$最小化，同时保持在距离当前点$x_k$的$\Delta_k$范围内。

可以把$\Delta_k$看作步长的预算。如果无约束地最小化$m_k$所建议的完整步长（牛顿或拟牛顿步长）落在预算之内，我们可能会采纳它。如果落在预算之外，约束$||p|| \le \Delta_k$将变为有效，并且最优解$p_k$将位于信赖域的边界上。

精确求解这个带约束的二次最小化问题可能很复杂。然而，实际的信赖域算法通常采用高效的方法来找到一个近似解$p_k$。常用的方法包括：

1. 狗腿法（Dogleg Method）： 当$B_k$是正定矩阵时尤其适用。它巧妙地在最速下降方向和牛顿方向之间找到一条路径（“狗腿”），并与信赖域边界相交。
2. Steihaug-Toint 共轭梯度法： 应用共轭梯度算法来近似最小化二次模型$m_k(p)$，但如果CG生成的迭代点超出信赖域边界，则终止进程。即使当$B_k$不是正定矩阵时，这种方法也表现良好。

子问题求解器的选择会影响信赖域方法的整体效率和适用性。

调整信赖域半径

信赖域方法的一个重要特点是半径$\Delta_k$的自适应调整。这种调整是根据目标函数$f$中实际获得的下降量与模型$m_k$预测的下降量进行比较。

我们计算比率$\rho_k$：

$$\rho_k = \frac{\text{实际下降}}{\text{预测下降}} = \frac{f(x_k) - f(x_k + p_k)}{m_k(0) - m_k(p_k)}$$

注意，$m_k(0) = f(x_k)$，所以分母代表了二次模型在迈出步长$p_k$时预测的下降量。

$\rho_k$的值表示我们的二次模型在当前信赖域内表现如何：

• 非常好的吻合（$\rho_k$大，例如，$\rho_k > 0.75$）： 模型准确。我们可以更进一步。接受该步长（$x_{k+1} = x_k + p_k$），并增加下一次迭代的信赖域半径（例如，$\Delta_{k+1} = \max(\Delta_k, 2 ||p_k||)$ 或 $\Delta_{k+1} = 2 \Delta_k$）。
• 合理吻合（$\rho_k$适中，例如，$0.1 < \rho_k \le 0.75$）： 模型有一定准确性。接受该步长（$x_{k+1} = x_k + p_k$），但要小心。保持信赖域半径不变或略微减小（$\Delta_{k+1} = \Delta_k$）。
• 吻合度差（$\rho_k$小或为负，例如，$\rho_k \le 0.1$）： 模型在这个范围内预测不佳，可能是因为步长过大或曲率变化迅速。拒绝该步长（$x_{k+1} = x_k$），并大幅缩小信赖域（$\Delta_{k+1} = 0.5 \Delta_k$ 或类似）。算法随后将在迭代$k$中用较小的$\Delta_{k+1}$再次解决子问题。

这种反馈机制使得信赖域方法能够根据损失函数 (loss function)的局部几何形状自动调整步长。

根据吻合度比率$\rho_k$来更新信赖域半径$\Delta$并接受/拒绝步长$p_k$的主要逻辑。

优点与考量

信赖域方法具有以下几个优点：

• 稳定性： 它们比标准线搜索方法更能从容应对不定Hessian矩阵（牛顿法可能在这种情况下失效或走向鞍点/最大值）。信赖域约束本身就能限制步长，避免发散。
• 强大的收敛理论： 它们拥有可靠的理论收敛保证，即使对于非凸问题，也常能证明收敛到满足二阶必要条件的点。
• 无需线搜索： 步长由信赖域半径$\Delta_k$隐式控制，无需单独的线搜索过程。

然而，也存在一些需要考量的地方：

• 子问题成本： 在每次迭代中求解或精确近似信赖域子问题的解，其计算量可能比L-BFGS等方法中的简单方向计算和线搜索更大。
• 参数 (parameter)调整： $\rho_k$的具体阈值以及用于增加/减少$\Delta_k$的系数是超参数 (hyperparameter)，可能需要调整以获得最佳性能。

在机器学习 (machine learning)中的相关性

在大规模深度学习 (deep learning)中，传统的信赖域方法较少用于直接的端到端训练，与自适应一阶方法（如Adam）或L-BFGS相比。这主要是因为Hessian信息（即使是近似的）及其在处理数百万参数 (parameter)的子问题上的成本较高。

然而，了解信赖域方法仍有以下几方面的重要性：

• 它们提供了一个使用曲率信息控制步长的不同视角。
• 受信赖域原理启发的方法，例如限制步长范数或使用模型吻合度检查，也出现在其他高级优化场景中。
• 无Hessian优化方法有时会融入信赖域的思想，以帮助涉及的线性系统求解更稳定。
• 它们通常对小规模机器学习问题或大型算法中对稳定性要求很高的特定子问题表现良好。

信赖域方法是一类精密的优化算法，通过细致地控制模型近似被认为准确的范围，它们提供了强大的理论特性和实际的稳定性。尽管它们今天可能不是训练大型神经网络 (neural network)的首选，但其核心原理能够增进我们对数值优化的认识。