重置 否
x (1 ) = x ( n + 1 )
例4.13：用DFP方法求解 min 2 x + x − 4 x1 + 2
2 1 2 2
初始点x
(1)
2 1 0 = , H1 = 1 0 1
λ1 =
5 18
2 1
8 9 4 9
SQP方法
• 良好的性质 • 广泛应用 • 与Lagrange-Newton 法的关系
总结
简单的“拟”可以 是革命性的进步!
1 v
( k )T
q (k )
∆H k =
p
(k )
⋅p
( k )T (k )
p
( k )TΒιβλιοθήκη q−Hkq q
(k )
⋅q
( k )T
Hk
( k )T
Hkq
(k )
计 算 步 骤：
x (1 ) , ε > 0
H1 = I n , d (1) = −∇f ( x(1) ), k = 1
∇f ( x ( k ) ) < ε
p ( k ) := x ( k +1) − x ( k ) ⇓ q ( k ) := ∇f ( x ( k +1) ) − ∇f ( x ( k ) ) q
(k )
≈ ∇ f (x
2
( k +1)
)p
(k )
p ( k ) = H k + 1q ( k )
p ( k ) ≈ ∇ 2 f ( x ( k +1) ) −1 q ( k )
FletcherDavidon(1959), Fletcher-Powell(1963) DFP 方法
DFP公式的逆形式 公式的逆形式
如果 H 是B 的拟矩阵
BFGS公式 公式
方法： 最常用的方法） BFGS 方法： (最常用的方法） Broyden(1970), Fletcher(1970), Goldfarb(1970), Shanno(1970)
H1 = I; H k + 1 = H k + ∆H k
校正 矩阵
秩1校正
∆H k = α k z
p ( k ) = H k + 1q ( k )
(k )
⋅z
( k )T
秩为 1
= (Hk + αk z z
( k ) ( k )T
)q ( k )
(k )
z
(k )
=
p
(k )
− Hkq
( k )T
收敛快 －－－ 二次收敛 程序简单
计算量大 －－－ 需要二阶导数 需要二阶导数 要求高 －－－ 需要二阶导数 需要计算Hesse矩阵，而此矩阵可能非正定， Hesse矩阵 需要计算Hesse矩阵，而此矩阵可能非正定， 能导致搜索方向不是下降方向。 可能导致搜索方向不是下降方向。
找替代牛顿法的方法
目标： 目标： 收敛快 程序简单 同时 不需要二阶导数 找： 的家伙！！！ 像牛顿 又不是牛顿 的家伙！！！
p
−
Bk p p
⋅p
( k )T
Bk
( k )T
Bk p
(k )
BFGS修正公式 BFGS修正公式
Bk +1 = Bk + ∆Bk H k +1 = Bk +1
→ H
BFGS k +1 ( M+uv ) = M −
T −1 −1
−1
M −1uvT M−1 1+vT M −1u
是
x = x(k )
否
d (k ) = − H k∇ f ( x (k ) )
λ k = arg min f ( x ( k ) + λ d ( k ) )
λ ≥0
x (k +1) = x (k ) + λ k d (k )
p (k ) = x (k +1) − x (k )
k<n
是
q (k ) = ∇ f ( x (k +1) ) − ∇ f ( x (k ) ) ∆H k H k +1 = H k + ∆ H k k := k + 1
1.秩 1.秩1校正 2.DFP(Davidon-Fletcher-Powell)算法 2.DFP(Davidon-Fletcher-Powell)算法： 算法： 秩2校正 3.BFGS(Broyden-Fletcher-Goldfarb3.BFGS(Broyden-Fletcher-GoldfarbShanno)公式及 Shanno)公式及Broyden族 公式及Broyden族
基本思想： 基本思想：
用不包含二阶导数的矩阵近似Hesse矩阵的逆 用不包含二阶导数的矩阵近似Hesse矩阵的逆。 矩阵近似 矩阵的逆。
拟牛顿条件
d
(k )
H k( k ) ) −1 ∇f ( x ( k ) ) = −∇ f ( x
2
x ( k +1) = x ( k ) + λ k d ( k )
1≤ i < j ≤ n 1≤ i ≤ k ≤ n
(i )
−1
H k +1 Ap = p 其中p =x
( i +1)
−x
= λi d
DFP法具有二次终止性！ DFP法具有二次终止性！ H n + 1 = A 法具有二次终止性
BFGS公式 BFGS公式
p ( k ) = H k + 1q ( k )
特 点 Hesse矩阵。 • 不必计算 不必计算Hesse矩阵 矩阵。
• 当Hk>0时，算法产生的方向均为下 >0时 降方向，具有二次终止性。 降方向，具有二次终止性。 • 存储量较大。 存储量较大。
拟牛顿法是无约束最优化方法 拟牛顿法是无约束最优化方法 最有效的一类算法。 中最有效的一类算法。
拟牛顿公式
q
经验表明，比DFP公式好。 公式好。 经验表明， DFP公式好
Broyden族 Broyden族
H k + 1 = (1 − φ ) H
φ
DFP k +1
+ φH
BFGS k +1
=H
其中 v ( k ) = ( q
( k )T
DFP k +1
+ φv v
( k ) ( k )T
Hkq
1 (k ) 2
(k )
)
⇒ ∇ f ( x ( k ) )T ⋅ d ( k ) < 0
搜索方向为下降方向
定理 设用DFP方法求解正定二次函数 1 T T min f ( x) = x Ax + b x + c 2 (1) 任取x ，令H1 > 0 共轭 则 p
(i ) (i )T
Ap
( j) (i)
=0
(i) (i )
λ1 =
H2 =
17 36
1 86 − 38 306 − 38 305
1 0
DFP法具有二 DFP法具有二 次终止性！ 次终止性！
定理 : 若∇f ( x ) ≠ 0(k = 1,..., n),
(k )
则DFP方法构造的H k > 0.
d
(k )
= − H k∇f ( x
+ βkv v
( k ) ( k )T
)q ( k )
αku u
(k )
( k )T
q
(k )
+ βkv v
1 u
( k )T
( k ) ( k )T
q( k ) = p( k ) − H k q( k )
= − H kq ；β k =
(k )
令u
(k )
= p ；αk =
(k )
q
(k )
;v
(k )
SR1公式 公式
对称秩一方法
非对称秩一公式
优点： 优点：克服对称秩一方法的分母为零的困难 缺点： 缺点： 不对称
PSB公式 公式
Powell 对称化技巧： 对称化技巧： 交替利用 秩一方法
和 对称化
有限内存拟牛顿法
约束问题的拟牛顿法
SQP方法 方法
目标函数是LAGRANGE 目标函数是LAGRANGE 函数的近似
αk z
( k )T
q(k )
− Hkq
(k )
αk (z
( k )T
q
(k ) 2
) =q
(p
(k )
)
∆H k =
( p ( k ) − H k q ( k ) )( p ( k ) − H k q ( k ) )T q
( k )T
(p
(k )
− Hkq
(k )
)
> 0?
注释 • 在一定条件下，收敛且具有二次终止性。 在一定条件下，收敛且具有二次终止性。
首先分析 ∇ f ( x ) 与一阶导数的关系：
2
( k ) −1
展开： 在点 x ( k +1) 处进行二阶 Taylor展开： 1 f ( x ) ≈ f ( x ( k +1) ) + ∇f ( x ( k +1) )( x − x ( k + 1) ) + ( x − x ( k + 1) )T ∇ 2 f ( x ( k +1) )( x − x ( k + 1) ) 2 ⇓
p( k ) H k q(k ) ) − p ( k )T q ( k ) q ( k )T H q ( k ) k