不等式約束最優(yōu)化問題的最優(yōu)性條件

1、 1 .3 .3 minxf .21:,2,1,0.,.,m),R(i:RR,cRfmixctsnini 其其中中不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件.0,)(|, xNSxclSSRSn的的閉閉包包定定義義為為：設(shè)設(shè) 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件). (), 0(,0, 0,directionfeasiblexSdSdxdRdclSxRSnn處處的的可可行行方方向向在在點(diǎn)點(diǎn)為為集集合合則則稱稱，使使得得若若存存在在設(shè)設(shè) )., 0(, 0, 0| SdxddD使使閉包閉包：可行方向可行方向：可行方向錐可行方向錐：S S在點(diǎn)在點(diǎn)

2、處的可行方向錐處的可行方向錐xFeasible direction cone注注:當(dāng)當(dāng) 時(shí)時(shí), S在在 處的可行方向錐是全空間處的可行方向錐是全空間Rn .Sxint x 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件.0)(|0 dxfdFT下降方向下降方向(descent direction)：., 0)(:, 0,處處的的下下降降方方向向在在點(diǎn)點(diǎn)為為則則處處可可微微，在在點(diǎn)點(diǎn)且且設(shè)設(shè)xfddxfxRSfdRdSxRSTnn 下降方向錐下降方向錐：f f在點(diǎn)在點(diǎn) 處的下降方向錐處的下降方向錐x 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件x)(xf 有

3、效約束有效約束：非有效約束非有效約束：有效集有效集： 0 xcixIIi不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件設(shè)設(shè)(3.3.1)(3.3.1)中的一個(gè)可行點(diǎn)中的一個(gè)可行點(diǎn)x滿足滿足 ,0 xcj 0 xcj為在為在x處的有效約束或緊約束處的有效約束或緊約束則稱約束則稱約束若有若有 ,0 xck則則 0 xck為為在在x處的非有效約束或松約束處的非有效約束或松約束稱稱x有效約束與非有效約束有效約束與非有效約束-幾何解釋幾何解釋不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件x(1)(1) 在點(diǎn)在點(diǎn) 處處, , g g1 1(x)0 (x)0 和和 g g

4、2 2 (x)0 (x)0是有效約束；是有效約束；g g3 3(x)0(x)0是非有效約束是非有效約束.x(2)(2) 的非有效約束的非有效約束g g3 3(x)0(x)0對對 處的可行方向沒有影響，處的可行方向沒有影響， 故非有效約束也稱為故非有效約束也稱為不起作用的約束不起作用的約束. .xx定理定理3.3.1:3.3.1:考慮約束最優(yōu)化問題考慮約束最優(yōu)化問題. ,)2 .3 .3(.,:(3.3.2) ),(min 0 DFxxfRSfRSxfnSx則則的的局局部部極極小小點(diǎn)點(diǎn)是是問問題題若若處處可可微微在在且且是是非非空空集集合合，其其中中 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最

5、優(yōu)化問題的最優(yōu)性條件定理定理3.3.2:3.3.2:在問題在問題(3.3.1)(3.3.1)中，假設(shè)：中，假設(shè)：(1)(1)*x為局部最優(yōu)解且為局部最優(yōu)解且 ；mixciIi 1 ,0*(2)(2) xf與 *Iixci 在在*x點(diǎn)可微；點(diǎn)可微；(3)(3) * IIixci在在*x點(diǎn)連續(xù)；點(diǎn)連續(xù)；則則,00 GF *0,0 IidxcRdGTin 其其中中 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件僅考慮在某點(diǎn)起作用的約束僅考慮在某點(diǎn)起作用的約束例例1 1： 確定確定： 0,01223042.26min2121212221 xxxxxxtsxxxf在點(diǎn)在點(diǎn)Tx3 ,2處

6、的可行下降方向處的可行下降方向. .解解： ，Tx3,2 .2,1 xI .23,2121 xcxc 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件 .28,4212221 xfxxxf設(shè)設(shè) 則則,21Tddd ,01 xcdT;0221 dd ,02 xcdT;02321 dd ,0 xfdT.02821 dd 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件.0,3241|22122 ddddRdFDx為為處處的的可可行行下下降降方方向向集集合合故故該該問問題題在在.一一定定不不是是問問題題的的極極小小點(diǎn)點(diǎn)，故故由由于于xFD 不等式約束最優(yōu)化問題的最優(yōu)性

7、條件不等式約束最優(yōu)化問題的最優(yōu)性條件l 幾何最優(yōu)性條件直觀幾何最優(yōu)性條件直觀, ,但難以在實(shí)際但難以在實(shí)際 計(jì)算中應(yīng)用計(jì)算中應(yīng)用. .l將幾何最優(yōu)性條件轉(zhuǎn)化為代數(shù)將幾何最優(yōu)性條件轉(zhuǎn)化為代數(shù) 最優(yōu)性條件最優(yōu)性條件. .?(1) Fritz John 條件條件(2) Kuhn-Tucker 條件條件(1948)(1948) 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件定理定理3.3.3:3.3.3:設(shè)設(shè)*x為問題為問題(3.3.1)(3.3.1)的局部最優(yōu)解且的局部最優(yōu)解且 xcxfi, mi 1在在*x點(diǎn)可微，點(diǎn)可微， 則存在非零則存在非零 ,*1*0*m 使得：使得： 01

8、*0 miiixcxf mixcii,2,10* mii,2,1 ,00* 則存在則存在非非零的向量零的向量例例2 2： 0,0,.,min2212231211121 xxxcxxxxctsxxxf驗(yàn)證驗(yàn)證Tx0,0*處處Fritz-John條件是否成立？條件是否成立？解解： ,2,1* I ,0,1*Txf ,1,0*1Txc .1,0*2Txc 取,00*2*1*0 有 .0,0,0*2*2*1*1*2*2*1*1*0 xcxcxcxcxf 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件即該問題在即該問題在x*處處Fritz-John條件成立條件成立. 不等式約束最優(yōu)化不

9、等式約束最優(yōu)化問題的最優(yōu)性條件問題的最優(yōu)性條件注注: (1)上例說明在上例說明在Fritz John條件中有可能條件中有可能0=0. 此時(shí)，目此時(shí)，目 標(biāo)標(biāo) 函數(shù)的梯度就會從函數(shù)的梯度就會從Fritz John中消失中消失, 即即Fritz John 條件實(shí)際上不包含目標(biāo)函數(shù)的任何信息，僅僅表明條件實(shí)際上不包含目標(biāo)函數(shù)的任何信息，僅僅表明 起作用約束函數(shù)的梯度線性相關(guān)，而這對表述最優(yōu)起作用約束函數(shù)的梯度線性相關(guān)，而這對表述最優(yōu) 點(diǎn)沒有什么實(shí)際價(jià)值點(diǎn)沒有什么實(shí)際價(jià)值.(2) 為了保證為了保證0 0, 還需要對約束再加上一些限制條件這種限還需要對約束再加上一些限制條件這種限 制條件通常稱為制條件通

10、常稱為約束規(guī)格約束規(guī)格(Constraint Qualification) 一個(gè)一個(gè) 自然的想法是附加自然的想法是附加 線性無關(guān)的約束規(guī)格線性無關(guān)的約束規(guī)格 (當(dāng)然還有許多其他的約束規(guī)格當(dāng)然還有許多其他的約束規(guī)格)，這樣就得到了著名的，這樣就得到了著名的 KuhnTuker條件條件.)()(xIixci (1951)(1951)定理定理3.3.43.3.4設(shè)設(shè)*x為為 (3.3.1)(3.3.1)局部最優(yōu)解局部最優(yōu)解, , ;0* xciIi xcxfi, mi 1在在*x點(diǎn)可微，點(diǎn)可微， 對于對于*Ii 的的 *xci 線性無關(guān)，線性無關(guān)，則存在非零向量則存在非零向量 *1*,m 使得：使得

11、： 01* miiixcxf mixcii,2,10* mii,2,10* 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件K-TK-T條條件件互補(bǔ)互補(bǔ)松弛松弛條件條件 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件式式(a)(a)的幾何意義的幾何意義: :在局部在局部極小點(diǎn)極小點(diǎn) x xk k 處處, ,目標(biāo)函數(shù)的梯度目標(biāo)函數(shù)的梯度能表示成有效約束梯度的能表示成有效約束梯度的非負(fù)組合非負(fù)組合, ,即目標(biāo)函數(shù)的即目標(biāo)函數(shù)的梯度屬于有效約束的梯度梯度屬于有效約束的梯度所生成的凸錐內(nèi)所生成的凸錐內(nèi). . (a) 1* miiixgxf 例例3 3： 0,0,.,m

12、in2212231211121 xxxcxxxxctsxxxf驗(yàn)證驗(yàn)證 Tx0,0* 處處kuhn-Tuckerkuhn-Tucker條件是否成立？條件是否成立？解解： 對對 有有,21T ,0121*22*11* xcxcxf所以所以Tx0,0*不是不是K-T點(diǎn)點(diǎn)原因是原因是 *2*1,xcxc 線性相關(guān)線性相關(guān) 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件定理定理3.3.53.3.5 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件設(shè)設(shè)在問題在問題(3.3.1)(3.3.1)中中 xcxfi , mi 1是凸函數(shù)是凸函數(shù), ,是可行點(diǎn)，是可行點(diǎn)，且x在在

13、 處可微處可微. . 若若 是是(3.3.1)(3.3.1)的的K-TK-T點(diǎn)點(diǎn), ,x則則xx ),.,2 , 1(,mixcxfi 是是(3.3.1)(3.3.1)的全局極小點(diǎn)的全局極小點(diǎn). .K-T條件對于約束問題的重要性在于：條件對于約束問題的重要性在于：1）檢驗(yàn)?zāi)滁c(diǎn)是否為約束最優(yōu)點(diǎn)；）檢驗(yàn)?zāi)滁c(diǎn)是否為約束最優(yōu)點(diǎn)；2）檢驗(yàn)一種搜索方法是否可行。）檢驗(yàn)一種搜索方法是否可行。例例4 4：判斷判斷x x(k)(k)=1 0=1 0T T是否為下列約束優(yōu)化問題最優(yōu)點(diǎn)：是否為下列約束優(yōu)化問題最優(yōu)點(diǎn)：01),(0),(0),(.)2(),(min22121322121211222121 xxxxgxxxgxxxgtsxxxxf 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件解：解：1）判斷）判斷該點(diǎn)起作用約束該點(diǎn)起作用約束：01),(211 xxg0),(212 xxg0),(213 xxg2）計(jì)算目標(biāo)函數(shù)及）計(jì)算目標(biāo)函數(shù)及有效約束在有效約束在 該點(diǎn)梯度：該點(diǎn)梯度： 022)2(2)x()(2)(1)(kkkxxf 10)x()(2kg 1212)x()(1)(3kkxg 不等式約束最優(yōu)化問題的最優(yōu)性條件不等式約束最優(yōu)化問題的最優(yōu)性條件