非線形規(guī)劃講稿

一、基本概念二、一維搜索由于線性規(guī)劃的目標函數(shù)為線性函數(shù)，可行域為凸集，因而求出的最優(yōu)解就是整個可行域上的全局最優(yōu)解。非線性規(guī)劃卻不然，有時求出的某個解雖是一部分可行域上的極值點，但并不一定是整個可行域上的全局最優(yōu)解。對于非線性規(guī)劃模型(NP)，可以采用迭代方法求它的最優(yōu)解。迭代方法的基本思想是：從一個選定的初始點出發(fā)，按照某一特定的迭代規(guī)則產(chǎn)生一個點列，使得當是有窮點列時，其最后一個點是(NP)的最優(yōu)解；當是無窮點列時，它有極限點，并且其極限點是(NP)的最優(yōu)解。0°選取初始點，令。1°構(gòu)造搜索方向，依照一定規(guī)則，構(gòu)造在點處關(guān)于的可行下降方向作為搜索方向。2°尋求搜索步長。以為起點沿搜索方向?qū)で筮m當?shù)牟介L，使目標函數(shù)值有某種意義的下降。3°求出下一個迭代點。按迭代格式（1）求出。若已滿足某種終止條件，停止迭代。4°以代替，回到1°步。無約束問題2.1一維搜索方法當用迭代法求函數(shù)的極小點時，常常用到一維搜索，即沿某一已知方向求目標函數(shù)的極小點。一維搜索的方法很多，常用的有：（1）試探法（“成功—失敗”，斐波那契法，0.618法等）；插值法（拋物線插值法，三次插值法等）；（3）微積分中的求根法（切線法，二分法等）。考慮一維極小化問題（2）若是區(qū)間上的下單峰函數(shù)，我們介紹通過不斷地縮短的長度，來搜索得（2）的近似最優(yōu)解的兩個方法。為了縮短區(qū)間，逐步搜索得（2）的最優(yōu)解的近似值，我們可以采用以下途徑：在中任取兩個關(guān)于是對稱的點和（不妨設(shè)，并把它們叫做搜索點），計算和并比較它們的大小。對于單峰函數(shù)，若，則必有，因而是縮短了的單峰區(qū)間；若，則有，故是縮短了的單峰區(qū)間；若，則和都是縮短了的單峰。因此通過兩個搜索點處目標函數(shù)值大小的比較，總可以獲得縮短了的單峰區(qū)間。對于新的單峰區(qū)間重復(fù)上述做法，顯然又可獲得更短的單峰區(qū)間。如此進行，在單峰區(qū)間縮短到充分小時，我們可以取最后的搜索點作為（2）最優(yōu)解的近似值。三、無約束極值無約束極值問題可表述為（5）求解問題（5）的迭代法大體上分為兩種：一是用到函數(shù)的一階導(dǎo)數(shù)或二階導(dǎo)數(shù)，稱為解析法。另一是僅用到函數(shù)值，稱為直接法。2.3.1解析法2.3.1.1梯度法（最速下降法）對基本迭代格式（6）我們總是考慮從點出發(fā)沿哪一個方向，使目標函數(shù)下降得最快。微積分的知識告訴我們，點的負梯度方向，是從點出發(fā)使下降最快的方向。為此，稱負梯度方向為在點處的最速下降方向。按基本迭代格式（6），每一輪從點出發(fā)沿最速下降方向作一維搜索，來建立求解無約束極值問題的方法，稱之為最速下降法。這個方法的特點是，每輪的搜索方向都是目標函數(shù)在當前點下降最快的方向。同時，用或作為停止條件。其具體步驟如下：1°選取初始數(shù)據(jù)。選取初始點，給定終止誤差，令。2°求梯度向量。計算，若，停止迭代，輸出。否則，進行3°。3°構(gòu)造負梯度方向。取.4°進行一維搜索。求，使得令轉(zhuǎn)2°。例4用最速下降法求解無約束非線性規(guī)劃問題其中，要求選取初始點，終止誤差。解：（=1\*romani）編寫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);（=2\*romanii）編寫M文件zuisu.mclcx=[2;2];[f0,g]=detaf(x);whilenorm(g)>0.000001p=-g'/norm(g);t=1.0;f=detaf(x+t*p);whilef>f0t=t/2;f=detaf(x+t*p);endx=x+t*p[f0,g]=detaf(x)end2.3.1.2Newton法考慮目標函數(shù)在點處的二次逼近式假定Hesse陣正定。由于正定，函數(shù)的穩(wěn)定點是的最小點。為求此最小點，令，即可解得.對照基本迭代格式（1），可知從點出發(fā)沿搜索方向。并取步長即可得的最小點。通常，把方向叫做從點出發(fā)的Newton方向。從一初始點開始，每一輪從當前迭代點出發(fā)，沿Newton方向并取步長為1的求解方法，稱之為Newton法。其具體步驟如下：1°選取初始數(shù)據(jù)。選取初始點，給定終止誤差，令。2°求梯度向量。計算，若，停止迭代，輸出。否則，進行3°。3°構(gòu)造Newton方向。計算，取.4°求下一迭代點。令，轉(zhuǎn)2°。例5用Newton法求解，選取，。解：（=1\*romani）編寫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);（=2\*romanii）編寫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)whilef>f0t=t/2,f=detaf(x+t*p),endx=x+t*p[f0,g1,g2]=nwfun(x)end如果目標函數(shù)是非二次函數(shù)，一般地說，用Newton法通過有限輪迭代并不能保證可求得其最優(yōu)解。Newton法的優(yōu)點是收斂速度快；缺點是有時不好用而需采取改進措施，此外，當維數(shù)較高時，計算的工作量很大?！?約束極值問題帶有約束條件的極值問題稱為約束極值問題，也叫約束規(guī)劃問題。求解約束極值問題要比求解無約束極值問題困難得多。為了簡化其優(yōu)化工作，可采用以下方法：將約束問題化為無約束問題；將非線性規(guī)劃問題化為線性規(guī)劃問題，以及能將復(fù)雜問題變換為較簡單問題的其它方法。二次規(guī)劃若某非線性規(guī)劃的目標函數(shù)為自變量的二次函數(shù)，約束條件又全是線性的，就稱這種規(guī)劃為二次規(guī)劃。Matlab中二次規(guī)劃的數(shù)學模型可表述如下：這里是實對稱矩矩陣，是列列向量，是是相應(yīng)維數(shù)數(shù)的矩陣。Matlab中中求解二次次規(guī)劃的命命令是[X,FVALL]=QQUADPPROG((H,f,,A,b,,Aeq,,beq,,LB,UUB,X00,OPTTIONSS)X的返回值是向量量，F(xiàn)VALL的返回值值是目標函函數(shù)在X處的值。（具具體細節(jié)可可以參看在在Matllab指令令中運行hhelpquaddprogg后的幫助助）。例8求解二次規(guī)劃解編寫如下程序：：h=[4,-44;-4,,8];f=[-6;--3];a=[1,1;;4,1]];b=[3;9]];[x,valuue]=qquadpprog((h,f,,a,b,,[],[[],zeeros((2,1)))求得。罰函數(shù)法利用罰函數(shù)法，可可將非線性性規(guī)劃問題題的求解，轉(zhuǎn)轉(zhuǎn)化為求解解一系列無無約束極值值問題，因因而也稱這這種方法為為序列無約約束最小化化技術(shù)，簡簡記為SSUMT(SeqquenttialUncoonstrraineedMiinimiizatiionTTechnniquee)。罰函數(shù)法求解非非線性規(guī)劃劃問題的思思想是，利利用問題中中的約束函函數(shù)作出適適當?shù)牧P函函數(shù)，由此此構(gòu)造出帶帶參數(shù)的增增廣目標函函數(shù)，把問問題轉(zhuǎn)化為為無約束非非線性規(guī)劃劃問題。主主要有兩種種形式，一一種叫外罰罰函數(shù)法，另另一種叫內(nèi)內(nèi)罰函數(shù)法法，下面介介紹外罰函函數(shù)法?？紤]如下問題：：s.t.取一個充分大的的數(shù)，構(gòu)造函函數(shù)（或這里，，，為適當?shù)男邢蛄苛浚琈attlab中中可以直接接利用和函數(shù)。）則則以增廣目目標函數(shù)為為目標函數(shù)數(shù)的無約束束極值問題題的最優(yōu)解也是原原問題的最最優(yōu)解。例9求下列非非線性規(guī)劃劃解(=1\*romani)編寫寫M文件testt.mfunctioong==testt(x);;M=500000;f=x(1)^^2+x((2)^22+8;g=f-M*mmin(xx(1),,0)-MM*minn(x(22),0))-M*mmin(xx(1)^^2-x((2),00)....+M*abbs(-xx(1)--x(2))^2+22);(=2\*romanii)在MMatlaab命令窗窗口輸入[x,y]=fmiinuncc('tesst',rrand((2,1))即可求得問題的的解?！?飛行管管理問題在約10，000m高空的的某邊長1160kmm的正方形形區(qū)域內(nèi)，經(jīng)經(jīng)常有若干干架飛機作作水平飛行行。區(qū)域內(nèi)內(nèi)每架飛機機的位置和和速度向量量均由計算算機記錄其其數(shù)據(jù)，以以便進行飛飛行管理。當當一架欲進進入該區(qū)域域的飛機到到達區(qū)域邊邊緣時，記記錄其數(shù)據(jù)據(jù)后，要立立即計算并并判斷是否否會與區(qū)域域內(nèi)的飛機機發(fā)生碰撞撞。如果會會碰撞，則則應(yīng)計算如如何調(diào)整各各架（包括括新進入的的）飛機飛飛行的方向向角，以避避免碰撞?，F(xiàn)現(xiàn)假定條件件如下：1）不碰撞的標準準為任意兩兩架飛機的的距離大于于8km;2）飛機飛行方向向角調(diào)整的的幅度不應(yīng)應(yīng)超過300度；3）所有飛機飛行行速度均為為每小時8800kmm;4）進入該區(qū)域的的飛機在到到達區(qū)域邊邊緣時，與與區(qū)域內(nèi)飛飛機的距離離應(yīng)在600km以上上；5）最多需考慮66架飛機；；6）不必考慮飛機機離開此區(qū)區(qū)域后的狀狀況。請你對這個避免免碰撞的飛飛行管理問問題建立數(shù)數(shù)學模型，列列出計算步步驟，對以以下數(shù)據(jù)進進行計算（方方向角誤差差不超過0.01度），要要求飛機飛飛行方向角角調(diào)整的幅幅度盡量小小。設(shè)該區(qū)域4個頂頂點的座標標為(0,0))，(160,,0)，(1600,1600)，(0,1660)。記記錄數(shù)據(jù)為為：飛機編號橫座標縱座標方向角（度度）1150014402432855885236315001555220..541455550159513001550230新進入000522注：方向角指飛飛行方向與與軸正向的的夾角。試根據(jù)實際應(yīng)用用背景對你你的模型進進行評價與與推廣。提示：，，其中為飛機的總總架數(shù)，為為時刻第架飛飛機的坐標標，分別表表示第架飛飛機飛出正正方形區(qū)域域邊界的時時刻。這里里，，；，，；其中為飛機的速速度，分別別為第架飛飛機的初始始方向角和和調(diào)整后的的方向角。令其中，則兩架飛機不碰碰撞的條件件是。習題：某工廠向用戶提提供發(fā)動