第三章非線性規(guī)劃

1、第三章非線性規(guī)劃1非線性規(guī)劃1.1非線性規(guī)劃的實(shí)例與定義如果目標(biāo)函數(shù)或約束條件中包含非線性函數(shù)，就稱這種規(guī)劃問題為非線性規(guī)劃問題。一般說來，解非線性規(guī)劃要比解線性規(guī)劃問題困難得多。而且，也不象線性規(guī)劃有單純形法這一通用方法，非線性規(guī)劃目前還沒有適于各種問題的一般算法，各個(gè)方法都有自己特定的適用范圍。下面通過實(shí)例歸納出非線性規(guī)劃數(shù)學(xué)模型的一般形式，介紹有關(guān)非線性規(guī)劃的基本概念。例1（投資決策問題）某企業(yè)有n個(gè)項(xiàng)目可供選擇投資，并且至少要對(duì)其中一個(gè)項(xiàng)目投資。已知該企業(yè)擁有總資金A元，投資于第i（i=1,A,n）個(gè)項(xiàng)目需花資金a元,i并預(yù)計(jì)可收益b元。試選擇最佳投資方案。i決定投資第i個(gè)項(xiàng)目.=人決

2、定不投資第i個(gè)項(xiàng)目.=解設(shè)投資決策變量為，投資總收益為刃bx。因?yàn)樵摴局辽僖獙?duì)一個(gè)項(xiàng)目投資，并iii=1x.Io,則投資總額為axiii=1且總的投資金額不能超過總資金A，故有限制條件0為axAiii=1另外，由于x（i=1,A,n）只取值0或1，所以還有ix（1一x）=0,i=1,A,n.ii最佳投資方案應(yīng)是投資額最小而總收益最大的方案，所以這個(gè)最佳投資決策問題歸結(jié)為總資金以及決策變量（取0或1）的限制條件下，極大化總收益和總投資之比。因此，其數(shù)學(xué)模型為：XnbxiimaxQ=axiii=1s.t.0axAiix（1-x）=0,i=1,A,n.ii上面例題是在一組等式或不等式的約束下，求一

3、個(gè)函數(shù)的最大值（或最小值）問題，其中目標(biāo)函數(shù)或約束條件中至少有一個(gè)非線性函數(shù)，這類問題稱之為非線性規(guī)劃問題，簡(jiǎn)記為（NP）。可概括為一般形式minf（x）s.t.h.(x)0,g(x)=0,ij=1,A,qi=1,A,P(NP)其中x二xAxT稱為模型(NP)的決策變量，f稱為目標(biāo)函數(shù)，g.(i=1,A,p)1ni和h.(j=1,A,q)稱為約束函數(shù)。另外，g.(x)二0(i=1,A,p)稱為等式約束，jih,x)0(j=1,A,q)稱為不等式約束。對(duì)于一個(gè)實(shí)際問題，在把它歸結(jié)成非線性規(guī)劃問題時(shí)，一般要注意如下幾點(diǎn)：(i) 確定供選方案：首先要收集同問題有關(guān)的資料和數(shù)據(jù)，在全面熟悉問題的基礎(chǔ)上

4、，確認(rèn)什么是問題的可供選擇的方案，并用一組變量來表示它們。(ii) 提出追求目標(biāo)：經(jīng)過資料分析，根據(jù)實(shí)際需要和可能，提出要追求極小化或極大化的目標(biāo)。并且，運(yùn)用各種科學(xué)和技術(shù)原理，把它表示成數(shù)學(xué)關(guān)系式。(iii) 給出價(jià)值標(biāo)準(zhǔn)：在提出要追求的目標(biāo)之后，要確立所考慮目標(biāo)的“好”或“壞”的價(jià)值標(biāo)準(zhǔn)，并用某種數(shù)量形式來描述它。(iv) 尋求限制條件：由于所追求的目標(biāo)一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問題的所有限制條件，這些條件通常用變量之間的一些不等式或等式來表示。1.2 線性規(guī)劃與非線性規(guī)劃的區(qū)別如果線性規(guī)劃的最優(yōu)解存在，其最優(yōu)解只能在其可行域的邊界上達(dá)到(特別是可行域的

5、頂點(diǎn)上達(dá)到)；而非線性規(guī)劃的最優(yōu)解(如果最優(yōu)解存在)則可能在其可行域的任意一點(diǎn)達(dá)到。1.3 非線性規(guī)劃的Matlab解法Matlab中非線性規(guī)劃的數(shù)學(xué)模型寫成以下形式minf(x)AxBAeqx=BeqC(x)0、Ceq(x)=0其中f(x)是標(biāo)量函數(shù)，A,B,Aeq,Beq是相應(yīng)維數(shù)的矩陣和向量，C(x),Ceq(x)是非線性向量函數(shù)。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)它的返回值是向量x，其中FUN是用M文件定義的函數(shù)f(x)；X0是x的初始值；A,B,Aeq,Beq定義了線性約束A*XB,Aeq*X=

