修正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•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•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•sTkH-1ksk.

证明 同结论1证明方法.

【参考文献】

［1］王宜举，修乃华.非线性规划理论与算法(修订版)［M］.西安：陕西科学出版社，2004.

基金项目：福建省教育厅资助（JB08258）.

推荐访问:正定 遗传性 校正 公式 修正