等式約束優(yōu)化

1、約束最優(yōu)化方法約束最優(yōu)化方法 問題問題 min f(x) s.t. g(x) 0 分量形式略分量形式略 h(x)=0 約束集約束集 S=x|g(x) 0 , h(x)=0 6.1 Kuhn-Tucker 條件條件一、等式約束性問題的最優(yōu)性條件：一、等式約束性問題的最優(yōu)性條件： 考慮考慮 min f(x) s.t. h(x)=0 回顧高等數(shù)學(xué)中所學(xué)的條件極值：回顧高等數(shù)學(xué)中所學(xué)的條件極值： 問題問題 求求z=f(x,y)極值極值 min f(x,y) 在在(x,y)=0的條件下。的條件下。 S.t. (x,y)=0 引入引入Lagrange乘子：乘子： Lagrange函數(shù)函數(shù) L(x,y;)=

2、 f(x,y)+ (x,y)(fgh)(fh)即一、等式約束性問題的最優(yōu)性條件：一、等式約束性問題的最優(yōu)性條件： (續(xù)續(xù))若若(x*,y*)是條件極值，則存在是條件極值，則存在* ，使，使 fx(x*,y*)+ * x (x*,y*) =0 fy(x*,y*)+ * y(x*,y*) =0 (x*,y*)=0 推廣到多元情況，可得到對(duì)于推廣到多元情況，可得到對(duì)于(fh)的情況：的情況： min f(x) s.t. hj(x)=0 j=1,2, ,l 若若x*是是(fh)的的l.opt. ,則存在則存在* Rl使使 矩陣形式：矩陣形式：分量形式：ljjjxhxf1*0)()(0)()(*xxhx

3、f一、等式約束性問題的最優(yōu)性條件：一、等式約束性問題的最優(yōu)性條件： (續(xù)續(xù)) 幾何意義是明顯的：考慮一個(gè)約束的情況：幾何意義是明顯的：考慮一個(gè)約束的情況： 最優(yōu)性條件即：最優(yōu)性條件即：-f( ) h( )h(x)-f(x*)h(x*)這里 x* -l.opt. f(x*)與h(x*) 共線，而非l.opt.f( )與h( )不共線。hjjjxhxf1*)(*)(二、不等式約束問題的二、不等式約束問題的Khun-Tucker條件：條件：考慮問題考慮問題 min f(x) s.t. gi(x) 0 i=1,2, ,m 設(shè)設(shè) x*S=x|gi(x) 0 i=1,2, ,m 令令 I=i| gi(x*

4、) =0 i=1,2, ,m 稱稱I為為 x*點(diǎn)處的起作用集（緊約束集）。點(diǎn)處的起作用集（緊約束集）。 如果如果x*是是l.opt. ,對(duì)每一個(gè)約束函數(shù)來說，只有當(dāng)它是起作用約對(duì)每一個(gè)約束函數(shù)來說，只有當(dāng)它是起作用約束時(shí)，才產(chǎn)生影響，如：束時(shí)，才產(chǎn)生影響，如：(fg)g2(x)=0 x*g1(x)=0g1(x*)=0, g1為起作用約束二、不等式約束問題的二、不等式約束問題的Khun-Tucker條件：條件： （續(xù)）（續(xù)） 特別特別 有如下特征：如圖有如下特征：如圖 在在x* ： f(x*)+u* g(x*)=0 u*0 要使函數(shù)值下降，必須使要使函數(shù)值下降，必須使g(x)值變大，則值變大，則

5、 在在 點(diǎn)使點(diǎn)使f(x)下降的方向（下降的方向（- f( ) 方向）指向約束集合內(nèi)方向）指向約束集合內(nèi)部，因此部，因此不是不是l.opt. l.opt. 。g( )-f( )X*-f(x*)g(x*)二、不等式約束問題的二、不等式約束問題的Khun-Tucker條件：條件： （續(xù)）（續(xù)） 定理（最優(yōu)性必要條件）：定理（最優(yōu)性必要條件）： （K-T條件）條件） 問題問題(fg), 設(shè)設(shè)S=x|gi(x) 0,x*S,I為為x*點(diǎn)處的起作用集，設(shè)點(diǎn)處的起作用集，設(shè)f, gi(x) ,i I在在x*點(diǎn)可微，點(diǎn)可微， gi(x) ,i I在在x*點(diǎn)連續(xù)。點(diǎn)連續(xù)。 向量組向量組gi(x*), i I線性

6、無關(guān)。線性無關(guān)。 如果如果x*-l.opt. 那么，那么， u*i0, i I使使點(diǎn)。稱條件的點(diǎn)滿足互補(bǔ)松弛條件。那么，可微，如果在TKxTKmixgumiuxguxfixgxxguxfiiimiiiiIiii*1*)(,2, 10)(,2, 100)()()(,0)()(二、不等式約束問題的二、不等式約束問題的Khun-Tucker條件：條件： （續(xù)）（續(xù)）0),(0),(042),(05),(.)2()3(),(min22141213212122221211222121xxxgxxxgxxxxgxxxxgtsxxxxf例123412g1=0g2=0g4=0 x1g3=0 x2x*g2(x*

7、)g1(x*)-f(x*)(3,2)T二、不等式約束問題的二、不等式約束問題的Khun-Tucker條件：條件： （續(xù)）（續(xù)）用用K-T條件求解：條件求解：0)()()()2,2()2(2),3(2()()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二、不等式約束問題的二、不等式約束問題的Khun-Tucker條件：條件：

8、（續(xù)）（續(xù)）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(224132122221143214221232111xuxuxxuxxuuuuuuuxuxuuxux二、不等式約束問題的二、不等式約束問題的Khun-Tucker條件：條件： （續(xù)）（續(xù)）可能的可能的K-T點(diǎn)出現(xiàn)在下列情況：點(diǎn)出現(xiàn)在下列情況： 兩約束曲線的交點(diǎn)：兩約束曲線的交點(diǎn)：g1與與g2,g1與與g3,g1與與g4,g2與與g3,g2與與g4,g3與與g4。 目標(biāo)函數(shù)與一條曲線相交的情況：目標(biāo)函數(shù)與一條曲線相交

9、的情況： g1，g2, g3, g4 對(duì)每一個(gè)情況求得滿足對(duì)每一個(gè)情況求得滿足(1)(6)的點(diǎn)的點(diǎn)(x1,x2)T及乘子及乘子u1,u2,u3,u4,驗(yàn)驗(yàn)證當(dāng)滿足可得，且證當(dāng)滿足可得，且ui 0時(shí)，即為一個(gè)時(shí)，即為一個(gè)K-T點(diǎn)。點(diǎn)。下面舉幾個(gè)情況：下面舉幾個(gè)情況： g1與與g2交點(diǎn)：交點(diǎn)：x=(2,1)TS ,I=1,2 則則u3=u4=0 解解點(diǎn)。是故得TKxuuuxuxuxuxT)1 ,2(032,31022)2(202)3(22122122111二、不等式約束問題的二、不等式約束問題的Khun-Tucker條件：條件： （續(xù)）（續(xù)）點(diǎn)。故不是不滿足點(diǎn)；故不是得交點(diǎn)：與TKgSTKSxxx

10、xggTTT,0,)5,0(,)5,0()5,0(00521222131.04, 060)20(20)30(204 , 3)0 , 0(:,43432143點(diǎn)故非得解故交點(diǎn)TKuuuuuuISxggT二、不等式約束問題的二、不等式約束問題的Khun-Tucker條件：條件： （續(xù)）（續(xù)）034. 04742),(),(0502)2(202)3(20,10)()(135132013452121320134522211221114321xxgTKSxxuxxuxxuuuIxgxf點(diǎn)故均不是得解則相切的情況：與目標(biāo)函數(shù)三、一般約束問題的三、一般約束問題的Kuhn-Tucker 條件條件線性無關(guān)。，向

11、量組約束規(guī)格）。（的某鄰域內(nèi)連續(xù)可微。在）（，連續(xù)，在可微在設(shè)為起作用集。，問題定理：)(,),(,),)(, 2 , 1)(,)(,0)(, 0)(|)(, 2 , 10)(, 2 , 10)(. .)(min)(1xhxhIixgCQxljhxIixgxIixgIxhxgxSxfghljxhmixgt sxffghlijiiji三、一般約束問題的三、一般約束問題的Kuhn-Tucker 條件條件 (續(xù)續(xù))點(diǎn)。是則及為凸規(guī)劃，滿足可微性若亦可微，那么在如果還有那么如果TKxoptlxCQfghmixguuxhvxguxfxIixgxhvxguxfljRvIiuoptlxiiiljjjmiii

12、iljjjIiiiji.)(,2, 10)(00)()()()(0)()()(,2, 1,0.111一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法為既約梯度稱相應(yīng)非基變量基變量，使非奇異，存在分解：、既約梯度及搜索方向）個(gè)正分量。（的每個(gè)極點(diǎn)都有列線性無關(guān)；的任意、非退化假設(shè)：的多面體同可行集：秩）、問題：（NBxfxfrxfxfxfxxxxxxxBNBASxbBmSmASLPxbAxxSRbmAAxbAxtsxfPTBTNTNNBNBNBNBmmmnm11)()(,)()()(0, 0,30212.)(0,|,0. .)(min1一、解線性約束問題的既約梯度法一、解線性約束問題

13、的既約梯度法 （續(xù)）（續(xù)）為可行方向。故即有）時(shí)，（則取由故又）時(shí)，（當(dāng)為可行方向，即時(shí)當(dāng)為可行方向?qū)ふ蚁陆悼尚蟹较颍篸SdxdxddxbAxdxAAdddxAdbAxbAdAxdxAdproofxdAdddjjjjjjjj.000|min.)(,0,0.0,00,0,)(0,0:.0,00)1(一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法 （續(xù)）（續(xù)）0)()()()()()()(0)(:)2(0, 00.1111NTNNTBTNNTNNTBNTNBTBTTNBjjNNBNBNBNBdrdNBxfxfdxfNdBxfdxfdxfdxfdxfdNdBddxddNdBdNdBdd

14、dNBAdddd分解：要求下降方向及中，對(duì)應(yīng)可行，可取在故要使得到根據(jù)考慮分解一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法 （續(xù)）（續(xù)）點(diǎn)。若的下降可行方向；為若那么方向定理：按上述方案產(chǎn)生的分量。為其中：時(shí)當(dāng)時(shí)當(dāng)?shù)姆桨赶虻囊环N產(chǎn)生下降可行方、結(jié)合TKxdPdddNdBdrrrrxrrdddNBNjjjjjjjN02)(, 01,00:)2() 1 ()3(1一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法 （續(xù)）（續(xù)）證畢。非零，于是或至少一個(gè)由于又保證故總有對(duì).0,000,0,0.0000001.221NTNjjjjjjjjjjNjjjNTNNBjjjjjjjj

15、jdrrxrdrrxrrdrdrdrAdNdBddrxdrrdrxproof得證。即條件：可得取故時(shí)，當(dāng)原因：則取矛盾；與那么，反證。若存在可得000)()(0)()(0)(,)(); 0000, 0, 0)00)(0:0)02111xuuuNBxfxfuBBxfxfuAvxfTKRBxfviiixrxdrruxuxuruuiidrdNjrridTTNTBTNTBTBTBTTTnTBTjjjjjNNNTNTNNBjjjjN一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法 （續(xù)）（續(xù)）證畢。也就是即故恒有時(shí)當(dāng)時(shí)當(dāng)，即由第三式得：由第一式得：點(diǎn)即.00,0,000000000,0)()

