第五章+約束優(yōu)化計(jì)算方法_第1頁(yè)
第五章+約束優(yōu)化計(jì)算方法_第2頁(yè)
第五章+約束優(yōu)化計(jì)算方法_第3頁(yè)
第五章+約束優(yōu)化計(jì)算方法_第4頁(yè)
第五章+約束優(yōu)化計(jì)算方法_第5頁(yè)
已閱讀5頁(yè),還剩51頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第五章約束優(yōu)化計(jì)算方法5.1引言5.2隨機(jī)方向搜索法5.3復(fù)合形法5.4懲罰函數(shù)法5.1引言

機(jī)械優(yōu)化設(shè)計(jì)中的問(wèn)題,大多數(shù)屬于約束優(yōu)化設(shè)計(jì)問(wèn)題,其數(shù)學(xué)模型為上一章討論的都是無(wú)約束條件下非線性函數(shù)的尋優(yōu)方法,但在實(shí)際工程中大部分問(wèn)題的變量取值都有一定的限制,也就是屬于有約束條件的尋優(yōu)問(wèn)題。與無(wú)約束問(wèn)題不同,約束問(wèn)題目標(biāo)函數(shù)的最小值是滿(mǎn)足約束條件下的最小值,即是由約束條件所限定的可行域內(nèi)的最小值。只要由約束條件所決定的可行域必是一個(gè)凸集,目標(biāo)函數(shù)是凸函數(shù),其約束最優(yōu)解就是全域最優(yōu)解。否則,將由于所選擇的初始點(diǎn)的不同,而探索到不同的局部最優(yōu)解上。在這種情況下,探索結(jié)果經(jīng)常與初始點(diǎn)的選擇有關(guān)。為了能得到全局最優(yōu)解,在探索過(guò)程中最好能改變初始點(diǎn),有時(shí)甚至要改換幾次。(1)直接法

直接法包括:網(wǎng)格法、復(fù)合形法、隨機(jī)試驗(yàn)法、隨機(jī)方向法、可變?nèi)莶罘ê涂尚蟹较蚍ā?/p>

(2)間接法

間接法包括:罰函數(shù)法、內(nèi)點(diǎn)罰函數(shù)法、外點(diǎn)罰函數(shù)法、混合罰函數(shù)法、廣義乘子法、廣義簡(jiǎn)約梯度法和約束變尺度法等。根據(jù)求解方式的不同,約束優(yōu)化設(shè)計(jì)問(wèn)題可分為:直接解法、間接解法。間接解法是將約束優(yōu)化問(wèn)題轉(zhuǎn)化為一系列無(wú)約束優(yōu)化問(wèn)題來(lái)解的一種方法。由于間接解法可以選用已研究比較成熟的無(wú)約束優(yōu)化方法,并且容易處理同時(shí)具有不等式約束和等式約束的問(wèn)題。因而在機(jī)械優(yōu)化設(shè)計(jì)得到廣泛的應(yīng)用。間接解法中具有代表性的是懲罰函數(shù)法。直接解法的基本思想:在由m個(gè)不等式約束條件gu(x)≤0所確定的可行域φ內(nèi),選擇一個(gè)初始點(diǎn)x(0),然后確定一個(gè)可行搜索方向S,且以適當(dāng)?shù)牟介L(zhǎng)沿S方向進(jìn)行搜索,取得一個(gè)目標(biāo)函數(shù)有所改善的可行的新點(diǎn)x(1),即完成了一次迭代。以新點(diǎn)為起始點(diǎn)重復(fù)上述搜索過(guò)程,每次均按如下的基本迭代格式進(jìn)行計(jì)算:

