拟牛顿法
拟牛顿法
基本思路：
为了避免
F
(
x
(
k
)
)
−
1
F(x^{(k)})^{-1}
F(x(k))−1这种矩阵求逆运算，可以通过设计其近似矩阵来代替。
x
(
k
+
1
)
=
x
(
k
)
−
α
H
k
g
(
k
)
x^{(k+1)}=x^{(k)}-\alpha H_kg^{(k)}
x(k+1)=x(k)−αHkg(k)
拟牛顿法的迭代公式：
d
(
k
)
=
−
H
k
g
(
k
)
α
k
=
a
r
g
min
α
⩾
0
f
(
x
(
k
)
+
α
d
(
k
)
)
x
(
k
+
1
)
=
x
(
k
)
+
α
k
d
(
k
)
d^{(k)}=-H_kg^{(k)} \\\alpha_k=arg\min \limits_{\alpha\geqslant0}f(x^{(k)}+\alpha d^{(k)}) \\x^{(k+1)}=x^{(k)}+\alpha_kd^{(k)}
d(k)=−Hkg(k)αk=argα⩾0minf(x(k)+αd(k))x(k+1)=x(k)+αkd(k)
黑塞矩阵逆矩阵的近似
g ( k + 1 ) − g ( k ) = Q ( x ( k + 1 ) − x ( k ) ) g^{(k+1)}-g^{(k)}=Q(x^{(k+1)}-x^{(k)}) g(k+1)−g(k)=Q(x(k+1)−x(k))
即：
△
g
(
k
)
=
Q
△
x
(
k
)
\vartriangle g^{(k)}=Q\vartriangle x^{(k)}
△g(k)=Q△x(k)
H k + 1 △ g ( i ) = △ x ( i ) H_{k+1}\vartriangle g^{(i)}=\vartriangle x^{(i)} Hk+1△g(i)=△x(i)
秩1修正公式
H k + 1 = H k + α k z ( k ) z ( k ) T H_{k+1}=H_k+\alpha_kz^{(k)}z^{(k)T} Hk+1=Hk+αkz(k)z(k)T
其中， r a n k z ( k ) z ( k ) T = 1 rankz^{(k)}z^{(k)T}=1 rankz(k)z(k)T=1，故称为秩1修正算法。
秩1算法过程
- 令 k = 0 k=0 k=0，选择初始点 x ( 0 ) x^{(0)} x(0)，任选一个对称正定实矩阵 H 0 H_0 H0，一般选单位矩阵；
- 如果 g ( k ) = 0 g^{(k)}=0 g(k)=0，停止迭代；否则，令 d ( k ) = − H k g ( k ) d^{(k)}=-H_kg^{(k)} d(k)=−Hkg(k)；
- 计算 α k = − g ( k ) d ( k ) d ( k ) T Q d ( k ) , x ( k + 1 ) = x ( k ) + α k d ( k ) \alpha_k=-\frac{g^{(k)}d^{(k)}}{d^{(k)T}Qd^{(k)}},x^{(k+1)}=x^{(k)}+\alpha_kd^{(k)} αk=−d(k)TQd(k)g(k)d(k),x(k+1)=x(k)+αkd(k)；
- 计算 △ x ( k ) = x ( k + 1 ) − x ( k ) = α k d ( k ) , g ( k + 1 ) = Q x ( k + 1 ) , △ g ( k ) = g ( k + 1 ) − g ( k ) \vartriangle x^{(k)}=x^{(k+1)}-x^{(k)}=\alpha_kd^{(k)},g^{(k+1)}=Qx^{(k+1)},\vartriangle g^{(k)}=g^{(k+1)}-g^{(k)} △x(k)=x(k+1)−x(k)=αkd(k),g(k+1)=Qx(k+1),△g(k)=g(k+1)−g(k)；
- 计算 H k + 1 = H k + ( △ x ( k ) − H k △ g ( k ) ) ( △ x ( k ) − H k △ g ( k ) ) T △ g ( k ) T ( △ x ( k ) − H k △ g ( k ) ) H_{k+1}=H_k+\frac{(\vartriangle x^{(k)}-H_k\vartriangle g^{(k)})(\vartriangle x^{(k)}-H_k\vartriangle g^{(k)})^T}{\vartriangle g^{(k)T}(\vartriangle x^{(k)}-H_k\vartriangle g^{(k)})} Hk+1=Hk+△g(k)T(△x(k)−Hk△g(k))(△x(k)−Hk△g(k))(△x(k)−Hk△g(k))T；
- 返回2，直到 g ( k ) = 0 g^{(k)}=0 g(k)=0。
DFP算法
- 令 k = 0 k=0 k=0，选择初始点 x ( 0 ) x^{(0)} x(0)，任选一个对称正定实矩阵 H 0 H_0 H0，一般选单位矩阵；
- 如果 g ( k ) = 0 g^{(k)}=0 g(k)=0，停止迭代；否则，令 d ( k ) = − H k g ( k ) d^{(k)}=-H_kg^{(k)} d(k)=−Hkg(k)；
- 计算 α k = − g ( k ) d ( k ) d ( k ) T Q d ( k ) , x ( k + 1 ) = x ( k ) + α k d ( k ) \alpha_k=-\frac{g^{(k)}d^{(k)}}{d^{(k)T}Qd^{(k)}},x^{(k+1)}=x^{(k)}+\alpha_kd^{(k)} αk=−d(k)TQd(k)g(k)d(k),x(k+1)=x(k)+αkd(k)；
- 计算 △ x ( k ) = x ( k + 1 ) − x ( k ) = α k d ( k ) , g ( k + 1 ) = Q x ( k + 1 ) , △ g ( k ) = g ( k + 1 ) − g ( k ) \vartriangle x^{(k)}=x^{(k+1)}-x^{(k)}=\alpha_kd^{(k)},g^{(k+1)}=Qx^{(k+1)},\vartriangle g^{(k)}=g^{(k+1)}-g^{(k)} △x(k)=x(k+1)−x(k)=αkd(k),g(k+1)=Qx(k+1),△g(k)=g(k+1)−g(k)；
- 计算 H k + 1 = H k + △ x ( k ) △ x ( k ) T △ x ( k ) T △ g ( k ) − [ H k △ g ( k ) ] [ H k △ g ( k ) ] T △ g ( k ) T H k △ g ( k ) H_{k+1}=H_k+\frac{\vartriangle x^{(k)}\vartriangle x^{(k)T}}{\vartriangle x^{(k)T}\vartriangle g^{(k)}}-\frac{[H_k\vartriangle g^{(k)}][H_k\vartriangle g^{(k)}]^T}{\vartriangle g^{(k)T}H_k\vartriangle g^{(k)}} Hk+1=Hk+△x(k)T△g(k)△x(k)△x(k)T−△g(k)THk△g(k)[Hk△g(k)][Hk△g(k)]T；
- 返回2，直到 g ( k ) = 0 g^{(k)}=0 g(k)=0。
BFGS算法
- 令 k = 0 k=0 k=0，选择初始点 x ( 0 ) x^{(0)} x(0)，任选一个对称正定实矩阵 H 0 H_0 H0，一般选单位矩阵；
- 如果 g ( k ) = 0 g^{(k)}=0 g(k)=0，停止迭代；否则，令 d ( k ) = − H k g ( k ) d^{(k)}=-H_kg^{(k)} d(k)=−Hkg(k)；
- 计算 α k = − g ( k ) d ( k ) d ( k ) T Q d ( k ) , x ( k + 1 ) = x ( k ) + α k d ( k ) \alpha_k=-\frac{g^{(k)}d^{(k)}}{d^{(k)T}Qd^{(k)}},x^{(k+1)}=x^{(k)}+\alpha_kd^{(k)} αk=−d(k)TQd(k)g(k)d(k),x(k+1)=x(k)+αkd(k)；
- 计算 △ x ( k ) = x ( k + 1 ) − x ( k ) = α k d ( k ) , g ( k + 1 ) = Q x ( k + 1 ) , △ g ( k ) = g ( k + 1 ) − g ( k ) \vartriangle x^{(k)}=x^{(k+1)}-x^{(k)}=\alpha_kd^{(k)},g^{(k+1)}=Qx^{(k+1)},\vartriangle g^{(k)}=g^{(k+1)}-g^{(k)} △x(k)=x(k+1)−x(k)=αkd(k),g(k+1)=Qx(k+1),△g(k)=g(k+1)−g(k)；
- 计算 H k + 1 = H k + ( 1 + △ g ( k ) T H k △ g ( k ) △ g ( k ) T △ x ( k ) ) △ x ( k ) △ x ( k ) T △ x ( k ) T △ g ( k ) − H k △ g ( k ) △ x ( k ) T + ( H k △ g ( k ) △ x ( k ) T ) T △ g ( k ) T △ x ( k ) H_{k+1}=H_k+(1+\frac{\vartriangle g^{(k)T}H_k\vartriangle g^{(k)}}{\vartriangle g^{(k)T}\vartriangle x^{(k)}})\frac{\vartriangle x^{(k)}\vartriangle x^{(k)T}}{\vartriangle x^{(k)T}\vartriangle g^{(k)}}-\frac{H_k\vartriangle g^{(k)}\vartriangle x^{(k)T}+(H_k\vartriangle g^{(k)}\vartriangle x^{(k)T})^T}{\vartriangle g^{(k)T}\vartriangle x^{(k)}} Hk+1=Hk+(1+△g(k)T△x(k)△g(k)THk△g(k))△x(k)T△g(k)△x(k)△x(k)T−△g(k)T△x(k)Hk△g(k)△x(k)T+(Hk△g(k)△x(k)T)T；
- 返回2，直到 g ( k ) = 0 g^{(k)}=0 g(k)=0。