6、Beq，如果沒有等式約束，則A=,B=,Aeq=,Beq=；LB和UB是變量x的下界和上界，如果上界和下界沒有約束，則LB=，UB=，如果x無下界，則LB=-inf,如果x無上界，則UB=inf；NONLCON是用M文件定義的非線性向量函數(shù)C(x),Ceq(x)；OPTIONS定義了優(yōu)化參數(shù)，可以使用Matlab缺省的參數(shù)設(shè)置。例2求下列非線性規(guī)劃問題minf(x)=x2+x2+812x2-xn012一x一x2+2=012x,xn0.12(i)編寫M文件funl.mfunctionf=fun1(x);f=x(1)入2+x(2)入2+8;和M文件fun2.mfunctiong,h=fun2(x)

7、;g=-x(1)入2+x(2);h=-x(1)-x(2)入2+2;%等式約束(ii)在Matlab的命令窗口依次輸入options=optimset;x,y=fmincon(fun1,rand(2,1),zeros(2,1),.fun2,options)就可以求得當(dāng)x二1,x二1時(shí)，最小值y=10。121.4求解非線性規(guī)劃的基本迭代格式記(NP)的可行域?yàn)镵。若x*eK，并且f(x*)f(x),VxeK則稱x*是(NP)的整體最優(yōu)解，f(x*)是(NP)的整體最優(yōu)值。如果有f(x*)f(x),VxeK,x豐x*則稱x*是(NP)的嚴(yán)格整體最優(yōu)解，f(x*)是(NP)的嚴(yán)格整體最優(yōu)值。若x*eK

8、，并且存在x*的鄰域N5(x*)，使f(x*)f(x),VxeN(x*)IK，則稱x*是(NP)的局部最優(yōu)解，f(x*)是(NP)的局部最優(yōu)值。如果有f(x*)0，使f(x+tp)0，使X+tpgK,稱向量p是點(diǎn)X處關(guān)于K的可行方向。一個(gè)向量P,若既是函數(shù)f在點(diǎn)X處的下降方向，又是該點(diǎn)關(guān)于區(qū)域K的可行方向，則稱之為函數(shù)f在點(diǎn)X處關(guān)于K的可行下降方向?，F(xiàn)在，我們給出用基本迭代格式(1)求解(NP)的一般步驟如下：0選取初始點(diǎn)X0，令k:二0。1構(gòu)造搜索方向，依照一定規(guī)則，構(gòu)造f在點(diǎn)Xk處關(guān)于K的可行下降方向作為搜索方向pk。2尋求搜索步長(zhǎng)。以Xk為起點(diǎn)沿搜索方向pk尋求適當(dāng)?shù)牟介L(zhǎng)t，使目標(biāo)函數(shù)值

