第三章非線性規(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è)有個(gè)項(xiàng)目可供選擇投資，并且至少要對(duì)其中一個(gè)項(xiàng)目投資。已知該企業(yè)擁有總資金元，投資于第個(gè)項(xiàng)目需花資金元，并預(yù)計(jì)可收益元。試選擇最佳投資方案。解 設(shè)投資決策變量為，則投資總額為，投資總收益為。因

2、為該公司至少要對(duì)一個(gè)項(xiàng)目投資，并且總的投資金額不能超過總資金，故有限制條件另外，由于只取值0或1，所以還有最佳投資方案應(yīng)是投資額最小而總收益最大的方案，所以這個(gè)最佳投資決策問題歸結(jié)為總資金以及決策變量（取0或1）的限制條件下，極大化總收益和總投資之比。因此，其數(shù)學(xué)模型為：s.t. 上面例題是在一組等式或不等式的約束下，求一個(gè)函數(shù)的最大值（或最小值）問題，其中目標(biāo)函數(shù)或約束條件中至少有一個(gè)非線性函數(shù)，這類問題稱之為非線性規(guī)劃問題，簡(jiǎn)記為（NP）?？筛爬橐话阈问?(NP)其中稱為模型（NP）的決策變量，稱為目標(biāo)函數(shù)，和稱為約束函數(shù)。另外，稱為等式約束，稱為不等式約束。對(duì)于一個(gè)實(shí)際問題，在把它歸結(jié)

3、成非線性規(guī)劃問題時(shí)，一般要注意如下幾點(diǎn)：（i）確定供選方案：首先要收集同問題有關(guān)的資料和數(shù)據(jù)，在全面熟悉問題的基礎(chǔ)上，確認(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)一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問題的所有限制條件，這些條件通常用變量之間的一些不等式或等式來表示。

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

5、,Beq=；LB和UB是變量的下界和上界，如果上界和下界沒有約束，則LB=，UB=，如果無下界，則LB=-inf，如果無上界，則UB=inf；NONLCON是用M文件定義的非線性向量函數(shù)；OPTIONS定義了優(yōu)化參數(shù)，可以使用Matlab缺省的參數(shù)設(shè)置。 例2 求下列非線性規(guī)劃問題（i）編寫M文件fun1.mfunction f=fun1(x);f=x(1)2+x(2)2+8;和M文件fun2.mfunction g,h=fun2(x);g=-x(1)2+x(2);h=-x(1)-x(2)2+2; %等式約束（ii）在Matlab的命令窗口依次輸入options=optimset;x,y=fm

6、incon(fun1,rand(2,1),zeros(2,1), .fun2, options)就可以求得當(dāng)時(shí)，最小值。1.4求解非線性規(guī)劃的基本迭代格式記（NP）的可行域?yàn)?。若，并且則稱是（NP）的整體最優(yōu)解，是(NP)的整體最優(yōu)值。如果有則稱是（NP）的嚴(yán)格整體最優(yōu)解，是(NP)的嚴(yán)格整體最優(yōu)值。若，并且存在的鄰域，使，則稱是（NP）的局部最優(yōu)解，是(NP)的局部最優(yōu)值。如果有則稱是（NP）的嚴(yán)格局部最優(yōu)解，是(NP)的嚴(yán)格局部最優(yōu)值。由于線性規(guī)劃的目標(biāo)函數(shù)為線性函數(shù)，可行域?yàn)橥辜蚨蟪龅淖顑?yōu)解就是整個(gè)可行域上的全局最優(yōu)解。非線性規(guī)劃卻不然，有時(shí)求出的某個(gè)解雖是一部分可行域上的極值點(diǎn)，

