第30卷第10期渊下冤
赤峰学院学报渊自然科学版冤
Vol.30No.102014年10月JournalofChifengUniversity渊NaturalScienceEdition冤Oct.2014求解非线性无约束优化问题的修正BFGS方法孙
威
渊绥化学院
信息工程学院袁黑龙江
绥化
152061冤
摘
要院在非线性无约束优化上常用的方式有两种袁即共轭梯度与拟牛顿袁其轭梯度方法具备低内存需求以及简单
迭代形式袁拟牛顿法则是借助于Hesse矩阵正定近似的方式进行牛顿法的近似袁因此其收敛速度相对较快袁通过大量数值实验证明相对于其他的Broyden族公式而言袁BFGS公式数值所具稳定性更好袁且将其和非精确搜索方式有机结合应用可获得更为显著的计算效果袁因此目前在实践实践计算过程中经常会采用这种方式来进行计算.因传统拟牛顿方程公式中所用梯度信息仅仅只有两步袁忽视了函数值信息袁因此袁有很大部分学者均在拟牛顿方程中添加了函数值袁以此希望获得更为显著的计算结果.本文针对求解非线性无约束优化问题的修正BFGS法进行了研究与分析.关键词院非线性曰BFGS曰优化曰求解曰方法中图分类号院O224文献标识码院A文章编号院1673-260X渊2014冤10-0005-021修正BEGS方法的分析
个领域中全部x均成立.基于此引理1袁若参数
渊δk袁γk冤为获得修正BFGS算法局部超线性收敛性以及全局收中袁K大于等于ko.敛性袁下面笔者基于AipingLiao所给参数渊δk袁γk冤的修正袁
1.2双参数修正BFGS法一般性结论
对tr渊Bk+1AipingLiao所提双参数BFGS公式B参数一般冤条件与det袁渊基于此再Bk+1冤两个量进行估计给出一个参数袁明具体选择与确新参数以其数及该
值k-1=Bk-啄kBkskskTBkskTBksk结果.∞
1.1修正BEGS方法的算法
+酌kykykTsT袁同时参数渊δk袁γk冤符合0<子k≤1和两个条件袁AipingLiao明确给出了这一算法超移ln子k<∞这kykk=0
1.1.1准备工作
线性收敛性
在本次研究中袁所用Bk迭代公式如下袁即Bk-1=Bk-啄k
以及全局收敛性袁其超线性收敛实验证明主要是参照J窑BkskskTBk+酌ykykTNncedal与R窑A窑Byrd的相关结论袁基于这些结论和实验证
sk
kTBkskskTyk
袁在参数选择上袁明确了常数酌大于等于
0且小于等于1.其算法主要如下院首先进行初始点和初始矩
明可获得limskT
Bksk
k→∞skTyk+skTB≤1ksk2袁结合上述这些结果袁不难发
阵的选取袁即x1∈Rn和B1∈Rn×n现修正BFGS法局部超线性收敛问题主要取决于参数渊δk0渊即着大于0冤且K等于袁其中1曰若B1大于0袁明确终止误差大于||gk||小于等于着袁则γ袁
k迭代停止曰对Bkdk=-gk这一方程组进行求解以获得搜索方行分冤=渊析子k,1冤.鉴于此袁下面笔者就参数渊δk.袁γk冤一般条件进
向.接着借助于Wolfe准则来进行αk的计算.在获得Xk+1以1.2.1算法条件
后袁基于上述所选参数来进行参数渊δk,γk参数选择2院给定常数τo
大于0且小于等于1袁常数po一步计算B大于且小于p1.基于此可知δk大于等于τo且小于等于1袁骤来进行计算袁.最后令k和k+1相等袁再重冤新的转入计算到袁接着上述步进k+1γk大于等于po且小于p1.在计算过程中袁首先进行初始矩1.1.2全局收敛性
阵以及初始点的选取袁令种终止误差大于0且K为1曰若假设渊fx冤一致凸和二阶连续可微袁为便于后文阐述袁在||gk||小于等于ε袁则迭代停曰并对Bkdk=-gk这一方程组进行此将该假设定义为假设a袁其中前者这一假设条件存在m＞求解获得搜索方向袁借助于Wolfe来进行αk的计算袁且利
0袁基于此可得m||z||2≤zTG(x)z袁坌x,z∈Rn用上述公式来进行参数渊δk平集存在有界闭凸集袁即m大于0且小袁于此等时于上述公M袁用公式中式水表则又转入至上述步骤来袁γk冤尧xk+1以及Bk+1的计算袁最后令k和k+1相等袁计算.示为m||z||2≤zTG(x)z≤M||z||2袁坌z∈Rn袁x∈L(x0).基于上述内1.2.2全局收敛性
容袁在此假设若Bk大于0同时ykTSk也大于0袁利用Wolfe准第一袁如果Bk迭代公式如上述所示袁其参数条件满足上
则来明确ak袁当δk大于等于0且小于等于1时袁则Bk+1大
述参数选择2袁基于此可得到tr(Bk+1)≤tr(Bk)-dos啄kqk
2于0.如果渊fx冤符合上述两个假设袁则可获得ykTskT
ksT≥ykyT≤兹和detk
kykyksk
≥籽0detmkM.如果B大于0袁基于此则可得到xTBx窑yTB-1y≥(xTy)2和y线性有关时袁则等号成立.袁当B(Bk+1)q.x
k
第二袁如果渊fx冤符合假设a袁则可利用上述算法获得迭
1.1.3局部超线性收敛
代数列{xk}袁在这种情况下袁任意P均存在相关的常数袁同时假设b院g为零袁G窑为正定曰渊fx冤中Hessian矩阵于x.位置任何自然数均大于1袁那么此时于[1,k]这一区间中最少有Lipschitz袁则有||G(x)-G[pk]个左右的i符合以下条件袁即COSθ1大于等于茁*||≤L||x-x*||袁L>0袁上述假设中袁xe某一
1'袁q1
-5-.com.cn. All Rights Reserved.大于等于茁2'且小于等于茁3'.1.2.3局部超线性收敛第一袁如果参数袁酌性
渊啄kk冤符合参数选择3袁即给定数∞列啄k大于0且小于等于1袁酌k大于0且小于等于1袁-移ln啄k<+∞k=0
∞与-得鬃(Bk+1)=tr(Bk+1)-ln(detBk+1)袁其中
k移=0
ln酌k<+∞.则可获軒軒軒tr(B軒k+1)=tr(B軒k)-啄k
||B軇軒k軇sk||2+酌k||y軇k||2
skT軒Bk軇sk軇skT軇yk
袁det(B軒k+1)=det(B軒k)第二袁如果渊fx冤蓸1-啄k+(1-啄k)酌k
軇ykT符合假设a与假设軇軒Bk-1軇yk+啄kskT軇yk酌kb袁则利用上述軇軇skT軇yk.skT軒Bk軇sk
算法所获得的迭代序列超线性收敛至x蔀e.对τ0和P0两个常数袁若其均存在常数k4袁该自然数较大.针对上述内容袁为考察所设参数渊δk数蓸选择3中的算法袁下面笔笔者取参袁γk数冤渊是δ否满足参k袁γk冤为1-1(k+1)p,1蔀袁在这之中p大于1.基于此来实施数值试验袁在维数上分别取4尧100尧12以及80.从实验结果来看袁当p为50与100的时候袁上述两种算法所得数值结构相同袁就该结果来看袁当p大于等于50的时候袁全部数值结果在某种意义上均一样曰当p大于等于100的时候袁全部数值结果
同样也应一样.对此袁当参数
渊δγ蓸1k袁k冤为1-(k+1)p,1的时候袁在此时P可不用取得太大袁若解决维数小于100蔀的问题袁最好令P小于100.2双参数修正BFGS法对非线性无约束问题的求解2.1准备工作
在上述内容袁对参数γk
已明确了这样的一个袁即
γk大于0且小于等于1.基于此袁在本次计算中袁所设δk同样也应该大于0且小于等于1袁明确这一要求的主要原因在于这是确保Bk保持正定性的必要条件袁而要求参数γk大于0且小于等于1袁则是由于证明过程的需求来明确的袁下面笔者就这方面的问题进行详细地阐述.在本次证明中袁假设skTyk*大于0这一条件成立袁Bk迭
代公式为BT*k-1=Bk-啄kBkskskBk
s+酌*TkykykkTBkskskTyk
*袁在该迭代公式中袁yk*
等于yk+浊kuk袁浊k袁uk等于yk或者sk2袁即存在常数曰而浊k等于O(||sk||).在参数选择上袁采用是参数选择Po与τoτ袁其中
o和po均大于0且小于等于1曰δk大于τ且小于等于1曰γk大于po且小于等于p1.其算法主要如下院首先选取初始矩阵以及初始点袁即B1∈Rn×n与x1∈Rnk等于1袁明确终止误差ε大于0曰若||B袁其中B1大于0袁令k||小于等于ε袁则停止迭代袁并对Bkdk=-gk这一方程组进行求解袁以此获得搜索方向袁接着再借助于Wolfe来进行αk的计算曰最后利用上述公式和参数选择2来进行渊δk算曰最后令k和k+1相等袁并重新转入袁γk到冤上述步骤尧xk+1以及Bk+1的计
进行计算.2.2全局收敛性
第一袁如果渊fx冤符合假设a袁αk符合Wolfe准则袁利用∞
迭代格式袁则移||sk||2
<+∞袁继而获得lim||sk||=0.其证明过程
k=0
k→∞
如下院利用Taylor展式获得f(xk+1)-f(xk)=gkTsk+乙1
0
(1-兹)skTG-6-(xk+兹sk)skd兹袁基于上述内容已知αk符合Wolfe乙准则袁且渊fx冤1符合假设a袁则可得到(1-滓1)(-gkTsk)≥0
(1-兹)skTG(xk+兹sk)∞
skd兹≥1m||sk||2和移(-gkTsk)≤k=0
滓1211
∞
移
∞)-f(xk)]≤k=0
[f(xk+1滓1[f1-f*]袁在此基础上可进一步获得移||sk||2<+∞袁且lim||sk||=0.k=0
k→∞
第二袁如果Bk迭代公式为Bk-1=Bk-啄kBkskskTBk
s+kTB酌k
ksk
yk*yk*TsTy袁且参数选择为参数选择3袁则可得到tr(Bk+1)≤tr(Bk
)-kk*
ukqkdos2兹+籽1Mk*和det(Bk+1)≥籽0det(Bk
)mk*.kqk
第三袁如果存在常数M*与m*获得m*小于等于mk*法中全局收敛性引理袁袁且符合0＜m*＜M*袁则可
1M*≥Mk*可知lim袁k→∞
||s有上述双参数修正BFGSk||=0袁因此对常数m+小于min{m,1}袁所存自然数k5相对比较大袁对任意K大于等于k5袁则可获得-m0≤浊k=O(||sk||)≤m0.如果uk等于sk得到mTk*=skyk*
袁则可
=skTyk+t≥m-m.此时令G*s和G+tI相等袁kTsk0kkkkskTsk且x不等于0袁坌x∈Rn袁则xTGk*x=xTGk*x+tkxTx≥(m-m0)xTx>0袁
因此GTG*T*
k*大于0袁xk*x=xTGk*+tkxTx≤(M+m0)xTx袁且Mk*=ykykskTyk
*=skT軍Gk*軍Gksk-(G軍k*1/2sk)T軍Gk*(G軍k*1/2
sk)≤M+m0.如果uk等于ykskT軍Gk*sk(G軍k
*1/2sk)T(G軍k*1/2sk)袁则
可得到以下结论袁即m=skTk*yk*
s=skTyk(1+t)≥m(1-m)与M*=kTsk0kkskTsk
yk*Tyk*sy=ykTyk(1+tk)≤M(1+m0).在证明中袁令M*=max{M+m0
,MkTk*skTyk
(1+m0)}且m*=min{m-m0,m(1-m0)}袁则可对该定理进行证明.第四袁如果渊fx冤符合假设a袁且{xk}为上述算法所得到的迭代数列袁则对于任意p∈(0,1)均存在相应的常数袁即茁1'.而这也使得任意自然数即k大于1袁且于[1袁K]这一区间最少有[pk]个i符合cos兹1≥茁1'.3结束语
综上所述袁文章就求解非线性无约束优化问题的修正BFGS法进行了详细地阐述袁基于AipingLiao的研究上袁假设了一个比较特殊的参数并提出了该阐述一般性条件袁最后再于修正BFGS公式中引入了新拟的牛顿方程袁获得了该参数的另外一个条件.望通过本文内容的阐述可为今后非线性无约束优化问题的求解提供相应的理论参考.要要要参考要要要文要要献要要院
要要要要要要要要要也1页李弛异文敬步并,刘之家行算法,蓝贞雄[J].计算等.机无约束工程与最应优用化,2012,48(17):44-问题的BFGS松也2页47.
李行算法与实文敬,王汝凉现[J].,廖伟志计算机等工.无约束程,2009,35(15):58-60,63.
最优化问题的BFGS并也3页吴红梅信赖域.算法非线性不等式[J].科学约束优技术与工化问题程,2010,10的一个修正(12):2820-BFGS
也4页2821,2828.
冯迎春湖南理,工郑学院学报列.一般约束渊自然科学版非线性规划冤,2010,23(1):20-23.
问题的光滑牛顿法[J].也5页王开荣梯度法,[J].刘计算奔.建数学立在,2012,34(1):81-92.
修正BFGS公式基础上的新的共轭.com.cn. All Rights Reserved.