x(k+1)=x(k)+α(k)S(k)(k=0,1,2,…)逐步趨向最優(yōu)解,直到滿(mǎn)足終止準(zhǔn)則才停止迭代。直接解法通常適用于僅含不等式約束的問(wèn)題,思路是在m個(gè)不等式約束條件所確定的可行域內(nèi),選擇一個(gè)初始點(diǎn),然后決定可行搜索方向S且以適當(dāng)?shù)牟介L(zhǎng),進(jìn)行搜索,得到一個(gè)使目標(biāo)函數(shù)值下降的可行的新點(diǎn),即完成一次迭代。再以新點(diǎn)為起點(diǎn),重復(fù)上述搜索過(guò)程,直至滿(mǎn)足收斂條件。-------步長(zhǎng)--------可行搜索方向可行搜索方向:當(dāng)設(shè)計(jì)點(diǎn)沿該方向作微量移動(dòng)時(shí),目標(biāo)函數(shù)值將下降,且不會(huì)越出可行域。直接解法的原理簡(jiǎn)單,方法實(shí)用,其特點(diǎn)是:1)由于整個(gè)過(guò)程在可行域內(nèi)進(jìn)行,因此,迭代計(jì)算不論何時(shí)終止,都可以獲得比初始點(diǎn)好的設(shè)計(jì)點(diǎn)。2)若目標(biāo)函數(shù)為凸函數(shù),可行域?yàn)橥辜瑒t可獲得全域最優(yōu)解,否則,可能存在多個(gè)局部最優(yōu)解,當(dāng)選擇的初始點(diǎn)不同,而搜索到不同的局部最優(yōu)解。3)要求可行域有界的非空集。a)可行域是凸集;b)可行域是非凸集間接解法的求解思路:將約束函數(shù)進(jìn)行特殊的加權(quán)處理后,和目標(biāo)函數(shù)結(jié)合起來(lái),構(gòu)成一個(gè)新的目標(biāo)函數(shù),即將原約束優(yōu)化問(wèn)題轉(zhuǎn)化為一個(gè)或一系列的無(wú)約束優(yōu)化問(wèn)題。新目標(biāo)函數(shù)加權(quán)因子然后對(duì)新目標(biāo)函數(shù)進(jìn)行無(wú)約束極小化計(jì)算。5.2隨機(jī)方向法

基本思想:利用計(jì)算機(jī)產(chǎn)生的隨機(jī)數(shù)所構(gòu)成的隨機(jī)方向進(jìn)行搜索,產(chǎn)生的新點(diǎn)必須在可行域內(nèi),即滿(mǎn)足直接法的特性。隨機(jī)方向法,是約束最優(yōu)化問(wèn)題的一種常用的直接求解方法。隨機(jī)方向法的基本思路:在可行域內(nèi)選擇一個(gè)初始點(diǎn),利用隨機(jī)數(shù)的概率特性,產(chǎn)生若干個(gè)隨機(jī)方向,并從中選擇一個(gè)能使目標(biāo)函數(shù)值下降最快的隨機(jī)方向作為搜索方向s。從初始點(diǎn)x0出發(fā),沿s方向以一定步長(zhǎng)進(jìn)行搜索,得到新點(diǎn)X,新點(diǎn)x應(yīng)滿(mǎn)足約束條件且f(x)<f(x0),至此完成一次迭代?;舅悸啡鐖D所示。隨機(jī)方向法程序設(shè)計(jì)簡(jiǎn)單,搜索速度快,是解決小型機(jī)械優(yōu)化問(wèn)題的十分有效的算法。隨機(jī)方向探索法的一般迭代計(jì)算公式為:

X(k+1)=X(k)+aS(k)

(k=0,1,2,…)

式中a為步長(zhǎng),S(k)為第k次迭代的隨機(jī)探索方向。因此,隨機(jī)方向探索法的計(jì)算過(guò)程可歸結(jié)為:

復(fù)合形法是求解約束非線性最優(yōu)化問(wèn)題的一種重要的直接方法。它來(lái)源于用于求解無(wú)約束非線性最優(yōu)化問(wèn)題的單純形法,實(shí)際上是單純形法在約束問(wèn)題中的發(fā)展。如前所述,在求解無(wú)約束問(wèn)題的單純形法中,不需計(jì)算目標(biāo)函數(shù)的梯度,而是靠選取單純形的頂點(diǎn)井比較各頂點(diǎn)處目標(biāo)函數(shù)值的大小,來(lái)尋找下一步的探索方向的。在用于求解約束問(wèn)題的復(fù)合形法中,復(fù)合形各頂點(diǎn)的選擇和替換,不僅要滿(mǎn)足目標(biāo)函數(shù)值的下降,還應(yīng)當(dāng)滿(mǎn)足所有的約束條件。5.3復(fù)合形法它的基本思路是在可行域內(nèi)構(gòu)造一個(gè)具有k個(gè)頂點(diǎn)的初始復(fù)合形。對(duì)該復(fù)合形各頂點(diǎn)的目標(biāo)函數(shù)值進(jìn)行比較,找到目標(biāo)函數(shù)最大的頂點(diǎn)(最壞點(diǎn)),然后按一定的法則求出目標(biāo)函數(shù)值有所下降的可行的新點(diǎn),并用此點(diǎn)代替最壞點(diǎn),構(gòu)成新的復(fù)合形,復(fù)合形的形狀沒(méi)改變一次,就向最優(yōu)點(diǎn)移動(dòng)一步,直至逼近最優(yōu)點(diǎn)。由于復(fù)合形的形狀不必保持規(guī)則的圖形,對(duì)目標(biāo)函數(shù)和約束函數(shù)無(wú)特殊要求,因此這種方法適應(yīng)性強(qiáng),在機(jī)械優(yōu)化設(shè)計(jì)中應(yīng)用廣泛。二.初始復(fù)合形的構(gòu)成1.復(fù)合形頂點(diǎn)數(shù)K的選擇建議:

