線(xiàn)性不等式約束優(yōu)化的弧線(xiàn)路徑信賴(lài)域算法

1、高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯線(xiàn)性不等式約束優(yōu)化的弧線(xiàn)路徑信賴(lài)域算法張樂(lè)瑛,朱德通上海師范大學(xué)數(shù)理信息學(xué)院數(shù)學(xué)系,上海2(00234)摘要:提供了弧線(xiàn)路徑結(jié)合仿射內(nèi)點(diǎn)信賴(lài)域策略的非單調(diào)回代算法解線(xiàn)性不等式約束的優(yōu)化問(wèn)題.基于仿射投影的信賴(lài)域子問(wèn)題獲得新的搜索方向,采用弧線(xiàn)路徑的近似信賴(lài)域和線(xiàn)搜索結(jié)合技術(shù)得到回代步,獲得新的步長(zhǎng).通過(guò)證明所提供的弧線(xiàn)路徑具有一系列良好性質(zhì),從而在合理的條件下,證明所提供的算法不僅具有整體收斂性,而且保持算法的局部超線(xiàn)性收斂速率.數(shù)值測(cè)試表明了算法的有效性與可靠性.關(guān)鍵詞:信賴(lài)域;回代法;非單調(diào)技術(shù);收斂性中圖分類(lèi)號(hào):O221.2文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1000-4424(

2、2005)04-0441-18E1引言本文考慮下面線(xiàn)性不等式約束的非線(xiàn)性?xún)?yōu)化問(wèn)題:FinH(G)GUVQULQ其中矩陣ILMN且向量O,P,STST,M1,P,M(,P,:OOWQ,KKK1QRW1Q)STX假設(shè)HUTYT是一般的光滑非線(xiàn)性函數(shù)X在本文中記UZMGST_IGJKU為可行集,并假設(shè)嚴(yán)格可行內(nèi)點(diǎn)集i非空X()MGST_IGKntZQ若不涉及問(wèn)題(的對(duì)偶可行性情況,則存在向量乘子a1.1)bST使得ee(1.1)和iacIGabdKbM0則向量G的穩(wěn)定點(diǎn),若a滿(mǎn)足一階必要條件X如果對(duì)于任意1.1)bSZ被稱(chēng)為優(yōu)化問(wèn)題(bJ0LLW的W即是O0和a,M1,P,OWQ兩個(gè)不等式中至少有一

3、個(gè)成立,WGbdKWfWGbdKWb0WW那么稱(chēng)在G其中a個(gè)分量Xa,M1,P,WQ,b0b點(diǎn)嚴(yán)格互補(bǔ)性成立,b是向量ab的第W收稿日期:2004-04-22基金項(xiàng)目:國(guó)家自然科學(xué)基金(10471094)eLH(GdIa.b)bM0(1.2)442高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯第20卷第4期使用Ne的仿射投影信賴(lài)域子問(wèn)題:11.1)wton法自然地給出問(wèn)題(min(d)=ks.t.(d;Ddefdef-k2其中f或?yàn)槠浣鼃=f(),Ax-b,=x-x,(),kxDk=diagCiagBfxdkkk=dkk為kdef似.是f在x()dkk點(diǎn)的局部二次近似,k為信賴(lài)域半徑而·表示歐氏范數(shù).-若作變

4、換d信賴(lài)域子問(wèn)題(等價(jià)于2A=Dk,1.3)defTdTTmin(d,d)=fdBd+dCdkkkkd+22(d;d)k*令d的解.中算法用來(lái)表示在可行域中沿著d1.3)1)()ddk是信賴(lài)域子問(wèn)題(k(kkk方向的最小值,即*-d)=()=min.k(kkkdk(d);s.t.(d;Dk2Ad),xdkkkkkk+kdefdef為保證解的嚴(yán)格可行性,在信賴(lài)域子問(wèn)題中求得d引進(jìn)參數(shù)其中0(,1,<<k后,k00且1,-1=O(d2).沿dkkk方向的迭代步sk定義如下defdef*sd,(1.6)k=kkk=kk.最后通過(guò)對(duì)實(shí)際下降量與預(yù)計(jì)下降量的比值進(jìn)行分析定義新的迭代點(diǎn)和調(diào)整信

5、賴(lài)域半徑,defT從而形成信賴(lài)域仿射內(nèi)點(diǎn)法(另外,引進(jìn)投影梯度方向,()=-(f()-A),TRAM)gxx*TT-1*并假設(shè)每次迭代都滿(mǎn)足此處這樣確()<(+g,(0,1).sgAgkkcskk)kADkCkk)cs保目標(biāo)函數(shù)在每次迭代中有充分的下降量.在信賴(lài)域子問(wèn)題(中,仿射投影矩陣Dk也1)Sk可以取為擾動(dòng)對(duì)角仿射矩陣-D:kdefTD(h(i|j,i=1,k,l,x),若x)=defi=0ix-bii-D(x)ii=否則.1,在本文中,只證明Dk的情形,取-Dk時(shí)會(huì)得到類(lèi)似的結(jié)果.Tfkd+TTT-1dBd+dADkCAdkk22(1.3)Ad)2;k(1.5)張樂(lè)瑛等:線(xiàn)性不等

6、式約束優(yōu)化的弧線(xiàn)路徑信賴(lài)域算法443重新求解搜索方向,因此,為求得一被接受的搜索方向往往需要多次求解信賴(lài)域子問(wèn)題使得計(jì)算量相當(dāng)大.本文采用回代法避免重復(fù)求解信賴(lài)域子問(wèn)題,即當(dāng)搜索方向不被接受時(shí),利用非單調(diào)線(xiàn)搜索技術(shù)得到接受步長(zhǎng),定義新的迭代點(diǎn),這樣就大大提高了計(jì)算速度.這里基于的優(yōu)化問(wèn)題(的信賴(lài)域子問(wèn)題的兩個(gè)等價(jià)形式(與(將弧線(xiàn)路徑和非單11.1)1.3)1.4),調(diào)技術(shù)結(jié)合得到回代步,獲得新的迭代點(diǎn).近似信賴(lài)域路徑的良好性質(zhì)可證明目標(biāo)函數(shù)在算法每一步產(chǎn)生的搜索方向都有充分的下降,而信賴(lài)域方法的使用不僅可以得到算法具有整體收斂性,還保證了其局部超線(xiàn)性收斂速率.本文論述如下:第二節(jié)中簡(jiǎn)單描述近似

7、信賴(lài)域路徑構(gòu)成,得到路徑的一些重要性質(zhì)以及給出非單調(diào)仿射投影信賴(lài)域算法.第三節(jié)得到算法的整體收斂性,第四節(jié)更進(jìn)一步討論局部收斂性和局部收斂速率,最后給出數(shù)值結(jié)果.,-弧線(xiàn)路徑的形成與算法本節(jié)在給出非單調(diào)仿射投影信賴(lài)域回代算法之前,對(duì)近似信賴(lài)域路徑的構(gòu)成作簡(jiǎn)單的介紹.給出信賴(lài)域子問(wèn)題(后定義:1.3)<45/123./0,4/;56/以及投影梯度方向B?)./0(=/AC/D1123-=(>),/(-.1)=AB/E.K.C/D10-J/5-的零空間上的正交投影那么令LJ/,A,/為=-/-B/AC/D1=?L0M=/0/MD5B由(知P由=1.3)()Q/?/決定的充分下降使得滿(mǎn)足

8、互補(bǔ)性:B/MMN/UVB-與RRSTM=,STMJ/C./AC/D1/D1M05M05/UVY設(shè)(為(的解,那么(的一階必要條件意味存在ZX)1.4)1.4)5使得QQ/=AB/Q/且D(./DZY0Z/C/D1/</-Q/J/5<當(dāng)信賴(lài)域子問(wèn)題中的<上變化時(shí),為了寫(xiě)出路徑的表示式,需要涉及矩陣5,DV)/在區(qū)間B/其中_特征值a正001c,01,d,./的分解.首先令對(duì)稱(chēng)陣4_SFGabe是實(shí)數(shù),/,/bb/交陣不失一般性,令a因?yàn)?d,gagdga,ff/的列f1-e為其相應(yīng)的正交特征向量,1-e那么./也為對(duì)稱(chēng)矩陣,<其中,乘子C由下面最小二乘方程決定EFGHF