7、但并不一定是整個(gè)可行域上的全局最優(yōu)解。對(duì)于非線性規(guī)劃模型(NP)，可以采用迭代方法求它的最優(yōu)解。迭代方法的基本思想是：從一個(gè)選定的初始點(diǎn)出發(fā)，按照某一特定的迭代規(guī)則產(chǎn)生一個(gè)點(diǎn)列，使得當(dāng)是有窮點(diǎn)列時(shí)，其最后一個(gè)點(diǎn)是(NP)的最優(yōu)解；當(dāng)是無窮點(diǎn)列時(shí)，它有極限點(diǎn)，并且其極限點(diǎn)是(NP)的最優(yōu)解。設(shè)是某迭代方法的第輪迭代點(diǎn)，是第輪迭代點(diǎn)，記 （1）這里，顯然是由點(diǎn)與點(diǎn)確定的方向。式（1）就是求解非線性規(guī)劃模型(NP)的基本迭代格式。通常，我們把基本迭代格式（1）中的稱為第輪搜索方向，為沿方向的步長(zhǎng)，使用迭代方法求解(NP)的關(guān)鍵在于，如何構(gòu)造每一輪的搜索方向和確定適當(dāng)?shù)牟介L(zhǎng)。設(shè)，若存在，使，稱向量是在

8、點(diǎn)處的下降方向。設(shè)，若存在，使，稱向量是點(diǎn)處關(guān)于的可行方向。一個(gè)向量，若既是函數(shù)在點(diǎn)處的下降方向，又是該點(diǎn)關(guān)于區(qū)域的可行方向，則稱之為函數(shù)在點(diǎn)處關(guān)于的可行下降方向?，F(xiàn)在，我們給出用基本迭代格式（1）求解(NP)的一般步驟如下：0 選取初始點(diǎn)，令。1 構(gòu)造搜索方向，依照一定規(guī)則，構(gòu)造在點(diǎn)處關(guān)于的可行下降方向作為搜索方向。2 尋求搜索步長(zhǎng)。以為起點(diǎn)沿搜索方向?qū)で筮m當(dāng)?shù)牟介L(zhǎng)，使目標(biāo)函數(shù)值有某種意義的下降。3 求出下一個(gè)迭代點(diǎn)。按迭代格式（1）求出。若已滿足某種終止條件，停止迭代。 4 以代替，回到1步。 1.5 凸函數(shù)、凸規(guī)劃設(shè)為定義在維歐氏空間中某個(gè)凸集上的函數(shù)，若對(duì)任何實(shí)數(shù)以及中的任意兩點(diǎn)和，恒

9、有則稱為定義在上的凸函數(shù)。若對(duì)每一個(gè)和恒有則稱為定義在上的嚴(yán)格凸函數(shù)。考慮非線性規(guī)劃假定其中為凸函數(shù)，為凸函數(shù)，這樣的非線性規(guī)劃稱為凸規(guī)劃。可以證明，凸規(guī)劃的可行域?yàn)橥辜?，其局部最?yōu)解即為全局最優(yōu)解，而且其最優(yōu)解的集合形成一個(gè)凸集。當(dāng)凸規(guī)劃的目標(biāo)函數(shù)為嚴(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法等）；插值法（拋物線插值法，三次插值

10、法等）；（3）微積分中的求根法（切線法，二分法等）?？紤]一維極小化問題 （2）若是區(qū)間上的下單峰函數(shù)，我們介紹通過不斷地縮短的長(zhǎng)度，來搜索得（2）的近似最優(yōu)解的兩個(gè)方法。為了縮短區(qū)間，逐步搜索得（2）的最優(yōu)解的近似值，我們可以采用以下途徑：在中任取兩個(gè)關(guān)于是對(duì)稱的點(diǎn)和（不妨設(shè)，并把它們叫做搜索點(diǎn)），計(jì)算和并比較它們的大小。對(duì)于單峰函數(shù)，若，則必有，因而是縮短了的單峰區(qū)間；若，則有，故是縮短了的單峰區(qū)間；若，則和都是縮短了的單峰。因此通過兩個(gè)搜索點(diǎn)處目標(biāo)函數(shù)值大小的比較，總可以獲得縮短了的單峰區(qū)間。對(duì)于新的單峰區(qū)間重復(fù)上述做法，顯然又可獲得更短的單峰區(qū)間。如此進(jìn)行，在單峰區(qū)間縮短到充分小時(shí)，我們

