1、第七章第七章約束最優化的理論約束最優化的理論與方法與方法一般形式的約束最優化問題一般形式的約束最優化問題min( )f x. .( )0,ist c xiE( )0,ic xiI |( )0,;( )0,iiXx c xiE c xiI可行域可行域min( )nx Rf x一般形式的無約束最優化問一般形式的無約束最優化問題題*xX*()( ),f xf xxX 全局極小點全局極小點設設則稱則稱x*為問題的為問題的全局極小點全局極小點；如果如果成立，成立，*()( ),f xf xxX xx 則稱則稱x*為為嚴格全局極小點嚴格全局極小點.進一步，如果進一步，如果成立，成立，(總體極小點總體極小點

2、)*,xX設*2( , ) |.N xxx x*()( ),(,)f xf xxN xX 局部極小點：局部極小點：如果對于某一如果對于某一成立，成立， 則稱則稱 x*是問題的是問題的局部極小點局部極小點，0 有其中其中則稱則稱x*為為嚴格局部極小點嚴格局部極小點.進一步，如果進一步，如果成立，成立，*()( ),(,),f xf xxN xX xx 全局極小點是局部極小點全局極小點是局部極小點有效約束、無效約束與內點、邊界點有效約束、無效約束與內點、邊界點有效有效(起作用起作用)約束：約束：對于可行點對于可行點 ， ，x在點xxxx0)(xci0)(xci( )0ic x 若0)(xci( )

3、0ixc x 稱 是約束如果如果0)(xci就稱不等式約束就稱不等式約束在點在點是有效約束。是有效約束。并稱可行點并稱可行點位于約束位于約束的邊界。的邊界。無效約束：無效約束：對于可行點對于可行點就稱不等式約束就稱不等式約束是無效約束是無效約束的內點的內點. .E E: :等式約束指標集等式約束指標集I I: :不等式約束指標集不等式約束指標集( ) |( )0,iI xi c xiI( )( )A xEI xnxR x點處的有效約束集點處的有效約束集( (有效集有效集) )( ),( )ic x iA x是在是在x點處的有效約束點處的有效約束( ),( )ic x iA x是在是在x點處的非

4、有效約束點處的非有效約束假設已知有效約束假設已知有效約束A(x)min( )f x. .( )0,ist c xiE( )0,ic xiImin( )f x. .( )0,( *)ist c xiA x定理定理（一階必要條件）（一階必要條件）1:DnfDRR設在開集 上連續可微，若min( )()0.nx RxDf xg x是的局部極小點，則定理定理（凸最優性定理）（凸最優性定理）11:.nfDRRfC設是凸函數，且則()0.xg x是總體極小點min ( )nx Rf x定理定理（二階必要條件）（二階必要條件）1:DnfDRR設在開集 上二階連續可微，若min( )()0,()0( ( *)

5、.nx RxDf xg xG xG x是的局部極小點，則正半定定理定理（二階充分條件）（二階充分條件）1:DnfDRR設在開集 上二階連續可微，()0().xDfg xG x則是 的一個嚴格局部極小點的充分條件是和是正定矩陣2( )f xC*()0f x2*()f x*xmin( )f x設函數設函數，若若，并且并且半正定，則半正定，則是是的局部最優解的局部最優解。 *xmin( )f x*x設設是是的局部最優解，則在的局部最優解，則在處的下降方向一定不是可行方向。處的下降方向一定不是可行方向。 定義定義設f(x)為定義在空間nR上的連續函數，點_nxR，若對于方向nsR存在數0使成立_()(

6、 ),(0, ),f xsf x則稱s為f(x)在_x處的一個下降方向下降方向.在點_x處的所有下降方向的全體記為_( ).D x定理定理設函數f(x)在點_x處連續可微，如存在非零向量nsR使成立_( )0Tf xs則s是f(x)在點_x處的一個下降方向.給出了在給出了在f(x)連續可微是下降方向同函數連續可微是下降方向同函數f(x)的梯度的梯度 之間的關系之間的關系. .( )f x( ) |( )0TD xd df x下降方向集下降方向集序列可行方向序列可行方向*,0,(1,2,). .nkkxXdRdkst設如果 序列和*.dXx則稱 是 在 處的序列可行方向*( *):SFD xXX

7、x，在 處的所有序列可行方向組成的集合*,kkxdXkk,00kkdd具有和，可行方向可行方向*,0,0, . .nxXdRst設如果*,0, xtdXt *.dXx則稱 是 在 處的可行方向*( *, ):FD x XXx在 處的所有可行方向組成的集合線性化可行方向線性化可行方向*,0,nxXdR設如果*()0,;Tidc xiE*.dXx則稱 是 在 處的線性化可行方向( *, ):LFD x X*()0,Tidc x*Xx在 處的所有線性化可行方向組成的集合12(,)Tdd d1 1223( )iiiic xa xa xa1122( )(,)iTiiadc xd da*();iI x11

8、12223( *)()()iiiic xdaxdaxda( *)( )Tiic xdc x如果所有的約束函數都在如果所有的約束函數都在*xX處可微，處可微，則有則有( *, )( *, )( *, )FDx XSFDx XLFDx X*,0, xtdXt *,kkxdXkk,00kkdd和*()0,;Tidc xiE*()0,Tidc x*();iI x序列可行方向序列可行方向可行方向可行方向線性化可行方向線性化可行方向( *,)( *,)FD xXSFD xX( *,)( *,)dFD xXdSFD xX ,2kkkdd( *,)( *,)SFD xXLFD xX( *,)( *,)dSFD

9、 xXdLFD xX *,kkxdXkk,00kkdd和*()0,;Tidc xiE*()0,Tidc x*();iI x序列可行方向序列可行方向線性化可行方向線性化可行方向0d 0d *kkxdX( *)( *)( *)Tikkikkic xdc xdc x引理引理min( )f x. .( )0,ist c xiE( )0,ic xiI*xX設是下列問題的局部極小點( )( )*if xc xx如果和都在處可微，kx則所有可行序列d的序列可行方向 滿足*()0,(,)Tdf xdSFD xX *(,)()SFD xXD x在局部極小點處沒有可行下降方向在局部極小點處沒有可行下降方向證明證明

10、: :反證法反證法. .假設存在可行序列假設存在可行序列kx的序列可行方向的序列可行方向d*.( )0,( ,),Tst df xdSFD x X 并且序列并且序列*lim.kkxx*()()()()(|)Tkkkf xf xxxf xoxx*|*|kkkxxddxx*() |()(|)Tkkf xxxdf xoxxk 0*()()kf xf xk 矛盾矛盾引理引理min( )f x. .( )0,ist c xiE( )0,ic xiI*xX設是下列問題的局部極小點( )( )*if xc xx如果和都在處可微，則必有*()0,(,)Tdf xdFD xX *(,)()FD xXD x在局部

11、極小點處沒有可行下降方向在局部極小點處沒有可行下降方向FarkasFarkas引理引理設nmRA為nm 矩陣，,nRb 則下述兩組方程中有且僅有一組有解：0 ,0 ,(1)TAxb x,0 ,(2)TA yby其中.,mnRyRxFarkasFarkas引理在最優化理論研究中起重要作用引理在最優化理論研究中起重要作用Farkas引理的另一種形式引理的另一種形式設設l. l是兩個非負整數，是兩個非負整數，a0,ai (i=1,l)和和bi (i=1,l)是是Rn中的向量，則線性方程組和不等式組中的向量，則線性方程組和不等式組0,1, ,Tid ail 0,1, ,Tid bil00Td a 無解

12、當且僅當存在實數無解當且僅當存在實數(1, )(1, )iiilil和 非 負 實 數使得使得011.lliiiiiiaabKKTKKT定理定理*xX設是下列問題的局部極小點( )( )*if xc xx如果和都在的鄰域內一階連續可微.()CQ如果約束規范條件min( )f x. .( )0,ist c xiE( )0,ic xiI( *,)( *,)SFD xXLFD xX*. .ist則存在成 立*1( *)()miiif xc x*()0,ic xiE*()0,ic xiI*0,iiI*()0,iic xiI駐點條件駐點條件可行性條件可行性條件乘子非負條件乘子非負條件互補松弛條件互補松弛

13、條件KKTKKT條件條件1, l1,lm 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最優點不一定是最優點不一定是KKTKKT點點2221232221123212314253min( )32. .( )30( )0( )0( )0( )0f xxxxstc xxxxcxxxc xxcxxc xx *(1,1,1,)KKTTx 驗證最

14、優點是否為點.*1,2I ( *)( 6, 2, 4)Tf x 1( *)(2,2,2)Tc x2( *)( 1,1,0)Tc x 12621022104200 1222 證明證明*1( *)()miiif xc x*0,iiI*()0,iic xiI*(,)dSFD xX設*x 是局部極小點*()0,(,)Tdf xdSFD xX ( *,)( *,)SFD xXLFD xX*(,)dLFD xX*()0,;Tidc xiE*()0,();Tidc xiI x*()0Tdf x*()dD x*(,)LFD xX方程組無解方程組無解*(),0() . .iiR iEiI xst*()( *)(

15、)()iiiii Ei I xf xc xc x*()( *)()()iiiii Ei I xf xc xc x*()( *)()()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 x*()0,.iic xiI 線性函數約束規范條件線性函數約束規范條件(LFCQ):*()()ic xiEI x所有的約束函數都是線性函數.線性無關約束規范條件線性無關約束規范條件(LICQ):*()()ic xiE

16、I x約束函數的梯度線性無關.可以證明可以證明(1) 如果如果LFCQ成立，則成立，則CQ成立成立(2) 如果如果LICQ成立，則成立，則CQ成立成立定理定理: :*xX設是約束優化問題的局部極小點，LGCQLICQ如果成立或者成立，KKT.則條件成立一階最一階最優性充優性充分條件分條件定理定理*,xX設*( )( )if xc xx如果和都在 處可微，并且有*()0,0(,)Tdf xdSFD xX 成立，*.x則 是問題的一個嚴格局部極小點證明證明: :*.x假設 不是嚴格局部極小點. .kxX st則*()()kf xf x*,1,2,kkxx xx k且有不失一般性，我們可假定不失一般

17、性，我們可假定*2|kkkxxddxx*2|kkxx*( , )d SFD x X*2()()()()Tkkkkf xf xdf xo*()f x0*()0Tkdf x*()0Tdf xk 矛盾矛盾*2()|()0,( *),0TiiFdLFDc xdiI x 線性化零約束方向集線性化零約束方向集2*2*2*1(,)()()mxxiiiL xf xc x 定理定理( (二階必要性條件二階必要性條件) )*x設 是約束優化問題的局部極小點，*Lagrange是相應的乘子.LICQ如果成立，則2*2(,)0,().TxxdL xddF 定理定理( (二階充分性條件二階充分性條件) )*KKTx設

18、是一個點，*是相應的如果2*2(,)0,(),0,TxxdL xddFd Lagrange乘子.*.x則 是問題的嚴格局部極小點 7.2 7.2 二次罰函數方法二次罰函數方法設法將約束問題求解轉化為無約束問題求解設法將約束問題求解轉化為無約束問題求解具體說：具體說：根據約束的特點，構造某種懲罰函數，根據約束的特點，構造某種懲罰函數，然后把它加到目標函數中去，將約束問題的然后把它加到目標函數中去，將約束問題的求解化為一系列無約束問題的求解求解化為一系列無約束問題的求解二次罰函數法引例：引例： 求解等式約束問題求解等式約束問題: :222121,minxxxxf02.21xxt s解解: :圖解法求出最優解圖解法求出最優解 .1 , 1*Tx 構造：構造：22,2121222121xxxxxxxxF但是但是21,xxF性態極壞，性態極壞， 無法用有效的無約束無法用有效的無約束優化算法求解優化算法求解設想構造：設想構造：2221212;2Q xxxxx其中其中求解此無約束問題得：求解此無約束問題得： 12221xx當當時時， 有：有： TTTxxxx1 , 1,*2*121是一個非常大的正數是一個非常大的正數等式約束問題等式約束問題 1minnRxxf .0istcxiE二次罰函數二次罰函數 21;( )2ii EQ xfxcx 0ic x 如果0