修正DFP和Broyden族校正公式及其正定遺傳性分析

【摘要】分析擬牛頓算法正定遺傳性問題，對DFP和Broyden族校正公式修正，得出相應的正定性一般性結論和正定遺傳性的等價條件，并證明了等價條件的結論.

【關鍵詞】校正公式；修正；擬牛頓算法；正定遺傳性

1.引 言

我們知道，對于DFP校正公式，由Hk的正定性要求對稱矩陣Hk+1正定的等價條件是sTkyk>0.

這里記yk=gk+1-gk，sk=xk+1-xk，gk=f(xk)，Hk+1yk=sk.

在Broyden族校正公式中：

設Hk+1=Hk+asksTk+b(HkyksTk+skyTkHk)+cHkykyTkHk.

由擬牛頓條件Hk+1yk=sk，假定Hkyk，sk線性無關，引入一個參數，則得到關于的校正公式：

Hk+1=Hk+sksTksTkyk-HkykyTkHkyTkHkyk+vkvTk

=HDFPk+1+vkvTk

=HBFGSk+1+(-1)vkvTk.

在文獻［1］中定理5.5.2.

定理 設Hk正定，對Broyden族校正公式，Hk+1正定的充分必要條件是sTkyk>0且>(sTkyk)2(sTkyk)2-yTkHkyksTkBksk.

討論了關于Hk+1正定遺傳性的等價問題.事實上，假定Hk正定，關于Broyden族校正公式的Hk+1正定性問題有更一般性結論.

2.問題分析與幾個結論

條件 修正DFP校正公式：

Hk+1=Hk+sgn(sk，yk)sksTksTkyk-HkykyTkHkyTkHkyk.

（1）

結論1 若=0，則對于公式（1）Hk+1正定的充分必要條件是sTkyk≠0.

證明 由于Hk正定，故存在可逆下三角矩陣Lk∈Rn×Rn，滿足Hk=LkLTk，對任意非零向量z∈Rn，由公式（1），

則zTHk+1z=zTLkLTkz+sgn(sk，yk)zTsksTkzsTkyk-

zTLkLTkyk#8226;yTkLkLTkzyTkHkyk.

記akLTkz，bkLTkyk，有

zTHk+1z=‖ak‖2-〈ak，bk〉2‖bk‖2+sgn(sk，yk)‖zTsk‖sTkyk.

利用CauchySchwarz不等式以及z的任意性，容易證得‖zTksk‖≠0.

所以，Hk+1正定zTHk+1z正定

‖ak‖2-〈ak，bk〉2‖bk‖2+

sgn(sk，yk)‖zTsk‖sTkyk>0

sTkyk≠0.

由（1）式中引入參數=-bsTkyk，

則a=1sTkyk+yTkHkyk(sTkyk)2，c=-1yTkHkyk.

由Hk+1正定性條件，可推得關于a，b，c的取值有如下結果：

（1）當=0時，有Hk+1=HDFPk+1，這時Hk+1正定等價于sTkyk>0，

則a=1sTkyk>0，b=0，c=-1yTkHkyk<0.

（2）當=1時，有Hk+1=HBFGSk+1，由Hk+1正定性的等價條件，

則a=yTkHkyk+sTkyk(sTkyk)2>0，b=-1sTkyk<0，c=0.

（3）當0<<1時，由HDFPk+1，HBFGSk+1正定，易知Hk+1正定，

則0<1sTkyk

（4）當>1時，易知Hk+1正定.

綜合上述（1）~（4），我們可以得到如下結論：

結論2 若Hk正定，則Hk+1正定sTkyk>0且≥0.

（5）當<0時，則Hk+1正定sTkyk>0且

>(sTkyk)2(sTkyk)2-yTkHkyk#8226;sTkH-1ksk.

證明可參見文獻［1］，這個結論指出在sTkyk>0時，Hk+1保持正定性參數取得的最小值.

3.修正Broyden校正公式

條件 對Broyden校正公式進行修正：

Hk+1=Hk+sgn(sk，yk)sksTksTkyk-HkykyTkHkyTkHkyk+vkvTk.

（2）

結論3 對于公式（2），Hk+1正定sTkyk≠0且=Λ，其中Λ=(sTkyk)2(sTkyk)2-yTkHkyk#8226;sTkH-1ksk.

證明 同結論1證明方法.

【參考文獻】

［1］王宜舉，修乃華.非線性規劃理論與算法(修訂版)［M］.西安：陜西科學出版社，2004.

基金項目：福建省教育廳資助（JB08258）.