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

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

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

3、成非線性規(guī)劃問題時，一般要注意如下幾點：（i）確定供選方案：首先要收集同問題有關的資料和數(shù)據(jù)，在全面熟悉問題的基礎上，確認什么是問題的可供選擇的方案，并用一組變量來表示它們。（ii）提出追求目標：經(jīng)過資料分析，根據(jù)實際需要和可能，提出要追求極小化或極大化的目標。并且，運用各種科學和技術原理，把它表示成數(shù)學關系式。（iii）給出價值標準：在提出要追求的目標之后，要確立所考慮目標的“好”或“壞”的價值標準，并用某種數(shù)量形式來描述它。（iv）尋求限制條件：由于所追求的目標一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問題的所有限制條件，這些條件通常用變量之間的一些不等式或等式來表示。

4、1.2線性規(guī)劃與非線性規(guī)劃的區(qū)別如果線性規(guī)劃的最優(yōu)解存在，其最優(yōu)解只能在其可行域的邊界上達到（特別是可行域的頂點上達到）；而非線性規(guī)劃的最優(yōu)解（如果最優(yōu)解存在）則可能在其可行域的任意一點達到。1.3非線性規(guī)劃的Matlab解法Matlab中非線性規(guī)劃的數(shù)學模型寫成以下形式,其中是標量函數(shù)，是相應維數(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ù)設置。 例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)就可以求得當時，最小值。1.4求解非線性規(guī)劃的基本迭代格式記（NP）的可行域為。若，并且則稱是（NP）的整體最優(yōu)解，是(NP)的整體最優(yōu)值。如果有則稱是（NP）的嚴格整體最優(yōu)解，是(NP)的嚴格整體最優(yōu)值。若，并且存在的鄰域，使，則稱是（NP）的局部最優(yōu)解，是(NP)的局部最優(yōu)值。如果有則稱是（NP）的嚴格局部最優(yōu)解，是(NP)的嚴格局部最優(yōu)值。由于線性規(guī)劃的目標函數(shù)為線性函數(shù)，可行域為凸集，因而求出的最優(yōu)解就是整個可行域上的全局最優(yōu)解。非線性規(guī)劃卻不然，有時求出的某個解雖是一部分可行域上的極值點，

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

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

9、有則稱為定義在上的凸函數(shù)。若對每一個和恒有則稱為定義在上的嚴格凸函數(shù)?？紤]非線性規(guī)劃假定其中為凸函數(shù)，為凸函數(shù)，這樣的非線性規(guī)劃稱為凸規(guī)劃?？梢宰C明，凸規(guī)劃的可行域為凸集，其局部最優(yōu)解即為全局最優(yōu)解，而且其最優(yōu)解的集合形成一個凸集。當凸規(guī)劃的目標函數(shù)為嚴格凸函數(shù)時，其最優(yōu)解必定唯一（假定最優(yōu)解存在）。由此可見，凸規(guī)劃是一類比較簡單而又具有重要理論意義的非線性規(guī)劃。2 無約束問題2.1 一維搜索方法當用迭代法求函數(shù)的極小點時，常常用到一維搜索，即沿某一已知方向求目標函數(shù)的極小點。一維搜索的方法很多，常用的有：（1）試探法（“成功失敗”，斐波那契法，0.618法等）；插值法（拋物線插值法，三次插值

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

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

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

13、短所考察的區(qū)間，它能以盡量少的函數(shù)求值次數(shù)，達到預定的某一縮短率。例3 試用斐波那契法求函數(shù)的近似極小點，要求縮短后的區(qū)間不大于區(qū)間的0.08倍。程序留作習題。2.1.2 0.618法若，滿足比例關系稱之為黃金分割數(shù)，其值為。黃金分割數(shù)和Fibonacci分數(shù)之間有著重要的關系，它們是1，為偶數(shù)，為奇數(shù)。2。現(xiàn)用不變的區(qū)間縮短率0.618，代替斐波那契法每次不同的縮短率，就得到了黃金分割法（0.618法）。這個方法可以看成是斐波那契法的近似，實現(xiàn)起來比較容易，效果也相當好，因而易于為人們所接受。用0.618法求解，從第2個探索點開始每增加一個探索點作一輪迭代以后，原單峰區(qū)間要縮短0.618倍。

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

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

