aiwiki.page
中文
数学 / 应用与计算数学 / gauss-newton-algorithm

高斯—牛顿算法

高斯—牛顿算法通过反复线性化残差并求解所得的线性最小二乘问题,求解非线性最小二乘问题。

22 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
数学优化最小二乘法雅可比矩阵梯度海森矩阵牛顿法正定矩阵自动微分高斯—牛顿…

高斯—牛顿算法是数学优化中用于最小化残差平方和的一种迭代方法。它利用非线性最小二乘法问题的结构,在当前参数估计处将残差函数线性化,再求解所得的最小二乘法问题。与完整的二阶方法不同,它不需要残差的二阶导数。当解附近的残差较小,且残差的导数能够提供足够的信息来确定参数时,该算法尤其有效。

问题表述

设 x∈Rnx\in\mathbb{R}^n 为未知参数向量,并令

r(x)=[r1(x)⋯rm(x)]Tr(x)= \begin{bmatrix} r_1(x)&\cdots&r_m(x) \end{bmatrix}^{\mathsf T}

为由可微残差函数组成的向量。优化目标为

min⁡x∈RnF(x),F(x)=12∥r(x)∥22=12∑i=1mri(x)2.\min_{x\in\mathbb{R}^n} F(x), \qquad F(x)=\frac12\|r(x)\|_2^2 =\frac12\sum_{i=1}^{m}r_i(x)^2.

因子 1/21/2 可以简化导数的表达式,而不改变极小点。一个常见的应用是将模型 f(t;x)f(t;x) 拟合到观测数据 (ti,yi)(t_i,y_i),此时

ri(x)=f(ti;x)−yi.r_i(x)=f(t_i;x)-y_i.

将所有残差的符号取反,所得目标函数不变;只要导数的定义与残差符号保持一致,参数更新也相同。

通常 m≥nm\geq n,即残差的数量不少于未知参数的数量。标准步要有唯一解,就要求残差的雅可比矩阵

J(x)ij=∂ri(x)∂xjJ(x)_{ij}=\frac{\partial r_i(x)}{\partial x_j}

具有满列秩。

推导

残差的线性化

在当前迭代点 xkx_k 处,用残差向量的一阶展开进行近似:

r(xk+p)≈r(xk)+J(xk)p.r(x_k+p)\approx r(x_k)+J(x_k)p.

记 rk=r(xk)r_k=r(x_k)、Jk=J(xk)J_k=J(x_k),则高斯—牛顿步由以下问题确定:

pk∈arg min⁡p12∥rk+Jkp∥22.p_k\in\operatorname*{arg\,min}_{p} \frac12\|r_k+J_kp\|_2^2.

这一线性最小二乘问题的正规方程为

JkTJkpk=−JkTrk.J_k^{\mathsf T}J_kp_k=-J_k^{\mathsf T}r_k.

基本迭代随后采用完整步:

xk+1=xk+pk.x_{k+1}=x_k+p_k.

虽然形式上可以用 JkTJkJ_k^{\mathsf T}J_k 的逆矩阵表示该步,但实际实现通常求解线性方程组或最小二乘问题,而不是显式构造这个逆矩阵。

与牛顿法的关系

对于二阶可微的残差,FF 的梯度和海森矩阵分别为

∇F(x)=J(x)Tr(x)\nabla F(x)=J(x)^{\mathsf T}r(x)

和

∇2F(x)=J(x)TJ(x)+∑i=1mri(x)∇2ri(x).\nabla^2F(x) = J(x)^{\mathsf T}J(x) + \sum_{i=1}^{m}r_i(x)\nabla^2r_i(x).

牛顿法使用完整的海森矩阵计算迭代步。高斯—牛顿算法则采用近似

∇2F(x)≈J(x)TJ(x),\nabla^2F(x)\approx J(x)^{\mathsf T}J(x),

舍去以残差为权重的二阶导数项。

这一近似有两点优势:

  • 只需要残差及其一阶导数。
  • 近似海森矩阵是半正定的,且当 J(x)J(x) 具有满列秩时,它是正定矩阵。

当残差加权的二阶导数项较小时,这一近似最为准确。这可能是因为残差较小、残差函数接近线性,或各项曲率贡献相互抵消。

基本流程

标准实现包含以下步骤:

  1. 选择初始参数向量 x0x_0。
  2. 计算 rkr_k 和 JkJ_k。
  3. 求解线性最小二乘子问题,得到 pkp_k。
  4. 令 xk+1=xk+pkx_{k+1}=x_k+p_k,或采用带保护措施的步。
  5. 重复上述过程,直到满足停止条件。

