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

字数 3622 2025-12-13 00:10:58

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

我们开始讲解非线性最小二乘问题的信赖域方法。这是一个在科学计算和工程优化中非常重要的数值算法。我们将从背景概念开始，逐步深入到该方法的核心思想和具体步骤。

背景：非线性最小二乘问题
- 什么是最小二乘问题？ 简单来说，就是寻找一组参数，使得模型预测值与实际观测值之间误差的平方和最小。这是数据拟合、参数估计等领域的基础问题。

线性 vs 非线性：如果模型关于待求参数是线性的（例如，用直线 $y=ax+b$ 拟合数据），就是线性最小二乘问题，有直接的解析解（如正规方程）或稳定的数值解（如QR分解）。但如果模型关于参数是非线性的（例如，指数衰减模型 $y = a e^{bx}$），就变成了非线性最小二乘问题。这时，问题通常没有解析解，必须依赖迭代数值算法。

通用迭代框架与挑战
- 求解非线性最小二乘问题的迭代算法，其核心思想是：从一个初始猜测解出发，在每一步迭代中，根据当前点的一些局部信息（如函数值和导数），构造一个局部近似模型，然后在这个近似模型上求出一个“建议的移动步” 。用这个“建议步”更新当前解，希望得到更优的解，如此反复直到收敛。
- 这里的关键挑战在于：如何构造一个既简单（便于求解）又足够精确（能反映原问题在局部特征）的近似模型？以及，如何判断和利用这个“建议步”？
核心思想：信赖域（Trust Region）

基本概念：信赖域方法的灵感非常直观。它承认，我们每一步构造的近似模型（通常是二次模型）只在当前迭代点 $\mathbf{x}_k$ 的一个有限邻域内是可信的（即能较好地近似原目标函数）。这个有限邻域就称为“信赖域”。
如何体现？ 信赖域通常定义为一个以当前点为中心、半径为 $\Delta_k$ 的球（或范数球）：$||\mathbf{d}|| \le \Delta_k$，其中 $\mathbf{d}$ 是我们打算移动的步长。
- 算法逻辑：

构建子问题：在当前点 $\mathbf{x}_k$ 处，利用目标函数 $f(\mathbf{x})$ 的泰勒展开（常用二阶展开），构造一个近似的二次模型 $m_k(\mathbf{d})$。然后，我们不去全局地最小化这个模型，而是在信赖域 $||\mathbf{d}|| \le \Delta_k$ 这个约束下，寻找能使模型 $m_k(\mathbf{d})$ 最小化的步长 $\mathbf{d}_k$。这个带约束的子问题通常比无约束的模型更容易控制，且其解必然落在我们“信任”的区域内。
评估与调整：计算出试探步 $\mathbf{d}_k$ 后，我们用真实目标函数在 $\mathbf{x}_k + \mathbf{d}_k$ 处的下降量，与近似模型预测的下降量进行比较。这个比值 $\rho_k$ 是决定是否接受这一步以及如何调整信赖域半径 $\Delta_k$ 的关键。

如果 $\rho_k$ 接近1，说明模型预测很准，这一步很好，可以接受，并且在下一次迭代可以尝试扩大信赖域半径，以允许更大幅度的移动，加速收敛。
如果 $\rho_k$ 是小的正数，说明实际下降不如预测，但仍有下降，可以接受这一步，但保持或缩小信赖域半径，因为模型在那个范围的准确性有限。
如果 $\rho_k$ 是零或负数，说明实际目标函数没有下降（甚至上升），这一步很差，拒绝这一步（即 $\mathbf{x}_{k+1} = \mathbf{x}_k$），并显著缩小信赖域半径，然后在更小的可信区域内重新求解子问题。

在非线性最小二乘问题中的特殊形式

