非线性最小二乘问题数值方法
字数 5492 2025-12-13 04:31:39

好的。我注意到“非线性最小二乘问题数值方法”已被讲过，但其下的一个具体且非常重要的子类“非线性最小二乘问题的信赖域方法”已独立列出。因此，我将围绕这个更具体、更具算法深度的主题，为您进行细致讲解。

非线性最小二乘问题的信赖域方法

我将带您逐步理解这个方法，这是一个专门针对非线性最小二乘问题设计的高效、稳健的数值优化算法。

步骤 1：问题回顾与动机

我们首先明确要解决的问题。非线性最小二乘问题的标准形式是：

\[\min_{x \in \mathbb{R}^n} f(x) = \frac{1}{2} \sum_{i=1}^{m} r_i^2 (x) = \frac{1}{2} \| r(x) \|_2^2 \]

其中，\(r(x) = [r_1(x), \ldots, r_m(x)]^T\) 是一个非线性残差向量函数，\(m \geq n\)。目标函数 \(f(x)\) 是这些残差的平方和的一半（系数 \(\frac{1}{2}\) 是为了后续求导形式简洁）。

为什么需要专门的方法？
普通优化方法（如拟牛顿法）直接处理 \(f(x)\)。但非线性最小二乘问题的目标函数具有特殊的和式结构，其梯度和海森矩阵有特定的形式，可以被有效利用：

  • 梯度： \(g(x) = \nabla f(x) = J(x)^T r(x)\)，其中 \(J(x)\) 是残差函数 \(r(x)\) 的 \(m \times n\) 雅可比矩阵（\(J_{ij} = \partial r_i / \partial x_j\)）。
  • 海森矩阵： \(H(x) = \nabla^2 f(x) = J(x)^T J(x) + \sum_{i=1}^m r_i(x) \nabla^2 r_i(x)\)。

注意，海森矩阵由两部分组成：第一部分 \(J^T J\) 是已知的（一旦计算出雅可比），并且总是半正定的；第二项（包含残差的二阶导数）在最优解附近（当 \(r_i\) 很小）或其影响可忽略时，常常被省略。利用这种特殊结构，可以设计出比通用算法更高效的专用算法。

信赖域方法就是一种能稳健利用此结构的主流框架。

步骤 2：信赖域方法的核心思想

信赖域方法的基本哲学是：在每次迭代中，在一个受信任的局部区域（“信赖域”）内，用一个简单的模型函数来近似复杂的原始目标函数。

  1. 模型函数：在当前迭代点 \(x_k\)，我们用一个二次模型 \(m_k(p)\) 来近似目标函数在位移 \(p\) 处的增量 \(f(x_k + p) - f(x_k)\)。
  2. 信赖域：我们只信任这个模型在以 \(x_k\) 为中心、半径为 \(\Delta_k > 0\) 的某个球域内是准确的。这个球域就是信赖域： \(\| p \| \le \Delta_k\)。
  3. 子问题：在信赖域内寻找使模型函数下降最多的位移 \(p_k\)：

\[ \min_{p \in \mathbb{R}^n} m_k(p) \quad \text{s.t.} \quad \| p \| \le \Delta_k. \]

  1. 接受性与半径调整：计算真实的函数下降量 \(f(x_k) - f(x_k + p_k)\) 与模型预测的下降量 \(m_k(0) - m_k(p_k)\) 的比值 \(\rho_k\)。这个比值衡量了模型的预测精度。
  • 若 \(\rho_k\) 接近1，说明模型很好，接受这一步 \(x_{k+1} = x_k + p_k\)，并可能扩大信赖域半径 \(\Delta_{k+1} > \Delta_k\)。
  • 若 \(\rho_k\) 很小甚至为负，说明模型很差，拒绝这一步 \(x_{k+1} = x_k\)，并缩小信赖域半径 \(\Delta_{k+1} < \Delta_k\)。
  • 若 \(\rho_k\) 在可接受的中间范围，则接受这一步，但保持或微调半径。

这种机制使得算法能自适应地调整步长，在远离解、模型不准确时采取保守的小步探索，在接近解、模型准确时快速大步收敛，兼具了全局收敛性和局部快速收敛性。