小取大值,大取小值2)為避免降維,K應(yīng)取大些;但過(guò)大,計(jì)算量也大.*1)為保證迭代點(diǎn)能逼近極小點(diǎn),應(yīng)使2.初始復(fù)合形頂點(diǎn)的確定

1)用試湊方法產(chǎn)生---適于低維情況;2)用隨機(jī)方法產(chǎn)生①用隨機(jī)方法產(chǎn)生K個(gè)頂點(diǎn)先用隨機(jī)函數(shù)產(chǎn)生

個(gè)隨機(jī)數(shù)

,然后變換到預(yù)定的區(qū)間

中去.這便得到了一個(gè)頂點(diǎn),要連續(xù)產(chǎn)生K個(gè)頂點(diǎn).初始復(fù)合形生成的方法:1)由設(shè)計(jì)者決定k個(gè)可形點(diǎn),構(gòu)成初始復(fù)合形。設(shè)計(jì)變量少時(shí)適用。2)由設(shè)計(jì)者選定一個(gè)可形點(diǎn),其余的k-1個(gè)可形點(diǎn)用隨機(jī)法產(chǎn)生。3)由計(jì)算機(jī)自動(dòng)生成初始復(fù)合形的所有頂點(diǎn)。二、復(fù)合形法的搜索方法1.反射1)計(jì)算復(fù)合形各頂點(diǎn)的目標(biāo)函數(shù)值,并比較其大小,求出最好點(diǎn)XL、最壞點(diǎn)XH

及次壞點(diǎn)XG,即2)計(jì)算除去最壞點(diǎn)XH

外的(k-1)個(gè)頂點(diǎn)的中心XC

3)從統(tǒng)計(jì)的觀點(diǎn)來(lái)看,一般情況下,最壞點(diǎn)XH和中心點(diǎn)XC的連線方向?yàn)槟繕?biāo)函數(shù)的下降方向。4)判別反射點(diǎn)XR的位置若XR

為可行點(diǎn),則比較XR

和XH

兩點(diǎn)的目標(biāo)函數(shù)值,如果f(XR)<f(XH),則用XR取代XH

,構(gòu)成新的復(fù)合形,完成一次迭代;如果f(XR)>=f(XH),則將α縮小0.7倍,重新計(jì)算新的反射點(diǎn),若仍不行,繼續(xù)縮小α,直至f(XR)<f(XH)為止。若為非可行點(diǎn),則將α縮小0.7倍,直至可行為止。然后再重復(fù)可行點(diǎn)的步驟。2.擴(kuò)張3.收縮三.終止判別條件各頂點(diǎn)與好點(diǎn)函數(shù)值之差的均方根應(yīng)不大于誤差限比較復(fù)合形各頂點(diǎn)的函數(shù)值,找出好點(diǎn)XL,壞點(diǎn)XHXH=XRα=0.5α找出次壞點(diǎn)XSH

,XH=XSH滿(mǎn)足終止條件?X*=XL,F*=F(XL)結(jié)束四.復(fù)合形法的

迭代步驟是否給定K,δ,α,ε,ai,bi

i=1,2,…n產(chǎn)生初始復(fù)合形頂點(diǎn)Xj,j=1,2,…,K計(jì)算復(fù)合形各頂點(diǎn)的函數(shù)值F(Xj),j=1,2,…,K是是是否否否XR∈DFR<F(XH)方法特點(diǎn)(1)復(fù)合形法是求解約束非線性最優(yōu)化問(wèn)題的一種直接方法,僅通過(guò)選取各頂點(diǎn)并比較各點(diǎn)處函數(shù)值的大小,就可尋找下一步的探索方向。但復(fù)合形各頂點(diǎn)的選擇和替換,不僅要滿(mǎn)足目標(biāo)函數(shù)值下降的要求,還應(yīng)當(dāng)滿(mǎn)足所有的約束條件。(2)復(fù)合形法適用于僅含不等式約束的問(wèn)題?!?-5懲罰函數(shù)法

