約束最優(yōu)化方法學(xué)習(xí)教案

1、會計學(xué)1約束約束(yush)最優(yōu)化方法最優(yōu)化方法第一頁，共42頁。(fgh)(fh)即第1頁/共42頁第二頁，共42頁。分量形式：ljjjxhxf1*0)()(0)()(*xxhxf第2頁/共42頁第三頁，共42頁。-f( ) h( )h(x)-f(x*)h(x*)這里 x* -l.opt. f(x*)與h(x*) 共線，而非l.opt.f( )與h( )不共線。hjjjxhxf1*)(*)(第3頁/共42頁第四頁，共42頁。(fg)g2(x)=0 x*g1(x)=0g1(x*)=0, g1為起作用約束第4頁/共42頁第五頁，共42頁。g( )-f( )X*-f(x*)g(x*)第5頁/共42

2、頁第六頁，共42頁。點。稱條件的點滿足互補松弛條件。那么，可微，如果在TKxTKmixgumiuxguxfixgxxguxfiiimiiiiIiii*1*)(,2, 10)(,2, 100)()()(,0)()(第6頁/共42頁第七頁，共42頁。0),(0),(042),(05),(.)2()3(),(min22141213212122221211222121xxxgxxxgxxxxgxxxxgtsxxxxf例123412g1=0g2=0g4=0 x1g3=0 x2x*g2(x*)g1(x*)-f(x*)(3,2)T第7頁/共42頁第八頁，共42頁。0)()()()2,2()2(2),3(2(

3、)()2, 1()()2,4()2,2()(2, 1120),(0),(232131*32*231*1*2*1*2211212211*xgxgxfuuxxxfxgxxxgIxxgxxgxTTTTTT使計算可得起作用集），交點（點在10,01)(21)2(,22)(,)2(2)3(2)(43221121gxggxxxgxxxf第8頁/共42頁第九頁，共42頁。0)(,2,1,00)()(xgumiuxguxfiiimiii個未知量個方程66)6(0)5(0)4(0)42()3(0)5(0,)2(022)2(2)1(02)3(224132122221143214221232111xuxuxxuxx

4、uuuuuuuxuxuuxux第9頁/共42頁第十頁，共42頁。點。是故得TKxuuuxuxuxuxT)1 , 2(032,31022)2(202)3(22122122111第10頁/共42頁第十一頁，共42頁。點。故不是不滿足點；故不是得交點：與TKgSTKSxxxxggTTT,0,)5,0(,)5,0()5,0(00521222131.04, 060)20(20)30(204, 3)0 , 0(:,43432143點故非得解故交點TKuuuuuuISxggT第11頁/共42頁第十二頁，共42頁。034. 04742),(),(0502)2(202)3(20,10)()(1351320134

5、52121320134522211221114321xxgTKSxxuxxuxxuuuIxgxf點故均不是得解則相切的情況：與目標函數(shù)第12頁/共42頁第十三頁，共42頁。線性無關(guān)。，向量組約束規(guī)格）。（的某鄰域內(nèi)連續(xù)可微。在）（，連續(xù)，在可微在設(shè)為起作用集。，問題定理：)(,),(,),)(, 2 , 1)(,)(,0)(, 0)(|)(, 2 , 10)(, 2 , 10)(. .)(min)(1xhxhIixgCQxljhxIixgxIixgIxhxgxSxfghljxhmixgt sxffghlijiiji第13頁/共42頁第十四頁，共42頁。點。是則及為凸規(guī)劃，滿足可微性若亦可微，那

6、么在如果還有那么如果TKxoptlxCQfghmixguuxhvxguxfxIixgxhvxguxfljRvIiuoptlxiiiljjjmiiiiljjjIiiiji.)(,2, 10)(00)()()()(0)()()(,2, 1,0.111第14頁/共42頁第十五頁，共42頁。為既約梯度稱相應(yīng)非基變量基變量，使非奇異，存在分解：、既約梯度及搜索方向）個正分量。（的每個極點都有列線性無關(guān)；的任意、非退化假設(shè)：的多面體同可行集：秩）、問題：（NBxfxfrxfxfxfxxxxxxxBNBASxbBmSmASLPxbAxxSRbmAAxbAxtsxfPTBTNTNNBNBNBNBmmmnm11

7、)()(,)()()(0, 0,30212.)(0,|,0. .)(min1第15頁/共42頁第十六頁，共42頁。為可行方向。故即有）時，（則取由故又）時，（當為可行方向，即時當為可行方向?qū)ふ蚁陆悼尚蟹较颍篸SdxdxddxbAxdxAAdddxAdbAxbAdAxdxAdproofxdAdddjjjjjjjj.000|min.)(,0,0.0,00,0,)(0,0:.0,00)1(第16頁/共42頁第十七頁，共42頁。0)()()()()()()(0)(:)2(0, 00.1111NTNNTBTNNTNNTBNTNBTBTTNBjjNNBNBNBNBdrdNBxfxfdxfNdBxfdxfd

8、xfdxfdxfdNdBddxddNdBdNdBdddNBAdddd分解：要求下降方向及中，對應(yīng)可行，可取在故要使得到根據(jù)考慮分解第17頁/共42頁第十八頁，共42頁。點。若的下降可行方向；為若那么方向定理：按上述方案產(chǎn)生的分量。為其中：時當時當?shù)姆桨赶虻囊环N產(chǎn)生下降可行方、結(jié)合TKxdPdddNdBdrrrrxrrdddNBNjjjjjjjN02)(, 01,00:)2() 1 ()3(1第18頁/共42頁第十九頁，共42頁。證畢。非零，于是或至少一個由于又保證故總有對.0,000,0,0.0000001.221NTNjjjjjjjjjjNjjjNTNNBjjjjjjjjjdrrxrdrrx

9、rrdrdrdrAdNdBddrxdrrdrxproof第19頁/共42頁第二十頁，共42頁。得證。即條件：可得取故時，當原因：則取矛盾；與那么，反證。若存在可得000)()(0)()(0)(,)(); 0000, 0, 0)00)(0:0)02111xuuuNBxfxfuBBxfxfuAvxfTKRBxfviiixrxdrruxuxuruuiidrdNjrridTTNTBTNTBTBTBTTTnTBTjjjjjNNNTNTNNBjjjjN第20頁/共42頁第二十一頁，共42頁。證畢。也就是即故恒有時當時當，即由第三式得：由第一式得：點即.00, 0, 000000000, 0)()(0)()