9、IG2/D1<<(-.-)(-.3)<MJC-/D1<<<M-O.(-.4)(-.W)MMQ/05.YQ/(-.)444高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯第20卷第4期.TB00QQ0kkkkMk=0I0C00Ckk(2.7)2.1近似信賴(lài)域路徑構(gòu)造由(以及(知2.2)2.6)gkdk(Mk+vI=,k2d-Dkkk+1假定對(duì)所有的k都有v使(均可逆,那么,0,)Mk+vIkkgkdk-1Mk+vI).k=(2dk-Dkk+1由(有2.7)(Mk+vI)=k結(jié)合(得2.9)-1(2.8)(2.9)(-1I)Q0(k+vkk0I0,-1I)(C0k+vk0TQk(2.10)

10、-1T(I)Qkk+vkkkgdQk.=-12d-(kCI)Dkk+vkk+1(2.11)又由k1+vk-1(I)=k+vk=-1,(CI)=k+vk+vk1k+1=,+vkmk+1令+vkkn(2.12)-1T(I)Qkk+vkkgkdQk(v)=k=k-12d-(kCI)Dkk+vkk+1進(jìn)一步寫(xiě)為是信賴(lài)域子問(wèn)題(的解,由(可將(d;d)1.4)2.12)kknTi2(aixk-bikkk+1iq,d,i=1,m,jk=-i+vk+vkk+1kTjkj(2.13)dk=(2.14)j=1的第個(gè)分量.i其中dik是dk2.2弧線(xiàn)路徑的性質(zhì)下面的敘述中,為表示方便起見(jiàn),將的下標(biāo)k省略.,v引理

11、2是在信賴(lài)域子問(wèn)題中得到的近似信賴(lài)域路徑,那么路徑的范數(shù)函數(shù).1令()v關(guān)于參數(shù)v是單調(diào)下降的.0,+)kTk證令由(以及q有()=()2,2.14)=1(=1,)vvjnjqj2T(v)=(v)(v)=d2+d=張樂(lè)瑛等:線(xiàn)性不等式約束優(yōu)化的弧線(xiàn)路徑信賴(lài)域算法n445j=1qjgk+2kj+v()nkT2kT2mi=1aixk-bik+1.2i+1+vk)mTi2Ti2(2.15)ikT兩邊對(duì)v求導(dǎo),且有則有+v>0>0,-b0,a+1+vkjixki'(v)=-2j=1jkikik+1-2<0.33kij+vk+1+v()i=1(2.16)因此,()對(duì)v0是單調(diào)下

12、降的.v引理2令d產(chǎn)生的,那么.2在第k步迭代中,2.14)k是在信賴(lài)域子問(wèn)題中由弧線(xiàn)路徑(T對(duì)所有的f都有,Mk和kgkkT-fkgkTTf|-fg1minkk-1kdMkkk2其中>0是獨(dú)立于k的常數(shù).1T證由(得到最小二乘的正規(guī)方程(由此可得2.3)=Af,AA+Dk)k+1kf+k-Ak+1-又由d=Dk2Adkk知T2D2kk+12=-TTTfAdAdk-k+k=kdk+1k+1-1Bkgk當(dāng)v為牛頓步.若由于(1)=0時(shí),(0)=(0),()對(duì)v0,+vk-12-Ck+1kDk2是單調(diào)下降的,則取為最優(yōu)解,有由(和(),(0)(0)2,2.14)2.15)vkk可得nT-fk