11、可以取最后的搜索點(diǎn)作為（2）最優(yōu)解的近似值。應(yīng)該按照怎樣的規(guī)則來選取探索點(diǎn)，使給定的單峰區(qū)間的長(zhǎng)度能盡快地縮短？2.1.1 Fibonacci法若數(shù)列滿足關(guān)系：則稱為Fibonacci數(shù)列，稱為第個(gè)Fibonacci數(shù)，稱相鄰兩個(gè)Fibonacci數(shù)之比為Fibonacci分?jǐn)?shù)。 當(dāng)用斐波那契法以個(gè)探索點(diǎn)來縮短某一區(qū)間時(shí)，區(qū)間長(zhǎng)度的第一次縮短率為，其后各次分別為。由此，若和是單峰區(qū)間中第1個(gè)和第2個(gè)探索點(diǎn)的話，那么應(yīng)有比例關(guān)系， 從而， （3）它們關(guān)于確是對(duì)稱的點(diǎn)。如果要求經(jīng)過一系列探索點(diǎn)搜索之后，使最后的探索點(diǎn)和最優(yōu)解之間的距離不超過精度，這就要求最后區(qū)間的長(zhǎng)度不超過，即 （4）據(jù)此，我們應(yīng)

12、按照預(yù)先給定的精度，確定使（4）成立的最小整數(shù)作為搜索次數(shù)，直到進(jìn)行到第個(gè)探索點(diǎn)時(shí)停止。用上述不斷縮短函數(shù)的單峰區(qū)間的辦法，來求得問題（2）的近似解，是Kiefer(1953年)提出的，叫做Finbonacci法，具體步驟如下：1 選取初始數(shù)據(jù)，確定單峰區(qū)間，給出搜索精度，由（4）確定搜索次數(shù)。2，計(jì)算最初兩個(gè)搜索點(diǎn)，按（3）計(jì)算和。3while if else endend4 當(dāng)進(jìn)行至?xí)r，這就無法借比較函數(shù)值和的大小確定最終區(qū)間，為此，取其中為任意小的數(shù)。在和這兩點(diǎn)中，以函數(shù)值較小者為近似極小點(diǎn)，相應(yīng)的函數(shù)值為近似極小值。并得最終區(qū)間或。 由上述分析可知，斐波那契法使用對(duì)稱搜索的方法，逐步縮

13、短所考察的區(qū)間，它能以盡量少的函數(shù)求值次數(shù)，達(dá)到預(yù)定的某一縮短率。例3 試用斐波那契法求函數(shù)的近似極小點(diǎn)，要求縮短后的區(qū)間不大于區(qū)間的0.08倍。程序留作習(xí)題。2.1.2 0.618法若，滿足比例關(guān)系稱之為黃金分割數(shù)，其值為。黃金分割數(shù)和Fibonacci分?jǐn)?shù)之間有著重要的關(guān)系，它們是1，為偶數(shù)，為奇數(shù)。2?，F(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倍。

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

15、述為 （5）求解問題（5）的迭代法大體上分為兩種：一是用到函數(shù)的一階導(dǎo)數(shù)或二階導(dǎo)數(shù)，稱為解析法。另一是僅用到函數(shù)值，稱為直接法。2.3.1 解析法2.3.1.1 梯度法（最速下降法）對(duì)基本迭代格式 （6）我們總是考慮從點(diǎn)出發(fā)沿哪一個(gè)方向，使目標(biāo)函數(shù)下降得最快。微積分的知識(shí)告訴我們，點(diǎn)的負(fù)梯度方向，是從點(diǎn)出發(fā)使下降最快的方向。為此，稱負(fù)梯度方向?yàn)樵邳c(diǎn)處的最速下降方向。按基本迭代格式（6），每一輪從點(diǎn)出發(fā)沿最速下降方向作一維搜索，來建立求解無約束極值問題的方法，稱之為最速下降法。這個(gè)方法的特點(diǎn)是，每輪的搜索方向都是目標(biāo)函數(shù)在當(dāng)前點(diǎn)下降最快的方向。同時(shí)，用或作為停止條件。其具體步驟如下：1選取初始數(shù)

