非線性規(guī)劃-KT條件

1、第三講非線性規(guī)劃4約束極值問題(1)問題minf(X)，問題R X(X) 0,j 1,11思路:有約束 無約束；非線性 線性；復(fù)雜 簡(jiǎn); 一、最優(yōu)性條件1.可行下降方向(有用約束，可行方向，下降方向)(1)有用(效)約束設(shè)1式的f (X),gj(X)有一階連續(xù)偏導(dǎo)設(shè)X(0)是一個(gè)可行解，下一步考察時(shí)，要討論約束第1頁共25頁分析：應(yīng)有g(shù)j(X(0) 0若gj(x(0) o, 則在U (X(0)內(nèi)， 有g(shù)j(x)o,此時(shí)各個(gè)方向均可選.若 gj(X(0) 0,gj(x(0)0則X(0) ggj(x(0)0第2頁共25頁故稱gj(X) 0是X(0)點(diǎn)的有效約束.(2)可行方向(對(duì)可行域來說) 設(shè)X

2、(0)為可行點(diǎn),P為某方向,0, 00的梯度若存在0 0, 00的梯度則稱P是X點(diǎn)的一個(gè)可行方向.(a)可行方向P與有效約束gj(X(0) gj(X)關(guān)系是：gj(X(0)TP 0.記有效約束下標(biāo)集第3頁共25頁J j|gj(x(0)0,1 j 1若p為x 若p為x (0)的可行方向存在0 0,使得當(dāng)gj(x(0)從而dgj(X(0) P)dP),則0, o，有g(shù)j(x(0)o,j Jgj(X(0)TP 0,j J第4頁共25頁(0) 0(0) 0(b)反之,若gj(X(0) )TP 0,則P必為可行方向.Qgj(X(0) P) gj(X(0)gj(X(0)TP o()對(duì)有效約束gj(X(0)

3、 0,只要 充分小，得第5頁共25頁gj(X(0) P) 0,所以P是可行方向；對(duì)無效約束gj(X(0) 0,同樣只要 充分小就有g(shù)j (X(0) P) 0 ,故P也是可行方向；事實(shí)上，對(duì)無效gj(X(0) 0, P都是可行方向.(3)下降方向(對(duì)目標(biāo)函數(shù)來說)設(shè)X(0) R,對(duì)某P方向，若在 0, 0, 0 0 內(nèi)，有f(X(0) P) f(X(0)第6頁共25頁則稱P是一個(gè)下降方向.下降方向判定：若f(X(0)TP 0,則P是X(0)的一個(gè)下降方向因?yàn)?f(X) f(X(0) P)f(X) f(X(0)TP o(), 只要充分小，都有f(X) f(X(0). (4)可行下降方向 若X(0)

4、 R的某方向P是可行方向+下降方向， 則稱P是X(0)的可行下BI方向.第7頁共25頁即存在0 0,當(dāng) 0, 0時(shí)，有g(shù)/X P) 0 且 f(X(0) P) f (X (0),是繼續(xù)尋優(yōu)方向.討論：X(0)非極小值點(diǎn)存在可行下降方向 P;X (0)極小值點(diǎn)無可行下降方向P;(可行但不下降，或下降不可行)第8頁共25頁定理(局部極(最)小必要條件)設(shè)X是min f(X),X gX) 0局部極小點(diǎn). f(X),gj(X), j J (有效約束下標(biāo)集)在X處可 微，gj(X), j J在X處連續(xù)，則在X處無可行下降方向 P，即不存在P ,使* Tgj(X)Tp o,j j, f(X*)TP o,(

5、)證 否則由(*)及前面的分析，可找出可行下降點(diǎn) X非局部極小值點(diǎn)矛盾.第9頁共25頁如圖 所示如圖 所示2.庫(kù)恩塔克條件（局部最小的必要條件） 是非線性規(guī)劃中最重要成果之一Gordan引理（不加證明）設(shè)A, A2,., A是l個(gè)n維向量,則第10頁共25頁P(yáng) , AT P 0,j 1,2,., lj0,不全為零，使jAj0.j i（不指向同側(cè)的向量，正組合為零）（如l=3,n=2）若同側(cè)，則有P（圖a）,否則無P（圖b）,但可正組為0.Fritz John 定理設(shè)X是1極小值點(diǎn),f(X)和gj(X)有一階連續(xù)偏導(dǎo)數(shù)，則存在不全為零的0, 1,., l ,使i0 f(X ) j gj(X )

6、0j 1jgj(X ) 0, j 1,2,.,lj 0,j 1,2,.,l證明因X是問題1的解，故由定理4,不存在可行下降方向P,使第12頁共25頁f(X )TP 0gj(x)tp 0, j j由Gordan引理,存在不全為零非負(fù)數(shù)o, j,j J使0 f(X ) j gj(x)0j j對(duì)無效約束j J ,令j 0,則j gj(X ) 0從而有(對(duì)所有l(wèi))第13頁共25頁l0 f (X ) j gj(X )0j i且有 jgj(X) 0, j 0, j 1,2.l ,證畢.注1：類似于條件極值的必要條件.注2若0 0，則有效約束的gj (X )正線性相關(guān)同側(cè)有可行下降方向X非極值點(diǎn).故一般設(shè)g

7、j(X )線性無關(guān) 0 0.以上條件稱為 Fritz John條件，X 稱為Fritz John 點(diǎn).第14頁共25頁(3)必要條件(庫(kù)恩-塔克條件)設(shè)X是極小值點(diǎn),f(X)和gj(X)有一階連續(xù)偏導(dǎo)，且有效約束梯度線性無關(guān)，則1 ,., l ,使if(x ) j gj(x)0j ijgj(X ) 0, j 1,2.lj 0,j 1,2,.,l證明 由Fritz John引理，gj(X ) j J線性無關(guān)第15頁共25頁得 00,作 j 0/ 00,即得.式2=庫(kù)恩-塔克條件. 式2=庫(kù)恩-塔克條件. 簡(jiǎn)稱K-T條件,K-T點(diǎn). 對(duì)一般非線性規(guī)劃min f (X),h(x)o,i imgj(X

8、) 0, j 1,l它的K-T條件如下設(shè)X是3極小值點(diǎn)，相應(yīng)點(diǎn)=庫(kù)恩-塔克點(diǎn).min f (X), hi(X) 0,hi(X) 0,i 1mgj(X) 0,j 1,l相應(yīng)函數(shù)有一階連續(xù)偏導(dǎo)第16頁共25頁且有效約束的hi(X )和 gj(X ), j J線性無 TOC o 1-5 h z 關(guān)，則 (1, 2，m)DM (1,., i)T, 使 mlf(X ) i hi(X ) j gj(X ) 0 i 1j 1 HYPERLINK l bookmark18 o Current Document jgj(X ) 0,j 1,2,.,ij 0, j 1,2,., l其中 1, 2，m, 1,.,

9、l稱為廣義Lagrange乘子. 注1對(duì)凸規(guī)劃，K-T條件也是充分的.第17頁共25頁設(shè)Xk為某可行解 若Xk是極小點(diǎn), 且gi（xk）0, 和g2（xk）0, 則f（x（k）必與,kk、gi（X ）和g2（X ）同側(cè)，否則有可行下降方向由gi(Xk)和g2(Xk)線性無關(guān)kkf(X )1 gi(X )2 g2(X )第18頁共25頁0例10用庫(kù)恩-塔克條件解非線性規(guī)劃02max f (x) (x 4)1 x 614 6第19頁共25頁14 6min f(x) (x 4) TOC o 1-5 h z 解變?yōu)?gi(x) x 10,g2(x) 6x0f(x)2(x 4), gi(x) 1, g2

10、(x)1 ,引入廣義拉格朗日乘子1, 2，則有2(x4) i 20l(x 1) 0, , f所以,具體分析如下2(6 x ) 0第20頁共25頁若10,若10,2若10,2若10,2若10,2所以最大值點(diǎn)注：f (x) TOC o 1-5 h z 0: x1,點(diǎn)；f (x)9 (16)0：x4, f (x )0；0: x6, f (x )4 (24)x 1,最大值f (x ) 9 .x 1,最大值f (x ) 9 .,八2(x 4)非凸函數(shù),第21頁共25頁附加例題（略）用K-T條件解非線性規(guī)劃一一 2min f (x) (x 3) 0 x5min f (x) (x 3)2, 解 gi(x) x 0,(是凸規(guī)劃)g2(x) 5x01,f(x) 2(x 3), gi(x) 1, g21,第22頁共25頁2(x3)1 x 0所以，具體分析如下.2(5 x ) 01，20若10,20,引出矛盾，無解；若10,20,解得 x0,16,非K-T 點(diǎn)；若i0,20,解得 x5,14,非K-T 點(diǎn)；若10,20,解得x 3 , f (x) 0全局