16、(0)()(0)(000)(111dNdBdddrxdrdrrxuxxuuxxurNBxfxfuuNvxfBxfvuBvxfxuuuAvxfTKxNBNjjjjjjjjjjjNTNBBBTBTNTBTNTNTNTTNTBTTBTTBTTTT算法：算法：x(1)S, k=1k=k+1Jk=j|xj為x(k)中最大m個(gè)正分量之一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. .)(min)(t sdxfk0,0,0|

17、/min)(ddddxjjkj否則當(dāng)一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法 （續(xù)）（續(xù)）.,:,:0)(. .)(min0,552. .32min.21212121212221babaRbaRRhRRfbxaxhtsxfPGRGxxxxxxtsxxxxxxExnlnn，且的分量允許連續(xù)可微。其中：）（標(biāo)準(zhǔn)形式）二、廣義既約梯度法（見書（略）二、廣義既約梯度法二、廣義既約梯度法 （續(xù)）（續(xù)）TTTyTzTzyyzyzylnlzxhyxhxfxfryxhbyabbbaaaRzRyzyxSxbxaxhxS)()()()()(2,1,0)(|1廣義既約梯度：非奇異使記使分解非退化

18、假設(shè)：記二、廣義既約梯度法二、廣義既約梯度法 （續(xù)）（續(xù)）點(diǎn)。時(shí)為下降可行方向；當(dāng)同樣有結(jié)論：或且或且令取方向：TKxdddzxhyxhdJirJidrbzraziJzTTyiziziziiizii0201)()(0)(0)(0)(|0)(|10)(0)()()()(:0)(:0)(.:)(min)(.1)(11xxxxxhxgxRRhxhRRgxgtsRRfxffghTechniqueonMinimizatinedUnconstraiSequentialSUMTljjmiilnmnn有不滿足約束的有目的：使?jié)M足約束的構(gòu)造罰函數(shù)：罰函數(shù)概念：序列無約束最優(yōu)化方法)2.(22|)(, 0max)

