引言
上一节介绍了牛顿法、拟牛顿法。本节将继续以拟牛顿法为基础,介绍 DFP , BFGS \text{DFP},\text{BFGS} DFP,BFGS方法。
回顾:经典牛顿法的缺陷与拟牛顿法思想
经典牛顿法缺陷与修正牛顿法
关于经典牛顿法中关于下降方向
D
k
(
k
=
1
,
2
,
⋯
,
∞
)
\mathcal D_k(k=1,2,\cdots,\infty)
Dk(k=1,2,⋯,∞)的数学符号表示如下:
D
k
=
−
[
∇
2
f
(
x
k
)
]
−
1
∇
f
(
x
k
)
\mathcal D_k = - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k)
Dk=−[∇2f(xk)]−1∇f(xk)
其中
∇
f
(
x
k
)
\nabla f(x_k)
∇f(xk)表示目标函数
f
(
⋅
)
f(\cdot)
f(⋅)在
x
k
x_k
xk位置的梯度向量结果;
∇
2
f
(
x
k
)
\nabla^2 f(x_k)
∇2f(xk)表示目标函数在
x
k
x_k
xk位置的
Hessian Matrix
\text{Hessian Matrix}
Hessian Matrix。问题在于:
∇
2
f
(
x
k
)
\nabla^2 f(x_k)
∇2f(xk)可能不是正定矩阵,从而无法求解
[
∇
2
f
(
x
k
)
]
−
1
[\nabla^2 f(x_k)]^{-1}
[∇2f(xk)]−1,最终无法执行迭代过程。
关于这类问题,可以使用正则化法对
∇
2
f
(
x
k
)
\nabla^2 f(x_k)
∇2f(xk)进行修正:
∇
2
f
(
x
k
)
:
=
∇
2
f
(
x
k
)
+
λ
I
\nabla^2 f(x_k):= \nabla^2 f(x_k) + \lambda \mathcal I
∇2f(xk):=∇2f(xk)+λI
其中
I
\mathcal I
I表示单位矩阵。执行该操作的目的是:保持
∇
2
f
(
x
k
)
\nabla^2 f(x_k)
∇2f(xk)是正定矩阵状态。但这种方法同样存在弊端:
λ
>
max
i
=
1
,
2
,
⋯
,
n
{
−
λ
i
}
\lambda > \mathop{\max}\limits_{i=1,2,\cdots,n} \{- \lambda_i\}
λ>i=1,2,⋯,nmax{−λi}
如果
λ
\lambda
λ数值过大,可能会发生原始
∇
2
f
(
x
k
)
\nabla^2 f(x_k)
∇2f(xk)中各特征值被
λ
\lambda
λ分掉相应权重,从而导致修正后的
∇
2
f
(
x
k
)
\nabla^2 f(x_k)
∇2f(xk)中关于
x
k
x_k
xk的二阶梯度信息减少,甚至无效。当然,也可以基于正则化法的思想,对
∇
2
f
(
x
k
)
\nabla^2 f(x_k)
∇2f(xk)进行优化:实际上,
正则化法中
λ
\lambda
λ过大最终影响当前迭代步骤的
下降方向,并使其收敛到
∇
f
(
x
k
)
λ
\begin{aligned}\frac{\nabla f(x_k)}{\lambda}\end{aligned}
λ∇f(xk)。
∇
2
f
(
x
k
)
=
Q
T
Diag
(
τ
i
)
Q
τ
i
=
{
τ
i
if
τ
i
≥
δ
δ
Otherwise
\begin{aligned} & \nabla^2 f(x_k) = \mathcal Q^T \text{Diag}(\tau_i) \mathcal Q \\ & \tau_i = \begin{cases} \tau_{i} \quad \text{if } \tau_i \geq \delta \\ \delta \quad \text{Otherwise} \end{cases} \end{aligned}
∇2f(xk)=QTDiag(τi)Qτi={τiif τi≥δδOtherwise
其中
δ
\delta
δ是一个适当正数;虽然该方式相比正则化法要缓和不少——仅调整非正特征值的结果,其余正特征值保持不变。但该方法依然存在逻辑上的缺失:通过强行修改二阶梯度信息的方式使其收敛。
拟牛顿法与矩阵 B k + 1 \mathcal B_{k+1} Bk+1的选择
而拟牛顿法的思想是:选择一个既包含
x
k
+
1
x_{k+1}
xk+1处的二阶梯度信息,并且容易获取的正定矩阵
B
k
+
1
\mathcal B_{k+1}
Bk+1来替代
∇
2
f
(
x
k
+
1
)
\nabla^2 f(x_{k+1})
∇2f(xk+1)。由于
[
∇
2
f
(
x
k
+
1
)
]
n
×
n
[\nabla^2 f(x_{k+1})]_{n \times n}
[∇2f(xk+1)]n×n自身计算量较大:
O
(
n
3
)
\mathcal O(n^3)
O(n3),从而不容易获取。
关于矩阵
B
k
+
1
\mathcal B_{k+1}
Bk+1满足的基本要求表示如下:
∇
f
(
x
k
+
1
)
−
∇
f
(
x
k
)
=
B
k
+
1
(
x
k
+
1
−
x
k
)
\nabla f(x_{k+1} )- \nabla f(x_k) = \mathcal B_{k+1} (x_{k+1} - x_k)
∇f(xk+1)−∇f(xk)=Bk+1(xk+1−xk)
可以发现:该式子是关于
n
n
n个方程构成的方程组;而未知量包含
n
(
n
+
1
)
2
\begin{aligned}\frac{n(n+1)}{2}\end{aligned}
2n(n+1)个(
B
k
+
1
\mathcal B_{k+1}
Bk+1上/下三角阵元素数量
),并且:
n
(
n
+
1
)
2
≥
n
;
n
∈
N
+
\begin{aligned}\frac{n(n+1)}{2} \geq n;n \in \mathbb N^{+}\end{aligned}
2n(n+1)≥n;n∈N+。这意味着拟牛顿方程的解
B
k
+
1
\mathcal B_{k+1}
Bk+1不唯一。
既然满足基本要求的解不唯一,可以尝试从这些解中选择与 B k / H k \mathcal B_k/\mathcal H_k Bk/Hk相似的矩阵作为 B k + 1 / H k + 1 \mathcal B_{k+1}/\mathcal H_{k+1} Bk+1/Hk+1:
-
其中:
{ S k = x k + 1 − x k y k = ∇ f ( x k + 1 ) − ∇ f ( x k ) H k = B k − 1 \begin{cases} \mathcal S_k = x_{k+1} - x_k \\ y_k = \nabla f(x_{k+1}) - \nabla f(x_k) \\ \mathcal H_k = \mathcal B_k^{-1} \end{cases} ⎩ ⎨ ⎧Sk=xk+1−xkyk=∇f(xk+1)−∇f(xk)Hk=Bk−1 -
通过这种
相似性来保证
二阶梯度信息的有效性。 -
无论是
B k + 1 \mathcal B_{k+1} Bk+1还是
H k + 1 \mathcal H_{k+1} Hk+1都可以作为我们的求解目标。因为最终都可以对
下降方向 D k + 1 \mathcal D_{k+1} Dk+1进行表示:
D k + 1 = − B k + 1 − 1 ∇ f ( x k + 1 ) = − H k + 1 ∇ f ( x k + 1 ) \mathcal D_{k+1} = - \mathcal B_{k+1}^{-1} \nabla f(x_{k+1}) = -\mathcal H_{k+1}\nabla f(x_{k+1}) Dk+1=−Bk+1−1∇f(xk+1)=−Hk+1∇f(xk+1)。
{ B k + 1 ⇒ B : { min ∥ B − B k ∥ s.t. B ⋅ S k = y k ; B T = B H k + 1 ⇒ H : { min ∥ H − H k ∥ s.t. H ⋅ y k = S k ; H T = H \begin{cases} \mathcal B_{k+1} \Rightarrow \mathcal B: \begin{cases} \min \|\mathcal B - \mathcal B_k\| \\ \text{s.t. } \mathcal B \cdot \mathcal S_k = y_k;\mathcal B^T = \mathcal B \end{cases} \\ \quad \\ \mathcal H_{k+1} \Rightarrow \mathcal H:\begin{cases} \min \|\mathcal H - \mathcal H_k\| \\ \text{s.t. } \mathcal H \cdot y_k = \mathcal S_k;\mathcal H^T = \mathcal H \end{cases} \end{cases} ⎩ ⎨ ⎧Bk+1⇒B:{min∥B−Bk∥s.t. B⋅Sk=yk;BT=BHk+1⇒H:{min∥H−Hk∥s.t. H⋅yk=Sk;HT=H
也可以尝试:将 B k + 1 / H k + 1 \mathcal B_{k+1}/\mathcal H_{k+1} Bk+1/Hk+1看作是 B k / H k \mathcal B_k/\mathcal H_k Bk/Hk的校正/优化后的结果。令 B k + 1 = B k + Δ B \mathcal B_{k+1} = \mathcal B_k + \Delta\mathcal B Bk+1=Bk+ΔB或者 H k + 1 = H k + Δ H \mathcal H_{k+1} = \mathcal H_{k} + \Delta \mathcal H Hk+1=Hk+ΔH,其中:
- SR-1 \text{SR-1} SR-1方法是 Rank-1 \text{Rank-1} Rank-1校正: Δ B 、 Δ H \Delta \mathcal B、\Delta \mathcal H ΔB、ΔH的秩为 1 1 1的代表方法;
- DFP,BFGS \text{DFP,BFGS} DFP,BFGS方法是 Rank-2 \text{Rank-2} Rank-2校正: Δ B 、 Δ H \Delta \mathcal B、\Delta \mathcal H ΔB、ΔH的秩为 2 2 2的代表方法。
拟牛顿法之 DFP \text{DFP} DFP方法
关于
DFP(Davidon-Fletcher-Power)
\text{DFP(Davidon-Fletcher-Power)}
DFP(Davidon-Fletcher-Power)方法可看做是对
H
k
\mathcal H_k
Hk进行
Rank-2
\text{Rank-2}
Rank-2校正。对应迭代公式表示如下:
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
y
k
T
S
k
\mathcal H_{k+1} = \mathcal H_k - \frac{\mathcal H_ky_ky_k^T \mathcal H_k}{y_k^T \mathcal H_k y_k} + \frac{\mathcal S_k\mathcal S_k^T}{y_k^T \mathcal S_k}
Hk+1=Hk−ykTHkykHkykykTHk+ykTSkSkSkT
DFP \text{DFP} DFP迭代公式的推导过程
DFP
\text{DFP}
DFP是一个
Rank-2
\text{Rank-2}
Rank-2校正方法,那么如何表示一个秩为
2
2
2的矩阵
?
?
?首先,先观察秩为
1
1
1的矩阵如何表示:某矩阵
A
n
×
n
\mathcal A_{n \times n}
An×n可表示为如下形式:该矩阵的所有行均相同。
A
=
U
V
T
U
,
V
∈
R
n
;
U
,
V
≠
0
\mathcal A = \mathcal U\mathcal V^T \quad \mathcal U,\mathcal V \in \mathbb R^n;\mathcal U,\mathcal V \neq 0
A=UVTU,V∈Rn;U,V=0
此时
A
\mathcal A
A就是一个秩为
1
1
1的矩阵。但由于
H
k
\mathcal H_k
Hk必然是一个对称矩阵,相比于上式,
Δ
H
\Delta \mathcal H
ΔH想满足是秩为
1
1
1仅需要满足:
Δ
H
=
U
U
T
U
∈
R
n
;
U
≠
0
\Delta \mathcal H = \mathcal U \mathcal U^T \quad \mathcal U \in \mathbb R^n;\mathcal U \neq 0
ΔH=UUTU∈Rn;U=0
这是秩为
1
1
1的情况。那秩为
2
2
2呢
?
?
?只需要满足:
Δ
H
=
U
U
T
+
V
V
T
{
U
,
V
∈
R
n
U
,
V
≠
0
U
≠
V
\Delta \mathcal H = \mathcal U \mathcal U^T + \mathcal V \mathcal V^T \quad \begin{cases}\mathcal U,\mathcal V \in \mathbb R^n \\ \mathcal U,\mathcal V \neq 0 \\ \mathcal U \neq \mathcal V \end{cases}
ΔH=UUT+VVT⎩
⎨
⎧U,V∈RnU,V=0U=V
综上,将迭代关系:
H
k
+
1
=
H
k
+
Δ
H
\mathcal H_{k+1} = \mathcal H_k + \Delta \mathcal H
Hk+1=Hk+ΔH表示为如下形式:其中
a
,
b
a,b
a,b是系数,均是标量~
H
k
+
1
=
H
k
+
a
⋅
U
U
T
+
b
⋅
V
V
T
\mathcal H_{k+1} = \mathcal H_k + a \cdot \mathcal U \mathcal U^T + b \cdot \mathcal V \mathcal V^T
Hk+1=Hk+a⋅UUT+b⋅VVT
由于
H
k
+
1
\mathcal H_{k+1}
Hk+1需要满足基本要求:
H
k
+
1
⋅
y
k
=
S
k
\mathcal H_{k+1} \cdot y_k = \mathcal S_k
Hk+1⋅yk=Sk,因而将上式带入。有:
H
k
y
k
+
a
⋅
U
U
T
y
k
+
b
⋅
V
V
T
y
k
−
S
k
=
0
\mathcal H_k y_k + a \cdot \mathcal U\mathcal U^T y_k + b\cdot \mathcal V\mathcal V^T y_k - \mathcal S_k = 0
Hkyk+a⋅UUTyk+b⋅VVTyk−Sk=0
其中:
- 由于 H k ∈ R n × n , y k ∈ R n \mathcal H_k \in \mathbb R^{n \times n},y_k \in \mathbb R^n Hk∈Rn×n,yk∈Rn,因而 H k y k ∈ R n \mathcal H_k y_k \in \mathbb R^n Hkyk∈Rn,是一个 n n n维向量;
- 由于 U T y k ∈ R \mathcal U^T y_k \in \mathbb R UTyk∈R,因而 a ⋅ U ( U T y k ) ∈ R n a \cdot \mathcal U (\mathcal U^T y_k) \in \mathbb R^n a⋅U(UTyk)∈Rn,可看做向量 U \mathcal U U的 a ⋅ ( U T y k ) a \cdot (\mathcal U^T y_k) a⋅(UTyk)倍;
- 同理, b ⋅ V ( V T y k ) ∈ R n b \cdot \mathcal V(\mathcal V^T y_k) \in \mathbb R^n b⋅V(VTyk)∈Rn,可看做向量 V \mathcal V V的 b ⋅ ( V T y k ) b \cdot (\mathcal V^T y_k) b⋅(VTyk)倍。
- S k = x k + 1 − x k ∈ R n \mathcal S_k = x_{k+1} - x_k \in \mathbb R^n Sk=xk+1−xk∈Rn
对
U
,
V
\mathcal U,\mathcal V
U,V进行取值。将项
H
k
,
a
⋅
U
(
U
T
y
k
)
\mathcal H_k,a \cdot \mathcal U (\mathcal U^T y_k)
Hk,a⋅U(UTyk)关联在一起;项
b
⋅
V
(
V
T
y
k
)
,
S
k
b \cdot \mathcal V (\mathcal V^T y_k),\mathcal S_k
b⋅V(VTyk),Sk关联在一起:
[
H
k
y
k
+
a
⋅
U
(
U
T
y
k
)
]
⏟
=
0
+
[
b
⋅
V
(
V
T
y
k
)
−
S
k
]
⏟
=
0
=
0
\underbrace{\left[\mathcal H_k y_k + a \cdot \mathcal U (\mathcal U^T y_k) \right]}_{=0} + \underbrace{\left[b \cdot \mathcal V ( \mathcal V^T y_k) - \mathcal S_k\right]}_{=0} = 0
=0
[Hkyk+a⋅U(UTyk)]+=0
[b⋅V(VTyk)−Sk]=0
观察第一项:令
U
=
H
k
y
k
\mathcal U = \mathcal H_k y_k
U=Hkyk,带入有:
H
k
y
k
+
a
⋅
U
(
U
T
y
k
)
=
H
k
y
k
+
a
⋅
H
k
y
k
[
(
H
k
y
k
)
T
y
k
]
=
(
H
k
y
k
)
[
1
+
a
⋅
(
H
k
y
k
)
T
y
k
]
=
0
⇒
1
+
a
⋅
(
H
k
y
k
)
T
y
k
=
0
\begin{aligned} \mathcal H_k y_k + a \cdot \mathcal U (\mathcal U^T y_k) & = \mathcal H_ky_k + a \cdot\mathcal H_k y_k [(\mathcal H_k y_k)^Ty_k] \\ & = (\mathcal H_k y_k)[1 + a \cdot (\mathcal H_k y_k)^T y_k] \\ & = 0 \\ & \Rightarrow1 + a \cdot (\mathcal H_k y_k)^T y_k = 0 \end{aligned}
Hkyk+a⋅U(UTyk)=Hkyk+a⋅Hkyk[(Hkyk)Tyk]=(Hkyk)[1+a⋅(Hkyk)Tyk]=0⇒1+a⋅(Hkyk)Tyk=0
整理得:
a
=
−
1
y
k
T
H
k
T
y
k
\begin{aligned}a = - \frac{1}{y_k^T \mathcal H_k^T y_k}\end{aligned}
a=−ykTHkTyk1。
同理,观察第二项:令
V
=
S
k
\mathcal V = \mathcal S_k
V=Sk,带入有:
b
⋅
S
k
T
y
k
−
1
=
0
⇒
b
=
1
S
k
T
y
k
b \cdot \mathcal S_k^T y_k - 1 = 0 \Rightarrow b = \frac{1}{\mathcal S_k^T y_k}
b⋅SkTyk−1=0⇒b=SkTyk1
至此,关于向量
U
,
V
\mathcal U,\mathcal V
U,V,系数
a
,
b
a,b
a,b均已取值完毕,将该结果带入
H
k
+
1
=
H
k
+
a
⋅
U
U
T
+
b
⋅
V
V
T
\mathcal H_{k+1} = \mathcal H_k + a \cdot \mathcal U \mathcal U^T + b \cdot \mathcal V \mathcal V^T
Hk+1=Hk+a⋅UUT+b⋅VVT,即可得到
DFP
\text{DFP}
DFP公式中
H
k
+
1
\mathcal H_{k+1}
Hk+1与
H
k
\mathcal H_k
Hk之间的迭代关系。
小插曲: DFP \text{DFP} DFP方法与最小范数方法
关于最小范数方法:
B
k
+
1
⇒
B
:
{
min
∥
B
−
B
k
∥
s.t.
B
⋅
S
k
=
y
k
;
B
T
=
B
\mathcal B_{k+1} \Rightarrow \mathcal B: \begin{cases} \min \|\mathcal B - \mathcal B_k\| \\ \text{s.t. } \mathcal B \cdot \mathcal S_k = y_k;\mathcal B^T = \mathcal B \end{cases}
Bk+1⇒B:{min∥B−Bk∥s.t. B⋅Sk=yk;BT=B,如果使用
Frobenius
\text{Frobenius}
Frobenius范数对
∥
B
−
B
k
∥
\|\mathcal B - \mathcal B_k\|
∥B−Bk∥进行表示:可以看成是关于矩阵的
L
2
L_2
L2范数
。
∥
B
−
B
k
∥
F
=
∑
i
=
1
n
∑
j
=
1
n
[
b
i
j
−
b
i
j
(
k
)
]
2
\|\mathcal B - \mathcal B_k\|_{F} = \sqrt{\sum_{i=1}^n \sum_{j=1}^n \left[b_{ij} - b_{ij}^{(k)}\right]^2}
∥B−Bk∥F=i=1∑nj=1∑n[bij−bij(k)]2
通过该范数求解出的
B
k
+
1
\mathcal B_{k+1}
Bk+1,它的逆:
B
k
+
1
−
1
\mathcal B_{k+1}^{-1}
Bk+1−1就是
DFP
\text{DFP}
DFP方法求解出的
H
k
+
1
\mathcal H_{k+1}
Hk+1。世界真奇妙~
拟牛顿法之 BFGS \text{BFGS} BFGS方法
关于
BFGS(Broyden-Fletch-Goldfarb-Shannon)
\text{BFGS(Broyden-Fletch-Goldfarb-Shannon)}
BFGS(Broyden-Fletch-Goldfarb-Shannon)方法可看做是对
B
k
\mathcal B_k
Bk进行
Rank-2
\text{Rank-2}
Rank-2校正。对应迭代公式表示如下:
B
k
+
1
=
B
k
−
B
k
S
k
S
k
T
B
k
S
k
T
B
k
S
k
+
y
k
y
k
T
y
k
T
S
k
\mathcal B_{k+1} = \mathcal B_k - \frac{\mathcal B_k \mathcal S_k \mathcal S_k^T \mathcal B_k}{\mathcal S_k^T \mathcal B_k \mathcal S_k} + \frac{y_k y_k^T}{y_k^T \mathcal S_k}
Bk+1=Bk−SkTBkSkBkSkSkTBk+ykTSkykykT
关于 BFGS \text{BFGS} BFGS公式的推导,它与 DFP \text{DFP} DFP公式的推导完全对称。只不过它使用的基本要求是: B k + 1 ⋅ S k = y k \mathcal B_{k+1} \cdot \mathcal S_k = y_k Bk+1⋅Sk=yk。
-
对比
DFP \text{DFP} DFP公式:仅需要将
第一项中的 y k y_k yk改成 S k \mathcal S_k Sk, H k \mathcal H_k Hk改成 B k \mathcal B_k Bk;第二项将分子中的 S k \mathcal S_k Sk改成 y k y_k yk即可。
-
关于
BFGS \text{BFGS} BFGS公式的推导不再赘述。
新的疑问:在使用 BFGS \text{BFGS} BFGS求解出 B k + 1 \mathcal B_{k+1} Bk+1后,在后续求解下降方向 D k = − B k + 1 − 1 ∇ f ( x k + 1 ) \mathcal D_k = - \mathcal B_{k+1}^{-1} \nabla f(x_{k+1}) Dk=−Bk+1−1∇f(xk+1)中,依然不可避免地需要求解逆: B k + 1 − 1 \mathcal B_{k+1}^{-1} Bk+1−1。而求逆同样是一个非常麻烦的操作,为什么还会使用 BFGS \text{BFGS} BFGS方法 ? ? ?主要有两点原因:
- 具备
B
k
+
1
=
B
k
+
a
⋅
U
U
T
+
b
⋅
V
V
T
\mathcal B_{k+1} = \mathcal B_k + a \cdot \mathcal U \mathcal U^T + b \cdot \mathcal V \mathcal V^T
Bk+1=Bk+a⋅UUT+b⋅VVT格式的逆可以使用
Sherman-Morrison
\text{Sherman-Morrison}
Sherman-Morrison公式直接求解:
可以看出,求逆操作自身并不麻烦。
( A + U V T ) − 1 = A − 1 − A − 1 U V T A − 1 1 + V T A − 1 U (\mathcal A + \mathcal U \mathcal V^T)^{-1} = \mathcal A^{-1} - \frac{\mathcal A^{-1} \mathcal U \mathcal V^T \mathcal A^{-1}}{1 + \mathcal V^T \mathcal A^{-1} \mathcal U} (A+UVT)−1=A−1−1+VTA−1UA−1UVTA−1 - DFP \text{DFP} DFP方法求解,其结果稳定性较差。在迭代过程中可能出现 H k + 1 \mathcal H_{k+1} Hk+1变成奇异矩阵。相反, BFGS \text{BFGS} BFGS迭代过程中的数值稳定性更强。并且 BFGS \text{BFGS} BFGS被认为是最有效的拟牛顿法,它的收敛速度可达到超线性收敛。
相比于牛顿法中直接求解 Hessian Matrix ⇒ ∇ 2 f ( x k ) \text{Hessian Matrix} \Rightarrow \nabla^2 f(x_k) Hessian Matrix⇒∇2f(xk), DFP,BFGS \text{DFP,BFGS} DFP,BFGS方法需要求解梯度 ∇ f ( x k ) , ∇ f ( x k + 1 ) \nabla f(x_k),\nabla f(x_{k+1}) ∇f(xk),∇f(xk+1),以及套用求逆公式。其计算量远小于求解 Hessian Matrix \text{Hessian Matrix} Hessian Matrix。
Broyden \text{Broyden} Broyden族
假设使用
DFP
\text{DFP}
DFP方法求解出
H
k
+
1
\mathcal H_{k+1}
Hk+1,将该结果求逆,将其还原:
B
DFP
;
k
+
1
=
H
k
+
1
−
1
\mathcal B_{\text{DFP};k+1} = \mathcal H_{k+1}^{-1}
BDFP;k+1=Hk+1−1
然后通过
BFGS
\text{BFGS}
BFGS方法直接求解出
B
k
+
1
\mathcal B_{k+1}
Bk+1。对这两个矩阵进行线性组合:
{
λ
⋅
B
DFP
;
k
+
1
+
(
1
−
λ
)
⋅
B
k
+
1
}
λ
∈
[
0
,
1
]
\{\lambda \cdot \mathcal B_{\text{DFP};k+1} + (1 - \lambda) \cdot \mathcal B_{k+1}\} \quad \lambda \in [0,1]
{λ⋅BDFP;k+1+(1−λ)⋅Bk+1}λ∈[0,1]
这明显是一个集合。如果迭代过程中,矩阵
B
k
+
1
\mathcal B_{k+1}
Bk+1落在集合内,对应的方法被称作
Broyden
\text{Broyden}
Broyden族。
拟牛顿法之 SR-1 \text{SR-1} SR-1方法
关于
SR-1
\text{SR-1}
SR-1方法可看做是对
B
k
\mathcal B_k
Bk进行
Rank-1
\text{Rank-1}
Rank-1校正。对应迭代公式表示如下:
B
k
+
1
=
B
k
+
(
y
k
−
B
k
S
k
)
(
y
k
−
B
k
S
k
)
T
(
y
k
−
B
k
S
k
)
T
S
k
\mathcal B_{k+1} = \mathcal B_k + \frac{(y_k - \mathcal B_k \mathcal S_k)(y_k - \mathcal B_k \mathcal S_k)^T}{(y_k - \mathcal B_k \mathcal S_k)^T \mathcal S_k}
Bk+1=Bk+(yk−BkSk)TSk(yk−BkSk)(yk−BkSk)T
SR-1 \text{SR-1} SR-1迭代公式的推导过程
与
DFP
\text{DFP}
DFP方法的推导过程类似。将迭代关系:
B
k
+
1
=
B
k
+
Δ
B
\mathcal B_{k+1} = \mathcal B_k + \Delta \mathcal B
Bk+1=Bk+ΔB表示为如下形式:
B
k
+
1
=
B
k
+
a
⋅
U
U
T
\mathcal B_{k+1} = \mathcal B_{k} + a \cdot \mathcal U \mathcal U^T
Bk+1=Bk+a⋅UUT
由于
B
k
+
1
\mathcal B_{k+1}
Bk+1需要满足基本要求:
B
k
+
1
⋅
S
k
=
y
k
\mathcal B_{k+1} \cdot \mathcal S_k = y_k
Bk+1⋅Sk=yk。因而将上式带入,有:
B
k
S
k
+
a
⋅
U
(
U
T
S
k
)
=
y
k
⇒
a
⋅
U
(
U
T
S
k
)
=
y
k
−
B
k
S
k
\mathcal B_k \mathcal S_k + a \cdot \mathcal U( \mathcal U^T \mathcal S_k) = y_k \Rightarrow a \cdot \mathcal U(\mathcal U^T \mathcal S_k) = y_k - \mathcal B_k \mathcal S_k
BkSk+a⋅U(UTSk)=yk⇒a⋅U(UTSk)=yk−BkSk
令
U
=
y
k
−
B
k
S
k
\mathcal U = y_k - \mathcal B_k \mathcal S_k
U=yk−BkSk,有:系数
a
⋅
(
U
T
S
k
)
=
1
a \cdot (\mathcal U^T \mathcal S_k) = 1
a⋅(UTSk)=1,最终可求出
a
a
a:
a
=
1
U
T
S
k
=
1
(
y
k
−
B
k
S
k
)
T
S
k
a = \frac{1}{\mathcal U^T \mathcal S_k} = \frac{1}{(y_k - \mathcal B_k \mathcal S_k)^T \mathcal S_k}
a=UTSk1=(yk−BkSk)TSk1
将
a
,
U
a,\mathcal U
a,U带回
B
k
+
1
=
B
k
+
a
⋅
U
U
T
\mathcal B_{k+1} = \mathcal B_{k} + a \cdot \mathcal U\mathcal U^T
Bk+1=Bk+a⋅UUT,就有
SR-1
\text{SR-1}
SR-1迭代公式。
不可否认:
SR-1
\text{SR-1}
SR-1方法的迭代公式更加简便,但它不能保证迭代过程中
B
k
+
1
\mathcal B_{k+1}
Bk+1的正定性。在适当条件下,
SR-1
\text{SR-1}
SR-1算法可达到
n
n
n步超线性收敛。这里的
n
n
n步超线性收敛是指:当前步骤与执行
n
n
n步之后的结果呈
超线性收敛趋势。对比
超线性收敛,其数学符号表示如下:
{
lim
k
→
∞
∥
x
k
+
1
−
x
∗
∥
∥
x
k
−
x
∗
∥
=
0
lim
k
⇒
∞
∥
x
k
+
n
−
x
∗
∥
∥
x
k
−
x
∗
∥
=
0
\begin{cases} \begin{aligned} \mathop{\lim}\limits_{k \rightarrow \infty} \frac{\|x_{k+1} - x^*\|}{\|x_k - x^*\|} = 0\\ \mathop{\lim}\limits_{k \Rightarrow \infty} \frac{\|x_{k+n} - x^*\|}{\|x_k - x^*\|} = 0 \end{aligned} \end{cases}
⎩
⎨
⎧k→∞lim∥xk−x∗∥∥xk+1−x∗∥=0k⇒∞lim∥xk−x∗∥∥xk+n−x∗∥=0文章来源:https://www.toymoban.com/news/detail-699837.html
Reference
\text{Reference}
Reference:
最优化理论与方法-第六讲-无约束优化问题(二)文章来源地址https://www.toymoban.com/news/detail-699837.html
到了这里,关于机器学习笔记之最优化理论与方法(九)无约束优化问题——常用求解方法(下)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!