16、據(jù)。選取初始點(diǎn)，給定終止誤差，令。2求梯度向量。計(jì)算， 若，停止迭代，輸出。否則，進(jìn)行3。3 構(gòu)造負(fù)梯度方向。取.4 進(jìn)行一維搜索。求，使得令轉(zhuǎn)2。例4 用最速下降法求解無約束非線性規(guī)劃問題其中，要求選取初始點(diǎn)，終止誤差。解：（i）編寫M文件detaf.m如下function f,df=detaf(x);f=x(1)2+25*x(2)2;df(1)=2*x(1);df(2)=50*x(2);（ii）編寫M文件zuisu.mclcx=2;2;f0,g=detaf(x);while norm(g)0.000001 p=-g/norm(g); t=1.0;f=detaf(x+t*p);while f

17、f0 t=t/2;f=detaf(x+t*p);endx=x+t*pf0,g=detaf(x)end2.3.1.2 Newton法考慮目標(biāo)函數(shù)在點(diǎn)處的二次逼近式假定Hesse陣正定。由于正定，函數(shù)的穩(wěn)定點(diǎn)是的最小點(diǎn)。為求此最小點(diǎn)，令，即可解得.對(duì)照基本迭代格式（1），可知從點(diǎn)出發(fā)沿搜索方向。并取步長(zhǎng)即可得的最小點(diǎn)。通常，把方向叫做從點(diǎn)出發(fā)的Newton方向。從一初始點(diǎn)開始，每一輪從當(dāng)前迭代點(diǎn)出發(fā)，沿Newton方向并取步長(zhǎng)為1的求解方法，稱之為Newton法。其具體步驟如下：1選取初始數(shù)據(jù)。選取初始點(diǎn)，給定終止誤差，令。2求梯度向量。計(jì)算，若，停止迭代，輸出。否則，進(jìn)行3。3構(gòu)造Newton方

18、向。計(jì)算，取.4 求下一迭代點(diǎn)。令，轉(zhuǎn)2。例5 用Newton法求解，選取，。解：（i）編寫M文件nwfun.m如下：function f,df,d2f=nwfun(x);f=x(1)4+25*x(2)4+x(1)2*x(2)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

19、(x)while norm(g1)0.00001 %dead loop,for i=1:3p=-inv(g2)*g1,p=p/norm(p) t=1.0,f=detaf(x+t*p)while ff0 t=t/2,f=detaf(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ì)算的工作量很大。2.3.1.3 變尺度法變尺度法（Variable Metric Algorithm）是近20多年

20、來發(fā)展起來的，它不僅是求解無約束極值問題非常有效的算法，而且也已被推廣用來求解約束極值問題。由于它既避免了計(jì)算二階導(dǎo)數(shù)矩陣及其求逆過程，又比梯度法的收斂速度快，特別是對(duì)高維問題具有顯著的優(yōu)越性，因而使變尺度法獲得了很高的聲譽(yù)。下面我們就來簡(jiǎn)要地介紹一種變尺度法DFP法的基本原理及其計(jì)算過程。這一方法首先由Davidon在1959年提出，后經(jīng)Fletcher和Powell加以改進(jìn)。 我們已經(jīng)知道，牛頓法的搜索方向是，為了不計(jì)算二階導(dǎo)數(shù)矩陣及其逆陣，我們?cè)O(shè)法構(gòu)造另一個(gè)矩陣，用它來逼近二階導(dǎo)數(shù)矩陣的逆陣，這一類方法也稱擬牛頓法（Quasi-Newton Method）。 下面研究如何構(gòu)造這樣的近似矩