13、gkMk2kjk+k2()jT2kT2mj=1i=1aixk-bik+12ik+1)=-TfkgkTi2f+D2k-Ak+1Mk22kk+1有k2Mk2結(jié)合(,2.19)nfdk=-Tknjk-kjkTj2kT2mj=1mi=1kiik+1i|k+1Tii2k+1Ti2i=1kki)-j=1-Tfkgk2TkkminkMk即當(dāng)最優(yōu)解為牛頓步時(shí)取=1可得(2.17).1Mk=-2-Mk,qg)+(ax-b()(TfTk-Ak+1dk=dk2Dkk+1下面分兩種情況來(lái)討論:2,(2.17)Tfkgk,(2.18)Tf.kkd(2.19).Tfkgk=(2.20)446高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯第20卷第

14、4期若則由是單調(diào)下降的,那么肯定存在在一個(gè)v(2)(0)>,()對(duì)v0,+)vkk2使得由()2=,2.15)vkknkT2jkk2+()kj+vmTi2ikik+12=.(2.21)ki2(|+v)kk+1j=1i=1kikikk因?yàn)槟敲?v>0,|+v>0,Mk,|Mk,+v>v+mi,njkk+1kjk+1|jkkjiiki由(有|,|+v>v+mi,|,=1,;=1,2.21)njnim.k+1k+1kkjk+12kqg)+(ax-b)(kTjk2Tikij=1i=1i2k+1)-=,|vinjk+1k+m()T2fkgkki2,ki2(vin,|)k+m