常见的停止准则考察梯度范数

∥JkTrk∥,\|J_k^{\mathsf T}r_k\|,

步长相对于 xkx_k 尺度的大小,或目标函数的变化量。

这些准则检测的是不同现象。梯度较小表明近似满足一阶驻点条件;步长较小则也可能是尺度选取不当或数值困难所致。因此,实际实现通常会结合多种准则,并设置迭代次数或函数求值次数的上限。

残差的导数可以通过解析方法、自动微分或有限差分近似计算。导数误差可能显著影响收敛,尤其是在解附近。

迭代步的数值求解

正规方程与条件性

如果 JkJ_k 具有满列秩,正规方程就有唯一解。然而,显式构造 JkTJkJ_k^{\mathsf T}J_k 可能降低数值稳定性。在欧几里得范数下,

κ2(JkTJk)=κ2(Jk)2,\kappa_2(J_k^{\mathsf T}J_k)=\kappa_2(J_k)^2,

其中 κ2\kappa_2 为谱条件数。

因此,即使雅可比矩阵只是中度病态,正规方程组也可能严重得多。对于稀疏问题,构造这一乘积还可能增加存储需求。

QR分解无需构造正规方程即可求解线性最小二乘问题,是稠密问题的常用选择。奇异值分解能够提供有关参数方向之间近似相关性的更多信息,并可在雅可比矩阵秩亏时给出最小范数步。

秩亏与尺度调整

当 JkJ_k 不具有满列秩时,可能有多个步都能使线性化目标达到最小。最小范数解是一种可选方案,但它本身无法弥补模型参数信息的不足。

尺度调整也很重要。参数的单位或数量级差异很大时,线性化问题可能难以精确求解,步长判据也可能受到干扰。残差加权与参数尺度调整的作用不同:加权改变了对各项偏差的重视程度,而可逆的重新参数化可以改善数值表现,同时不改变原本的拟合问题。

收敛性与局限

局部收敛

高斯—牛顿算法主要是一种局部方法:其收敛性取决于初始估计,以及残差函数在解附近的性质。

设 x∗x_* 为驻点,即

J(x∗)Tr(x∗)=0.J(x_*)^{\mathsf T}r(x_*)=0.

若 J(x∗)J(x_*) 具有满列秩,定义

S∗=∑i=1mri(x∗)∇2ri(x∗).S_*=\sum_{i=1}^{m}r_i(x_*)\nabla^2r_i(x_*).

在适当的光滑性条件下,完整步迭代映射在 x∗x_* 处的导数为

−(J(x∗)TJ(x∗))−1S∗.-\bigl(J(x_*)^{\mathsf T}J(x_*)\bigr)^{-1}S_*.

这一表达式解释了该方法的典型表现:

  • **零残差解:**若 r(x∗)=0r(x_*)=0,则 S∗=0S_*=0。如果雅可比矩阵局部满足利普希茨条件,且在解处具有满列秩,那么从足够接近解的初始估计出发,可获得局部二次收敛。
  • **非零残差解:**当迭代映射局部具有压缩性时,通常呈线性收敛。较小的残差往往能提高收敛速度,但评估残差是否足够小时,必须结合雅可比矩阵的条件性和残差曲率来判断。
  • **曲率贡献较大:**如果被舍去项的影响过大,即使在驻点附近,完整步迭代也可能不收敛。

残差为零是被舍去项消失的充分条件,但不是必要条件。

下降方向并不保证完整步有效

当 JkJ_k 具有满列秩且梯度非零时,

∇F(xk)Tpk=−pkTJkTJkpk=−∥Jkpk∥22<0.\nabla F(x_k)^{\mathsf T}p_k = -p_k^{\mathsf T}J_k^{\mathsf T}J_kp_k = -\|J_kp_k\|_2^2<0.

因此,高斯—牛顿方向是一个下降方向。

然而,完整更新 xk+pkx_k+p_k 仍可能使目标函数增大,因为对于较大的步,线性化残差模型可能不够准确。下降方向只能保证在正步长足够小时目标函数下降,并不一定保证单位步长有效。

其他局限还包括对初值敏感、可能收敛到非全局最优的驻点、雅可比矩阵可能奇异,以及平方误差目标对异常观测值敏感。

带保护措施的变体

阻尼高斯—牛顿法

阻尼迭代采用

xk+1=xk+αkpk,0<αk≤1.x_{k+1}=x_k+\alpha_kp_k, \qquad 0<\alpha_k\leq1.

通过线搜索选择 αk\alpha_k,使目标函数充分下降。当完整步过大时,这种方法可以提高稳健性。

