約束最優(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 1 kuhn-tucker 條件條件一、等式約束性問題的最優(yōu)性條件：一、等式約束性問題的最優(yōu)性條件： 考慮考慮 min f(x) s.t. h(x)=0 回顧高等數(shù)學中所學的條件極值：回顧高等數(shù)學中所學的條件極值： 問題問題 求求z=f(x,y)極值極值 min f(x,y) 在在(x,y)=0的條件下。的條件下。 s.t. (x,y)=0 引入引入lagrange乘子：乘子： lagrange函數(shù)函數(shù) l(x,y;)= f

2、(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 推廣到多元情況，可得到對于推廣到多元情況，可得到對于(fh)的情況：的情況： min f(x) s.t. hj(x)=0 j=1,2, ,l 若若x*是是(fh)的的l.opt. ,則存在則存在* rl使使 矩陣形式：矩陣形式：分量形式：ljjjxhxf1*0)()(0)()(*xxhxf一

3、、等式約束性問題的最優(yōu)性條件：一、等式約束性問題的最優(yōu)性條件： (續(xù)續(xù)) 幾何意義是明顯的：考慮一個約束的情況：幾何意義是明顯的：考慮一個約束的情況： 最優(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*點處的起作用集（緊約束集）。點處的起作用集（緊約束集）。 如果如果x*是是l.opt. ,對每一個約束函數(shù)來說，只有當它是起作用約對每一個約束函數(shù)來說，只有當它是起作用約束時，才產(chǎn)生影響，如：束時，才產(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、在 點使點使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*點處的起作用集，設(shè)點處的起作用集，設(shè)f, gi(x) ,i i在在x*點可微，點可微， gi(x) ,i i在在x*點連續(xù)。點連續(xù)。 向量組向量組gi(x*), i i線性無關(guān)

6、。線性無關(guān)。 如果如果x*-l.opt. 那么，那么， u*i0, i i使使點。稱條件的點滿足互補松弛條件。那么，可微，如果在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*)g

7、1(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使計算可得起作用集），交點（點在 10,01)(21)2(,22)(,)2(2)3(2)(43221121gxggxxxgxxxf二、不等式約束問題的二、不等式約束問題的khun-tucker條件：條件： （續(xù)

8、）（續(xù)）0)(,2,1,00)()(xgumiuxguxfiiimiii個未知量個方程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點出現(xiàn)在下列情況：點出現(xiàn)在下列情況： 兩約束曲線的交點：兩約束曲線的交點：g1與與g2,g1與與g3,g1與與g4,g2與與g3,g2與與g4,g3與與g4。 目標函數(shù)與一條曲線相交的情況：目標函數(shù)與一條曲線相交的情

9、況： g1，g2, g3, g4 對每一個情況求得滿足對每一個情況求得滿足(1)(6)的點的點(x1,x2)t及乘子及乘子u1,u2,u3,u4,驗驗證當滿足可得，且證當滿足可得，且ui 0時，即為一個時，即為一個k-t點。點。下面舉幾個情況：下面舉幾個情況： g1與與g2交點：交點：x=(2,1)ts ,i=1,2 則則u3=u4=0 解解點。是故得tkxuuuxuxuxuxt)1 ,2(032,31022)2(202)3(22122122111二、不等式約束問題的二、不等式約束問題的khun-tucker條件：條件： （續(xù)）（續(xù)）點。故不是不滿足點；故不是得交點：與tkgstksxxxxg

10、gttt,0,)5,0(,)5,0()5,0(00521222131.04, 060)20(20)30(204 , 3)0 , 0(:,43432143點故非得解故交點tkuuuuuuisxggt二、不等式約束問題的二、不等式約束問題的khun-tucker條件：條件： （續(xù)）（續(xù)）034. 04742),(),(0502)2(202)3(20,10)()(135132013452121320134522211221114321xxgtksxxuxxuxxuuuixgxf點故均不是得解則相切的情況：與目標函數(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ù))點。是則及為凸規(guī)劃，滿足可微性若亦可微，那么在如果還有那么如果tkxoptlxcqfghmixguuxhvxguxfxiixgxhvxguxfljrviiuoptlxiiiljjjmiiiil

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

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

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

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

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

17、in)(ddddxjjkj否則當一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法 （續(xù)）（續(xù)）.,:,:0)(. .)(min0,552. .32min.21212121212221babarbarrhrrfbxaxhtsxfpgrgxxxxxxtsxxxxxxexnlnn，且的分量允許連續(xù)可微。其中：）（標準形式）二、廣義既約梯度法（見書（略）二、廣義既約梯度法二、廣義既約梯度法 （續(xù)）（續(xù)）tttytztzyyzyzylnlzxhyxhxfxfryxhbyabbbaaarzryzyxsxbxaxhxs)()()()()(2,1,0)(|1廣義既約梯度：非奇異使記使分解非退化假設(shè)

18、：記二、廣義既約梯度法二、廣義既約梯度法 （續(xù)）（續(xù)）點。時為下降可行方向；當同樣有結(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ù)。的典型取法：輔助問題輔助函數(shù)不可行可行懲罰項可構(gòu)造取時當時當時當時當其中：ppttttttxxfxxfxttttttpp.22),(,22214),(,22,2,4) 14()2()()(),(:2)()()(min,2, 02,)2(2, 0max)(:02. .min.2222optxxxgxxxgxxxxxxxxxxfxgxxfxxfxxxxxxtsxex 故的最小值點時當?shù)鸟v點時當輔助函數(shù)解析解時當如圖二次罰函數(shù)2.罰函數(shù)法罰函數(shù)法： （fgh）的單調(diào)非增函數(shù)關(guān)于

20、的單調(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 則使若推論：在定理條件下，且那么，有即單調(diào)增加的正數(shù)列在引理假設(shè)下，設(shè)存在定理：算法：算法：初始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(