9、k有某種意義的下降。3求出下一個(gè)迭代點(diǎn)。按迭代格式(1)求出Xk+1=Xk+tpk。k若Xk+1已滿足某種終止條件，停止迭代。4以Xk+1代替Xk,回到1步。1.5凸函數(shù)、凸規(guī)劃設(shè)f(X)為定義在n維歐氏空間E(n)中某個(gè)凸集R上的函數(shù)，若對(duì)任何實(shí)數(shù)a(0a1)以及R中的任意兩點(diǎn)X(1)和X，恒有f(a%+(1a)x(2)af(x(1)+(1a)f(x)則稱f(x)為定義在R上的凸函數(shù)。若對(duì)每一個(gè)a(0a1)和x豐xgR恒有f(aX(1)+(1a)X(2)af(X(1)+(1a)f(X(2)則稱f(%)為定義在R上的嚴(yán)格凸函數(shù)?？紤]非線性規(guī)劃minf(x)SXGRR二xIg(x)0,j=1,2

10、,A,1假定其中f(x)為凸函數(shù)，g.(x)(j=1,2,A,1)為凸函數(shù)，這樣的非線性規(guī)劃稱為凸規(guī)劃?？梢宰C明，凸規(guī)劃的可行域?yàn)橥辜?，其局部最?yōu)解即為全局最優(yōu)解，而且其最優(yōu)解的集合形成一個(gè)凸集。當(dāng)凸規(guī)劃的目標(biāo)函數(shù)f(%)為嚴(yán)格凸函數(shù)時(shí)，其最優(yōu)解必定唯一(假定最優(yōu)解存在)。由此可見，凸規(guī)劃是一類比較簡(jiǎn)單而又具有重要理論意義的非線性規(guī)劃。2無約束問題2.1一維搜索方法當(dāng)用迭代法求函數(shù)的極小點(diǎn)時(shí)，常常用到一維搜索，即沿某一已知方向求目標(biāo)函數(shù)的極小點(diǎn)。一維搜索的方法很多，常用的有：(1)試探法(“成功失敗”，斐波那契法，0.618法等)；插值法(拋物線插值法，三次插值法等)；(3)微積分中的求根法(

11、切線法，二分法等)?？紤]一維極小化問題minf(t)(2)atb若f(t)是a,b區(qū)間上的下單峰函數(shù)，我們介紹通過不斷地縮短a,b的長(zhǎng)度，來搜索得(2)的近似最優(yōu)解的兩個(gè)方法。為了縮短區(qū)間a,b，逐步搜索得(2)的最優(yōu)解t*的近似值，我們可以采用以下途徑：在a,b中任取兩個(gè)關(guān)于a,b是對(duì)稱的點(diǎn)t和t(不妨設(shè)tt，并把它們叫1221做搜索點(diǎn))，計(jì)算f(t)和f(t)并比較它們的大小。對(duì)于單峰函數(shù)，若f(t)f(t)，1221則必有t*ga,t，因而a,t是縮短了的單峰區(qū)間；若f(t)f(t)，則有1112t*gt,b，故t,b是縮短了的單峰區(qū)間；若f(t)=f(t)，則a,t和t,b都是2221

12、12縮短了的單峰。因此通過兩個(gè)搜索點(diǎn)處目標(biāo)函數(shù)值大小的比較，總可以獲得縮短了的單峰區(qū)間。對(duì)于新的單峰區(qū)間重復(fù)上述做法，顯然又可獲得更短的單峰區(qū)間。如此進(jìn)行，在單峰區(qū)間縮短到充分小時(shí)，我們可以取最后的搜索點(diǎn)作為(2)最優(yōu)解的近似值。應(yīng)該按照怎樣的規(guī)則來選取探索點(diǎn)，使給定的單峰區(qū)間的長(zhǎng)度能盡快地縮短？2.1.1 Fibonacci法若數(shù)列F滿足關(guān)系：nF二F二101F二F+F,n二2,3A,nn-2n一1則稱F為Fibonacci數(shù)列，F(xiàn)稱為第n個(gè)Fibonacci數(shù)，稱相鄰兩個(gè)Fibonacci數(shù)之nnF比n1為Fibonacci分?jǐn)?shù)。Fn當(dāng)用斐波那契法以n個(gè)探索點(diǎn)來縮短某一區(qū)間時(shí)，區(qū)間長(zhǎng)度的第

