本文格式為Word版，下載可任意編輯——牛頓法和擬牛頓法

牛頓法和擬牛頓法

牛頓法和擬牛頓法法和擬牛頓法

牛頓法和擬牛頓法

無約束優(yōu)化問題

牛頓法和擬牛頓法

線探尋方法

dk：探尋方向（下降就可）：dk▽f(xk)0αk：探尋步長：1）確切探尋：f(x＋αd)達到最小2）Wolfe探尋：（兩個條件）

牛頓法和擬牛頓法

確切探尋

牛頓法和擬牛頓法

Wolfe非確切探尋

牛頓法和擬牛頓法

Wolfe非確切探尋

牛頓法和擬牛頓法

線探尋方法的下降

方法收斂之關鍵：估計探尋方向與最速下降方向的夾角

牛頓法和擬牛頓法

線探尋方法的收斂性

假使f(x)下方有界，假使探尋方向定理與最速下降法的夾角不靠近π/2,則由線探尋方法產生的點列xk滿足：||gk||→0

牛頓法和擬牛頓法

探尋方向

最速下降法：

共軛梯度法：

牛頓法：

牛頓法和擬牛頓法

牛頓方向

牛頓方向

是如下問題的解

牛頓法和擬牛頓法

牛頓法的優(yōu)缺點

收斂快－－－二次收斂程序簡單

計算量大－－－需要二階導數(shù)需要二階導數(shù)要求高－－－需要二階導數(shù)需要計算Hesse矩陣，而此矩陣可能非正定，Hesse矩陣需要計算Hesse矩陣，而此矩陣可能非正定，能導致探尋方向不是下降方向。可能導致探尋方向不是下降方向。

牛頓法和擬牛頓法

找替代牛頓法的方法

目標：目標：收斂快程序簡單同時不需要二階導數(shù)找：的家伙?。。∠衽ｎD又不是牛頓的家伙?。?！

牛頓法和擬牛頓法

基本思想：基本思想：

用不包含二階導數(shù)的矩陣近似Hesse矩陣的逆用不包含二階導數(shù)的矩陣近似Hesse矩陣的逆。矩陣近似矩陣的逆。

牛頓法和擬牛頓法

擬牛頓條件

d

(k)

Hk(k))1f(x(k))=f(x

2

x(k+1)=x(k)+λkd(k)

首先分析f(x)與一階導數(shù)的關系：

2

(k)1

展開：在點x(k+1)處進行二階Taylor展開：1f(x)≈f(x(k+1))+f(x(k+1))(xx(k+1))+(xx(k+1))T2f(x(k+1))(xx(k+1))2

f(x)≈f(x(k+1))+2f(x(k+1))(xx(k+1))f(x(k))≈f(x(k+1))+2f(x(k+1))(x(k)x(k+1))

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)=Hk+1q(k)

p(k)≈2f(x(k+1))1q(k)

牛頓法和擬牛頓法

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族

H1=I;Hk+1=Hk+Hk

校正矩陣

牛頓法和擬牛頓法

秩1校正

Hk=αkz

p(k)=Hk+1q(k)

(k)

z

(k)T

秩為1

=(Hk+αkzz

(k)(k)T

)q(k)

(k)

z

(k)

=

p

(k)

Hkq

(k)T

αkz

(k)T

q(k)

Hkq

(k)

αk(z

(k)T

q

(k)2

)=q

(p

(k)

)

Hk=

(p(k)Hkq(k))(p(k)Hkq(k))Tq

(k)T

(p

(k)

Hkq

(k)

)

0?