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

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

2、頁(yè)第六頁(yè)，共42頁(yè)。點(diǎn)。稱(chēng)條件的點(diǎn)滿(mǎn)足互補(bǔ)松弛條件。那么，可微，如果在TKxTKmixgumiuxguxfixgxxguxfiiimiiiiIiii*1*)(,2, 10)(,2, 100)()()(,0)()(第6頁(yè)/共42頁(yè)第七頁(yè)，共42頁(yè)。0),(0),(042),(05),(.)2()3(),(min22141213212122221211222121xxxgxxxgxxxxgxxxxgtsxxxxf例123412g1=0g2=0g4=0 x1g3=0 x2x*g2(x*)g1(x*)-f(x*)(3,2)T第7頁(yè)/共42頁(yè)第八頁(yè)，共42頁(yè)。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使計(jì)算可得起作用集），交點(diǎn)（點(diǎn)在10,01)(21)2(,22)(,)2(2)3(2)(43221121gxggxxxgxxxf第8頁(yè)/共42頁(yè)第九頁(yè)，共42頁(yè)。0)(,2,1,00)()(xgumiuxguxfiiimiii個(gè)未知量個(gè)方程66)6(0)5(0)4(0)42()3(0)5(0,)2(022)2(2)1(02)3(224132122221143214221232111xuxuxxuxx

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

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

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

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

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

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

10、(0)(000)(111dNdBdddrxdrdrrxuxxuuxxurNBxfxfuuNvxfBxfvuBvxfxuuuAvxfTKxNBNjjjjjjjjjjjNTNBBBTBTNTBTNTNTNTTNTBTTBTTBTTTT第21頁(yè)/共42頁(yè)第二十二頁(yè)，共42頁(yè)。x(1)S, k=1k=k+1Jk=j|xj為x(k)中最大m個(gè)正分量(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點(diǎn) 0,0,jjjjjjrrxrrd當(dāng)當(dāng)0. .)(

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

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

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

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

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