利用LBFGS算法进行数值计算的拟牛顿法
上篇记录了拟牛顿法的思路：通过迭代矩阵
G
k
G_{k}
Gk近似海森矩阵
H
k
−
1
H_k^{-1}
Hk−1，满足拟牛顿条件：
G
k
+
1
(
J
(
x
k
+
1
)
−
J
(
x
k
)
)
=
x
k
+
1
−
x
k
G_{k+1}(J({\bf x}_{k+1})-J({\bf x}_k))={\bf x}_{k+1} - {\bf x}_{k} \\
Gk+1(J(xk+1)−J(xk))=xk+1−xk
构造迭代表达式：
G
k
+
1
=
G
k
+
P
k
+
Q
k
G
k
+
1
y
k
=
s
k
=
G
k
y
k
+
P
k
y
k
+
Q
k
y
k
G_{k+1}=G_k+P_k+Q_k \\ G_{k+1}y_k = s_k=G_ky_k+P_ky_k+Q_ky_k
Gk+1=Gk+Pk+QkGk+1yk=sk=Gkyk+Pkyk+Qkyk
DFP算法用
G
k
G_k
Gk近似
H
k
−
1
H_k^{-1}
Hk−1：
G
k
+
1
=
G
k
+
s
k
s
k
T
s
k
T
y
k
−
G
k
y
k
y
k
T
G
k
y
k
T
G
k
y
k
G_{k+1} = G_k+ \frac{s_ks_k^T}{s_k^Ty_k} - \frac {G_ky_ky_k^TG_k}{y_k^TG_ky_k} \\
Gk+1=Gk+skTykskskT−ykTGkykGkykykTGk
BFGS算法用
B
k
−
1
B_k^{-1}
Bk−1近似
H
k
−
1
H_k^{-1}
Hk−1：
B
k
+
1
−
1
=
(
I
−
s
k
y
k
T
y
k
T
s
k
)
B
k
−
1
(
I
−
y
k
s
k
T
y
k
T
s
k
)
+
s
k
s
k
T
y
k
T
s
k
B_{k+1}^{-1} = (I - \frac{s_ky_k^T}{y_k^Ts_k})B_k^{-1}(I-\frac{y_ks_k^T}{y^T_ks_k}) + \frac{s_ks_k^T}{y_k^Ts_k}
Bk+1−1=(I−ykTskskykT)Bk−1(I−ykTskykskT)+ykTskskskT
迭代过程中，需要存储近似矩阵 G k G_k Gk或 B k B_k Bk，当输入维度很大时，这个近似矩阵所需的内存非常惊人，比如输入维度为10000，则存储 G G G需要400MB，因此在大规模优化问题中，通常使用LBFGS算法来降低内存消耗
推荐阅读