1、第六章 非線性規劃,第一節 基本概念 第三節 無約束極值問題 第四節 約束極值問題,1/110,第一節 基本概念,一、非線性規劃數學模型,2/110,3/110,非線性規劃數學模型一般形式： Min f(X) s.t. hi(X)=0 (i=1, 2, , m) gj(X)0， (j=1, 2, , l) X=(x1, x2, , xn )T 是n維歐式空間En中的點，目標函數f(X)，約束函數hi(X)和gj(X) 是X實函數。 有時，非線性規劃數學模型寫成： Min f(X) s.t. gj(X)0， (j=1, 2, , l) 若某gj(X) =0，可以gj(X)0和 -gj(X)0代替

2、之,4/110,5/110,A(0,5,B,C,D(4,1,1,O,1,2,5,x1,x2,3,4,6/110,7/110,8/110,9/110,10/110,AT=A，即 aji =aij 。若aij均為實數，則稱f(X)=XTAX為實二次型。A與二次型一一對應。 (1)若對于非零X ，實二次型總有XTAX0，則稱為正定的； (2)若對于非零X ，實二次型總有XTAX0，而對另一些非零X， XTAX0，則稱為不定的； (4)若對任意非零X ，XTAX0 ，則稱為半正定的。若對任意非零X ，XTAX0 ，則稱為半負定的。 (5)A相應地稱正定、負定、不定、半定,11/110,實二次型f(X)

3、=XTAX為正定的充要條件是：0 a110，|a11 a12 | |a11 a12 a13| |a21 a22 |0 |a21 a22 a23|0 |a31 a32 a33| |a11 a12 a1n | |a21 a22 a2n | |. . . |0 |. . . | |. . . | |an1 an2 ann,12/110,實二次型f(X)=XTAX為負定的充要條件是： a110 |a21 a22 a23|0 |. . . | |. . . | |an1 an2 ann,13/110,例1判定如下二次型的性質。 -5 2 2 0 1 1 A= 2 -6 0 B= 1 0 -3 2 0 -

4、4 1 -3 0 矩陣A： -50 |-5 2 2| | 2 -6 | | 2 -6 0|= -800 | 2 0 -4| 矩陣A為負定。 矩陣B： b11=0， | 0 1 | = -10 | 1 0 | 矩陣B為不定,14/110,15/110,16/110,17/110,18/110,19/110,20/110,顛倒上述定義中不等式方向，可得凹和嚴格凹函數的定義。 若f(X)是（嚴格）凸函數，則g(X)=- f(X)是（嚴格）凹函數。（幾何意義見下圖） 2. 凸函數性質 性質1 設f(X)為定義在凸集Rc上凸函數，則對于任何實數0， f(X)也是定義在Rc上凸函數。 性質2 設f1(X)

5、和f2(X)均為定義在凸集Rc上凸函數，則 f(X)=f1(X)+f2(X)也是定義在Rc上凸函數,21/110,x,f(x,f(x(2,f(x(1,x(1,x (2,22/110,x,f(x,f(x(2,f(x(1,x(1,x (2,23/110,x,f(x,f(x(2,f(x(1,x(1,x (2,24/110,性質2 推論 若干凸函數非負線性組合 1f1(X)+2f2(X)+mfm(X)仍為凸集Rc上的凸函數。i0(i=1, 2, , m) 性質3設f(X)為凸集Rc上的凸函數，則對于每一個實數0，集合（稱為水平集） S=X|XRc，f(X)是凸集。 3.凸函數的判定 可直接從定義出發。

6、但是，對于可微凸函數，也可利用如下兩個條件,25/110,26/110,27/110,28/110,29/110,O,Rc,x1,x2,30/110,31/110,凸規劃性質 (1) 可行解集為凸集。 (2) 若有最優解，則最優解集為凸集。 (3) 任何局部極值點也是全局極值點。 (4) 若目標函數為嚴格凸函數，且有最優解，則該最優解唯一。 以下驗證上述四個性質： 考慮凸規劃 Min f(X) s.t. gj(X)0， (j=1, 2, , l) f(X)和-gj(X) (j=1, 2, , l)均為凸函數,32/110,33/110,34/110,例4驗證如下非線性規劃為凸規劃： Min f

7、(X)=x12+x22-4x1+4 s.t. g1(X)=x1-x2+20， g2(X)= -x12+x2-10， g3(X)= x10， g4(X)= x20 g1(X)、g3(X)和g4(X)是x1和x2的線性函數，也是凹函數。 對于g2(X)，有,35/110,36/110,0,Rc,x1,x2,1.0,g1(X)=0,g2(X)=0,37/110,38/110,目標函數求最小的規劃問題，應有f(X(0)f(X(1)f(X(2)f(X(3)f(X(k) 這就是下降迭代算法。 該算法一般格式與步驟： (1)選取初始X(0)，k:=0; (2)確定下降方向。若已到達的X(k)不是極小點，就確

8、定一個方向P(k)，使目標函數沿此方向能夠下降，但不要越出可行域。 (3)確定步長。沿P(k)前進一定距離（步長），到達新點X(k+1)。即在從X(k)出發的射線X=X(k) +P(k)上(0)，選擇一個k，到達新點X(k+1) =X(k) +k P(k)，使得,39/110,f(X(k)f(X(k+1)=f(X(k) +kP(k) k是使f(X(k) +kP(k)=minf(X(k) +P(k)成立的。 (4)檢查新點是否或接近極小點。若是，停。否則，k:= k+1，返回(2)繼續迭代。 已有不少辦法確定搜索方向P(k) 。 多數按使目標函數下快最快的原則確定步長，即求解一維問題f(X(k)

9、 +kP(k)=minf(X(k) +P(k)，故稱這一過程為（最優）一維搜索或線搜索。如此確定的步長，稱為最優步長,40/110,41/110,42/110,43/110,第三節 無約束極值問題,44/110,45/110,無約束極值問題表示 Min f(X)，XRc 前文已指出，須用迭代法求解。迭代法有解析法和直接法兩類。 解析法要用到目標函數一階和二階導數。 直接法不用，只用目標函數值。有些目標函數沒有導數，只能用直接法,46/110,47/110,48/110,49/110,50/110,51/110,52/110,53/110,54/110,55/110,56/110,例9人工神經網

10、絡 模仿人腦神經網絡，將具有識別、記憶功能的人工神經元以各種不同的方式連接成不同的網絡。用于計算、分類、模式識別、評價、預測、控制、智能機器人、數據挖掘等領域。 1. 人工神經元與感知機 (1) 神經元感知功能 人工神經元 （感知機,57/110,58/110,59/110,60/110,61/110,62/110,63/110,先賦予w=(w1,w2 , , wm)T一個初始值，然后逐步調整，使其逐步逼近極值點w*=(w*1,w*2 , , w*m)T，調整方向P=(p1, p2 , , pm)T，調整量是P，步長就是上面的“學習系數”。 當P= -f(w)時，總誤差f(w)下降最快,64/

11、110,65/110,66/110,67/110,68/110,69/110,70/110,71/110,72/110,第四節 約束極值問題,73/110,74/110,75/110,76/110,0,Rc,x1,x2,1.0,g1(X)=0,g2(X)=0,黑色方向不可行,77/110,78/110,79/110,80/110,81/110,例】 Min f (x)= - 4x1 - 6x2 +2x12+2 x1x2+2x22 s.t. -x1 -2x2 +20，1x10，x20 x=(x1, x2)T=(1/2, 3/4)T是否為上面問題的解？ 【解】 f(x)=(4x1+2x2-4，2x

12、1+4x2-6)T g1(x)=(-1，-2)T g2(x)=(1，0)T g3(x)=(0，1)T,82/110,記x(0)=(1/2, 3/4)T g1(x(0)= -1/2 -2(3/4) +2=0 g2(x(0)= 1 -1/2=1/20 g3(x(0)= 3/40 所以，在x(0)處，g1(x)是有效約束。 f(x(0)=(-1/2，-2)T，g1(x(0)=(-1，-2)T， g2(x(0)=(1，0)T，g3(x(0)=(0，1)T,x1,x2,83/110,x(0)不是解。 因在f(x(0)和g1(x(0)之間，可找到一個方向P，使得f(x(0)TP0同時成立，即P同f(x(0

13、)成鈍角，而同g1(x(0)成銳角,1,2,1,P,f(x(0,g1(x(0,x(0,84/110,或者，令P=(p1，p2)T， 下列不等式組有解： f(x(0)TP= -p1/2-2p20 只須令p1= -1，p2= 3/8即可，所以，x(0)= (1/2, 3/4)T不是問題的解,85/110,2. 庫恩塔克條件Kuhn-Tucker 先講幾個預備性定理。 (1)Gordan引理 設A1, A2, , Al是l個n維向量，不存在n維向量P使 AjTP0 (j=1, 2, , l) 成立的充要條件是，存在不全為零的非負實數1, 2, , l，使 1A1+ 2A2+lAl=0 幾何意義明顯,

14、86/110,Gordan引理 設A1, A2, , Al是l個n維向量， AjTP0 (j=1, 2, , l) 成立的充要條件是，不存在=(1, 2, , l)T0，使 1A1+ 2A2+lAl=0成立。 或Gordan引理 A1T 方程組 A2T P0有解的充要條件是 . . . AlT 方程組 (A1, A2, , Al) =0， 0無解,87/110,如果有n維向量P使 AjTP0 (j=1, 2, , l) 則對于 =(1, 2, , l)T0，有 1A1TP+2A2TP+ +lAlTP0 但1A1TP+2A2TP+lAlTP =PT(1A1+2A2+lAl)，這時要說存在 =(1

15、, 2, , l)T0，有1A1+2A2+lAl=0，則產生矛盾,88/110,A1,A2,A3,P,H,O,A1,A3,A2,P,H,O,a,b,89/110,90/110,91/110,92/110,Fritz John(19101994)1933在哥廷根大學學數學，當年因希特勒得勢，被迫前往英國。1934年獲得哥廷根大學博士學位。1935年任肯塔基大學副教授，1941年入美國籍。19431945于馬里蘭阿伯丁試驗場研究彈道學，1946年到紐約大學工作，一直到退休,93/110,94/110,Harold W. Kuhn Professor Emeritus Mathematics Pri

16、nceton University kuhnmath.Princeton.EDU,95/110,96/110,97/110,K-T條件是X*成為極小點的必要條件，但是對于凸規劃，也是充分條件,98/110,99/110,100/110,101/110,4x1+4x2 + 1 +22=6 4x1+6x2 + 1 +32=3 1(1-x1-x2)=0 2(4-2x1-3x2)=0 1, 20 分成幾種情況： (i) 1=2=0 x1=3, x2= -1.5, g1(X)=1-x1-x2=1-3+1.5= -0.50 不是K-T點,102/110,ii) 1=0, 20 4x1+4x2 +22=6

17、4x1+6x2 +32=3 4-2x1-3x2=0 x1 =2-1.5x2代入前兩式，得 2= -5/30，是K-T點,103/110,iv) 10, 20 4x1+4x2 +1+22=6 4x1+6x2 +1+32=3 4-2x1-3x2=0 1-x1-x2=0 解后兩個方程，得x1= -1, x2= 2, 代入前兩個方程 1+22=2 1+32= -5，得1=16, 2= -7, 不是K-T點。 所以，X* =(x1, x2)T=(5/2, -3/2)T， f(X*)= 2x12+4x1x2+3x22-6x1-3x2 =25/2-15+27/4-15+9/2=95/4-30= -25/2,

18、104/110,105/110,4x1+4x2 + 1 +22-3=6 4x1+6x2 + 1 +32-4=3 1(1-x1-x2)=0 2(4-2x1-3x2)=0 3x1=0 4x2=0 1, 2, 3, 4 0 構造如下線性規劃問題,106/110,Min (z)=z1+z2 4x1+4x2 + 1 +22-3 +z1 =6 4x1+6x2 + 1 +32 -4 +z2=3 x1+ x2 + x3 =1 2x1+3x2 +x4 =4 x1, x2, x3, x4, 1, 2, 3, 4, z1, z2 0 可利用單純形表求解，但注意x1和3, x2和4, x3和1, x4和2,不能同時為基變量,107/66,108/66,x4和2不能同時