21、陣，并將它記為。我們要求：每一步都能以現(xiàn)有的信息來確定下一個(gè)搜索方向；每做一次選代，目標(biāo)函數(shù)值均有所下降；這些近似矩陣最后應(yīng)收斂于解點(diǎn)處的Hesse陣的逆陣。當(dāng)是二次函數(shù)時(shí)，其Hesse陣為常數(shù)陣，任兩點(diǎn)和處的梯度之差為或?qū)τ诜嵌魏瘮?shù)，仿照二次函數(shù)的情形，要求其Hesse陣的逆陣的第次近似矩陣滿足關(guān)系式 （7）這就是常說的擬Newton條件。若令 （8）則式（7）變?yōu)椋?（9）現(xiàn)假定已知，用下式求（設(shè)和均為對(duì)稱正定陣）；（10）其中稱為第次校正矩陣。顯然，應(yīng)滿足擬Newton條件（9），即要求或 （11）由此可以設(shè)想， 的一種比較簡(jiǎn)單的形式是 (12)其中和為兩個(gè)待定列向量。將式（12）中的

22、代入（11），得這說明，應(yīng)使 （13）考慮到應(yīng)為對(duì)稱陣，最簡(jiǎn)單的辦法就是取 （14）由式（13）得 （15）若和不等于零，則有 （16）于是，得校正矩陣(17)從而得到 （18）上述矩陣稱為尺度矩陣。通常，我們?nèi)〉谝粋€(gè)尺度矩陣為單位陣，以后的尺度矩陣按式（18）逐步形成。可以證明：（i）當(dāng)不是極小點(diǎn)且正定時(shí)，式（17）右端兩項(xiàng)的分母不為零，從而可按式（18）產(chǎn)生下一個(gè)尺度矩陣；（ii）若為對(duì)稱正定陣，則由式（18）產(chǎn)生的也是對(duì)稱正定陣；（iii）由此推出DFP法的搜索方向?yàn)橄陆捣较颉，F(xiàn)將DFP變尺度法的計(jì)算步驟總結(jié)如下。1給定初始點(diǎn)及梯度允許誤差。2若，則即為近似極小點(diǎn)，停止迭代，否則，轉(zhuǎn)向下

23、一步。3令（單位矩陣），在方向進(jìn)行一維搜索，確定最佳步長(zhǎng)：如此可得下一個(gè)近似點(diǎn) 4一般地，設(shè)已得到近似點(diǎn)，算出，若則即為所求的近似解，停止迭代；否則，計(jì)算：并令，在方向上進(jìn)行一維搜索，得，從而可得下一個(gè)近似點(diǎn)5若滿足精度要求，則即為所求的近似解，否則，轉(zhuǎn)回4，直到求出某點(diǎn)滿足精度要求為止。2.3.2 直接法在無約束非線性規(guī)劃方法中，遇到問題的目標(biāo)函數(shù)不可導(dǎo)或?qū)Ш瘮?shù)的解析式難以表示時(shí)，人們一般需要使用直接搜索方法。同時(shí)，由于這些方法一般都比較直觀和易于理解，因而在實(shí)際應(yīng)用中常為人們所采用。下面我們介紹Powell方法。這個(gè)方法主要由所謂基本搜索、加速搜索和調(diào)整搜索方向三部分組成，具體步驟如下：1