13、一次縮短率為FFFFh，其后各次分別為畀T,廠34，卡。由此，若t和t(tt)是單峰區(qū)間a,bFFFF1221nnn一22中第1個(gè)和第2個(gè)探索點(diǎn)的話，那么應(yīng)有比例關(guān)系t一aFtaFn1n2n1，厶n2b一aFbaF從而nn十,Fta+n1(b-a)，ta+Fn-2(ba)(3)1F2Fnn它們關(guān)于a,b確是對(duì)稱的點(diǎn)。如果要求經(jīng)過一系列探索點(diǎn)搜索之后，使最后的探索點(diǎn)和最優(yōu)解之間的距離不超0，這就要求最后區(qū)間的長(zhǎng)度不超過，即4)n據(jù)此，我們應(yīng)按照預(yù)先給定的精度5，確定使(4)成立的最小整數(shù)n作為搜索次數(shù)，直到進(jìn)行到第n個(gè)探索點(diǎn)時(shí)停止。用上述不斷縮短函數(shù)f(t)的單峰區(qū)間a,b的辦法，來求得問題(2

14、)的近似解,是Kiefer(1953年)提出的，叫做Finbonacci法，具體步驟如下：1選取初始數(shù)據(jù)，確定單峰區(qū)間a,b，給出搜索精度50，由(4)確定搜00索次數(shù)n。2k=1,a=a,b=b，計(jì)算最初兩個(gè)搜索點(diǎn)，按(3)計(jì)算t和t。00123whilekn1f=f(t),f=f(t)1122iff1f212=丄F(n1k)a=t;t=t;t=a+(ba)2211F(nk)else77丄F(n一1一k)b=t;t=t;t=b+(ab)1122F(nk)endk=k丄1end4當(dāng)進(jìn)行至k=n1時(shí)，t=t=(a+b)122這就無法借比較函數(shù)值f(t)和f(t)的大小確定最終區(qū)間，為此，取12t

15、=丄(a+b)0，滿足比例關(guān)系11J51稱之為黃金分割數(shù)，其值為=0.6180339887A。黃金分割數(shù)和Fibonacci分?jǐn)?shù)之間有著重要的關(guān)系，它們是FF1n1n，n為奇數(shù)。FFnn12-lim-=i。nfgFn現(xiàn)用不變的區(qū)間縮短率0.618，代替斐波那契法每次不同的縮短率，就得到了黃金分割法(0.618法)。這個(gè)方法可以看成是斐波那契法的近似，實(shí)現(xiàn)起來比較容易，效果也相當(dāng)好，因而易于為人們所接受。用0.618法求解，從第2個(gè)探索點(diǎn)開始每增加一個(gè)探索點(diǎn)作一輪迭代以后，原單峰區(qū)間要縮短0.618倍。計(jì)算n個(gè)探索點(diǎn)的函數(shù)值可以把原區(qū)間a,b連續(xù)縮短n-100次，因?yàn)槊看蔚目s短率均為卩，故最后的

16、區(qū)間長(zhǎng)度為(b-a)卩n-i00這就是說，當(dāng)已知縮短的相對(duì)精度為時(shí)，可用下式計(jì)算探索點(diǎn)個(gè)數(shù)n:卩n-1當(dāng)然，也可以不預(yù)先計(jì)算探索點(diǎn)的數(shù)目n，而在計(jì)算過程中逐次加以判斷，看是否已滿足了提出的精度要求。0.618法是一種等速對(duì)稱進(jìn)行試探的方法，每次的探索點(diǎn)均取在區(qū)間長(zhǎng)度的0.618倍和0.382倍處。2.2 二次插值法對(duì)極小化問題(2)，當(dāng)f(t)在a,b上連續(xù)時(shí)，可以考慮用多項(xiàng)式插值來進(jìn)行一維搜索。它的基本思想是:在搜索區(qū)間中，不斷用低次(通常不超過三次)多項(xiàng)式來近似目標(biāo)函數(shù)，并逐步用插值多項(xiàng)式的極小點(diǎn)來逼近(2)的最優(yōu)解。2.3 無約束極值問題的解法無約束極值問題可表述為minf(x),xgE

