1、第六章非線性規劃11 引 言非線性規劃是運籌學中包含內容最多，應用最廣泛的一個分支，計算遠比線性規劃復雜，由于時間的限制，只能作簡單的介紹。例6-1 電廠投資分配問題水電部門打算將一筆資金分配去建設n個水電廠，其庫容量為ki,i=1,2.n,各2電廠水庫徑流輸入量分布為Fi(Q)，發電量隨庫容與徑流量而變化，以Ei(ki,Q)表示。計劃部門構造一個模型，即在一定條件下，使總發電量年平均值最大，用數學語言來說，使其期望值最大。對每個電廠i ，其年發電量的期望值為 Ei(ki,Q) dFi(Q)設V為總投資額，Vi為各水電廠的投資，3都是ki的非線性函數，構造非線性規劃模型如下： Max Ei(k

2、i,Q) dFi(Q)s.t.V1(k1)+ V2(k2)+ + Vn(kn)=VV1(k1), V2(k2),Vn(kn) 0利用一定的算法，可求出最優分配ki*和Vi *(i=1,2,.n).4主要內容非線性規劃理論方面應用方面算法方面互補穩定靈敏對偶問題最優性條件無約束問題直接法有約束問題間接法5一般模型Min f(X)s.t. hi(X) = 0 (i=1,2,.m) （P） gj(X) 0 (j=1,2.l) X En f(X) hi(X) gj(X) 為En上的實函數。6幾個概念定義1 如果X滿足（P）的約束條件 hi(X)=0 (i=1,2,.m) gj(X) 0 (j=1,2.

3、l) 則稱X En 為（P）的一個可行解。記（P）的所有可行解的集合為D，D稱為（P）可行域。7幾個概念定義2 X*稱為（P）的一個（整體）最優解，如果X* D，滿足 f(X) f(X*)， X D。 8幾個概念定義3 X*稱為（P）的一個（局部）最優解，如果X* D，且存在一個X*的鄰域N(X* ,)= X En X- X* 0滿足 f(X) f(X*)， X D N(X* ,) 9f(X)局部最優解整體最優解10模型分類Min f(X)s.t. hi(X)=0 (i=1,2,.m) （P） gj(X) 0 (j=1,2.l) X En f(X) hi(X) gj(X) 為En上的實函數。1

4、1模型分類1 如果 f(X) hi(X) gj(X) 中至少有一個函數不是線性（仿射）函數，則稱（P）為非線性問題。 如果 f(X) hi(X) gj(X) 都是線性（仿射）函數，則稱（P）為線性問題。12模型分類2若m=l=0 ，則稱（P）為無約束問題。 （P1） Min f(X) X En 13模型分類2若m0，l=0 ，則稱（P）為帶等式約束問題。 （P2） Min f(X) s.t. hi(X)=0 (i=1,2,.m) X En 14模型分類2若m=0，l 0 ，則稱（P）為帶不等式約束問題。 （P3） Min f(X) s.t. gj(X) 0 (j=1,2.l) X En 15模

5、型分類2若m 0，l 0 ，則稱（P）為一般問題。 （P） Min f(X) s.t. hi(X)=0 (i=1,2,.m) gj(X) 0 (j=1,2.l) X En 16凸函數的概念凸集概念： 設D是n維線性空間En的一個點集，若D中的任意兩點x(1),x(2)的連線上的一切點x仍在D中，則稱D為凸集。即：若D中的任意兩點x(1),x(2) D，存在01 使得x= x(1)+(1- )x(2) D,則稱D為凸集17凸函數的概念定義：定義在凸集DEn上的函數f(X)如果對任意兩點x(1),x(2) D，均有0 0( 0 )則稱H(X)在X* 點正定(半正定).24海賽(Hesse)矩陣 x

6、xf(X) = H(X)2f/x12 2f/x1x2 . 2f/x1xn2f/x2x1 2f/x22 . 2f/x2xn.2f/xnx1 2f/xnx2 . 2f/xn2=252 最優性條件最優性條件的研究是非線性規劃理論研究的一個中心問題。為什么要研究最優性條件？本質上把可行解集合的范圍縮小。它是許多算法設計的基礎。26無約束問題的最優性條件（P1） Min f(X) X En 定理1（一階必要條件） 設f(X)在X*點可微，則X*為（P1） 的一個局部最優解，一定有f(X*)=grad f(X*)=0（ X*稱為駐點）27無約束問題的最優性條件（P1） Min f(X) X En 定理2（

7、二階必要條件） 設f(X)在X*點二階可微，如果X*為（P1） 的一個局部最優解，則有 f(X*) =0 和 H（ X* ）為半正定。28無約束問題的最優性條件（P1） Min f(X) X En 定理3（二階充分條件） 設f(X)在X*點二階可微，如果f(X*) =0 和 H(X*)為正定，則X*為(P1) 的一個局部最優解。（ H(X)在X*的鄰域內為半正定。29無約束問題的最優性條件（P1） Min f(X) X En 定理4（一階充分條件） 設f(X)為En上的凸函數，又設f(X)在X*點可微，如果f(X*) =0 ，則X*為(P1) 的一個整體最優解。30例6-2 Min f(X)=