15、jk+1則|-0vk|-ki-min,|=jk+1kT2|fkgkkimax-,-|+Mk,jk+1k又由(2.19)nTkfdk=-j=1kT2jk-kj+vkTmi=1Ti2ikik+1i|+vk+1k2kk+1f+D2k-Ak+1|-Tf|kgkT2k2-|-2Mk+Tk|-3maxMk|-3T|-fkgkfgmikn,kMk223解信賴(lài)域問(wèn)題要確保算法的整體收斂性,期望在每一步迭代后目標(biāo)函數(shù)都有充分下降量,即在第k次迭代中的預(yù)計(jì)改變量定義為Pred(d)=-(d).kk滿(mǎn)足如下引理.引理2中由弧線(xiàn)路徑(產(chǎn)生的解,那么存在.3令d)2.14)>0使Sk為信賴(lài)域子問(wèn)題(kT得對(duì)所有f

16、,Mk都有kgkkPred(d)|-k證因?yàn)镻red(d)=-kT2|-f|kgkTf|mikgkn.kMk2Tfkdk-T,kMkk2那么當(dāng)v由(引理2有0時(shí),2.11),.2以及(2.26)Mk+vkTf|kgkTk2nmTfkgkfgk+kTk2(2.22)fg|kk=(2.23)(2.24)(2.25)(2.26)張樂(lè)瑛等:線(xiàn)性不等式約束優(yōu)化的弧線(xiàn)路徑信賴(lài)域算法n447Pred(d)=kqjgk+kj+vkT2mj=1aixk-bik+1-ik+1+vTi2i=1T-1T-1TQQ(I)Q(I)Qkk+vkkk+vkkgkgB0k=2-12-120CkCI)DkCI)Dk-(-(k+v

17、k+1k+vk+1-|-6T2|-fkgkfgmikn,kMkTk2即得取式,定理得證.=,(2.25)6選取參數(shù)(0,1),0<<<1,0<<<1<,>0及整數(shù)M00,.令121232選取對(duì)稱(chēng)矩陣B初始信賴(lài)域半徑給定初始點(diǎn)0)=0.,>0及最大信賴(lài)域半徑>0,m(00max()n轉(zhuǎn)主步.=0,R.令kx0主步以及C選一個(gè)對(duì)Ax-b1.計(jì)算f=f(),f=f(),=d.kk+1xxDk=diagiagkkkkk2稱(chēng)矩陣B計(jì)算最小二乘的L乘子的近似.f(),xagrangekkk+1見(jiàn)(其中v3.構(gòu)造近似信賴(lài)域路徑()(2.14),0,

18、+).v記解為d4.求解信賴(lài)域子問(wèn)題(),.Skkmin(d)=kndRdefTfkd+TTT-1dBd+dADkCAdkk22,(d;Dk2Ad)(v)k-1d;D(-2k)Ad2直到下列不等式滿(mǎn)足5.選取=1,kTf(xd)f(x)+f(x)d,k+kkl(k)kkk且xd,k+kk其中f(x)()=maf.k-jxxl(k)0jm(k)6.令d,若xdnt(),kkk+kkihk=d,否則.kkk2其中對(duì)某個(gè)0則(,1,<<1和-1=O(,k00kkd)x.k+1=xk+hk計(jì)算T2fk+kdk22(2.27)(2.28)(2.29)(2.30)(2.31)448高校應(yīng)用數(shù)學(xué)

19、學(xué)報(bào)A輯Pred(h)=-(h),kkkh)=f(x)-f(x),Ared(kl(k)k+hkk.k=Pred(h)k第20卷第4期(2.32)(2.33)(2.34)7.取若,1k2kk1若(,2kk1<k<2k+1=(,min,若.3kmaxkk2計(jì)算f和g.k+1k+1校正B8.取m(+1)=mi)+1,.置kk+1轉(zhuǎn)步2.knm(kMk得到Bk+1TTT注1在信賴(lài)域子問(wèn)題(中,();)=f+d+ddSdBdCd是目標(biāo)函數(shù)f在kkkkkkd22而迭代方向d是在x半徑為xk鄰域的局部二次模型.k為中心,k的橢圓內(nèi)通過(guò)近似信賴(lài)域的曲線(xiàn)路徑求解極小化二次模型產(chǎn)生的.(,)dd注2第

20、四步中中意味著是沿d可取為2.29)k在(k方向到邊界的步長(zhǎng),TTikiikiin->0,i=1,m.k=mTTaaidkidkdef(2.35)Tdefa-bki若對(duì)所有的i都有-ix則0,dk=+.這樣定義的k可以證明由步kk產(chǎn)生的點(diǎn)Takid4+.xdkkk均滿(mǎn)足線(xiàn)性不等式約束T注3在線(xiàn)搜索中,我們用(中的f且線(xiàn)2.28)kdk代替?zhèn)鹘y(tǒng)信賴(lài)域方法中的接受準(zhǔn)則,T-1搜索準(zhǔn)則(比傳統(tǒng)的信賴(lài)域步更容易滿(mǎn)足,因?yàn)槿绻鸅那么2.28)+ADkCA是半正定的,kk().fdkdkkk注4通常的單調(diào)算法可以看作是本文算法M=0的特殊情況.Tn3算法的整體收斂性q1q本節(jié)假設(shè)f由算法產(chǎn)生sp,o

21、prp是二階連續(xù)可微的且有下界.給定初始可行解x0q迭代點(diǎn)列tp.定義f的水平集為oxk(x)=xspuqf(x)f(x),Axb.0下面的假設(shè)是得到一般線(xiàn)性不等式約束優(yōu)化問(wèn)題收斂性所必需的.q假設(shè)v均包含于緊集u1算法產(chǎn)生的迭代點(diǎn)列tp().xxk02假設(shè)v和xMkxw2存在正常數(shù)w()xw,yxsu()yk.xxf和wM使得xfkf0M,假設(shè)v是行滿(mǎn)秩的,對(duì)所有x23假定-D(su().A,xx0q定理3是由算法產(chǎn)生的迭代點(diǎn)列,且問(wèn)題.1假定假設(shè)條件A1ztpA3成立,xk在x那么(1.1)處嚴(yán)格互補(bǔ)松弛性成立,(2.36)張樂(lè)瑛等:線(xiàn)性不等式約束優(yōu)化的弧線(xiàn)路徑信賴(lài)域算法liminf|-k

22、449證若定理結(jié)論不真,那么存在某個(gè)使得>0,|-T2f|,k=1,2,.kgkTf(x)-f(xd)f.l(k)k+kkkkdk考慮到m(則m(有+1)=mi)+1,+1)m()+1和f()f(),knm(kMkkxxk+1l(k)f(x)=l(k+1)0jm(k+1)maxf(x)k+1-j0jm(k)+1maxf(x)=maxf(x),f(x)=f(x).k+1-jl(k)k+1l(k)這意味著序列對(duì)所有的k是遞減的,因此是收斂的.由(和()()2.17)2.28)fxfxl(k)l(k)有Tf(x)=f(xd)f(x)+fdl(k)l(k)-1+l(k)-1l(k)-1l(k)-

23、1l(k)-1l(k)-1l(k)-1.f(x)-minl(k)-1l(k)-11l(k)-1kM由的收斂性,可得()fxl(k)klim,l(k)-1l(k)-1=0即是l=0iminfl(k)-1kk或者k=0.liml(k)-1jj對(duì)l由=0,iml(k)-11kk+j2k知klim.k=0Tiki界約束中若對(duì)所有的i則若存在i使,-0(=1,im)k的取法知:k取為+,TakidTki2如式所決定又因?yàn)橛械?i>0,(2.36),=Ad2.6)Dkdkkk和(TaidkTiikik+1TTi2d=-aa,ixk-bik=(idkivkk+iTkikik那么-則在1使得=,m中必存

24、在某個(gè)jTiaidkk+1jjTkkkikkj=.k=-Tjak+1jdkk+1由(知存在常數(shù)k2.6)>0,>0使得k12kk).k+11+(2+vkk聯(lián)合(表明存在常數(shù)k2.22)>0有33-Mkv+Mk.kkk此式意味著kkkkkk.k22kk+11k+k2k+k3k+Mkkjj根據(jù)算法第5步中的接受準(zhǔn)則知Tf|=0.kgk(3.1)(3.2)(3.3)(3.4)(3.5)(3.6)(3.7)(3.8)(3.9)(3.10)450高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯第20卷第4期表明當(dāng)可得邊界約束決定的0時(shí),+.那么0應(yīng)由線(xiàn)搜索約束決定.下面證kkk明由線(xiàn)搜索準(zhǔn)則,可得k=1Tf(x)

25、f(x)+f.k+dkl(k)kkd(3.11)滿(mǎn)足線(xiàn)搜索約束.那么由(有2.28)(3.12)TTf(x)>f(x)+f(x)+f.k+dkl(k)kfkkkdkd因?yàn)閒是二次連續(xù)可微的()xf(x)-f(x)=k+dkk其中和(0,1).由(3.13)3.14)T(1-)fkdk+Tfkdk+T2d(xd)d.kfk+kk2T2d(xd)d,kfk+kk>02k2>0.Mdk2由此可得T(1-)fkdk+因?yàn)?則有2.17),2+k-(1-)min,k1Mk>0k2M由l=0則對(duì)充分大的k必有imkkk,kkMMkMhd)d=O(d2),k=kk=dk+(k-1kk

26、-1k故有TPred(h)=fkk+khTT-1hBA)hk+ADkk=k(kC2Pred(d)+()kk-1Tfkdk+TT-1d(3.20)BA)dk(k+ADkCkk+22TT-1()dBA)d.k-1k(k+ADkCkk2又由Ared(h)-Pred(h=kk-Tfkhk-T2hf(xh)hkk+kk+2Tfkhk+T2T-1d(xd()d)-(BA)dk+k+k-1kk+ADkk+kfkC2TT-1()d(xd()d)-(BA)dk-1k+k+k-1kk+ADkk+kfkC2如果上述結(jié)論不真,則必有(3.13)(3.14)(3.15)(3.16)(3.17)(3.18)(3.19)T

27、T-1hBA)hk(k+ADkCkk=2張樂(lè)瑛等:線(xiàn)性不等式約束優(yōu)化的弧線(xiàn)路徑信賴(lài)域算法45122TT-1()d(xd()d)-(BA)d(k-1k+k+k-1kk+ADkkkfkC3.21)2其中那么(意味著(0,1).當(dāng)l=0時(shí),=0,3.19)1.又由(2.25),imlimdkkkkk與(以及(2.34),(3.20)3.21)T2T-12d(xd()d)-(B)d,kfkCkk+k+k-1kk+ADkkkM2可得從而那么這與(矛盾.0,3.6)kkk2k的下確界必定遠(yuǎn)離0即是liminf.k0又因?yàn)?結(jié)合(有;),3.5)ddkkkkkk上式由中定理可知l5=0和imhl(k)-jk