步骤 3：针对非线性最小二乘的模型构造

对于非线性最小二乘问题，我们利用其梯度 \(g_k = J_k^T r_k\) 和海森矩阵的结构来构造模型。最常用的两种模型是：

  1. 高斯-牛顿模型：
    这是最核心的模型。它直接忽略海森矩阵中的第二项（包含二阶导数的项），使用：

\[ m_k^{GN}(p) = f_k + g_k^T p + \frac{1}{2} p^T (J_k^T J_k) p \]

这个模型本质上是将非线性函数 \(r(x_k + p)\) 在当前点进行一阶泰勒展开 \(r(x_k + p) \approx r_k + J_k p\)，然后代入 \(f(x) = \frac{1}{2}\|r(x)\|^2\) 得到的。它的优势在于：\(J_k^T J_k\) 是已知且半正定的，构造它只需要一阶导数（雅可比矩阵），计算成本低。在残差较小或问题接近线性时，此模型非常精确。

  1. 带海森近似的模型（如Levenberg-Marquardt的变体）：
    当高斯-牛顿模型不准确（例如，残差 \(r_k\) 很大，二阶项不可忽略）时，可以在模型中加入对二阶项 \(S(x) = \sum r_i \nabla^2 r_i\) 的近似。一种常见做法是使用对称秩1（SR1）或BFGS等拟牛顿法来近似完整的海森矩阵 \(H_k \approx J_k^T J_k + B_k\)：

\[ m_k^Q(p) = f_k + g_k^T p + \frac{1}{2} p^T (J_k^T J_k + B_k) p \]

这种模型更精确，但需要维护和更新矩阵 \(B_k\)，增加了计算和存储开销。

在标准实现中（如经典的Levenberg-Marquardt算法，它就是信赖域方法的一个特例），通常优先使用高斯-牛顿模型。

步骤 4：信赖域子问题的求解

我们现在需要求解子问题：

\[\min_{p} m_k(p) = f_k + g_k^T p + \frac{1}{2} p^T H_k p \quad \text{s.t.} \quad \| p \| \le \Delta_k. \]

其中 \(H_k = J_k^T J_k\) （高斯-牛顿模型）或更一般的近似。求解此子问题是信赖域方法的关键计算步骤。

  1. 直观理解：
  • 如果无约束最小值点 \(p_k^B\) （即解方程 \(H_k p = -g_k\) ）位于信赖域内部（\(\| p_k^B \| \le \Delta_k\)），那么它就是子问题的最优解 \(p_k^* = p_k^B\)。
  • 否则，最优解必定落在信赖域的边界上（\(\| p_k^* \| = \Delta_k\)），此时约束是起作用的。
  1. 数学解（起作用约束情况）：
    当约束起作用时，根据优化理论的最优性条件（KKT条件），存在一个拉格朗日乘子 \(\lambda \ge 0\)，使得最优解 \(p^*\) 满足：

\[ (H_k + \lambda I) p^* = -g_k, \quad \lambda (\Delta_k - \| p^* \|) = 0, \quad \| p^* \| \le \Delta_k. \]

并且矩阵 \((H_k + \lambda I)\) 需要是半正定的。这个方程告诉我们，最优步长等价于求解一个带正则化参数 \(\lambda\) 的正则化正规方程。

  1. 求解算法：
    核心是找到正确的 \(\lambda \ge 0\)，使得 \(\| p(\lambda) \| = \Delta_k\)，其中 \(p(\lambda) = -(H_k + \lambda I)^{-1} g_k\)。
  • 对于高斯-牛顿模型，\(H_k = J_k^T J_k\)，这可以通过求解增广系统或利用矩阵分解（如Cholesky分解 \(J_k^T J_k + \lambda I = L L^T\) ）来实现。
  • 更高效、数值稳定的方法是利用正交分解。对雅可比矩阵进行QR分解：\(J_k = Q \begin{bmatrix} R \\ 0 \end{bmatrix}\)，可以将问题转化为求解一个上三角系统，并利用折线（dogleg）路径等启发式方法高效地找到满足边界条件的 \(\lambda\) 和 \(p\)。