非线性最小二乘问题的目标函数具有特殊形式：$f(\mathbf{x}) = \frac{1}{2} \sum_{i=1}^{m} r_i(\mathbf{x})^2 = \frac{1}{2} ||\mathbf{r}(\mathbf{x})||_2^2$，其中 $\mathbf{r}(\mathbf{x})$ 是残差向量。
这种特殊形式使得其二阶导数（Hessian矩阵） 具有特殊结构，可以被残差的雅可比矩阵（Jacobian） $\mathbf{J}(\mathbf{x})$ 很好地近似。具体来说，$f(\mathbf{x})$ 的梯度和近似的Hessian矩阵为：
梯度：$\nabla f(\mathbf{x}) = \mathbf{J}(\mathbf{x})^T \mathbf{r}(\mathbf{x})$
近似Hessian：$\nabla^2 f(\mathbf{x}) \approx \mathbf{J}(\mathbf{x})^T \mathbf{J}(\mathbf{x}) + \mathbf{S}(\mathbf{x})$，其中 $\mathbf{S}(\mathbf{x})$ 包含残差 $r_i(\mathbf{x})$ 的二阶导数信息。在高斯-牛顿近似中，我们忽略 $\mathbf{S}(\mathbf{x})$，因为它通常较小（特别是当残差 $r_i$ 很小，或问题接近线性时）。
- 因此，在每一步迭代，我们构造的信赖域子问题具体为：
  在约束 $||\mathbf{d}|| \le \Delta_k$ 下，最小化二次模型：

\[ m_k(\mathbf{d}) = f(\mathbf{x}_k) + \mathbf{d}^T \mathbf{J}_k^T \mathbf{r}_k + \frac{1}{2} \mathbf{d}^T (\mathbf{J}_k^T \mathbf{J}_k) \mathbf{d} \]

其中 $\mathbf{J}_k = \mathbf{J}(\mathbf{x}_k)$， $\mathbf{r}_k = \mathbf{r}(\mathbf{x}_k)$。这个模型被称为高斯-牛顿模型。如果残差较大或非线性很强，有时会在模型中加上 $\mathbf{S}(\mathbf{x})$ 的近似项，这时模型接近完整的二阶模型。

求解信赖域子问题

求解带球约束的二次优化子问题是信赖域方法的核心计算步骤。这通常通过求解一个“折中”方程来完成。其解 $\mathbf{d}_k$ 满足以下最优性条件：

\[ (\mathbf{J}_k^T \mathbf{J}_k + \lambda \mathbf{I}) \mathbf{d}_k = -\mathbf{J}_k^T \mathbf{r}_k \]

其中 $\lambda \ge 0$ 是一个拉格朗日乘子，$\mathbf{I}$ 是单位矩阵。并且， $\lambda$ 和 $\mathbf{d}_k$ 的关系满足互补条件：要么 $\lambda = 0$ 且 $||\mathbf{d}_k|| < \Delta_k$ （此时子问题解在信赖域内部，等价于无约束高斯-牛顿步）；要么 $\lambda > 0$ 且 $||\mathbf{d}_k|| = \Delta_k$ （此时解落在信赖域边界上）。

从几何和代数上看，增加 $\lambda \mathbf{I}$ 这一项相当于给近似的Hessian矩阵 $\mathbf{J}_k^T \mathbf{J}_k$ 加上了一个正则化项。当 $\lambda$ 很大时，方程的解 $\mathbf{d}_k$ 会趋向于最速下降方向（步长很小）；当 $\lambda = 0$ 时，就是标准的高斯-牛顿方向。算法通过调整 $\lambda$ 的值，来精确地找到那个满足 $||\mathbf{d}|| = \Delta_k$ （或落在域内）的最优解。

算法优势与总结

鲁棒性强：相比于线搜索类方法（如最速下降法、非线性共轭梯度法），信赖域方法通过显式地限制步长范围，能更稳定地处理病态（$\mathbf{J}_k^T \mathbf{J}_k$ 接近奇异）或非凸的问题。即使模型在远处不准确，算法也能通过收缩信赖域来保证稳定性。
- 收敛性好：在合理的假设下，信赖域方法具有全局收敛性（即从任意初始点出发都能收敛到稳定点）和局部超线性收敛速度（在解附近收敛很快）。
- 应用广泛：它是求解非线性最小二乘问题（如MATLAB中的 lsqnonlin 函数）和更一般无约束优化问题的标准算法之一，是连接优化理论与高效数值计算的重要桥梁。

总而言之，非线性最小二乘问题的信赖域方法巧妙地结合了局部模型近似、区域信赖管理和子问题高效求解，为我们提供了一条稳定、可靠地寻找复杂非线性模型最佳拟合参数的数值路径。