24、 選取初始數(shù)據(jù)。選取初始點(diǎn)，個(gè)線性無關(guān)初始方向，組成初搜索方向組。給定終止誤差，令。2進(jìn)行基本搜索。令，依次沿中的方向進(jìn)行一維搜索。對(duì)應(yīng)地得到輔助迭代點(diǎn)，即3構(gòu)造加速方向。令，若，停止迭代，輸出。否則進(jìn)行4。4確定調(diào)整方向。按下式找出。若成立，進(jìn)行5。否則，進(jìn)行6。5調(diào)整搜索方向組。令.同時(shí)，令，轉(zhuǎn)2。 6不調(diào)整搜索方向組。令，轉(zhuǎn)2。2.4 Matlab求函數(shù)的極小值和函數(shù)的零點(diǎn) 求單變量有界非線性函數(shù)在區(qū)間上的極小值Matlab的命令為X,FVAL = FMINBND(FUN,x1,x2,OPTIONS)，它的返回值是極小點(diǎn)和函數(shù)的極小值。這里fun 是用M文件定義的函數(shù)或Matlab中的單

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

26、數(shù)陣（Hessian陣）。X0是向量的初始值，OPTIONS是優(yōu)化參數(shù)，使用確省參數(shù)時(shí)，OPTIONS為空矩陣。P1，P2是可以傳遞給FUN的一些參數(shù)。例7 求函數(shù)的最小值。解：編寫M文件fun2.m如下：function f,g=fun2(x);f=100*(x(2)-x(1)2)2+(1-x(1)2;g=-400*x(1)*(x(2)-x(1)2)-2(1-x(1) 200*(x(2)-x(1)2);在Matlab命令窗口輸入fminunc(fun2,rand(1,2)即可求得函數(shù)的極小值。求多元函數(shù)的極值也可以使用Matlab的命令X,FVAL= FMINSEARCH(FUN,X0,OP

27、TIONS,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ù)為自變量的二次函數(shù)，約束條件又全是線性的，就稱這種規(guī)劃為二次規(guī)劃。Matlab中二

28、次規(guī)劃的數(shù)學(xué)模型可表述如下：這里是實(shí)對(duì)稱矩陣，是列向量，是相應(yīng)維數(shù)的矩陣。Matlab中求解二次規(guī)劃的命令是X,FVAL= QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)X的返回值是向量，F(xiàn)VAL的返回值是目標(biāo)函數(shù)在X處的值。（具體細(xì)節(jié)可以參看在Matlab指令中運(yùn)行help quadprog后的幫助）。例8 求解二次規(guī)劃解 編寫如下程序：h=4,-4;-4,8;f=-6;-3;a=1,1;4,1;b=3;9;x,value=quadprog(h,f,a,b,zeros(2,1)求得。3.3 罰函數(shù)法利用罰函數(shù)法，可將非線性規(guī)劃問題的求解，轉(zhuǎn)化為求解一系列

29、無約束極值問題，因而也稱這種方法為序列無約束最小化技術(shù)，簡(jiǎn)記為SUMT (Sequential Unconstrained Minimization Technique)。罰函數(shù)法求解非線性規(guī)劃問題的思想是，利用問題中的約束函數(shù)作出適當(dāng)?shù)牧P函數(shù)，由此構(gòu)造出帶參數(shù)的增廣目標(biāo)函數(shù)，把問題轉(zhuǎn)化為無約束非線性規(guī)劃問題。主要有兩種形式，一種叫外罰函數(shù)法，另一種叫內(nèi)罰函數(shù)法，下面介紹外罰函數(shù)法?？紤]如下問題：s.t. 取一個(gè)充分大的數(shù) ，構(gòu)造函數(shù)（或這里 ，為適當(dāng)?shù)男邢蛄浚琈atlab中可以直接利用 和 函數(shù)。）則以增廣目標(biāo)函數(shù)為目標(biāo)函數(shù)的無約束極值問題的最優(yōu)解也是原問題的最優(yōu)解。例9 求下列非線性規(guī)劃解 (i)編寫 M 文件 test.mfunction g=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命