Levenberg-Marquardt方法就是上述过程的一个具体实现，其中参数 \(\lambda\) （在LM中常记作 \(\mu\) ）的动态调整机制，本质上就是信赖域半径 \(\Delta_k\) 的调整机制。

步骤 5：算法流程与优势总结

将以上步骤整合，一个标准的非线性最小二乘信赖域算法流程如下：

  1. 初始化：给定初始点 \(x_0\)，初始信赖域半径 \(\Delta_0 > 0\)，参数 \(\eta \in (0,1)\) （用于判断接受步长的阈值），以及半径缩放常数 \(\gamma_1 < 1 < \gamma_2\)。
  2. 对于 k = 0, 1, 2, ... 直到收敛：
    a. 计算函数信息：计算残差 \(r(x_k)\)、目标函数值 \(f(x_k)\)、雅可比矩阵 \(J(x_k)\) 和梯度 \(g_k = J_k^T r_k\)。
    b. 构造模型：形成二次模型 \(m_k(p)\) （通常用高斯-牛顿模型）。
    c. 求解子问题：在约束 \(\| p \| \le \Delta_k\) 下，求模型 \(m_k(p)\) 的近似极小点 \(p_k\)。
    d. 评估步长：
  • 计算实际下降量： \(\text{ared}_k = f(x_k) - f(x_k + p_k)\)。
  • 计算预测下降量： \(\text{pred}_k = m_k(0) - m_k(p_k)\)。
  • 计算比值： \(\rho_k = \text{ared}_k / \text{pred}_k\)。
    e. 更新迭代点和信赖域半径：
  • 若 \(\rho_k > \eta\)：接受步长，令 \(x_{k+1} = x_k + p_k\)。
  • 否则：拒绝步长，令 \(x_{k+1} = x_k\)。
  • 根据 \(\rho_k\) 调整 \(\Delta_{k+1}\)：
  • 若 \(\rho_k < 0.25\): \(\Delta_{k+1} = \gamma_1 \Delta_k\) （大幅缩小）。
  • 若 \(\rho_k > 0.75\) 且步长碰到了边界： \(\Delta_{k+1} = \gamma_2 \Delta_k\) （扩大）。
  • 否则： \(\Delta_{k+1} = \Delta_k\) （保持）。

优势总结：

  • 全局收敛：得益于信赖域机制，即使从远离解的点开始，算法也能稳定地向局部极小点前进。
  • 结构利用：高斯-牛顿模型充分利用了最小二乘的一阶信息，计算高效。
  • 稳健性：自动处理病态雅可比矩阵（通过 \(\lambda I\) 正则化），对初始点不敏感。
  • 超线性收敛：在最优解附近，若二阶项可忽略，高斯-牛顿步长恢复为牛顿步长，具有局部二次收敛速度。

步骤 6：与其他方法的联系与扩展

  • 与线搜索方法的比较：线搜索方法（如高斯-牛顿法结合线搜索）是先确定方向（如高斯-牛顿方向），再沿此方向搜索步长。而信赖域方法是先确定一个最大步长范围（半径），再在这个范围内找最优方向和步长的组合。信赖域方法在理论上通常更强健。
  • Levenberg-Marquardt算法：是最著名的非线性最小二乘法，它就是基于高斯-牛顿模型和信赖域思想（或等价的正则化思想）的算法。参数 \(\mu\) 扮演了 \(\lambda\) 的角色，其调整策略对应于信赖域半径的调整。
  • 狗腿法（Dogleg Method）：是求解高斯-牛顿信赖域子问题的一种高效近似算法。它通过连接最速下降方向和高斯-牛顿方向，形成一条折线路径，并直接在这条路径上寻找与信赖域边界的交点，避免了对 \(\lambda\) 的迭代求解，计算更简便。

通过以上循序渐进的讲解，您应该能够理解非线性最小二乘问题的信赖域方法如何通过结合问题的特殊结构、在局部信赖域内求解模型子问题，并通过反馈机制自适应调整信任范围，从而成为一个强大且实用的数值优化工具。