懲罰函數(shù)法是一種很廣泛、很有效的間接解法。它的基本原理是將約束優(yōu)化問(wèn)題中的不等式和不等式約束函數(shù)經(jīng)加權(quán)后,和原目標(biāo)函數(shù)結(jié)合為新的目標(biāo)函數(shù)——懲罰函數(shù)。

將約束優(yōu)化問(wèn)題轉(zhuǎn)換為無(wú)約束優(yōu)化問(wèn)題。求解無(wú)約束優(yōu)化問(wèn)題的極小值,從而得到原約束優(yōu)化問(wèn)題的最優(yōu)解。加權(quán)轉(zhuǎn)化項(xiàng)將有約束的優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題來(lái)求解。前提:一是不能破壞約束問(wèn)題的約束條件,二是使它歸結(jié)到原約束問(wèn)題的同一最優(yōu)解上去。

構(gòu)成一個(gè)新的目標(biāo)函數(shù),稱(chēng)為懲罰函數(shù)

從而有懲罰項(xiàng)必須具有以下極限性質(zhì):

求解該新目標(biāo)函數(shù)的無(wú)約束極小值,以期得到原問(wèn)題的約束最優(yōu)解。按一定的法則改變罰因子r1

和r2的值,求得一序列的無(wú)約束最優(yōu)解,不斷地逼近原約束優(yōu)化問(wèn)題的最優(yōu)解。

根據(jù)約束形式和定義的泛函及罰因子的遞推方法等不同,罰函數(shù)法可分為內(nèi)點(diǎn)法、外點(diǎn)法和混合罰函數(shù)法三種。這種方法是1968年由美國(guó)學(xué)者A.V.Fiacco和G.P.Mcormick提出的,把不等式約束引入數(shù)學(xué)模型中,為求多維有約束非線性規(guī)劃問(wèn)題開(kāi)創(chuàng)了一個(gè)新局面。內(nèi)點(diǎn)法

這種方法將新目標(biāo)函數(shù)定義于可行域內(nèi),序列迭代點(diǎn)在可行域內(nèi)逐步逼近約束邊界上的最優(yōu)點(diǎn)。內(nèi)點(diǎn)法只能用來(lái)求解具有不等式約束的優(yōu)化問(wèn)題。對(duì)于只具有不等式約束的優(yōu)化問(wèn)題:

轉(zhuǎn)化后的懲罰函數(shù)形式為:或:rk是懲罰因子,它是一個(gè)由大到小且趨近于0的正數(shù)列,即:由于內(nèi)點(diǎn)法的迭代過(guò)程在可行域內(nèi)進(jìn)行,“障礙項(xiàng)”的作用是阻止迭代點(diǎn)越出可行域。由“障礙項(xiàng)”的函數(shù)形式可知,當(dāng)?shù)c(diǎn)靠近某一約束邊界時(shí),其值趨近于0,而“障礙項(xiàng)”的值陡然增加,并趨近于無(wú)窮大,好像在可行域的邊界上筑起了一道“高墻”,使迭代點(diǎn)始終不能越出可行域。顯然,只有當(dāng)懲罰因子時(shí),才能求得在約束邊界上的最優(yōu)解。

罰因子的作用是:由于內(nèi)點(diǎn)法只能在可行域內(nèi)迭代,而最優(yōu)解很可能在可行域內(nèi)靠近邊界處或就在邊界上,此時(shí)盡管泛函的值很大,但罰因子是不斷遞減的正值,經(jīng)多次迭代,接近最優(yōu)解時(shí),懲罰項(xiàng)已是很小的正值。

例5-2用內(nèi)點(diǎn)法求的約束最優(yōu)解。解:用內(nèi)點(diǎn)法求解該問(wèn)題時(shí),首先構(gòu)造內(nèi)點(diǎn)懲罰函數(shù):用解析法求函數(shù)的極小值,運(yùn)用極值條件:

聯(lián)立求解得:時(shí)不滿(mǎn)足約束條件

應(yīng)舍去。無(wú)約束極值點(diǎn)為當(dāng)1)