17、(n)(5)求解問題(5)的迭代法大體上分為兩種:一是用到函數(shù)的一階導(dǎo)數(shù)或二階導(dǎo)數(shù)，稱為解析法。另一是僅用到函數(shù)值，稱為直接法。2.3.1解析法2.3.1.1梯度法(最速下降法)對(duì)基本迭代格式Xk+1=Xk+tpk(6)k我們總是考慮從點(diǎn)Xk出發(fā)沿哪一個(gè)方向pk，使目標(biāo)函數(shù)f下降得最快。微積分的知識(shí)告訴我們，點(diǎn)xk的負(fù)梯度方向Pk=(Xk)，是從點(diǎn)Xk出發(fā)使f下降最快的方向。為此，稱負(fù)梯度方向(Xk)為f在點(diǎn)Xk處的最速下降方向。按基本迭代格式(6),每一輪從點(diǎn)Xk出發(fā)沿最速下降方向(Xk)作一維搜索，來建立求解無約束極值問題的方法，稱之為最速下降法。這個(gè)方法的特點(diǎn)是，每輪的搜索方向都是目標(biāo)函

18、數(shù)在當(dāng)前點(diǎn)下降最快的方向。同時(shí)，用Vf(Xk)二0或阿(Xk)|8作為停止條件。其具體步驟如下：1選取初始數(shù)據(jù)。選取初始點(diǎn)X0，給定終止誤差，令k:二0。2求梯度向量。計(jì)算Vf(Xk)，若|Vf(Xk)|0令Xk+1=Xk+tpk,k:=k+1,轉(zhuǎn)2。k例4用最速下降法求解無約束非線性規(guī)劃問題minf(x)=x2+25x212其中x=(x,x)t，要求選取初始點(diǎn)xo=(2,2)t，終止誤差=10-6。12解：(i)(x)=(2x,50x)t12編寫M文件detaf.m如下functionf,df=detaf(x);f=x(1)入2+25*x(2)入2;df(1)=2*x(1);df(2)=50

19、*x(2);(ii)編寫M文件zuisu.mclcx=2;2;f0,g=detaf(x);whilenorm(g)0.000001p=-g/norm(g);t=1.0;f=detaf(x+t*p);whileff0t=t/2;f=detaf(x+t*p);endx=x+t*pf0,g=detaf(x)end2.3.1.2 Newton法考慮目標(biāo)函數(shù)f在點(diǎn)xk處的二次逼近式f(x)沁Q(x)=f(xk)+Vf(xk)T(x一xk)+(x一xk)TV2f(xk)(x一xk)2f(Xk)Ox202f(Xk)OxOxn102f(xk)OxOx1MnO2f(Xk)OX2n假定Hesse陣V2f(xk)=

20、正定。由于V2f(Xk)正定，函數(shù)Q的穩(wěn)定點(diǎn)Xk+1是Q(X)的最小點(diǎn)。為求此最小點(diǎn)，令VQ(xk+i)=Vf(xk)+V2f(xk)(xk+i-xk)=0，即可解得Xk+1=XkV2f(Xk)-1Vf(Xk).對(duì)照基本迭代格式(1)，可知從點(diǎn)xk出發(fā)沿搜索方向。pk2f(Xk)-1Vf(xk)并取步長(zhǎng)t二1即可得Q(X)的最小點(diǎn)Xk+1。通常，把方向pk叫做從點(diǎn)xk出發(fā)的kNewton方向。從一初始點(diǎn)開始，每一輪從當(dāng)前迭代點(diǎn)出發(fā)，沿Newton方向并取步長(zhǎng)為1的求解方法，稱之為Newton法。其具體步驟如下：1選取初始數(shù)據(jù)。選取初始點(diǎn)X0，給定終止誤差0，令k:二0。2求梯度向量。計(jì)算Vf(

21、xk)，若|Vf(xk)|G,停止迭代，輸出xk。否則，進(jìn)行3。3構(gòu)造Newton方向。計(jì)算V2f(xk)-1，取pk二-V2f(xk)-1Vf(xk).4求下一迭代點(diǎn)。令Xk+1=Xk+pk,k:=k+1，轉(zhuǎn)2。例5用Newton法求解，minf(x)=x4+25x4+x2x21212選取x0(2,2)t，=10-6。112x2+2x2124xx12解：(i)Vf(x)-4x3+2xx2100x3+2x2xt122124xx12300x2+4x2_21編寫M文件nwfun.m如下：functionf,df,d2f=nwfun(x);f=x(1)入4+25*x(2)入4+x(1)入2*x(2)

