高斯—牛顿算法是数学优化中用于最小化残差平方和的一种迭代方法。它利用非线性最小二乘法问题的结构,在当前参数估计处将残差函数线性化,再求解所得的最小二乘法问题。与完整的二阶方法不同,它不需要残差的二阶导数。当解附近的残差较小,且残差的导数能够提供足够的信息来确定参数时,该算法尤其有效。
问题表述
设 x∈Rn 为未知参数向量,并令
r(x)=[r1(x)⋯rm(x)]T
为由可微残差函数组成的向量。优化目标为
x∈RnminF(x),F(x)=21∥r(x)∥22=21i=1∑mri(x)2.
因子 1/2 可以简化导数的表达式,而不改变极小点。一个常见的应用是将模型 f(t;x) 拟合到观测数据 (ti,yi),此时
ri(x)=f(ti;x)−yi.
将所有残差的符号取反,所得目标函数不变;只要导数的定义与残差符号保持一致,参数更新也相同。
通常 m≥n,即残差的数量不少于未知参数的数量。标准步要有唯一解,就要求残差的雅可比矩阵
J(x)ij=∂xj∂ri(x)
具有满列秩。
推导
残差的线性化
在当前迭代点 xk 处,用残差向量的一阶展开进行近似:
r(xk+p)≈r(xk)+J(xk)p.
记 rk=r(xk)、Jk=J(xk),则高斯—牛顿步由以下问题确定:
pk∈pargmin21∥rk+Jkp∥22.
这一线性最小二乘问题的正规方程为
JkTJkpk=−JkTrk.
基本迭代随后采用完整步:
xk+1=xk+pk.
虽然形式上可以用 JkTJk 的逆矩阵表示该步,但实际实现通常求解线性方程组或最小二乘问题,而不是显式构造这个逆矩阵。
与牛顿法的关系
对于二阶可微的残差,F 的梯度和海森矩阵分别为
∇F(x)=J(x)Tr(x)
和
∇2F(x)=J(x)TJ(x)+i=1∑mri(x)∇2ri(x).
牛顿法使用完整的海森矩阵计算迭代步。高斯—牛顿算法则采用近似
∇2F(x)≈J(x)TJ(x),
舍去以残差为权重的二阶导数项。
这一近似有两点优势:
- 只需要残差及其一阶导数。
- 近似海森矩阵是半正定的,且当 J(x) 具有满列秩时,它是正定矩阵。
当残差加权的二阶导数项较小时,这一近似最为准确。这可能是因为残差较小、残差函数接近线性,或各项曲率贡献相互抵消。
基本流程
标准实现包含以下步骤:
- 选择初始参数向量 x0。
- 计算 rk 和 Jk。
- 求解线性最小二乘子问题,得到 pk。
- 令 xk+1=xk+pk,或采用带保护措施的步。
- 重复上述过程,直到满足停止条件。
常见的停止准则考察梯度范数
∥JkTrk∥,
步长相对于 xk 尺度的大小,或目标函数的变化量。
这些准则检测的是不同现象。梯度较小表明近似满足一阶驻点条件;步长较小则也可能是尺度选取不当或数值困难所致。因此,实际实现通常会结合多种准则,并设置迭代次数或函数求值次数的上限。
残差的导数可以通过解析方法、自动微分或有限差分近似计算。导数误差可能显著影响收敛,尤其是在解附近。
迭代步的数值求解
正规方程与条件性
如果 Jk 具有满列秩,正规方程就有唯一解。然而,显式构造 JkTJk 可能降低数值稳定性。在欧几里得范数下,
κ2(JkTJk)=κ2(Jk)2,
其中 κ2 为谱条件数。
因此,即使雅可比矩阵只是中度病态,正规方程组也可能严重得多。对于稀疏问题,构造这一乘积还可能增加存储需求。
QR分解无需构造正规方程即可求解线性最小二乘问题,是稠密问题的常用选择。奇异值分解能够提供有关参数方向之间近似相关性的更多信息,并可在雅可比矩阵秩亏时给出最小范数步。
秩亏与尺度调整
当 Jk 不具有满列秩时,可能有多个步都能使线性化目标达到最小。最小范数解是一种可选方案,但它本身无法弥补模型参数信息的不足。
尺度调整也很重要。参数的单位或数量级差异很大时,线性化问题可能难以精确求解,步长判据也可能受到干扰。残差加权与参数尺度调整的作用不同:加权改变了对各项偏差的重视程度,而可逆的重新参数化可以改善数值表现,同时不改变原本的拟合问题。
收敛性与局限
局部收敛
高斯—牛顿算法主要是一种局部方法:其收敛性取决于初始估计,以及残差函数在解附近的性质。
设 x∗ 为驻点,即
J(x∗)Tr(x∗)=0.
若 J(x∗) 具有满列秩,定义
S∗=i=1∑mri(x∗)∇2ri(x∗).
在适当的光滑性条件下,完整步迭代映射在 x∗ 处的导数为
−(J(x∗)TJ(x∗))−1S∗.
这一表达式解释了该方法的典型表现:
- **零残差解:**若 r(x∗)=0,则 S∗=0。如果雅可比矩阵局部满足利普希茨条件,且在解处具有满列秩,那么从足够接近解的初始估计出发,可获得局部二次收敛。
- **非零残差解:**当迭代映射局部具有压缩性时,通常呈线性收敛。较小的残差往往能提高收敛速度,但评估残差是否足够小时,必须结合雅可比矩阵的条件性和残差曲率来判断。
- **曲率贡献较大:**如果被舍去项的影响过大,即使在驻点附近,完整步迭代也可能不收敛。
残差为零是被舍去项消失的充分条件,但不是必要条件。
下降方向并不保证完整步有效
当 Jk 具有满列秩且梯度非零时,
∇F(xk)Tpk=−pkTJkTJkpk=−∥Jkpk∥22<0.
因此,高斯—牛顿方向是一个下降方向。
然而,完整更新 xk+pk 仍可能使目标函数增大,因为对于较大的步,线性化残差模型可能不够准确。下降方向只能保证在正步长足够小时目标函数下降,并不一定保证单位步长有效。
其他局限还包括对初值敏感、可能收敛到非全局最优的驻点、雅可比矩阵可能奇异,以及平方误差目标对异常观测值敏感。
带保护措施的变体
阻尼高斯—牛顿法
阻尼迭代采用
xk+1=xk+αkpk,0<αk≤1.
通过线搜索选择 αk,使目标函数充分下降。当完整步过大时,这种方法可以提高稳健性。
列文伯格—马尔夸特算法
列文伯格—马尔夸特算法将迭代步方程修改为
(JkTJk+λkDkTDk)pk=−JkTrk,
其中 λk≥0 为阻尼参数,Dk 为尺度矩阵。
阻尼较小时,该步接近高斯—牛顿步。当 Dk=I 且阻尼较大时,它趋近于按比例缩放的负梯度步。在雅可比矩阵秩亏时,适当的阻尼还可使线性方程组的系数矩阵非奇异。
信赖域方法
信赖域方法将迭代步限制在认为线性化残差模型可靠的区域内:
pmin21∥rk+Jkp∥22subject to∥Dkp∥2≤Δk.
通过比较目标函数的实际下降量与预测下降量来调整半径 Δk。列文伯格—马尔夸特算法与这一形式密切相关。
应当区分自适应阻尼与对原始估计问题的正则化。阻尼项用于控制优化步;而在目标函数中持续存在的惩罚项会改变所求解的问题。
示例:指数模型拟合
考虑观测数据 (ti,yi) 和模型
f(ti;a,b)=aebti.
令 x=(a,b)T,则残差为
ri(a,b)=aebti−yi,
雅可比矩阵的第 i 行为
Ji(a,b)=[ebtiatiebti].
每次迭代时,算法求解
Δa,Δbmini=1∑m[aebti−yi+ebtiΔa+atiebtiΔb]2
并更新 a 和 b。
由于 b 出现在指数中,原始问题是非线性的,但每一步都是关于 Δa 和 Δb 的线性最小二乘问题。如果 a=0,雅可比矩阵中与 b 对应的列就会变为零,这说明当前参数估计可能导致秩亏。
对于所有参数都以线性形式出现的模型,线性化是精确的。如果设计矩阵具有满列秩,那么从任意初始点出发,只需一个完整的高斯—牛顿步即可到达最小二乘解。
加权最小二乘与统计解释
对于固定的对称正定权重矩阵 W,目标函数变为
F(x)=21r(x)TWr(x).
相应的迭代步满足
JkTWJkpk=−JkTWrk.
如果 W=LTL,这就相当于对变换后的残差向量 Lr(x) 应用普通高斯—牛顿算法。
在具有加性高斯误差的统计模型中,如果协方差矩阵 Σ 已知且不依赖于参数,那么取 W=Σ−1,就能使加权最小二乘与均值参数的最大似然估计等价。
在参数可被充分辨识的解附近,若满足适当的正则性条件和线性化假设,矩阵
(JTΣ−1J)−1
也可作为参数估计协方差的局部近似。这一解释并不自动适用于任意残差函数或误差模型设定错误的情况。如果误差协方差依赖于参数,似然通常会包含额外的项,而不再只是一个权重固定的最小二乘目标。
应用与历史背景
高斯—牛顿算法广泛用于非线性回归、科学模型拟合、校准和逆问题。大规模版本会利用雅可比矩阵的稀疏性,或在不存储整个矩阵的情况下计算雅可比矩阵与向量的乘积。
该方法以卡尔·弗里德里希·高斯和艾萨克·牛顿的名字命名。其核心构造将与高斯相关的最小二乘原理同牛顿型局部迭代相结合,用由残差一阶导数构成的矩阵替代目标函数的精确海森矩阵。