非線形規(guī)劃講稿

一、基本概念二、一維搜索由于線性規(guī)劃的目標(biāo)函數(shù)為線性函數(shù)，可行域?yàn)橥辜?，因而求出的最?yōu)解就是整個(gè)可行域上的全局最優(yōu)解。非線性規(guī)劃卻不然，有時(shí)求出的某個(gè)解雖是一部分可行域上的極值點(diǎn)，但并不一定是整個(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)解。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°步。無約束問題2.1一維搜索方法當(dāng)用迭代法求函數(shù)的極小點(diǎn)時(shí)，常常用到一維搜索，即沿某一已知方向求目標(biāo)函數(shù)的極小點(diǎn)。一維搜索的方法很多，常用的有：（1）試探法（“成功—失敗”，斐波那契法，0.618法等）；插值法（拋物線插值法，三次插值法等）；（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í)，我們可以取最后的搜索點(diǎn)作為（2）最優(yōu)解的近似值。三、無約束極值無約束極值問題可表述為（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ù)據(jù)。選取初始點(diǎn)，給定終止誤差，令。2°求梯度向量。計(jì)算，若，停止迭代，輸出。否則，進(jìn)行3°。3°構(gòu)造負(fù)梯度方向。取.4°進(jìn)行一維搜索。求，使得令轉(zhuǎn)2°。例4用最速下降法求解無約束非線性規(guī)劃問題其中，要求選取初始點(diǎn)，終止誤差。解：（=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法考慮目標(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方向。計(jì)算，取.4°求下一迭代點(diǎn)。令，轉(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如果目標(biāo)函數(shù)是非二次函數(shù)，一般地說，用Newton法通過有限輪迭代并不能保證可求得其最優(yōu)解。Newton法的優(yōu)點(diǎn)是收斂速度快；缺點(diǎn)是有時(shí)不好用而需采取改進(jìn)措施，此外，當(dāng)維數(shù)較高時(shí)，計(jì)算的工作量很大。§3約束極值問題帶有約束條件的極值問題稱為約束極值問題，也叫約束規(guī)劃問題。求解約束極值問題要比求解無約束極值問題困難得多。為了簡(jiǎn)化其優(yōu)化工作，可采用以下方法：將約束問題化為無約束問題；將非線性規(guī)劃問題化為線性規(guī)劃問題，以及能將復(fù)雜問題變換為較簡(jiǎn)單問題的其它方法。二次規(guī)劃若某非線性規(guī)劃的目標(biāo)函數(shù)為自變量的二次函數(shù)，約束條件又全是線性的，就稱這種規(guī)劃為二次規(guī)劃。Matlab中二次規(guī)劃的數(shù)學(xué)模型可表述如下：這里是實(shí)對(duì)稱矩矩陣，是列列向量，是是相應(yīng)維數(shù)數(shù)的矩陣。Matlab中中求解二次次規(guī)劃的命命令是[X,FVALL]=QQUADPPROG((H,f,,A,b,,Aeq,,beq,,LB,UUB,X00,OPTTIONSS)X的返回值是向量量，F(xiàn)VALL的返回值值是目標(biāo)函函數(shù)在X處的值。（具具體細(xì)節(jié)可可以參看在在Matllab指令令中運(yùn)行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ù)，簡(jiǎn)簡(jiǎn)記為SSUMT(SeqquenttialUncoonstrraineedMiinimiizatiionTTechnniquee)。罰函數(shù)法求解非非線性規(guī)劃劃問題的思思想是，利利用問題中中的約束函函數(shù)作出適適當(dāng)?shù)牧P函函數(shù)，由此此構(gòu)造出帶帶參數(shù)的增增廣目標(biāo)函函數(shù)，把問問題轉(zhuǎn)化為為無約束非非線性規(guī)劃劃問題。主主要有兩種種形式，一一種叫外罰罰函數(shù)法，另另一種叫內(nèi)內(nèi)罰函數(shù)法法，下面介介紹外罰函函數(shù)法。考慮如下問題：：s.t.取一個(gè)充分大的的數(shù)，構(gòu)造函函數(shù)（或這里，，，為適當(dāng)?shù)男邢蛄苛?，Mattlab中中可以直接接利用和函數(shù)。）則則以增廣目目標(biāo)函數(shù)為為目標(biāo)函數(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))即可求得問題的的解。§4飛行管管理問題在約10，000m高空的的某邊長(zhǎng)1160kmm的正方形形區(qū)域內(nèi)，經(jīng)經(jīng)常有若干干架飛機(jī)作作水平飛行行。區(qū)域內(nèi)內(nèi)每架飛機(jī)機(jī)的位置和和速度向量量均由計(jì)算算機(jī)記錄其其數(shù)據(jù)，以以便進(jìn)行飛飛行管理。當(dāng)當(dāng)一架欲進(jìn)進(jìn)入該區(qū)域域的飛機(jī)到到達(dá)區(qū)域邊邊緣時(shí)，記記錄其數(shù)據(jù)據(jù)后，要立立即計(jì)算并并判斷是否否會(huì)與區(qū)域域內(nèi)的飛機(jī)機(jī)發(fā)生碰撞撞。如果會(huì)會(huì)碰撞，則則應(yīng)計(jì)算如如何調(diào)整各各架（包括括新進(jìn)入的的）飛機(jī)飛飛行的方向向角，以避避免碰撞?，F(xiàn)現(xiàn)假定條件件如下：1）不碰撞的標(biāo)準(zhǔn)準(zhǔn)為任意兩兩架飛機(jī)的的距離大于于8km;2）飛機(jī)飛行方向向角調(diào)整的的幅度不應(yīng)應(yīng)超過300度；3）所有飛機(jī)飛行行速度均為為每小時(shí)8800kmm;4）進(jìn)入該區(qū)域的的飛機(jī)在到到達(dá)區(qū)域邊邊緣時(shí)，與與區(qū)域內(nèi)飛飛機(jī)的距離離應(yīng)在600km以上上；5）最多需考慮66架飛機(jī)；；6）不必考慮飛機(jī)機(jī)離開此區(qū)區(qū)域后的狀狀況。請(qǐng)你對(duì)這個(gè)避免免碰撞的飛飛行管理問問題建立數(shù)數(shù)學(xué)模型，列列出計(jì)算步步驟，對(duì)以以下數(shù)據(jù)進(jìn)進(jìn)行計(jì)算（方方向角誤差差不超過0.01度），要要求飛機(jī)飛飛行方向角角調(diào)整的幅幅度盡量小小。設(shè)該區(qū)域4個(gè)頂頂點(diǎn)的座標(biāo)標(biāo)為(0,0))，(160,,0)，(1600,1600)，(0,1660)。記記錄數(shù)據(jù)為為：飛機(jī)編號(hào)橫座標(biāo)縱座標(biāo)方向角（度度）1150014402432855885236315001555220..541455550159513001550230新進(jìn)入000522注：方向角指飛飛行方向與與軸正向的的夾角。試根據(jù)實(shí)際應(yīng)用用背景對(duì)你你的模型進(jìn)進(jìn)行評(píng)價(jià)與與推廣。提示：，，其中為飛機(jī)的總總架數(shù)，為為時(shí)刻第架飛飛機(jī)的坐標(biāo)標(biāo)，分別表表示第架飛飛機(jī)飛出正正方形區(qū)域域邊界的時(shí)時(shí)刻。這里里，，；，，；其中為飛機(jī)的速速度，分別別為第架飛飛機(jī)的初始始方向角和和調(diào)整后的的方向角。令其中，則兩架飛機(jī)不碰碰撞的條件件是。習(xí)題：某工廠向用戶提提供發(fā)動(dòng)