約束最優(yōu)化方法ppt課件

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)()

3、(*xxhxf一、等式約束性問題的最優(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 設設 x*S=x|gi(x) 0 i=1,2, ,m 令令 I=i|

4、 gi(x*) =0 i=1,2, ,m 稱稱I為為 x*點處的起作用集緊約束集。點處的起作用集緊約束集。 假設假設x*是是l.opt. ,對每一個約束函數(shù)來說，只需當它是起作用約對每一個約束函數(shù)來說，只需當它是起作用約束時，才產生影響，如：束時，才產生影響，如：(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( ) 方向指向約束集合內方向指向約束集合內部，因此不是部，因此不是l.opt. 。g( )-f( )X*-f(x*)g(x*)二、不等式約束問題的二、不等式約束問題的Khun-Tucker條件：條件： 續(xù)續(xù) 定理最優(yōu)性必要條件：定理最優(yōu)性必要條件： K-T條件條件 問題問題(fg), 設設S=x|gi(x) 0,x*S,I為為x*點處的起作用集，設點處的起作用集，設f, gi(x) ,i I在在x*點可微，點可微， gi(x) ,i I在在x*點延續(xù)。點延續(xù)。 向量組向量組gi(x*), i I線性無關。線性無關。 假設假設x*-l.opt.

6、 那么，那么， 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*)g1(x*)-f(x*)(3,2)T二、不等式約束

7、問題的二、不等式約束問題的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ù)續(xù)0)(,2,1,00)()(xgumiuxguxfiii

8、miii個未知量個方程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點出如今以下情況：點出如今以下情況： 兩約束曲線的交點：兩約束曲線的交點：g1與與g2,g1與與g3,g1與與g4,g2與與g3,g2與與g4,g3與與g4。 目的函數(shù)與一條曲線相交的情況：目的函數(shù)與一條曲線相交的情況： g1，g2, g3, g4 對每一個情況求得滿足對每一個情況求得滿

9、足(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ù)點。故不是不滿足點；故不是得交點：與TKgSTKSxxxxggTTT,0,)5,0(,)5,0()5,0(00521222131.04,

10、 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ī)格）。（的某鄰域內連續(xù)可微。在）（，連續(xù)，在可微在設為起作用集。，問題定理：)

