信赖域方法
信赖域方法是一类用于求解非线性优化问题的数值算法，特别适用于目标函数或约束条件为复杂非线性的情形。其核心思想是：在每次迭代中，在当前迭代点附近的一个小区域（即“信赖域”）内，用一个简单的模型（通常是二次模型）来近似原始复杂函数，然后在这个信赖域内求解该近似模型的极小值点，从而得到候选迭代点。通过比较候选点处实际函数的下降量与近似模型的预测下降量，来决定是否接受该候选点，并动态调整信赖域的大小。
- 基本思想与动机
在优化问题中，我们常常需要最小化一个非线性函数 \(f(x)\)。如果 \(f(x)\) 非常复杂（例如，高度非线性、计算代价高昂），直接在其整个定义域上寻找极小值点会非常困难。信赖域方法的策略是“局部近似，逐步推进”。它在当前点 \(x_k\) 周围定义一个可信赖的区域（信赖域）\(\Delta_k\)，通常是一个球域 \(\{ x : \|x - x_k\| \le \Delta_k \}\)。在这个有限的区域内，我们用一个更简单的函数 \(m_k(s)\)（其中 \(s = x - x_k\) 是位移）来近似 \(f(x_k + s)\)。这个近似模型 \(m_k(s)\) 通常取为二次函数：
\[ m_k(s) = f(x_k) + \nabla f(x_k)^T s + \frac{1}{2} s^T B_k s \]
其中，\(B_k\) 是Hessian矩阵 \(\nabla^2 f(x_k)\) 或其某个近似。然后，我们在信赖域约束 \(\|s\| \le \Delta_k\) 下求解子问题：
\[ \min_{s} m_k(s) \quad \text{subject to} \quad \|s\| \le \Delta_k \]
得到位移 \(s_k\)。这个子问题是一个带约束的二次规划问题，有高效的数值解法。
- 算法框架与关键步骤
信赖域方法的一个标准迭代框架包含以下核心步骤：
a. 模型构建：在当前迭代点 \(x_k\)，构建局部二次近似模型 \(m_k(s)\)。
b. 子问题求解：在信赖域 \(\|s\| \le \Delta_k\) 内，求解 \(\min m_k(s)\) 得到试探步 \(s_k\)。
c. 实际下降与预测下降的比较：计算实际函数下降量 \(\text{ared}_k = f(x_k) - f(x_k + s_k)\) 和模型预测下降量 \(\text{pred}_k = m_k(0) - m_k(s_k)\)。
d. 比率计算与迭代更新：计算比率 \(\rho_k = \frac{\text{ared}_k}{\text{pred}_k}\)。这个比率衡量了近似模型在当前信赖域内的准确程度。
- 如果 \(\rho_k\) 接近1（例如，大于某个阈值 \(\eta_1 > 0\)），说明模型预测很准确，我们接受该步长，令 \(x_{k+1} = x_k + s_k\)。
- 如果 \(\rho_k\) 很小甚至是负值，说明模型预测很差，我们拒绝该步长，保持 \(x_{k+1} = x_k\)。
e. 信赖域半径调整：根据比率 \(\rho_k\) 动态调整信赖域半径 \(\Delta_k\) 为 \(\Delta_{k+1}\)。 - 如果 \(\rho_k\) 很大（例如，大于另一个阈值 \(\eta_2\)），说明模型在更大的区域内可能仍然准确，可以尝试增大信赖域半径 \(\Delta_{k+1} > \Delta_k\)。
- 如果 \(\rho_k\) 很小，说明当前信赖域过大，模型已经不准确，需要缩小信赖域半径 \(\Delta_{k+1} < \Delta_k\)。
- 否则，保持信赖域半径基本不变。
-
子问题求解技术
求解信赖域子问题 \(\min_{\|s\| \le \Delta} m_k(s)\) 是算法的核心计算步骤。主要有两种思路：
a. 精确求解法（柯西点与狗腿法）：对于中小规模问题，可以高效地求得子问题的全局解或高质量近似解。著名的“狗腿法”适用于当 \(B_k\) 正定时，它通过结合最速下降方向（柯西点）和牛顿方向，找到一条折衷路径，并在这条路径上寻找满足约束的最优解。当 \(B_k\) 不定时，需要更复杂的策略，如求解一个带参数的特征值问题。
b. 共轭梯度法（截断CG法）：对于大规模问题，精确求解子问题计算量过大。通常采用截断的共轭梯度法来近似求解。该方法从最速下降方向开始，进行共轭梯度迭代。一旦迭代点触及信赖域边界，或者产生了负曲率方向，就停止迭代。这种方法计算效率高，且能产生满足全局收敛要求的解。 -
收敛性分析与实际应用
在适当的正则性条件下（例如，函数 \(f\) 连续可微且有下界，近似Hessian矩阵 \(B_k\) 一致有界），信赖域方法具有强健的全局收敛性，即算法产生的序列至少有一个聚点是稳定点（梯度为零的点）。与线搜索方法（如最速下降法、牛顿法）相比，信赖域方法在处理高度非线性、非凸函数或病态Hessian矩阵时通常更为稳定可靠，因为它通过信赖域半径直接控制了步长，避免了可能使迭代发散的大步长。因此，信赖域方法被广泛应用于科学计算、工程优化、机器学习等领域的复杂非线性优化问题中。