- 高斯牛顿法
- 算法步骤
- 讨论
高斯牛顿法
高斯牛顿法的思想是将
f
(
x
)
f(x)
f(x)进行一阶的泰勒展开：
f
(
x
+
Δ
x
)
≈
f
(
x
)
+
J
(
x
)
T
Δ
x
f(x+Delta x)approx f(x)+J(x)^TDelta x
f(x+Δx)≈f(x)+J(x)TΔx
当前目标是寻找增量
Δ
x
Delta x
Δx，使得
∣
∣
f
(
x
+
Δ
x
)
∣
∣
2
||f(x+Delta x)||^2
∣∣f(x+Δx)∣∣2达到最小。为了求
Δ
x
Delta x
Δx，我们需要解一个线性的最小二乘问题：
Δ
x
∗
=
arg
min
Δ
x
1
2
∥
f
(
x
)
+
J
(
x
)
T
Δ
x
∥
2
Delta x^*=arg min_{Delta x}frac{1}{2}lVert f(x)+J(x)^TDelta xrVert ^2
Δx∗=argΔxmin21∥f(x)+J(x)TΔx∥2
对上述目标函数对
Δ
x
Delta x
Δx求导，并令其导数为零：
J
(
x
)
f
(
x
)
+
J
(
x
)
J
(
x
)
T
Δ
x
=
0
J(x)f(x)+J(x)J(x)^TDelta x=0
J(x)f(x)+J(x)J(x)TΔx=0
可以得到如下方程组：
J
(
x
)
J
(
x
)
T
⏟
H
(
x
)
Δ
x
=
−
J
(
x
)
f
(
x
)
⏟
g
(
x
)
underbrace{J(x)J(x)^T}_{H(x)}Delta x=underbrace{-J(x)f(x)}_{g(x)}
H(x)
J(x)J(x)TΔx=g(x)
−J(x)f(x)
该方程式关于变量
Δ
x
Delta x
Δx的线性方程组，称为增量方程，也可以称为高斯牛顿方程或者正规方程。将上式左边系数定义为
H
H
H，右边定义为
g
g
g，则上式变为：
H
Δ
x
=
g
HDelta x=g
HΔx=g
此处对比牛顿法可见，高丝牛顿法用
J
J
T
JJ^T
JJT作为牛顿法中二阶
H
e
s
s
i
a
n
Hessian
Hessian矩阵的近似，从而省略了计算
H
H
H的过程。
- 给定初始值 x 0 。 x_0。 x0。
- 对于第k次迭代，求出当前的雅克比矩阵 J ( x k ) J(x_k) J(xk)和误差 f ( x k ) f(x_k) f(xk)。
- 求解增量方程： H Δ x k = g HDelta x_k=g HΔxk=g。
- 若 Δ x k Delta x_k Δxk足够小，则停止。否则，令 x k + 1 = x k + Δ x k x_{k+1}=x_k+Delta x_k xk+1=xk+Δxk，返回第 2 2 2步。
为了求解增量方程，需要求解 H − 1 H^{-1} H−1，因此要求 H H H为正定矩阵。但实际过程中可能出现 J J T JJ^T JJT为奇异矩阵或者病态的情况，此时增量的稳定性较差，导致算法不收敛。