16、據(jù)。選取初始點，給定終止誤差，令。2求梯度向量。計算， 若，停止迭代，輸出。否則，進行3。3 構造負梯度方向。取.4 進行一維搜索。求，使得令轉2。例4 用最速下降法求解無約束非線性規(guī)劃問題其中，要求選取初始點，終止誤差。解：（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法考慮目標函數(shù)在點處的二次逼近式假定Hesse陣正定。由于正定，函數(shù)的穩(wěn)定點是的最小點。為求此最小點，令，即可解得.對照基本迭代格式（1），可知從點出發(fā)沿搜索方向。并取步長即可得的最小點。通常，把方向叫做從點出發(fā)的Newton方向。從一初始點開始，每一輪從當前迭代點出發(fā)，沿Newton方向并取步長為1的求解方法，稱之為Newton法。其具體步驟如下：1選取初始數(shù)據(jù)。選取初始點，給定終止誤差，令。2求梯度向量。計算，若，停止迭代，輸出。否則，進行3。3構造Newton方

18、向。計算，取.4 求下一迭代點。令，轉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如果目標函數(shù)是非二次函數(shù)，一般地說，用Newton法通過有限輪迭代并不能保證可求得其最優(yōu)解。Newton法的優(yōu)點是收斂速度快；缺點是有時不好用而需采取改進措施，此外，當維數(shù)較高時，計算的工作量很大。2.3.1.3 變尺度法變尺度法（Variable Metric Algorithm）是近20多年

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

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

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

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

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

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

26、數(shù)陣（Hessian陣）。X0是向量的初始值，OPTIONS是優(yōu)化參數(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ī)劃問題。求解約束極值問題要比求解無約束極值問題困難得多。為了簡化其優(yōu)化工作，可采用以下方法：將約束問題化為無約束問題；將非線性規(guī)劃問題化為線性規(guī)劃問題，以及能將復雜問題變換為較簡單問題的其它方法。3.1 最優(yōu)性條件庫恩塔克條件是非線性規(guī)劃領域中最重要的理論成果之一，是確定某點為最優(yōu)點的必要條件，但一般說它并不是充分條件（對于凸規(guī)劃，它既是最優(yōu)點存在的必要條件，同時也是充分條件）。3.2 二次規(guī)劃若某非線性規(guī)劃的目標函數(shù)為自變量的二次函數(shù)，約束條件又全是線性的，就稱這種規(guī)劃為二次規(guī)劃。Matlab中二

28、次規(guī)劃的數(shù)學模型可表述如下：這里是實對稱矩陣，是列向量，是相應維數(shù)的矩陣。Matlab中求解二次規(guī)劃的命令是X,FVAL= QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)X的返回值是向量，F(xiàn)VAL的返回值是目標函數(shù)在X處的值。（具體細節(jié)可以參看在Matlab指令中運行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ī)劃問題的求解，轉化為求解一系列

29、無約束極值問題，因而也稱這種方法為序列無約束最小化技術，簡記為SUMT (Sequential Unconstrained Minimization Technique)。罰函數(shù)法求解非線性規(guī)劃問題的思想是，利用問題中的約束函數(shù)作出適當?shù)牧P函數(shù)，由此構造出帶參數(shù)的增廣目標函數(shù)，把問題轉化為無約束非線性規(guī)劃問題。主要有兩種形式，一種叫外罰函數(shù)法，另一種叫內罰函數(shù)法，下面介紹外罰函數(shù)法。考慮如下問題：s.t. 取一個充分大的數(shù) ，構造函數(shù)（或這里 ，為適當?shù)男邢蛄?，Matlab中可以直接利用 和 函數(shù)。）則以增廣目標函數(shù)為目標函數(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命