11、(,),(,),)(, 2 , 1)(,)(,0)(, 0)(|)(, 2 , 10)(, 2 , 10)(. .)(min)(1xhxhIixgCQxljhxIixgxIixgIxhxgxSxfghljxhmixgt sxffghlijiiji三、普通約束問題的三、普通約束問題的Kuhn-Tucker 條件條件 (續(xù)續(xù))點。是則及為凸規(guī)劃，滿足可微性若亦可微，那么在如果還有那么如果TKxoptlxCQfghmixguuxhvxguxfxIixgxhvxguxfljRvIiuoptlxiiiljjjmiiiiljjjIiiiji.)(,2, 10)(00)()()()(0)()()(,2, 1

12、,0.111一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法為既約梯度稱相應非基變量基變量，使非奇異，存在分解：、既約梯度及搜索方向）個正分量。（的每個極點都有列線性無關；的任意、非退化假設：的多面體同可行集：秩）、問題：（NBxfxfrxfxfxfxxxxxxxBNBASxbBmSmASLPxbAxxSRbmAAxbAxtsxfPTBTNTNNBNBNBNBmmmnm11)()(,)()()(0, 0,30212.)(0,|,0. .)(min1一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法 續(xù)續(xù)為可行方向。故即有）時，（則取由故又）時，（當為可行方向，即時當為可行

13、方向尋找下降可行方向：dSdxdxddxbAxdxAAdddxAdbAxbAdAxdxAdproofxdAdddjjjjjjjj.000|min.)(,0,0.0,00,0,)(0,0:.0,00)1(一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法 續(xù)續(xù)0)()()()()()()(0)(:)2(0, 00.1111NTNNTBTNNTNNTBNTNBTBTTNBjjNNBNBNBNBdrdNBxfxfdxfNdBxfdxfdxfdxfdxfdNdBddxddNdBdNdBdddNBAdddd分解：要求下降方向及中，對應可行，可取在故要使得到根據(jù)考慮分解一、解線性約束問題的既約梯

14、度法一、解線性約束問題的既約梯度法 續(xù)續(xù)點。若的下降可行方向；為若那么方向定理：按上述方案產生的分量。為其中：時當時當?shù)姆桨赶虻囊环N產生下降可行方、結合TKxdPdddNdBdrrrrxrrdddNBNjjjjjjjN02)(, 01,00:)2() 1 ()3(1一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法 續(xù)續(xù)證畢。非零，于是或至少一個由于又保證故總有對.0,000,0,0.0000001.221NTNjjjjjjjjjjNjjjNTNNBjjjjjjjjjdrrxrdrrxrrdrdrdrAdNdBddrxdrrdrxproof得證。即條件：可得取故時，當原因：則取矛盾；

15、與那么，反證。若存在可得000)()(0)()(0)(,)(); 0000, 0, 0)00)(0:0)02111xuuuNBxfxfuBBxfxfuAvxfTKRBxfviiixrxdrruxuxuruuiidrdNjrridTTNTBTNTBTBTBTTTnTBTjjjjjNNNTNTNNBjjjjN一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法 續(xù)續(xù)證畢。也就是即故恒有時當時當，即由第三式得：由第一式得：點即.00,0,000000000,0)()(0)()(0)(000)(111dNdBdddrxdrdrrxuxxuuxxurNBxfxfuuNvxfBxfvuBvxfxu

16、uuAvxfTKxNBNjjjjjjjjjjjNTNBBBTBTNTBTNTNTNTTNTBTTBTTBTTTT算法：算法：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|/min)(ddddxjjkj否則當一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法 續(xù)續(xù).,:,:0)(. .)(

17、min0,552. .32min.21212121212221babaRbaRRhRRfbxaxhtsxfPGRGxxxxxxtsxxxxxxExnlnn，且的分量允許連續(xù)可微。其中：）（標準形式）二、廣義既約梯度法（見書（略）二、廣義既約梯度法二、廣義既約梯度法 續(xù)續(xù)TTTyTzTzyyzyzylnlzxhyxhxfxfryxhbyabbbaaaRzRyzyxSxbxaxhxS)()()()()(2,1,0)(|1廣義既約梯度：非奇異使記使分解非退化假設：記二、廣義既約梯度法二、廣義既約梯度法 續(xù)續(xù)點。時為下降可行方向；當同樣有結論：或且或且令取方向：TKxdddzxhyxhdJirJidr

18、bzraziJzTTyiziziziiizii0201)()(0)(0)(0)(|0)(|10)(0)()()()(:0)(:0)(.:)(min)(.1)(11xxxxxhxgxRRhxhRRgxgtsRRfxffghTechniqueonMinimizatinedUnconstraiSequentialSUMTljjmiilnmnn有不滿足約束的有目的：使?jié)M足約束的構造罰函數(shù)：罰函數(shù)概念：序列無約束最優(yōu)化方法)2.(22|)(, 0max)()(),()()(min)()(0)(, 0000,0)(000,0)(次是最低次的光滑函數(shù)常用：因次罰函數(shù)時，稱當為正整數(shù)。的典型取法：輔助問題輔助

19、函數(shù)不可行可行懲罰項可構造取時當時當時當時當其中：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的單調非增函數(shù)關于的單調非降函數(shù)；關于）（則）（使：，再設為罰函數(shù)，連續(xù)。連續(xù)，引理：設下確界）（定義：0)(0)(),(20|sup| )(inf1)()(,0)(,)()(infxxfSxxfxxfDxxhgfxxfxx2.罰函數(shù)法：罰函數(shù)法： 續(xù)續(xù).,0)(00)(.2)(lim0|)(sup|)(inf1.0,0)(,0)(|),()(21optxxoptxSxxfxxxhxgxSfghxkkkk 則使若推論：在定理條件下，且那么，有即單調增加的正數(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(