列文伯格—马尔夸特算法

列文伯格—马尔夸特算法将迭代步方程修改为

(JkTJk+λkDkTDk)pk=−JkTrk,\bigl(J_k^{\mathsf T}J_k+\lambda_kD_k^{\mathsf T}D_k\bigr)p_k = -J_k^{\mathsf T}r_k,

其中 λk≥0\lambda_k\geq0 为阻尼参数,DkD_k 为尺度矩阵。

阻尼较小时,该步接近高斯—牛顿步。当 Dk=ID_k=I 且阻尼较大时,它趋近于按比例缩放的负梯度步。在雅可比矩阵秩亏时,适当的阻尼还可使线性方程组的系数矩阵非奇异。

信赖域方法

信赖域方法将迭代步限制在认为线性化残差模型可靠的区域内:

min⁡p12∥rk+Jkp∥22subject to∥Dkp∥2≤Δk.\min_p \frac12\|r_k+J_kp\|_2^2 \quad\text{subject to}\quad \|D_kp\|_2\leq\Delta_k.

通过比较目标函数的实际下降量与预测下降量来调整半径 Δk\Delta_k。列文伯格—马尔夸特算法与这一形式密切相关。

应当区分自适应阻尼与对原始估计问题的正则化。阻尼项用于控制优化步;而在目标函数中持续存在的惩罚项会改变所求解的问题。

示例:指数模型拟合

考虑观测数据 (ti,yi)(t_i,y_i) 和模型

f(ti;a,b)=aebti.f(t_i;a,b)=ae^{bt_i}.

令 x=(a,b)Tx=(a,b)^{\mathsf T},则残差为

ri(a,b)=aebti−yi,r_i(a,b)=ae^{bt_i}-y_i,

雅可比矩阵的第 ii 行为

Ji(a,b)=[ebtiatiebti].J_i(a,b)= \begin{bmatrix} e^{bt_i}&at_i e^{bt_i} \end{bmatrix}.

每次迭代时,算法求解

min⁡Δa,Δb∑i=1m[aebti−yi+ebtiΔa+atiebtiΔb]2\min_{\Delta a,\Delta b} \sum_{i=1}^{m} \left[ ae^{bt_i}-y_i +e^{bt_i}\Delta a +at_i e^{bt_i}\Delta b \right]^2

并更新 aa 和 bb。

由于 bb 出现在指数中,原始问题是非线性的,但每一步都是关于 Δa\Delta a 和 Δb\Delta b 的线性最小二乘问题。如果 a=0a=0,雅可比矩阵中与 bb 对应的列就会变为零,这说明当前参数估计可能导致秩亏。

对于所有参数都以线性形式出现的模型,线性化是精确的。如果设计矩阵具有满列秩,那么从任意初始点出发,只需一个完整的高斯—牛顿步即可到达最小二乘解。

加权最小二乘与统计解释

对于固定的对称正定权重矩阵 WW,目标函数变为

F(x)=12r(x)TWr(x).F(x)=\frac12r(x)^{\mathsf T}Wr(x).

相应的迭代步满足

JkTWJkpk=−JkTWrk.J_k^{\mathsf T}WJ_kp_k=-J_k^{\mathsf T}Wr_k.

如果 W=LTLW=L^{\mathsf T}L,这就相当于对变换后的残差向量 Lr(x)Lr(x) 应用普通高斯—牛顿算法。

在具有加性高斯误差的统计模型中,如果协方差矩阵 Σ\Sigma 已知且不依赖于参数,那么取 W=Σ−1W=\Sigma^{-1},就能使加权最小二乘与均值参数的最大似然估计等价。

在参数可被充分辨识的解附近,若满足适当的正则性条件和线性化假设,矩阵

(JTΣ−1J)−1\bigl(J^{\mathsf T}\Sigma^{-1}J\bigr)^{-1}

也可作为参数估计协方差的局部近似。这一解释并不自动适用于任意残差函数或误差模型设定错误的情况。如果误差协方差依赖于参数,似然通常会包含额外的项,而不再只是一个权重固定的最小二乘目标。

应用与历史背景

高斯—牛顿算法广泛用于非线性回归、科学模型拟合、校准和逆问题。大规模版本会利用雅可比矩阵的稀疏性,或在不存储整个矩阵的情况下计算雅可比矩阵与向量的乘积。

该方法以卡尔·弗里德里希·高斯和艾萨克·牛顿的名字命名。其核心构造将与高斯相关的最小二乘原理同牛顿型局部迭代相结合,用由残差一阶导数构成的矩阵替代目标函数的精确海森矩阵。