DFP算法
在拟牛顿法中取修正矩阵
D
k
\mathbf{D}_k
D
k
为秩2矩阵
D
k
=
α
u
k
u
k
T
+
β
v
k
v
k
T
\mathbf{D}_k=\alpha\mathbf{u}_k\mathbf{u}_k^T+\beta\mathbf{v}_k\mathbf{v}_k^T
D
k
=
α
u
k
u
k
T
+
β
v
k
v
k
T
于是
(
H
k
+
α
u
k
u
k
T
+
β
v
k
v
k
T
)
y
k
=
s
k
\left(\mathbf{H}_k+\alpha\mathbf{u}_k\mathbf{u}_k^T+\beta\mathbf{v}_k\mathbf{v}_k^T\right)\mathbf{y}_k=\mathbf{s}_k
(
H
k
+
α
u
k
u
k
T
+
β
v
k
v
k
T
)
y
k
=
s
k
剩下懒得写了
推到和
BFGS算法
基本一样
把
B
\mathbf{B}
B
换成
H
\mathbf{H}
H
,然后
s
\mathbf{s}
s
和
y
\mathbf{y}
y
互换，就可以得到结果
H
k
+
1
=
H
k
−
H
k
y
k
y
k
T
H
k
y
k
T
H
k
y
k
+
s
k
s
k
T
s
k
T
y
k
\mathbf{H}_{k+1}=\mathbf{H}_k-\frac{\mathbf{H}_k\mathbf{y}_k\mathbf{y}_k^T\mathbf{H}_k}{\mathbf{y}_k^T\mathbf{H}_k\mathbf{y}_k}+\frac{\mathbf{s}_k\mathbf{s}_k^T}{\mathbf{s}_k^T\mathbf{y}_k}
H
k
+
1
=
H
k
−
y
k
T
H
k
y
k
H
k
y
k
y
k
T
H
k
+
s
k
T
y
k
s
k
s
k
T
B
k
+
1
=
B
k
−
y
k
s
k
T
B
k
y
k
T
s
k
−
B
k
s
k
y
k
T
y
k
T
s
k
+
y
k
s
k
T
B
k
s
k
y
k
T
(
y
k
T
s
k
)
2
+
y
k
y
k
T
y
k
T
s
k
=
(
I
−
s
k
y
k
T
y
k
T
s
k
)
T
B
k
(
I
−
s
k
y
k
T
y
k
T
s
k
)
+
y
k
y
k
T
y
k
T
s
k
\begin{aligned} \mathbf{B}_{k+1}&=\mathbf{B}_k-\frac{\mathbf{y}_k\mathbf{s}_k^T\mathbf{B}_k}{\mathbf{y}_k^T\mathbf{s}_k}-\frac{\mathbf{B}_k\mathbf{s}_k\mathbf{y}_k^T}{\mathbf{y}_k^T\mathbf{s}_k}+\frac{\mathbf{y}_k\mathbf{s}_k^T\mathbf{B}_k\mathbf{s}_k\mathbf{y}_k^T}{\left(\mathbf{y}_k^T\mathbf{s}_k\right)^2}+\frac{\mathbf{y}_k\mathbf{y}_k^T}{\mathbf{y}_k^T\mathbf{s}_k}\\ &=\left(\mathbf{I}-\frac{\mathbf{s}_k\mathbf{y}_k^T}{\mathbf{y}_k^T\mathbf{s}_k}\right)^T\mathbf{B}_{k}\left(\mathbf{I}-\frac{\mathbf{s}_k\mathbf{y}_k^T}{\mathbf{y}_k^T\mathbf{s}_k}\right)+\frac{\mathbf{y}_k\mathbf{y}_k^T}{\mathbf{y}_k^T\mathbf{s}_k} \end{aligned}
B
k
+
1
=
B
k
−
y
k
T
s
k
y
k
s
k
T
B
k
−
y
k
T
s
k
B
k
s
k
y
k
T
+
(
y
k
T
s
k
)
2
y
k
s
k
T
B
k
s
k
y
k
T
+
y
k
T
s
k
y
k
y
k
T
=
(
I
−
y
k
T
s
k
s
k
y
k
T
)
T
B
k
(
I
−
y
k
T
s
k
s
k
y
k
T
)
+
y
k
T
s
k
y
k
y
k
T
性质
性质1
设
H
k
\mathbf{H}_k
H
k
对称正定，
H
k
+
1
\mathbf{H}_{k+1}
H
k
+
1
由DFP校正公式确定，则
H
k
+
1
\mathbf{H}_{k+1}
H
k
+
1
对称正定的充要条件是
s
k
T
y
k
>
0
\mathbf{s}_k^T \mathbf{y}_k>0
s
k
T
y
k
>
0
证明：
和BFGS那篇一样
性质2
DFP中采用精确线搜索或者Wolfe搜索准则，则有
s
k
T
y
k
>
0
\mathbf{s}_k^T\mathbf{y}_k>0
s
k
T
y
k
>
0
尽管Armijo准则（回溯法）一般不能保证
s
k
T
y
k
>
0
\mathbf{s}_k^T\mathbf{y}_k>0
s
k
T
y
k
>
0
但是因为简单，所以可以采用
H
k
+
1
=
{
H
k
,
s
k
T
y
k
≤
0
H
k
+
1
=
H
k
−
H
k
y
k
y
k
T
H
k
y
k
T
B
k
y
k
+
s
k
s
k
T
s
k
T
y
k
s
k
T
y
k
>
0
\mathbf{H}_{k+1}=\begin{cases} \mathbf{H}_k,&\mathbf{s}_k^T\mathbf{y}_k\le 0\\ \mathbf{H}_{k+1}=\mathbf{H}_k-\frac{\mathbf{H}_k\mathbf{y}_k\mathbf{y}_k^T\mathbf{H}_k}{\mathbf{y}_k^T\mathbf{B}_k\mathbf{y}_k}+\frac{\mathbf{s}_k\mathbf{s}_k^T}{\mathbf{s}_k^T\mathbf{y}_k}&\mathbf{s}_k^T\mathbf{y}_k>0 \end{cases}
H
k
+
1
=
{
H
k
,
H
k
+
1
=
H
k
−
y
k
T
B
k
y
k
H
k
y
k
y
k
T
H
k
+
s
k
T
y
k
s
k
s
k
T
s
k
T
y
k
≤
0
s
k
T
y
k
>
0
只要
B
0
\mathbf{B}_0
B
0
时正定的，
B
k
+
1
\mathbf{B}_{k+1}
B
k
+
1
也是正定的
步骤
初始化：选择起点
x
0
\mathbf{x}_0
x
0
,
选择
H
0
\mathbf{H}_0
H
0
(一般取
∇
−
2
f
(
x
0
)
\nabla^{-2} f\left(\mathbf{x}_0\right)
∇
−
2
f
(
x
0
)
或者
I
\mathbf{I}
I
)
步骤
1.若
∥
g
k
∥
≤
ϵ
\|\mathbf{g}_k\|\le \epsilon
∥
g
k
∥
≤
ϵ
,停止，输出
x
k
\mathbf{x}_k
x
k
2.计算
d
k
=
−
H
k
g
k
\mathbf{d}_k=-\mathbf{H}_k\mathbf{g}_k
d
k
=
−
H
k
g
k
3.求步长
α
k
\alpha_k
α
k
4.
x
k
+
1
=
x
k
+
α
k
d
k
\mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{d}_k
x
k
+
1
=
x
k
+
α
k
d
k
,矫正
H
k
\mathbf{H}_{k}
H
k
得到
H
k
+
1
\mathbf{H}_{k+1}
H
k
+
1
5.k=k+1,转1