初始點(diǎn)x0的選取使用內(nèi)點(diǎn)法時(shí),初始點(diǎn)應(yīng)選擇一個(gè)離約束邊界較遠(yuǎn)的可行點(diǎn)。如太靠近某一約束邊界,構(gòu)造的懲罰函數(shù)可能由于障礙項(xiàng)的值很大而變得畸形,使求解無(wú)約束優(yōu)化問(wèn)題發(fā)生困難.2)

懲罰因子初值r0的選取懲罰因子的初值應(yīng)適當(dāng),否則會(huì)影響迭代計(jì)算的正常進(jìn)行。一般而言,太大,將增加迭代次數(shù);太小,會(huì)使懲罰函數(shù)的性態(tài)變壞,甚至難以收斂到極值點(diǎn)。無(wú)一般性的有效方法。對(duì)于不同的問(wèn)題,都要經(jīng)過(guò)多次試算,才能決定一個(gè)適當(dāng)

r0

3)懲罰因子的縮減系數(shù)c的選取在構(gòu)造序列懲罰函數(shù)時(shí),懲罰因子r是一個(gè)逐次遞減到0的數(shù)列,相鄰兩次迭代的懲罰因子的關(guān)系為

:式中的c稱(chēng)為懲罰因子的縮減系數(shù),c為小于1的正數(shù)。一般的看法是,c值的大小在迭代過(guò)程中不起決定性作用,通常的取值范圍在0.1~0.7之間。

4)收斂條件算法步驟:1)選擇可行域內(nèi)初始點(diǎn)X(0);2)選取初始罰因子r(0)與罰因子降低系數(shù)c,并置K←0;3)求minφ(x(K),r(K))解出最優(yōu)點(diǎn)xK*;4)當(dāng)K=0轉(zhuǎn)步驟5),否則轉(zhuǎn)步驟6);5)K←K+1,r(K+1)←r(K),xK+10←xK*,并轉(zhuǎn)步驟3);6)按終止準(zhǔn)則判別,若滿(mǎn)足轉(zhuǎn)步驟7),否則轉(zhuǎn)步驟5);7)輸出最優(yōu)解(X*,F(xiàn)*),停止計(jì)算。2.

外點(diǎn)法

外點(diǎn)法是從可行域的外部構(gòu)造一個(gè)點(diǎn)序列去逼近原約束問(wèn)題的最優(yōu)解。外點(diǎn)法可以用來(lái)求解含不等式和等式約束的優(yōu)化問(wèn)題。

外點(diǎn)懲罰函數(shù)的形式為:

r是懲罰因子

,外點(diǎn)法的迭代過(guò)程在可行域之外進(jìn)行,懲罰項(xiàng)的作用是迫使迭代點(diǎn)逼近約束邊界或等式約束曲面。由懲罰項(xiàng)的形式可知,當(dāng)?shù)c(diǎn)x

不可行時(shí),懲罰項(xiàng)的值大于0。

懲罰因子,它是由小到大。懲罰項(xiàng)由懲罰項(xiàng)可知,當(dāng)?shù)c(diǎn)不可行時(shí),懲罰項(xiàng)的值大于零。

當(dāng)?shù)c(diǎn)離約束邊界越遠(yuǎn)時(shí),懲罰項(xiàng)愈大,這可看成是對(duì)迭代點(diǎn)不滿(mǎn)足約束條件的一種懲罰。轉(zhuǎn)化后的外點(diǎn)懲罰函數(shù)的形式為:例

用外點(diǎn)法求解下列有約束優(yōu)化問(wèn)題解:懲罰函數(shù)為:

對(duì)上式求偏導(dǎo),得

無(wú)約束目標(biāo)函數(shù)極小化問(wèn)題的最優(yōu)解系列為:當(dāng)懲罰因子漸增時(shí),由下表可看出收斂情況。r0.01-0.80975-50.00000-24.9650-49.99770.1-0.45969-5.00000-2.2344-4.947410.23607-0.500000.96310.1295100.83216-0.050002.30682.000110000.99800-0.000502.66242.6582∞108/38/3例6-6用外點(diǎn)法求問(wèn)題約束最優(yōu)解。首先構(gòu)造外點(diǎn)懲罰函數(shù):用解析法求解求解得外點(diǎn)法懲罰因子按下式遞增遞增系數(shù),通常取c=5-10。與內(nèi)點(diǎn)法相反計(jì)算r0

值。選取的r0

太大則會(huì)使懲罰函數(shù)等值線偏心或變形,難以取得極小值。但r0太小

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論