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

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

2、(0)為可行點,P為某方向,0, 00的梯度若存在0 0, 00的梯度則稱P是X點的一個可行方向.(a)可行方向P與有效約束gj(X(0) gj(X)關系是：gj(X(0)TP 0.記有效約束下標集第3頁共25頁J j|gj(x(0)0,1 j 1若p為x 若p為x (0)的可行方向存在0 0,使得當gj(x(0)從而dgj(X(0) P)dP),則0, o，有gj(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()對有效約束gj(X(0)

3、 0,只要 充分小，得第5頁共25頁gj(X(0) P) 0,所以P是可行方向；對無效約束gj(X(0) 0,同樣只要 充分小就有gj (X(0) P) 0 ,故P也是可行方向；事實上，對無效gj(X(0) 0, P都是可行方向.(3)下降方向(對目標函數(shù)來說)設X(0) R,對某P方向，若在 0, 0, 0 0 內，有f(X(0) P) f(X(0)第6頁共25頁則稱P是一個下降方向.下降方向判定：若f(X(0)TP 0,則P是X(0)的一個下降方向因為 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,當 0, 0時，有g/X P) 0 且 f(X(0) P) f (X (0),是繼續(xù)尋優(yōu)方向.討論：X(0)非極小值點存在可行下降方向 P;X (0)極小值點無可行下降方向P;(可行但不下降，或下降不可行)第8頁共25頁定理(局部極(最)小必要條件)設X是min f(X),X gX) 0局部極小點. f(X),gj(X), j J (有效約束下標集)在X處可 微，gj(X), j J在X處連續(xù)，則在X處無可行下降方向 P，即不存在P ,使* Tgj(X)Tp o,j j, f(X*)TP o,(

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

7、j(X )線性無關 0 0.以上條件稱為 Fritz John條件，X 稱為Fritz John 點.第14頁共25頁(3)必要條件(庫恩-塔克條件)設X是極小值點,f(X)和gj(X)有一階連續(xù)偏導，且有效約束梯度線性無關，則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線性無關第15頁共25頁得 00,作 j 0/ 00,即得.式2=庫恩-塔克條件. 式2=庫恩-塔克條件. 簡稱K-T條件,K-T點. 對一般非線性規(guī)劃min f (X),h(x)o,i imgj(X

8、) 0, j 1,l它的K-T條件如下設X是3極小值點，相應點=庫恩-塔克點.min f (X), hi(X) 0,hi(X) 0,i 1mgj(X) 0,j 1,l相應函數(shù)有一階連續(xù)偏導第16頁共25頁且有效約束的hi(X )和 gj(X ), j J線性無 TOC o 1-5 h z 關，則 (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對凸規(guī)劃，K-T條件也是充分的.第17頁共25頁設Xk為某可行解 若Xk是極小點, 且gi（xk）0, 和g2（xk）0, 則f（x（k）必與,kk、gi（X ）和g2（X ）同側，否則有可行下降方向由gi(Xk)和g2(Xk)線性無關kkf(X )1 gi(X )2 g2(X )第18頁共25頁0例10用庫恩-塔克條件解非線性規(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所以最大值點注：f (x) TOC o 1-5 h z 0: x1,點；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 點；若i0,20,解得 x5,14,非K-T 點；若10,20,解得x 3 , f (x) 0全局