19、()(),()()(min)()(0)(, 0000,0)(000,0)(次是最低次的光滑函數(shù)常用：因次罰函數(shù)時(shí)，稱當(dāng)為正整數(shù)。的典型取法：輔助問題輔助函數(shù)不可行可行懲罰項(xiàng)可構(gòu)造取時(shí)當(dāng)時(shí)當(dāng)時(shí)當(dāng)時(shí)當(dāng)其中：ppttttttxxfxxfxttttttpp.22),(,22214),(,22,2,4) 14()2()()(),(:2)()()(min,2, 02,)2(2, 0max)(:02. .min.2222optxxxgxxxgxxxxxxxxxxfxgxxfxxfxxxxxxtsxEx 故的最小值點(diǎn)時(shí)當(dāng)?shù)鸟v點(diǎn)時(shí)當(dāng)輔助函數(shù)解析解時(shí)當(dāng)如圖二次罰函數(shù)2.罰函數(shù)法罰函數(shù)法： （fgh）的單調(diào)非增函數(shù)

20、關(guān)于的單調(diào)非降函數(shù)；關(guān)于）（則）（使：，再設(shè)為罰函數(shù)，連續(xù)。連續(xù)，引理：設(shè)下確界）（定義：0)(0)(),(20|sup| )(inf1)()(,0)(,)()(infxxfSxxfxxfDxxhgfxxfxx2.罰函數(shù)法罰函數(shù)法： （續(xù)）（續(xù)）.,0)(00)(.2)(lim0|)(sup|)(inf1.0,0)(,0)(|),()(21optxxoptxSxxfxxxhxgxSfghxkkkk 則使若推論：在定理?xiàng)l件下，且那么，有即單調(diào)增加的正數(shù)列在引理假設(shè)下，設(shè)存在定理：算法：算法：初始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(