8、（x2-1)3 X E1 解：利用一階必要條件求出有可能成為最優解的那些點: f(X) = 6x(x2-1)2 =0 得到：x1=0,x2=1,x3= -1進一步考慮二階必要條件，縮小范圍：31H(X) =xxf(X) = 6(x2-1)2+24 x2(x2-1) H(x1) =xxf(x1) = xxf(0) =60H(x2) =xxf(x2) = xxf(1) = 0H(x3) =xxf(x3) = xxf(-1) =0 f(X)在x1=0點正定，依二階必要條件， x1=0為（P1）的局部最優解。而x2=1， x3= -1滿足二階必要條件和一階必要條件，但它們顯然都不是最優解。32例6-3

9、 Min f(X)= 2x12+5x22+x32+ 2x2x3 + 2x1x3 - 6x2+3 X E3 解：f(X) = （4x1+ 2x3, 10 x2+ 2x3 6, 2x1+ 2x2 + 2x3 ）=0 駐點x*=(1,1,-2)H(X) =xxf(X)= 0 20 10 22 2 2 33H(X) =xxf(X)= 0 20 10 22 2 2 各階主子式：40,4 00 10=400 0 20 10 22 2 2 =24034H(X)正定， X*=(1,1,-2)為最優解。 f(X*)=035解無約束問題的算法：求f(X)的駐點X*，若是凸函數，得到最優解。否則，轉下一步。在駐點X

10、*處，計算H(x)。根據H(x)來判斷該駐點X*是否是極值點。36若H(x)為正定，該駐點X*是嚴格局部極小值點；若H(x)為負定，該駐點X*是嚴格局部極大值點；若H(x)為半正定（半負定）則進一步觀察它在該點某鄰域內的情況，如果保持半正定（半負定），那它們是嚴格局部極小值點（極大值點）；如果H(x) 不定的，該駐點X*就不是f(X)極值點。37例6-4 求極值 f(X)= x1 + 2x3 +x2x3 -x12-x22-x32 X E3 解：f(X) = (1-2x1,x3 -2x2, 2+x2 - 2x3 ) = 0 駐點x*=(1/2,2/3,4/3)H(X) =xxf(X)=-2 0

11、00 -2 10 1 -2 38H(X) =xxf(X)=各階主子式：-20= - 60-2 0 00 -2 10 1 -2 -2 0 00 -2 10 1 -2 39H(X)負定， f(X) 是凹函數X*=(1/2,2/3,4/3)為極大值點。 f(X*)= f(1/2,2/3,4/3)=19/1240帶不等式約束問題的最優性條件（P3） Min f(X) s.t. gj(X) 0 (j=1,2.l) X En 令X* D，記J（X*）= j gj(X*) =0 緊約束集合。41定理5（Kuhn-Tucker必要條件） 設f(X)和每個gj(X)在X* D點可微，又設 gj(X) ( j J

12、（X*）) 線性無關，如果X* 為（P3）的局部最優解，則存在（u1,u2,ul) 0,使得 f(X* )+ uj gj(X* ) =0gj(X* ) 0 j=1,2.luj gj(X* ) =0 j=1,2.l42定理6（一階充分條件） 設f(X)和每個gj(X)都是En中的凸函數，且在X* D點可微，如果存在（u1,u2,ul) 0,使得 f(X* )+ uj gj(X* ) =0gj(X* ) 0 j=1,2.luj gj(X* ) =0 j=1,2.l則X* 為（P3）的一個最優解。43一般問題的最優性條件（P） Min f(X) s.t. hi(X)=0 (i=1,2,.m) gj(

13、X) 0 (j=1,2.l) X En 44定理7（Kuhn-Tucker必要條件） 設f(X)和每個gj(X)在X*D點可微，每個hi(X)在X*D點連續可微,又設gj(X)( j J(X*)和hi(X) 線性無關,如果X* 為(P)的局部最優解,一定存在(u1,u2,ul) 0和(v1,v2,vm),使得 f(X*)+ujgj(X* ) + vihi(X* ) =0gj(X* ) 0 uj gj(X* ) =0 j=1,2.lhi(X* ) =0 i=1,2.m45定理8（ Kuhn-Tucker充分條件） 設f(X)和每個gj(X)都是En中的凸函數，每個gj(X) 都是線性函數，如果存

14、在（u1,u2,ul) 0,和(v1,v2,vm),使得 f(X*)+ujgj(X* ) + vihi(X* ) =0gj(X* ) 0 uj gj(X* ) =0 j=1,2.lhi(X* ) =0 i=1,2.m則X* 為（P）的一個最優解。46算法概述 一個算法（Algorithm)就是一種求解方法，它可看作為一個循環過程，按照一組指令和規定的停算準則，產生近似解序列，它應該收斂到整體最優解，但由于某些原因（不連續性、無凸性、規模大、實現方面困難等）常使得計算難以符合以上條件，往往是一個無限的過程，因而給出停算準則，如果在第k次循環時，滿足停算準則條件，則停算。47 常用的停算準則條件：Xk+n-Xk Xk+1-Xk / Xk (Xk)- (Xk+1) (Xk)- (Xk+1) )/ (Xk) (Xk)- (X*) etc48 評價一個算法（Algorithm)的好壞，通常注意以下幾個方面：通用性(Generality) 可求解問題的廣度，越大越好。可靠性(Reliability) 指以合理的精度，求解設計的這個算法時，針對要解決那個問題的能力。 任意給定一個算法