非线性最小二乘问题的信赖域方法我们开始讲解非线性最小二乘问题的信赖域方法。这是一个在科学计算和工程优化中非常重要的数值算法。我们将从背景概念开始，逐步深入到该方法的核心思想和具体步骤。背景：非线性最小二乘问题什么是最小二乘问题？简单来说，就是寻找一组参数，使得模型预测值与实际观测值之间误差的平方和最小。这是数据拟合、参数估计等领域的基础问题。线性 vs 非线性：如果模型关于待求参数是线性的（例如，用直线 $y=ax+b$ 拟合数据），就是线性最小二乘问题，有直接的解析解（如正规方程）或稳定的数值解（如QR分解）。但如果模型关于参数是非线性的（例如，指数衰减模型 $y = a e^{bx}$），就变成了非线性最小二乘问题。这时，问题通常没有解析解，必须依赖迭代数值算法。通用迭代框架与挑战求解非线性最小二乘问题的迭代算法，其核心思想是：从一个初始猜测解出发，在每一步迭代中，根据当前点的一些局部信息（如函数值和导数），构造一个局部近似模型，然后在这个近似模型上求出一个“建议的移动步” 。用这个“建议步”更新当前解，希望得到更优的解，如此反复直到收敛。这里的关键挑战在于：如何构造一个既简单（便于求解）又足够精确（能反映原问题在局部特征）的近似模型？以及，如何判断和利用这个“建议步”？核心思想：信赖域（Trust Region）基本概念：信赖域方法的灵感非常直观。它承认，我们每一步构造的近似模型（通常是二次模型）只在当前迭代点 $\mathbf{x}_ k$ 的一个有限邻域内是可信的（即能较好地近似原目标函数）。这个有限邻域就称为“信赖域”。如何体现？信赖域通常定义为一个以当前点为中心、半径为 $\Delta_ k$ 的球（或范数球）：$||\mathbf{d}|| \le \Delta_ k$，其中 $\mathbf{d}$ 是我们打算移动的步长。算法逻辑：构建子问题：在当前点 $\mathbf{x}_ k$ 处，利用目标函数 $f(\mathbf{x})$ 的泰勒展开（常用二阶展开），构造一个近似的二次模型 $m_ k(\mathbf{d})$。然后，我们不去全局地最小化这个模型，而是在信赖域 $||\mathbf{d}|| \le \Delta_ k$ 这个约束下，寻找能使模型 $m_ k(\mathbf{d})$ 最小化的步长 $\mathbf{d}_ k$ 。这个带约束的子问题通常比无约束的模型更容易控制，且其解必然落在我们“信任”的区域内。评估与调整：计算出试探步 $\mathbf{d}_ k$ 后，我们用真实目标函数在 $\mathbf{x}_ k + \mathbf{d}_ k$ 处的下降量，与近似模型预测的下降量进行比较。这个比值 $\rho_ k$ 是决定是否接受这一步以及如何调整信赖域半径 $\Delta_ k$ 的关键。如果 $\rho_ k$ 接近1，说明模型预测很准，这一步很好，可以接受，并且在下一次迭代可以尝试扩大信赖域半径，以允许更大幅度的移动，加速收敛。如果 $\rho_ k$ 是小的正数，说明实际下降不如预测，但仍有下降，可以接受这一步，但保持或缩小信赖域半径，因为模型在那个范围的准确性有限。如果 $\rho_ k$ 是零或负数，说明实际目标函数没有下降（甚至上升），这一步很差，拒绝这一步（即 $\mathbf{x}_ {k+1} = \mathbf{x}_ k$），并显著缩小信赖域半径，然后在更小的可信区域内重新求解子问题。在非线性最小二乘问题中的特殊形式非线性最小二乘问题的目标函数具有特殊形式：$f(\mathbf{x}) = \frac{1}{2} \sum_ {i=1}^{m} r_ i(\mathbf{x})^2 = \frac{1}{2} ||\mathbf{r}(\mathbf{x})||_ 2^2$，其中 $\mathbf{r}(\mathbf{x})$ 是残差向量。这种特殊形式使得其二阶导数（Hessian矩阵）具有特殊结构，可以被残差的雅可比矩阵（Jacobian） $\mathbf{J}(\mathbf{x})$ 很好地近似。具体来说，$f(\mathbf{x})$ 的梯度和近似的Hessian矩阵为：梯度：$\nabla f(\mathbf{x}) = \mathbf{J}(\mathbf{x})^T \mathbf{r}(\mathbf{x})$ 近似Hessian：$\nabla^2 f(\mathbf{x}) \approx \mathbf{J}(\mathbf{x})^T \mathbf{J}(\mathbf{x}) + \mathbf{S}(\mathbf{x})$，其中 $\mathbf{S}(\mathbf{x})$ 包含残差 $r_ i(\mathbf{x})$ 的二阶导数信息。在高斯-牛顿近似中，我们忽略 $\mathbf{S}(\mathbf{x})$，因为它通常较小（特别是当残差 $r_ i$ 很小，或问题接近线性时）。因此，在每一步迭代，我们构造的信赖域子问题具体为：在约束 $||\mathbf{d}|| \le \Delta_ k$ 下，最小化二次模型： $$ m_ k(\mathbf{d}) = f(\mathbf{x}_ k) + \mathbf{d}^T \mathbf{J}_ k^T \mathbf{r}_ k + \frac{1}{2} \mathbf{d}^T (\mathbf{J}_ k^T \mathbf{J}_ k) \mathbf{d} $$ 其中 $\mathbf{J}_ k = \mathbf{J}(\mathbf{x}_ k)$， $\mathbf{r}_ k = \mathbf{r}(\mathbf{x}_ k)$。这个模型被称为高斯-牛顿模型。如果残差较大或非线性很强，有时会在模型中加上 $\mathbf{S}(\mathbf{x})$ 的近似项，这时模型接近完整的二阶模型。求解信赖域子问题求解带球约束的二次优化子问题是信赖域方法的核心计算步骤。这通常通过求解一个“折中”方程来完成。其解 $\mathbf{d}_ k$ 满足以下最优性条件： $$ (\mathbf{J}_ k^T \mathbf{J}_ k + \lambda \mathbf{I}) \mathbf{d}_ k = -\mathbf{J}_ k^T \mathbf{r}_ k $$ 其中 $\lambda \ge 0$ 是一个拉格朗日乘子，$\mathbf{I}$ 是单位矩阵。并且， $\lambda$ 和 $\mathbf{d}_ k$ 的关系满足互补条件：要么 $\lambda = 0$ 且 $||\mathbf{d}_ k|| < \Delta_ k$ （此时子问题解在信赖域内部，等价于无约束高斯-牛顿步）；要么 $\lambda > 0$ 且 $||\mathbf{d}_ k|| = \Delta_ k$ （此时解落在信赖域边界上）。从几何和代数上看，增加 $\lambda \mathbf{I}$ 这一项相当于给近似的Hessian矩阵 $\mathbf{J}_ k^T \mathbf{J}_ k$ 加上了一个正则化项。当 $\lambda$ 很大时，方程的解 $\mathbf{d}_ k$ 会趋向于最速下降方向（步长很小）；当 $\lambda = 0$ 时，就是标准的高斯-牛顿方向。算法通过调整 $\lambda$ 的值，来精确地找到那个满足 $||\mathbf{d}|| = \Delta_ k$ （或落在域内）的最优解。算法优势与总结鲁棒性强：相比于线搜索类方法（如最速下降法、非线性共轭梯度法），信赖域方法通过显式地限制步长范围，能更稳定地处理病态（$\mathbf{J}_ k^T \mathbf{J}_ k$ 接近奇异）或非凸的问题。即使模型在远处不准确，算法也能通过收缩信赖域来保证稳定性。收敛性好：在合理的假设下，信赖域方法具有全局收敛性（即从任意初始点出发都能收敛到稳定点）和局部超线性收敛速度（在解附近收敛很快）。应用广泛：它是求解非线性最小二乘问题（如MATLAB中的 lsqnonlin 函数）和更一般无约束优化问题的标准算法之一，是连接优化理论与高效数值计算的重要桥梁。总而言之，非线性最小二乘问题的信赖域方法巧妙地结合了局部模型近似、区域信赖管理和子问题高效求解，为我们提供了一条稳定、可靠地寻找复杂非线性模型最佳拟合参数的数值路径。