22、入2;df(1)=4*x(1)入3+2*x(1)*x(2)入2;df(2)=100*x(2)入3+2*x(1)入2*x(2);d2f(1,1)=12*x(1)入2+2*x(2)入2;d2f(1,2)=4*x(1)*x(2);d2f(2,1)=d2f(1,2);d2f(2,2)=300*x(2)入2+4*x(1)*x(2);(ii)編寫M文件：clcx=2;2;f0,g1,g2=nwfun(x)whilenorm(g1)0.00001%deadloop,fori=1:3p=-inv(g2)*g1,p=p/norm(p)t=1.0,f=detaf(x+t*p)whileff0t=t/2,f=det

23、af(x+t*p),endx=x+t*pf0,g1,g2=nwfun(x)end如果目標(biāo)函數(shù)是非二次函數(shù)，一般地說，用Newton法通過有限輪迭代并不能保證可求得其最優(yōu)解。Newton法的優(yōu)點(diǎn)是收斂速度快；缺點(diǎn)是有時(shí)不好用而需采取改進(jìn)措施，此外，當(dāng)維數(shù)較高時(shí)，計(jì)算-V2f(xk)-1的工作量很大。2.3.1.3變尺度法變尺度法(VariableMetricAlgorithm)是近20多年來發(fā)展起來的，它不僅是求解無約束極值問題非常有效的算法，而且也已被推廣用來求解約束極值問題。由于它既避免了計(jì)算二階導(dǎo)數(shù)矩陣及其求逆過程，又比梯度法的收斂速度快，特別是對(duì)高維問題具有顯著的優(yōu)越性，因而使變尺度法獲

24、得了很高的聲譽(yù)。下面我們就來簡(jiǎn)要地介紹一種變尺度法一DFP法的基本原理及其計(jì)算過程。這一方法首先由Davidon在1959年提出，后經(jīng)Fletcher和Powell加以改進(jìn)。我們已經(jīng)知道，牛頓法的搜索方向是-W2f(xk)-1Vf(xk)，為了不計(jì)算二階導(dǎo)數(shù)矩陣V2f(xk)及其逆陣，我們?cè)O(shè)法構(gòu)造另一個(gè)矩陣，用它來逼近二階導(dǎo)數(shù)矩陣的逆陣V2f(xk)-1，這一類方法也稱擬牛頓法(Quasi-NewtonMethod)。下面研究如何構(gòu)造這樣的近似矩陣，并將它記為H(k)。我們要求：每一步都能以現(xiàn)有的信息來確定下一個(gè)搜索方向；每做一次選代，目標(biāo)函數(shù)值均有所下降；這些近似矩陣最后應(yīng)收斂于解點(diǎn)處的He