28、代入算法的接受準(zhǔn)則(得到2.28)T.f(x)-f(x)fminkk+1l(k)kk-k1kdkM這與(意味著3.22)liminf.k=0kTki若對(duì)所有的i都有-i則顯然不能有(若存在0(=1,3.26).im)k取為+,TaidkTki使得-i則有(式.因?yàn)閱?wèn)題(在x當(dāng),>0,3.7)1.1)i*處嚴(yán)格互補(bǔ)松弛性成立,TaidkT時(shí),又由極限的保號(hào)性,當(dāng)k充分大時(shí)有>0ajx*-bjTajxk-bjT(a)>0,(3.27)jx*-bj2TTjj.k>0由(3.7)jkk,kkk)1+(2+vkk即有(2.29)fxk+又有2kkT2kTfx(x)=fd(xd)d

29、,dkkdk+kfk+kkk+k-f22(kkkT(x)fx(x)>f,ddkl(k)kdkk-fk+k-f)()()其中和(0,1).由(3.30)3.31)(3.22)limd=0.l(k)-1l(k)-1(3.23)limf(x)=limf(x),l(k)kk(3.24)(3.25)(3.26)(3.28)(3.29)(3.30)(3.31)452高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯2kkT2T(1-fd(xd)d.kdk+kfk+kk>022第20卷第4期k因?yàn)?gt;0和假設(shè)A2知T(1-)fk+kdkkd2>0.fk2k2由(和(有-(+2.17)3.2)1-)>0即kkm