10、(0)(000)(111dNdBdddrxdrdrrxuxxuuxxurNBxfxfuuNvxfBxfvuBvxfxuuuAvxfTKxNBNjjjjjjjjjjjNTNBBBTBTNTBTNTNTNTTNTBTTBTTBTTTT第21頁/共42頁第二十二頁，共42頁。x(1)S, k=1k=k+1Jk=j|xj為x(k)中最大m個正分量(fn ling)之一B=,aj(jJk),N=,aj(jJk),YNT=NfT(x(k)- BfT(x(k)B-1NdB=-B-1NdN解得 x(k+1)=x(k)+kdd=0?YNStop;x(k)K-T點 0,0,jjjjjjrrxrrd當當0. .)(

11、min)(t sdxfk0,0,0|/min)(ddddxjjkj否則當?shù)?2頁/共42頁第二十三頁，共42頁。.,:,:0)(. .)(min0,552. .32min.21212121212221babaRbaRRhRRfbxaxhtsxfPGRGxxxxxxtsxxxxxxExnlnn，且的分量允許連續(xù)可微。其中：）（標準形式）二、廣義既約梯度法（見書（略）第23頁/共42頁第二十四頁，共42頁。TTTyTzTzyyzyzylnlzxhyxhxfxfryxhbyabbbaaaRzRyzyxSxbxaxhxS)()()()()(2,1,0)(|1廣義既約梯度：非奇異使記使分解非退化假設(shè)：記

12、第24頁/共42頁第二十五頁，共42頁。點。時為下降可行方向；當同樣有結(jié)論：或且或且令取方向：TKxdddzxhyxhdJirJidrbzraziJzTTyiziziziiizii0201)()(0)(0)(0)(|0)(|1第25頁/共42頁第二十六頁，共42頁。0)(0)()()()(:0)(:0)(.:)(min)(.1)(11xxxxxhxgxRRhxhRRgxgtsRRfxffghTechniqueonMinimizatinedUnconstraiSequentialSUMTljjmiilnmnn有不滿足約束的有目的：使?jié)M足約束的構(gòu)造罰函數(shù)：罰函數(shù)概念：序列無約束最優(yōu)化方法第26頁/

13、共42頁第二十七頁，共42頁。)2.(22|)(, 0max)()(),()()(min)()(0)(, 0000,0)(000,0)(次是最低次的光滑函數(shù)常用：因次罰函數(shù)時，稱當為正整數(shù)。的典型取法：輔助問題輔助函數(shù)不可行可行懲罰項可構(gòu)造取時當時當時當時當其中：ppttttttxxfxxfxttttttpp第27頁/共42頁第二十八頁，共42頁。.22),(,22214),(,22,2,4) 14()2()()(),(:2)()()(min,2, 02,)2(2, 0max)(:02. .min.2222optxxxgxxxgxxxxxxxxxxfxgxxfxxfxxxxxxtsxEx 故的

14、最小值點時當?shù)鸟v點時當輔助函數(shù)解析解時當如圖二次罰函數(shù)第28頁/共42頁第二十九頁，共42頁。第29頁/共42頁第三十頁，共42頁。的單調(diào)非增函數(shù)關(guān)于的單調(diào)非降函數(shù)；關(guān)于）（則）（使：，再設(shè)為罰函數(shù)，連續(xù)。連續(xù)，引理：設(shè)下確界）（定義：0)(0)(),(20|sup| )(inf1)()(,0)(,)()(infxxfSxxfxxfDxxhgfxxfxx第30頁/共42頁第三十一頁，共42頁。.,0)(00)(.2)(lim0| )(sup| )(inf1.0,0)(,0)(|),()(21optxxoptxSxxfxxxhxgxSfghxkkkk 則使若推論：在定理條件下，且那么，有即單調(diào)增

15、加的正數(shù)列在引理假設(shè)下，設(shè)存在定理：第31頁/共42頁第三十二頁，共42頁。初始x(1), 10, 1, 0,k=1以x(k)為初始點，解min f(x)+ (x)得到，x(k+1)k (x(k+1)0, 0,1, 0,k=1min f(x)+ k B(x)s.t. x S0從x(k）出發(fā)，求得，x(k+1)k B(x(k+1) yes停；x(k+1)解Nok+1 = k k=k+1第37頁/共42頁第三十八頁，共42頁。轉(zhuǎn)置否則停，說明若；轉(zhuǎn)為初始內(nèi)點，得到解以用閘函數(shù)法求解：；轉(zhuǎn)使否則，取為初始內(nèi)點。則若令；轉(zhuǎn)求初始內(nèi)點：2, 1.,0)(44,0)(.)(min33|)(max)(,0)(|22, 1,10)1()1()()()()()()1(kkSxgxxIixgtsxgIixgxgjxIxgiIkxkjkkkijkkikjkkkik第38頁/共42頁第三十九頁，共42頁。: )(:0)(. .:)(min)(xfLagrangeRDDxRRhxhtsRRfxffhDnlnn函數(shù)代替用約束構(gòu)成。是一個集合，常由簡單第39頁/共42頁第四十頁，共42頁。及調(diào)整否則及乘子得到解若得到求解為罰因子。為乘子，其中：乘子罰函數(shù)：