25、sse陣的逆陣。當(dāng)f(x)是二次函數(shù)時(shí)，其Hesse陣為常數(shù)陣A，任兩點(diǎn)xk和xk+1處的梯度之差為Vf(xk+1)-Vf(xk)=A(xk+1-xk)或xk+1-xk=A-1Vf(xk+1)-Vf(xk)對(duì)于非二次函數(shù)，仿照二次函數(shù)的情形，要求其Hesse陣的逆陣的第k+1次近似矩陣H(k+1)滿足關(guān)系式xk+1-xk=H(k+1)Vf(xk+1)-Vf(xk)(7)這就是常說的擬Newton條件。若令A(yù)G(k)=Vf(xk+1)-Vf(xk)仁_(8)lAxk=xk+1xk則式(7)變?yōu)開Axk=H(k+1)AG(k)，(9)現(xiàn)假定H(k)已知，用下式求H(k+1)(設(shè)H(k)和H(k+1

26、)均為對(duì)稱正定陣)；H(k+1)=H(k)+AH(k)(10)其中AH(k)稱為第k次校正矩陣。顯然，H(k+1)應(yīng)滿足擬Newton條件(9),即要求Axk=(H(k)+AH(k)AG(k)或AH(k)AG(k)=Axk一H(k)AG(k)(11)由此可以設(shè)想，AH(k)的一種比較簡(jiǎn)單的形式是AH(k)=Axk(Q(k)T一H(k)AG(k)(W(k)T(12)其中Q(k)和W(k)為兩個(gè)待定列向量。將式(12)中的AH(k)代入(11),得Axk(Q(k)TAG(k)-H(k)AG(k)(W(k)TAG(k)二Axk-H(k)AG(k)這說明，應(yīng)使(Q(k)TAG(k)(W(k)TAG(k

27、)1考慮到AH(k)應(yīng)為對(duì)稱陣，最簡(jiǎn)單的辦法就是取Jq(k)=nAxk、W(k)gH(k)Ag(k)k由式(13)得_耳(AXk)TAG(k)g(AG(k)TH(k)AG(k)1k_若(Axk)TAG(k)和(AG(k)tH(k)AG(k)不等于零，則有11n-kVgk于是，得校正矩陣(Axk)TAG(k)(AG(k)TAxk1(AG(k)tH(k)AG(k)從而得到AH(k)AXk(AXk)T_H(k)AG(k)(G(k)TAH(k)(Ag(k)TAxk(AG(k)tH(k)Ag(k)14)(15)(16)(17)Axk(Axk)T(AG(k)TAXkH(k)AG(k)(G(k)TAH(k)

28、(AG(k)tH(k)AG(k)18)上述矩陣稱為尺度矩陣。通常，我們?nèi)〉谝粋€(gè)尺度矩陣H(0)為單位陣，以后的尺度矩陣按式(18)逐步形成?？梢宰C明：(i)當(dāng)xk不是極小點(diǎn)且H(k)正定時(shí)，式(17)右端兩項(xiàng)的分母不為零，從而可按式(18)產(chǎn)生下一個(gè)尺度矩陣H(k+i)；(ii) 若H(k)為對(duì)稱正定陣，則由式(18)產(chǎn)生的H(k+i)也是對(duì)稱正定陣；(iii) 由此推出DFP法的搜索方向?yàn)橄陆捣较颉，F(xiàn)將DFP變尺度法的計(jì)算步驟總結(jié)如下。1給定初始點(diǎn)X0及梯度允許誤差0。2若|Vf(xo)|，則x0即為近似極小點(diǎn)，停止迭代，否則，轉(zhuǎn)向下一步。令_H(0)I(單位矩陣),po_H(0)Vf(xo

29、)在p0方向進(jìn)行一維搜索，確定最佳步長(zhǎng)九:0minf(x0+Xp0)=f(x0+九p0)九0如此可得下一個(gè)近似點(diǎn)x1x0+Xp004。一般地，設(shè)已得到近似點(diǎn)xk，算出Vf(xk)，若Vf(xk)|0，令k:二0。2進(jìn)行基本搜索。令y0：=Xk，依次沿p0,p1,A,pn-1中的方向進(jìn)行一維搜索。對(duì)應(yīng)地得到輔助迭代點(diǎn)y1,y2,A,yn，即yj二yj-1+1pj-1j-1f(yj-1+1pj-1)二minf(yj-1+tpj-1)j二1,A,n丿Tt03構(gòu)造加速方向。令pn二yn一y0，若o，停止迭代，輸出xk+1二y”。否則進(jìn)行4。4確定調(diào)整方向。按下式f(ym-1)-f(ym)二maxf(y

30、jT)-f(yj)11jn找出m。若f(y0)-2f(yn)+f(2yn-y0)0nnm-1,pm+1,A,pn-1,pn，同時(shí)，令po,p1,A,pn+1:二p0,A,pk+1k:二k+1，轉(zhuǎn)2。6不調(diào)整搜索方向組。令xk+1:-yn,k:-k+1，轉(zhuǎn)2。2.4Matlab求函數(shù)的極小值和函數(shù)的零點(diǎn)2.4.1求單變量有界非線性函數(shù)在區(qū)間上的極小值minf(x),xwa,bxMatlab的命令為X,FVAL=FMINBND(FUN,x1,x2,OPTIONS)，它的返回值是極小點(diǎn)x和函數(shù)的極小值。這里fun是用M文件定義的函數(shù)或Matlab中的單變量數(shù)學(xué)函數(shù)。例6求函數(shù)f(x)=(x3)2-1

31、,xg0,5的最小值。解編寫M文件fun1.mfunctionf=fun1(x);f=(x-3)人2-1;在Matlab的命令窗口輸入x,y=fminbnd(fun1,0,5)即可求得極小點(diǎn)和極小值。2.4.2求多變量函數(shù)的極小值minf(x),x其中x是一個(gè)向量，f(x)是一個(gè)標(biāo)量函數(shù)。Matlab中的基本命令是X,FVAL=FMINUNC(FUN,X0,OPTIONS,P1,P2,.)它的返回值是向量x的值和函數(shù)的極小值。FUN是一個(gè)M文件，當(dāng)FUN只有一個(gè)返回值時(shí)，它的返回值是函數(shù)f(x)；當(dāng)FUN有兩個(gè)返回值時(shí)，它的第二個(gè)返回值是f(x)的一階導(dǎo)數(shù)行向量；當(dāng)FUN有三個(gè)返回值時(shí)，它的第

32、三個(gè)返回值是f(x)的二階導(dǎo)數(shù)陣(Hessian陣)。X0是向量x的初始值，OPTIONS是優(yōu)化參數(shù)，使用確省參數(shù)時(shí)，OPTIONS為空矩陣。P1，P2是可以傳遞給FUN的一些參數(shù)。例7求函數(shù)f(x)二100(xx2)2+(1-x)2的最小值。211解：編寫M文件fun2.m如下：functionf,g=fun2(x);f=100*(x(2)_x(1)W2+(1_x(1)入2;g=400*x(1)*(x(2)x(1)入2)2(1x(1)200*(x(2)_x(1)入2);在Matlab命令窗口輸入fminunc(fun2,rand(1,2)即可求得函數(shù)的極小值。求多元函數(shù)的極值也可以使用Mat

33、lab的命令X,FVAL=FMINSEARCH(FUN,X0,OPTIONS,P1,P2,.)。3約束極值問題帶有約束條件的極值問題稱為約束極值問題，也叫約束規(guī)劃問題。求解約束極值問題要比求解無約束極值問題困難得多。為了簡(jiǎn)化其優(yōu)化工作，可采用以下方法：將約束問題化為無約束問題；將非線性規(guī)劃問題化為線性規(guī)劃問題，以及能將復(fù)雜問題變換為較簡(jiǎn)單問題的其它方法。3.1 最優(yōu)性條件庫恩塔克條件是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，是確定某點(diǎn)為最優(yōu)點(diǎn)的必要條件，但一般說它并不是充分條件(對(duì)于凸規(guī)劃，它既是最優(yōu)點(diǎn)存在的必要條件，同時(shí)也是充分條件)。3.2 二次規(guī)劃若某非線性規(guī)劃的目標(biāo)函數(shù)為自變量x的二次函

34、數(shù)，約束條件又全是線性的，就稱這種規(guī)劃為二次規(guī)劃。Matlab中二次規(guī)劃的數(shù)學(xué)模型可表述如下：min1xtHx+ftx,s.t.Ax0，構(gòu)造函數(shù)P(x,M)=f(x)+M工ma*g(x),0)一M丫min(h(x),0)+M工|k(x)Iiiii=1i=1i=1(或P(x,M)=f(x)+Mmax(G(x),0)+Mmin(H(x),0)+M|K(x)|3這里G(x)=g(x)1M1，H(x)=h(x)1M2，K(x)=k(x)1M_g(x)_h(x)_k(x)_，M,M,M為適當(dāng)?shù)?23rst行向量，Matlab中可以直接利用max和min函數(shù)。)則以增廣目標(biāo)函數(shù)P(x,M)為i目標(biāo)函數(shù)的無

35、約束極值問題minP(x,M)的最優(yōu)解X也是原問題的最優(yōu)解。例9求下列非線性規(guī)劃minf(x)=x2+x2+812x2一xn0112-xx2+2=012x,xn0.12解(i)編寫M文件test.mfunctiong=test(x);M=50000;f=x(1)入2+x(2)入2+8;g=f-M*min(x(1),0)-M*min(x(2),0)-M*min(x(1)入2-x(2),0).+M*abs(-x(1)-x(2)入2+2);(ii)在Matlab命令窗口輸入x,y=fminunc(test,rand(2,1)即可求得問題的解。4飛行管理問題在約10,000m高空的某邊長(zhǎng)160km的正方形區(qū)域內(nèi)，經(jīng)常有若干架飛機(jī)作水平飛行。區(qū)域內(nèi)每架飛機(jī)的位置和速