30、in1fkk2M2(1-)mink1M,k>2kfk再由(有l(wèi)3.26)=0即imkkMl(k)-1kliml(k)-1=+,與算法矛盾,則假設(shè)均不成立.綜上所述,定理結(jié)論成立.K4算法的局部收斂速率定理3至少有一個(gè)極限點(diǎn)是穩(wěn)定點(diǎn),本節(jié)將這個(gè)定理L1說(shuō)明算法得到的迭代點(diǎn)列xk發(fā)展為更強(qiáng)的結(jié)果,以及得到算法的局部收斂速率,但這需要更多的假設(shè).假設(shè)M的解x令P2的零1.1)N問(wèn)題(O滿(mǎn)足強(qiáng)二階充分條件.即是,O的列由STQ,-RO空間的正交基構(gòu)成,那么存一個(gè)常數(shù)U使得>0,TTV(PVXUV2,YV.OWOPO)2f(x0O)其中WO=.Z0O2f(x)0k2零空間的正交基構(gòu)成那么假設(shè)

31、M令且的列由_,PS-RkT,Wk=Q,kZ0kkkkklim=0.(4.2)kdk這意味著TTTT2bdPP)dPP)dd,kk(kMkkk=dk(kWkkk+ac0k其中Mk=.0Zk定理N問(wèn)題(在的每一個(gè)極限點(diǎn)處滿(mǎn)足嚴(yán)格互補(bǔ)Ld若假設(shè)條件A1e1.1)A5成立,xk性,那么klimf-Tff=0.kgk證(3.32)(3.33)(3.34)(3.35)(4.1)(4.3)(4.4)張樂(lè)瑛等j線(xiàn)性不等式約束優(yōu)化的弧線(xiàn)路徑信賴(lài)域算法45NTfTk-Ak+1dddkkkTTTTT(M+vIddf=-d-dMkkkkkkkdk=k()().dddkkk2-Dkk+1ddkk2222因?yàn)镈k則那么

32、這里=Ad,(-Dk=0,B-DkC),(B-DkC)dA,A,A,kkAA(ddkkddddkkkkTTT2的零空間則表示(從而-Dk),=A,DDEEk+Ek)=Ekkkk=(,ddddkkkkdd2kkT以及由假設(shè)條件H4與H5及以上分析,可寫(xiě)為(當(dāng)kGFdF2,(4.5)EkkddkkF充分大時(shí))dkTTTTTdfdE(EE)EkIk)kdkMkk=k-(kkdkddkkTTTTd-(dIE(EE)EEk)kkJkkk+kddkkTk另外,由(和(知N.4)4.M)Tf(O)f(O)+QRfd(O)-RQP(k)P(k)-1P(k)-1P(k)-1P(k)-1fP(k)-1P(k)-1

33、2因?yàn)镾收斂,則U又因?yàn)?)T.FdF=0fOVWQP(k)P(k)-1P(k)-1kXYTf(O)-f(Od)GQRfP(k)k+QkkkkdkG那么類(lèi)似于B定理證明得到的(有5CN.2N)kXYUVWQFdF2=0.kk分析知其中那么當(dāng)Q決定時(shí)U否B1C=+2.NM)=1,VWQk,k為牛頓步乘子,k+1kk由(kkXYaka則對(duì)所有的a都有-,(=1,b,0則有U=+Yfac)VWQkTkX+Ydkad當(dāng)F(那么由定理N(2)I)F=X0,1分析類(lèi)似可得U=Yf所以QddVWQkkkkk應(yīng)由線(xiàn)搜索kX+YT2h(1-R)fkdk2約束決定f由(有Q對(duì)此式取極限,由(有N.N2)FdFg-

34、G0,4.)kkifkXYTUVW(-Tf)=0,kdk(4.5)FFFFFFF2dkTE-k2dkFFF2dkT+EkdkFF2=-kd2dkF2dk+dkFF2k2-FdF.4(4.M)2d.P(k)-1FF4RQFdF2,kk4(4.Z)(4.)(4.)454高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯第20卷第4期T那么由(知-f也對(duì)此式同時(shí)取極限有4.6)d20,kkkd4limd=0.kkT另外,知1對(duì)(兩端同除以d然后取極限->0,f<0和1,3.32),kdkkkT(1-)fkdk(4.10)0limkdk=lim(1-kdkklim-TTgmimi和某個(gè)正常數(shù)現(xiàn)假設(shè)定理的結(jié)論不真,即存在

35、的一個(gè)子序列-f使對(duì)-f,kgk1|-那么由引理2知.1中(2.17)Tfd|-mimi-1T2|-fgmmTfg|minmimimiMmi21mi-min11M,對(duì)(兩邊同時(shí)除以-d則4.13),mi-dmiTfdmimimimimi.11MmidmimidTfdmimimi由則且則意味著這與,1,=0.(4.14)-,ddlimmimimi11kddmimi矛盾,則假設(shè)不成立,那么定理結(jié)論成立.(4.11)定理4若問(wèn)題(在的每一個(gè)極限點(diǎn)處滿(mǎn)足嚴(yán)格.2假定假設(shè)條件A1-1.1)A5成立,xk互補(bǔ)性,那么超線(xiàn)性收斂到x即是xk*,klimk+1*=0.xk-x*證為了證明結(jié)論,先作下述說(shuō)明:由

36、問(wèn)題(的一階必要條件(以及C1.1)1.2)k和Dk的-T=0iT定義有(又因?yàn)閐則d中引a,=1,=Dk2Ad,.類(lèi)似于1im,ix*-bikk*d*=0*C)理1的分析及假設(shè)A3知是連續(xù)的,那么(),()xCx2TT-1TTT)2)dAdddd=od.kkkADkCkk=dkCkk=dkCkk-d*C*d*=o(f(x)0kB0ddd2kkkkTTTTdd=d+,(4.17)kdkkk(dd0CdkkkkC0k2TTT-1TTT-1可得d即由(d2)+d=d()+d+o,4.16)dAdxdAdkkBkkkADkCkkkfkkkADkCkk(由定理4.1的分析有2所有的mi都有,=1,2,

37、iT2fg|,mimi1dk進(jìn)一步可得Tfkdk=0.Tfkdk+kkd0,fk2(4.11)(4.12)(4.13)(4.14)(4.15)(4.16)張樂(lè)瑛等:線(xiàn)性不等式約束優(yōu)化的弧線(xiàn)路徑信賴(lài)域算法得TTT-12)d(x)dBA)dd.kkfkk-dk(k+ADkCkk=o(455f(x)0kdk2TTTTd(x)dddkdkkfkk=(kCkk-ddkC0kkd2dk再由(和(知2.8)2.19)TkTkTfdB)d+k+d(k+ADCAk=-vkdk-1kk情況下klim.k=1k若假設(shè)對(duì)充分大的k按(中線(xiàn)搜索要求知那么,1,2.27)1,kkkkTfx(x)>fx(x)+f,d

38、dkl(k)kdkk+k-fk+k>f()()k類(lèi)似于定理3得.1對(duì)上不等式左邊展開(kāi)后并兩邊同時(shí)除以,kT2T2)(1-)fd+d(x)dd>0,kkkkfkk+o(2那么T2TT-1df(x)dBA)dkkk-dk(k+ADkCkk+22kT2)(x)dd>0.-1dkkfkk+o(2由(和(上式即為4.18)4.20),)(4.23)結(jié)合(和(有-d+-1d>0即-1>4.6)4.19),224)24則由即>1這與假設(shè)矛盾,因此假設(shè)不成立,即l-,0,-1>0,.im=12(2)2kTT2)-fd+df(x)dd>0.-1kkk+okkk(2

39、2)k2kkkPred(d)=-kTfkdk-TTT-1BA)ddfk+ADkCkk(k=-kdk-222T-1TTTBA)dfk+ADkkCkdk+dk(k-fd2,(4.24)kkkd28-2)Tfkdk+T-1TTBA)dfk+ADkCkkdk+dk(k+2kk2另外由假設(shè)條件A4知2(4.18)222)+odk(d2,k4-2k2(4.19)(2DAdk0.(4.20)(4.21)(4.22)kkk456高校應(yīng)用數(shù)學(xué)學(xué)報(bào)r輯第20卷第4期那么類(lèi)似與(與(的證明,以及(式有3.20)3.21)(4.18)4.24)2k.(4.25)k-Pred(d)k和(意味著當(dāng)d故存在使得當(dāng)d因此(4

40、.24)4.25)0時(shí),1,>0,kkkk2于是存在K'使得當(dāng)KK'時(shí)有d故.d0,k+1kkk.k(4.26)kK'那么,對(duì)充分大的k信賴(lài)域約束不起作用,則取最優(yōu)解此時(shí)那么,(0),=1,=1,kk-1hk=dk=-Bkgk為牛頓步或者為擬牛頓步,算法具有超線(xiàn)性收斂速率,故定理得證.L5數(shù)值結(jié)果最后根據(jù)線(xiàn)性不等式約束優(yōu)化問(wèn)題的內(nèi)點(diǎn)回代信賴(lài)域算法,應(yīng)用數(shù)學(xué)軟件MNOPNQ編寫(xiě)-20,=0T2,=0T8,=0TW5,=0T2,=0T8,=2.取最大信賴(lài)=0T4,=0T5,=10XXXSUV121232221T()()=10000(-c)+(1-c),eQr_Yabc

41、c211程序用于解下列線(xiàn)性不等式約束優(yōu)化問(wèn)題.為了檢驗(yàn)算法的有效性,選取參數(shù)如下Re+d,-dece+d.-decO12fgf其最優(yōu)解為c=(1,1),(=0.bc)2244+10)+5(-c)+(-2)+10(-c),2T()()=(PhePPYabccccccc12342314.-dece+di=1,j,4Oifgf其最優(yōu)解為c=(0,0,0,0),(=0.bc)表1數(shù)值結(jié)果編號(hào)123456q8W10k2422224223l2422224222m=0np843452255031558816518m=50m=12243T()=(10(-c)+(-1),Yabccc121.-dece+d,-d

42、ece+dO12fgf其最優(yōu)解為c=(1,1),(=0.bc)張樂(lè)瑛等:線(xiàn)性不等式約束優(yōu)化的弧線(xiàn)路徑信賴(lài)域算法4.=minf3(+1)+x,x123.1,0stxx12457*T*其最優(yōu)解為x=(1,0),(=.fx)322221225.=0.112+x+,minf12+44xxx112.1x3,1x3st1226.()=s(+x)+(-x)-1.5+2.5+1,minfxinxxxx121212.-1.5x4,-3x3st12T*其最優(yōu)解為x=-+,-,(.fx)323232222227.()()=100(-x)+(1-x)+90(-x)+(1-x)+Woodminfxxx211433()2

43、210.1(-1)+(-1)+19.8(-1)(-1)xxxx2424.-10x10i=1,4,sti*T*其最優(yōu)解為x=(1,1,1,1),(=0.fx)228.()=4(-5)+(-6),minfxxx12+x>0,-x+x0.stx1212*T*其最優(yōu)解為x=(5,6),(=0.fx)2229.()=100(-x)+(1-x),minfxx211.x+x+0.10,-x+x+0.10st121233*T*其最優(yōu)解為x=(1,1),(=0.fx)2210.=0.01+x-100minfx12.10-x-100,2x50,-50x50stx1212表中m,n表示系數(shù)矩陣A的行數(shù)和列數(shù),

44、NF表示目標(biāo)函數(shù)的計(jì)算次數(shù),NG表示其梯度函數(shù)的計(jì)算次數(shù),且M表示非單調(diào)的控制參數(shù).數(shù)值結(jié)果表示所提供的算法是有效和可靠的,非單調(diào)搜索略?xún)?yōu)于單調(diào)搜索.參考文獻(xiàn):1C,olemanTFLiY.Atrustregionandaffinescalinginteriorpointmethodfornonconvex.,2000,88:1-31.minimizationwithlinearinequalityconstraintsJMathProg2Z.huDCurvilinearpathsandtrustregionmethodswithnonmonotonicbacktrackingtechniquefor.,2001,19:241-258.unconstrainedoptimizationJJofComputationMathematics3C,N.,G.T-.S,onnARouldIM,TointPhLrustRegionMethodsMIAM,P