好的。我注意到“ 非线性最小二乘问题数值方法 ”已被讲过，但其下的一个具体且非常重要的子类“ 非线性最小二乘问题的信赖域方法 ”已独立列出。因此，我将围绕这个更具体、更具算法深度的主题，为您进行细致讲解。 非线性最小二乘问题的信赖域方法 我将带您逐步理解这个方法，这是一个专门针对非线性最小二乘问题设计的高效、稳健的数值优化算法。 步骤 1：问题回顾与动机 我们首先明确要解决的问题。 非线性最小二乘问题 的标准形式是： \[ \min_ {x \in \mathbb{R}^n} f(x) = \frac{1}{2} \sum_ {i=1}^{m} r_ i^2 (x) = \frac{1}{2} \| r(x) \|_ 2^2 \] 其中，\( r(x) = [ r_ 1(x), \ldots, r_ m(x) ]^T \) 是一个非线性残差向量函数，\( m \geq n \)。目标函数 \( f(x) \) 是这些残差的平方和的一半（系数 \( \frac{1}{2} \) 是为了后续求导形式简洁）。 为什么需要专门的方法？ 普通优化方法（如拟牛顿法）直接处理 \( f(x) \)。但非线性最小二乘问题的目标函数具有特殊的和式结构，其梯度和海森矩阵有特定的形式，可以被有效利用： 梯度 ： \( g(x) = \nabla f(x) = J(x)^T r(x) \)，其中 \( J(x) \) 是残差函数 \( r(x) \) 的 \( m \times n \) 雅可比矩阵（\( J_ {ij} = \partial r_ i / \partial x_ j \)）。 海森矩阵 ： \( H(x) = \nabla^2 f(x) = J(x)^T J(x) + \sum_ {i=1}^m r_ i(x) \nabla^2 r_ i(x) \)。 注意，海森矩阵由两部分组成： 第一部分 \( J^T J \) 是已知的（一旦计算出雅可比），并且总是半正定的； 第二项 （包含残差的二阶导数）在最优解附近（当 \( r_ i \) 很小）或其影响可忽略时，常常被省略。利用这种特殊结构，可以设计出比通用算法更高效的专用算法。 信赖域方法 就是一种能稳健利用此结构的主流框架。 步骤 2：信赖域方法的核心思想 信赖域方法的基本哲学是： 在每次迭代中，在一个受信任的局部区域（“信赖域”）内，用一个简单的模型函数来近似复杂的原始目标函数。 模型函数 ：在当前迭代点 \( x_ k \)，我们用一个二次模型 \( m_ k(p) \) 来近似目标函数在位移 \( p \) 处的增量 \( f(x_ k + p) - f(x_ k) \)。 信赖域 ：我们只信任这个模型在以 \( x_ k \) 为中心、半径为 \( \Delta_ k > 0 \) 的某个球域内是准确的。这个球域就是信赖域： \( \| p \| \le \Delta_ k \)。 子问题 ：在信赖域内寻找使模型函数下降最多的位移 \( p_ k \)： \[ \min_ {p \in \mathbb{R}^n} m_ k(p) \quad \text{s.t.} \quad \| p \| \le \Delta_ k. \] 接受性与半径调整 ：计算真实的函数下降量 \( f(x_ k) - f(x_ k + p_ k) \) 与模型预测的下降量 \( m_ k(0) - m_ k(p_ k) \) 的比值 \( \rho_ k \)。这个比值衡量了模型的预测精度。 若 \( \rho_ k \) 接近1，说明模型很好，接受这一步 \( x_ {k+1} = x_ k + p_ k \)，并可能扩大信赖域半径 \( \Delta_ {k+1} > \Delta_ k \)。 若 \( \rho_ k \) 很小甚至为负，说明模型很差，拒绝这一步 \( x_ {k+1} = x_ k \)，并缩小信赖域半径 \( \Delta_ {k+1} < \Delta_ k \)。 若 \( \rho_ k \) 在可接受的中间范围，则接受这一步，但保持或微调半径。 这种机制使得算法能自适应地调整步长，在远离解、模型不准确时采取保守的小步探索，在接近解、模型准确时快速大步收敛， 兼具了全局收敛性和局部快速收敛性 。 步骤 3：针对非线性最小二乘的模型构造 对于非线性最小二乘问题，我们利用其梯度 \( g_ k = J_ k^T r_ k \) 和海森矩阵的结构来构造模型。最常用的两种模型是： 高斯-牛顿模型 ： 这是最核心的模型。它直接忽略海森矩阵中的第二项（包含二阶导数的项），使用： \[ m_ k^{GN}(p) = f_ k + g_ k^T p + \frac{1}{2} p^T (J_ k^T J_ k) p \] 这个模型本质上是将非线性函数 \( r(x_ k + p) \) 在当前点进行一阶泰勒展开 \( r(x_ k + p) \approx r_ k + J_ k p \)，然后代入 \( f(x) = \frac{1}{2}\|r(x)\|^2 \) 得到的。 它的优势在于 ：\( J_ k^T J_ k \) 是已知且半正定的，构造它只需要一阶导数（雅可比矩阵），计算成本低。在残差较小或问题接近线性时，此模型非常精确。 带海森近似的模型（如Levenberg-Marquardt的变体） ： 当高斯-牛顿模型不准确（例如，残差 \( r_ k \) 很大，二阶项不可忽略）时，可以在模型中加入对二阶项 \( S(x) = \sum r_ i \nabla^2 r_ i \) 的近似。一种常见做法是使用对称秩1（SR1）或BFGS等拟牛顿法来近似完整的海森矩阵 \( H_ k \approx J_ k^T J_ k + B_ k \)： \[ m_ k^Q(p) = f_ k + g_ k^T p + \frac{1}{2} p^T (J_ k^T J_ k + B_ k) p \] 这种模型更精确，但需要维护和更新矩阵 \( B_ k \)，增加了计算和存储开销。 在标准实现中（如经典的Levenberg-Marquardt算法，它就是信赖域方法的一个特例），通常优先使用 高斯-牛顿模型 。 步骤 4：信赖域子问题的求解 我们现在需要求解子问题： \[ \min_ {p} m_ k(p) = f_ k + g_ k^T p + \frac{1}{2} p^T H_ k p \quad \text{s.t.} \quad \| p \| \le \Delta_ k. \] 其中 \( H_ k = J_ k^T J_ k \) （高斯-牛顿模型）或更一般的近似。求解此子问题是信赖域方法的关键计算步骤。 直观理解 ： 如果无约束最小值点 \( p_ k^B \) （即解方程 \( H_ k p = -g_ k \) ）位于信赖域内部（\( \| p_ k^B \| \le \Delta_ k \)），那么它就是子问题的最优解 \( p_ k^* = p_ k^B \)。 否则，最优解必定落在信赖域的边界上（\( \| p_ k^* \| = \Delta_ k \)），此时约束是 起作用 的。 数学解（起作用约束情况） ： 当约束起作用时，根据优化理论的最优性条件（KKT条件），存在一个拉格朗日乘子 \( \lambda \ge 0 \)，使得最优解 \( p^* \) 满足： \[ (H_ k + \lambda I) p^* = -g_ k, \quad \lambda (\Delta_ k - \| p^* \|) = 0, \quad \| p^* \| \le \Delta_ k. \] 并且矩阵 \( (H_ k + \lambda I) \) 需要是半正定的。这个方程告诉我们， 最优步长等价于求解一个带正则化参数 \( \lambda \) 的正则化正规方程 。 求解算法 ： 核心是找到正确的 \( \lambda \ge 0 \)，使得 \( \| p(\lambda) \| = \Delta_ k \)，其中 \( p(\lambda) = -(H_ k + \lambda I)^{-1} g_ k \)。 对于高斯-牛顿模型，\( H_ k = J_ k^T J_ k \)，这可以通过求解增广系统或利用矩阵分解（如Cholesky分解 \( J_ k^T J_ k + \lambda I = L L^T \) ）来实现。 更高效、数值稳定的方法是利用 正交分解 。对雅可比矩阵进行QR分解：\( J_ k = Q \begin{bmatrix} R \\ 0 \end{bmatrix} \)，可以将问题转化为求解一个上三角系统，并利用折线（dogleg）路径等启发式方法高效地找到满足边界条件的 \( \lambda \) 和 \( p \)。 Levenberg-Marquardt方法 就是上述过程的一个具体实现，其中参数 \( \lambda \) （在LM中常记作 \( \mu \) ）的动态调整机制，本质上就是信赖域半径 \( \Delta_ k \) 的调整机制。 步骤 5：算法流程与优势总结 将以上步骤整合，一个标准的非线性最小二乘信赖域算法流程如下： 初始化 ：给定初始点 \( x_ 0 \)，初始信赖域半径 \( \Delta_ 0 > 0 \)，参数 \( \eta \in (0,1) \) （用于判断接受步长的阈值），以及半径缩放常数 \( \gamma_ 1 < 1 < \gamma_ 2 \)。 对于 k = 0, 1, 2, ... 直到收敛 ： a. 计算函数信息 ：计算残差 \( r(x_ k) \)、目标函数值 \( f(x_ k) \)、雅可比矩阵 \( J(x_ k) \) 和梯度 \( g_ k = J_ k^T r_ k \)。 b. 构造模型 ：形成二次模型 \( m_ k(p) \) （通常用高斯-牛顿模型）。 c. 求解子问题 ：在约束 \( \| p \| \le \Delta_ k \) 下，求模型 \( m_ k(p) \) 的近似极小点 \( p_ k \)。 d. 评估步长 ： - 计算实际下降量： \( \text{ared} k = f(x_ k) - f(x_ k + p_ k) \)。 - 计算预测下降量： \( \text{pred} k = m_ k(0) - m_ k(p_ k) \)。 - 计算比值： \( \rho_ k = \text{ared} k / \text{pred} k \)。 e. 更新迭代点和信赖域半径 ： - 若 \( \rho_ k > \eta \)：接受步长，令 \( x {k+1} = x_ k + p_ k \)。 - 否则：拒绝步长，令 \( x {k+1} = x_ k \)。 - 根据 \( \rho_ k \) 调整 \( \Delta {k+1} \)： * 若 \( \rho_ k < 0.25 \): \( \Delta {k+1} = \gamma_ 1 \Delta_ k \) （大幅缩小）。 * 若 \( \rho_ k > 0.75 \) 且步长碰到了边界： \( \Delta_ {k+1} = \gamma_ 2 \Delta_ k \) （扩大）。 * 否则： \( \Delta_ {k+1} = \Delta_ k \) （保持）。 优势总结 ： 全局收敛 ：得益于信赖域机制，即使从远离解的点开始，算法也能稳定地向局部极小点前进。 结构利用 ：高斯-牛顿模型充分利用了最小二乘的一阶信息，计算高效。 稳健性 ：自动处理病态雅可比矩阵（通过 \( \lambda I \) 正则化），对初始点不敏感。 超线性收敛 ：在最优解附近，若二阶项可忽略，高斯-牛顿步长恢复为牛顿步长，具有局部二次收敛速度。 步骤 6：与其他方法的联系与扩展 与线搜索方法的比较 ：线搜索方法（如高斯-牛顿法结合线搜索）是先确定方向（如高斯-牛顿方向），再沿此方向搜索步长。而信赖域方法是先确定一个最大步长范围（半径），再在这个范围内找最优方向和步长的组合。信赖域方法在理论上通常更强健。 Levenberg-Marquardt算法 ：是最著名的非线性最小二乘法，它就是基于高斯-牛顿模型和信赖域思想（或等价的正则化思想）的算法。参数 \( \mu \) 扮演了 \( \lambda \) 的角色，其调整策略对应于信赖域半径的调整。 狗腿法（Dogleg Method） ：是求解高斯-牛顿信赖域子问题的一种高效近似算法。它通过连接最速下降方向和高斯-牛顿方向，形成一条折线路径，并直接在这条路径上寻找与信赖域边界的交点，避免了对 \( \lambda \) 的迭代求解，计算更简便。 通过以上循序渐进的讲解，您应该能够理解 非线性最小二乘问题的信赖域方法 如何通过结合问题的特殊结构、在局部信赖域内求解模型子问题，并通过反馈机制自适应调整信任范围，从而成为一个强大且实用的数值优化工具。