運(yùn)籌學(xué)資料非線性規(guī)劃

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

2、i,Q) dFi(Q)s.t.V1(k1)+ V2(k2)+ + Vn(kn)=VV1(k1), V2(k2),Vn(kn) 0利用一定的算法，可求出最優(yōu)分配ki*和Vi *(i=1,2,.n).4主要內(nèi)容非線性規(guī)劃理論方面應(yīng)用方面算法方面互補(bǔ)穩(wěn)定靈敏對(duì)偶問題最優(yōu)性條件無約束問題直接法有約束問題間接法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上的實(shí)函數(shù)。6幾個(gè)概念定義1 如果X滿足（P）的約束條件 hi(X)=0 (i=1,2,.m) gj(X) 0 (j=1,2.

3、l) 則稱X En 為（P）的一個(gè)可行解。記（P）的所有可行解的集合為D，D稱為（P）可行域。7幾個(gè)概念定義2 X*稱為（P）的一個(gè)（整體）最優(yōu)解，如果X* D，滿足 f(X) f(X*)， X D。 8幾個(gè)概念定義3 X*稱為（P）的一個(gè)（局部）最優(yōu)解，如果X* D，且存在一個(gè)X*的鄰域N(X* ,)= X En X- X* 0滿足 f(X) f(X*)， X D N(X* ,) 9f(X)局部最優(yōu)解整體最優(yōu)解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上的實(shí)函數(shù)。1

4、1模型分類1 如果 f(X) hi(X) gj(X) 中至少有一個(gè)函數(shù)不是線性（仿射）函數(shù)，則稱（P）為非線性問題。 如果 f(X) hi(X) gj(X) 都是線性（仿射）函數(shù)，則稱（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凸函數(shù)的概念凸集概念： 設(shè)D是n維線性空間En的一個(gè)點(diǎn)集，若D中的任意兩點(diǎn)x(1),x(2)的連線上的一切點(diǎn)x仍在D中，則稱D為凸集。即：若D中的任意兩點(diǎn)x(1),x(2) D，存在01 使得x= x(1)+(1- )x(2) D,則稱D為凸集17凸函數(shù)的概念定義：定義在凸集DEn上的函數(shù)f(X)如果對(duì)任意兩點(diǎn)x(1),x(2) D，均有0 0( 0 )則稱H(X)在X* 點(diǎn)正定(半正定).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 最優(yōu)性條件最優(yōu)性條件的研究是非線性規(guī)劃理論研究的一個(gè)中心問題。為什么要研究最優(yōu)性條件？本質(zhì)上把可行解集合的范圍縮小。它是許多算法設(shè)計(jì)的基礎(chǔ)。26無約束問題的最優(yōu)性條件（P1） Min f(X) X En 定理1（一階必要條件） 設(shè)f(X)在X*點(diǎn)可微，則X*為（P1） 的一個(gè)局部最優(yōu)解，一定有f(X*)=grad f(X*)=0（ X*稱為駐點(diǎn)）27無約束問題的最優(yōu)性條件（P1） Min f(X) X En 定理2（

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

8、（x2-1)3 X E1 解：利用一階必要條件求出有可能成為最優(yōu)解的那些點(diǎn): f(X) = 6x(x2-1)2 =0 得到：x1=0,x2=1,x3= -1進(jìn)一步考慮二階必要條件，縮小范圍：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點(diǎn)正定，依二階必要條件， x1=0為（P1）的局部最優(yōu)解。而x2=1， x3= -1滿足二階必要條件和一階必要條件，但它們顯然都不是最優(yōu)解。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 駐點(diǎn)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)為最優(yōu)解。 f(X*)=035解無約束問題的算法：求f(X)的駐點(diǎn)X*，若是凸函數(shù)，得到最優(yōu)解。否則，轉(zhuǎn)下一步。在駐點(diǎn)X

10、*處，計(jì)算H(x)。根據(jù)H(x)來判斷該駐點(diǎn)X*是否是極值點(diǎn)。36若H(x)為正定，該駐點(diǎn)X*是嚴(yán)格局部極小值點(diǎn)；若H(x)為負(fù)定，該駐點(diǎn)X*是嚴(yán)格局部極大值點(diǎn)；若H(x)為半正定（半負(fù)定）則進(jìn)一步觀察它在該點(diǎn)某鄰域內(nèi)的情況，如果保持半正定（半負(fù)定），那它們是嚴(yán)格局部極小值點(diǎn)（極大值點(diǎn)）；如果H(x) 不定的，該駐點(diǎn)X*就不是f(X)極值點(diǎn)。37例6-4 求極值 f(X)= x1 + 2x3 +x2x3 -x12-x22-x32 X E3 解：f(X) = (1-2x1,x3 -2x2, 2+x2 - 2x3 ) = 0 駐點(diǎn)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ù)定， f(X) 是凹函數(shù)X*=(1/2,2/3,4/3)為極大值點(diǎn)。 f(X*)= f(1/2,2/3,4/3)=19/1240帶不等式約束問題的最優(yōu)性條件（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必要條件） 設(shè)f(X)和每個(gè)gj(X)在X* D點(diǎn)可微，又設(shè) gj(X) ( j J

12、（X*）) 線性無關(guān)，如果X* 為（P3）的局部最優(yōu)解，則存在（u1,u2,ul) 0,使得 f(X* )+ uj gj(X* ) =0gj(X* ) 0 j=1,2.luj gj(X* ) =0 j=1,2.l42定理6（一階充分條件） 設(shè)f(X)和每個(gè)gj(X)都是En中的凸函數(shù)，且在X* D點(diǎn)可微，如果存在（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）的一個(gè)最優(yōu)解。43一般問題的最優(yōu)性條件（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必要條件） 設(shè)f(X)和每個(gè)gj(X)在X*D點(diǎn)可微，每個(gè)hi(X)在X*D點(diǎn)連續(xù)可微,又設(shè)gj(X)( j J(X*)和hi(X) 線性無關(guān),如果X* 為(P)的局部最優(yōu)解,一定存在(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充分條件） 設(shè)f(X)和每個(gè)gj(X)都是En中的凸函數(shù)，每個(gè)gj(X) 都是線性函數(shù)，如果存

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）的一個(gè)最優(yōu)解。46算法概述 一個(gè)算法（Algorithm)就是一種求解方法，它可看作為一個(gè)循環(huán)過程，按照一組指令和規(guī)定的停算準(zhǔn)則，產(chǎn)生近似解序列，它應(yīng)該收斂到整體最優(yōu)解，但由于某些原因（不連續(xù)性、無凸性、規(guī)模大、實(shí)現(xiàn)方面困難等）常使得計(jì)算難以符合以上條件，往往是一個(gè)無限的過程，因而給出停算準(zhǔn)則，如果在第k次循環(huán)時(shí)，滿足停算準(zhǔn)則條件，則停算。47 常用的停算準(zhǔn)則條件：Xk+n-Xk Xk+1-Xk / Xk (Xk)- (Xk+1) (Xk)- (Xk+1) )/ (Xk) (Xk)- (X*) etc48 評(píng)價(jià)一個(gè)算法（Algorithm)的好壞，通常注意以下幾個(gè)方面：通用性(Generality) 可求解問題的廣度，越大越好?？煽啃?Reliability) 指以合理的精度，求解設(shè)計(jì)的這個(gè)算法時(shí)，針對(duì)要解決那個(gè)問題的能力。 任意給定一個(gè)算法