約束最優(yōu)化理論與方法PPT課件

1、一般形式的約束最優(yōu)化問題min( )f x. .( )0,ist c xiE( )0,ic xiI |( )0,;( )0,iiXx c xiE c xiI可行域min( )nx Rf x一般形式的無約束最優(yōu)化問題第1頁/共34頁*xX*()( ),f xf xxX 全局極小點(diǎn)設(shè)則稱x*為問題的全局極小點(diǎn)；如果成立，*()( ),f xf xxX xx 則稱x*為嚴(yán)格全局極小點(diǎn).進(jìn)一步，如果成立，(總體極小點(diǎn))第2頁/共34頁*,xX設(shè)*2( , ) |.N xxx x*()( ),(, )f xf xxN xX 局部極小點(diǎn)：如果對于某一成立，則稱 x*是問題的局部極小點(diǎn)，0 有其中則稱x*為

2、嚴(yán)格局部極小點(diǎn).進(jìn)一步，如果成立，*()( ),(, ),f xf xxN xX xx 全局極小點(diǎn)是局部極小點(diǎn)第3頁/共34頁有效約束、無效約束與內(nèi)點(diǎn)、邊界點(diǎn)有效(起作用)約束：對于可行點(diǎn) ， ，x在點(diǎn)xxxx0)(xci0)(xci( )0ic x 若0)(xci( )0ixc x 稱 是約束如果0)(xci就稱不等式約束在點(diǎn) 是有效約束。并稱可行點(diǎn)位于約束的邊界。無效約束：對于可行點(diǎn)就稱不等式約束是無效約束的內(nèi)點(diǎn).第4頁/共34頁E:等式約束指標(biāo)集I:不等式約束指標(biāo)集( ) |( )0,iI xi c xiI( )( )A xEI xnxR x點(diǎn)處的有效約束集(有效集)( ),( )ic

3、x iA x是在x點(diǎn)處的有效約束( ),( )ic x iA x是在x點(diǎn)處的非有效約束假設(shè)已知有效約束A(x)min( )f x. .( )0,ist c xiE( )0,ic xiImin( )f x. .( )0,( *)ist c xiA x第5頁/共34頁定理（一階必要條件）1:DnfDRR設(shè)在開集 上連續(xù)可微，若min( )()0.nx RxDf xg x是的局部極小點(diǎn)，則定理（凸最優(yōu)性定理）11:.nfDRRfC設(shè)是凸函數(shù)，且則()0.xg x是總體極小點(diǎn)min ( )nx Rf x第6頁/共34頁定理（二階必要條件）1:DnfDRR設(shè)在開集 上二階連續(xù)可微，若min( )()0,

4、()0( ( *).nx RxDf xg xG xG x是的局部極小點(diǎn)，則正半定定理（二階充分條件）1:DnfDRR設(shè)在開集 上二階連續(xù)可微，()0().xDfg xG x則是 的一個嚴(yán)格局部極小點(diǎn)的充分條件是和是正定矩陣第7頁/共34頁2( )f xC*()0f x2*()f x*xmin( )f x設(shè)函數(shù)，若，并且半正定，則是的局部最優(yōu)解。 *xmin( )f x*x設(shè)是的局部最優(yōu)解，則在處的下降方向一定不是可行方向。 第8頁/共34頁定義設(shè)f(x)為定義在空間nR上的連續(xù)函數(shù)，點(diǎn)_nxR，若對于方向nsR存在數(shù)0使成立_()( ),(0, ),f xsf x則稱s為f(x)在_x處的一個

5、下降方向. 在點(diǎn)_x處的所有下降方向的全體記為_( ).D x第9頁/共34頁定理設(shè)函數(shù)f(x)在點(diǎn)_x處連續(xù)可微，如存在非零向量nsR使成立_( )0Tf xs則s是f(x)在點(diǎn)_x處的一個下降方向.給出了在f(x)連續(xù)可微是下降方向同函數(shù)f(x)的梯度 之間的關(guān)系.( )f x( ) |( )0TD xd df x下降方向集第10頁/共34頁序列可行方向*,0,(1,2,). .nkkxXdRdkst設(shè)如果 序列和*.dXx則稱 是 在 處的序列可行方向*( *):SFD xXXx，在 處的所有序列可行方向組成的集合*,kkxdXkk,00kkdd具有和，可行方向*,0,0, . .nxX

6、dRst設(shè)如果*,0, xtdXt *.dXx則稱 是 在 處的可行方向*( *,):FD xXXx在 處的所有可行方向組成的集合第11頁/共34頁線性化可行方向*,0,nxXdR設(shè)如果*()0,;Tidc xiE*.dXx則稱 是 在 處的線性化可行方向( *, ):LFD x X*()0,Tidc x*Xx在 處的所有線性化可行方向組成的集合12(,)Tdd d1 1223( )iiiic xa xa xa1122( )(,)iTiiadc xd da*();iI x1112223( *)()()iiiic xdaxdaxda( *)( )Tiic xdc x第12頁/共34頁如果所有的約

7、束函數(shù)都在*xX處可微，則有( *,)( *,)( *,)FD xXSFD xXLFD xX*,0, xtdXt *,kkxdXkk,00kkdd和*()0,;Tidc xiE*()0,Tidc x*();iI x序列可行方向可行方向線性化可行方向( *,)( *,)FD xXSFD xX( *,)( *,)dFD xXdSFD xX ,2kkkdd第13頁/共34頁( *,)( *,)SFD xXLFD xX( *,)( *,)dSFD xXdLFD xX *,kkxdXkk,00kkdd和*()0,;Tidc xiE*()0,Tidc x*();iI x序列可行方向線性化可行方向0d 0d

8、 *kkxdX( *)( *)( *)Tikkikkic xdc xdc x第14頁/共34頁引理min( )f x. .( )0,ist c xiE( )0,ic xiI*xX設(shè)是下列問題的局部極小點(diǎn)( )( )*if xc xx如果和都在處可微，kx則所有可行序列d的序列可行方向 滿足*()0,(,)Tdf xdSFD xX *(,)()SFD xXD x在局部極小點(diǎn)處沒有可行下降方向第15頁/共34頁證明:反證法.假設(shè)存在可行序列kx的序列可行方向d*.( )0,( ,),Tst df xdSFD x X 并且序列*lim.kkxx*()()()()(|)Tkkkf xf xxxf xo

9、xx*|*|kkkxxddxx*() |()(|)Tkkf xxxdf xoxxk 0*()()kf xf xk 矛盾第16頁/共34頁引理min( )f x. .( )0,ist c xiE( )0,ic xiI*xX設(shè)是下列問題的局部極小點(diǎn)( )( )*if xc xx如果和都在處可微，則必有*()0,(,)Tdf xdFD xX *(,)()FD xXD x在局部極小點(diǎn)處沒有可行下降方向第17頁/共34頁Farkas引理設(shè)nmRA為nm矩陣，,nRb則下述兩組方程中有且僅有一組有解：0 ,0 ,(1)TAxb x,0 ,(2)TA yb y其中.,mnRyRxFarkas引理在最優(yōu)化理論

10、研究中起重要作用第18頁/共34頁Farkas引理的另一種形式設(shè)l. l是兩個非負(fù)整數(shù)，a0,ai (i=1,l)和bi (i=1,l)是Rn中的向量，則線性方程組和不等式組0,1, ,Tid ail 0,1, ,Tid bil00Td a 無解當(dāng)且僅當(dāng)存在實數(shù)(1, )(1, )iiilil和 非 負(fù) 實 數(shù)使得011.lliiiiiiaab第19頁/共34頁KKT定理*xX設(shè)是下列問題的局部極小點(diǎn)( )( )*if xc xx如果和都在的鄰域內(nèi)一階連續(xù)可微.()CQ如果約束規(guī)范條件min( )f x. .( )0,ist c xiE( )0,ic xiI( *,)( *,)SFD xXLF

11、D xX*. .ist則存在成 立*1( *)()miiif xc x*()0,ic xiE*()0,ic xiI*0,iiI*()0,iic xiI駐點(diǎn)條件可行性條件乘子非負(fù)條件互補(bǔ)松弛條件KKT條件1, l1, lm 第20頁/共34頁13122min. .00 xstxxx2x1x*(0,0)Tx *10()1c x*20()1c x *1( *)()miiif xc x*()0,ic xiE*()0,ic xiI*0,iiI*()0,iic xiI*1()0f x ( *,) |0LFD xXd d( *,) |,00SFD xXd d最優(yōu)點(diǎn)不一定是KKT點(diǎn)第21頁/共34頁22212

12、32221123212314253min( )32. .( )30( )0( )0( )0( )0f xxxxstc xxxxcxxxc xxcxxc xx *(1,1,1,)KKTTx 驗證最優(yōu)點(diǎn)是否為點(diǎn).*1,2I ( *)( 6, 2, 4)Tf x 1( *)(2,2,2)Tc x2( *)( 1,1,0)Tc x 12621022104200 1222 第22頁/共34頁證明*1( *)()miiif xc x*0,iiI*()0,iic xiI*(,)dSFD xX設(shè)*x 是局部極小點(diǎn)*()0,(,)Tdf xdSFD xX ( *,)( *,)SFD xXLFD xX*(,)dL

13、FD xX*()0,;Tidc xiE*()0,();Tidc xiI x*()0Tdf x*()dD x*(,)LFD xX方程組無解*(),0() . .iiR iEiI xst*()( *)()()iiiii Ei I xf xc xc x*()( *)()()iiiii Ei I xf xc xc x第23頁/共34頁*()( *)()()iiiii Ei I xf xc xc x*0, ()iiI I x令* ()()iii I I xc x*1()miiic x1, El1, Ilm *1()()miiif xc x*0,iiI *()( *)0iiI xc x* ()0iiI I

14、 x*()0,.iic xiI 第24頁/共34頁線性函數(shù)約束規(guī)范條件(LFCQ):*()()ic xiEI x所有的約束函數(shù)都是線性函數(shù).線性無關(guān)約束規(guī)范條件(LICQ):*()()ic xiEI x約束函數(shù)的梯度線性無關(guān).可以證明(1) 如果LFCQ成立，則CQ成立(2) 如果LICQ成立，則CQ成立定理:*xX設(shè)是約束優(yōu)化問題的局部極小點(diǎn)，LGCQLICQ如果成立或者成立，KKT.則條件成立第25頁/共34頁一階最優(yōu)性充分條件定理*,xX設(shè)*( )( )if xc xx如果和都在 處可微，并且有*()0,0(,)Tdf xdSFD xX 成立，*.x則 是問題的一個嚴(yán)格局部極小點(diǎn)證明:*

15、.x假設(shè) 不是嚴(yán)格局部極小點(diǎn). .kxX st則*()()kf xf x*,1,2,kkxx xx k且有不失一般性，我們可假定*2|kkkxxddxx*2|kkxx*( , )d SFD x X*2()()()()Tkkkkf xf xdf xo*()f x0*()0Tkdf x*()0Tdf xk 矛盾第26頁/共34頁*2()|()0,( *),0TiiFdLFDc xdiI x 線性化零約束方向集2*2*2*1(,)()()mxxiiiL xf xc x 定理(二階必要性條件)*x設(shè) 是約束優(yōu)化問題的局部極小點(diǎn)，*Lagrange是相應(yīng)的乘子.LICQ如果成立，則2*2(,)0,().

16、TxxdL xddF 定理(二階充分性條件)*KKTx設(shè) 是一個點(diǎn)，*是相應(yīng)的如果2*2(,)0,(),0,TxxdL xddFd Lagrange乘子.*.x則 是問題的嚴(yán)格局部極小點(diǎn)第27頁/共34頁 7.2 二次罰函數(shù)方法設(shè)法將約束問題求解轉(zhuǎn)化為無約束問題求解具體說：根據(jù)約束的特點(diǎn)，構(gòu)造某種懲罰函數(shù)，然后把它加到目標(biāo)函數(shù)中去，將約束問題的求解化為一系列無約束問題的求解第28頁/共34頁二次罰函數(shù)法引例： 求解等式約束問題:222121,minxxxxf02.21 xxt s解:圖解法求出最優(yōu)解.1 , 1*Tx 構(gòu)造：22,2121222121xxxxxxxxF但是21,xxF性態(tài)極壞， 無法用有效的無約束優(yōu)化算法求解第29頁/共34頁設(shè)想構(gòu)造：2221212;2Q xxxxx其中求解此無約束問題得： 12221xx當(dāng)時， 有： TTTxxxx1 , 1,*2*121是一個非常大的正數(shù)第30頁/共34頁等式約束問題 1minnRxxf .0istcxiE二次罰函數(shù) 21;( )2ii EQ xfxcx 0ic x 如果0 是罰參數(shù)00( ; )Q x的極小點(diǎn)就是原問題的極小點(diǎn)第31頁/共34頁1212min,f x xxx2