第五章+約束優(yōu)化計(jì)算方法

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

機(jī)械優(yōu)化設(shè)計(jì)中的問題，大多數(shù)屬于約束優(yōu)化設(shè)計(jì)問題，其數(shù)學(xué)模型為上一章討論的都是無約束條件下非線性函數(shù)的尋優(yōu)方法，但在實(shí)際工程中大部分問題的變量取值都有一定的限制，也就是屬于有約束條件的尋優(yōu)問題。與無約束問題不同，約束問題目標(biāo)函數(shù)的最小值是滿足約束條件下的最小值，即是由約束條件所限定的可行域內(nèi)的最小值。只要由約束條件所決定的可行域必是一個(gè)凸集，目標(biāo)函數(shù)是凸函數(shù)，其約束最優(yōu)解就是全域最優(yōu)解。否則，將由于所選擇的初始點(diǎn)的不同，而探索到不同的局部最優(yōu)解上。在這種情況下，探索結(jié)果經(jīng)常與初始點(diǎn)的選擇有關(guān)。為了能得到全局最優(yōu)解，在探索過程中最好能改變初始點(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ù)法、廣義乘子法、廣義簡約梯度法和約束變尺度法等。根據(jù)求解方式的不同，約束優(yōu)化設(shè)計(jì)問題可分為:直接解法、間接解法。間接解法是將約束優(yōu)化問題轉(zhuǎn)化為一系列無約束優(yōu)化問題來解的一種方法。由于間接解法可以選用已研究比較成熟的無約束優(yōu)化方法，并且容易處理同時(shí)具有不等式約束和等式約束的問題。因而在機(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沿S方向進(jìn)行搜索，取得一個(gè)目標(biāo)函數(shù)有所改善的可行的新點(diǎn)x(1)，即完成了一次迭代。以新點(diǎn)為起始點(diǎn)重復(fù)上述搜索過程，每次均按如下的基本迭代格式進(jìn)行計(jì)算：

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

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

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

(k=0,1,2,…)

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

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

小取大值,大取小值2)為避免降維,K應(yīng)取大些;但過大,計(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)來看，一般情況下，最壞點(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滿足終止條件？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)化問題的一種直接方法，僅通過選取各頂點(diǎn)并比較各點(diǎn)處函數(shù)值的大小，就可尋找下一步的探索方向。但復(fù)合形各頂點(diǎn)的選擇和替換，不僅要滿足目標(biāo)函數(shù)值下降的要求，還應(yīng)當(dāng)滿足所有的約束條件。（2）復(fù)合形法適用于僅含不等式約束的問題?！?-5懲罰函數(shù)法

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

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

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

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

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

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

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

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

轉(zhuǎn)化后的懲罰函數(shù)形式為：或：rk是懲罰因子，它是一個(gè)由大到小且趨近于0的正數(shù)列，即:由于內(nèi)點(diǎn)法的迭代過程在可行域內(nèi)進(jìn)行，“障礙項(xiàng)”的作用是阻止迭代點(diǎn)越出可行域。由“障礙項(xiàng)”的函數(shù)形式可知，當(dāng)?shù)c(diǎn)靠近某一約束邊界時(shí)，其值趨近于0，而“障礙項(xiàng)”的值陡然增加，并趨近于無窮大，好像在可行域的邊界上筑起了一道“高墻”，使迭代點(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)法求解該問題時(shí)，首先構(gòu)造內(nèi)點(diǎn)懲罰函數(shù):用解析法求函數(shù)的極小值，運(yùn)用極值條件：

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

應(yīng)舍去。無約束極值點(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)的值很大而變得畸形，使求解無約束優(yōu)化問題發(fā)生困難.2）

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

r0

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

:式中的c稱為懲罰因子的縮減系數(shù)，c為小于1的正數(shù)。一般的看法是，c值的大小在迭代過程中不起決定性作用，通常的取值范圍在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)則判別，若滿足轉(zhuǎn)步驟7），否則轉(zhuǎn)步驟5）；7）輸出最優(yōu)解（X*，F(xiàn)*），停止計(jì)算。2.

外點(diǎn)法

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

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

r是懲罰因子

,外點(diǎn)法的迭代過程在可行域之外進(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)愈大，這可看成是對迭代點(diǎn)不滿足約束條件的一種懲罰。轉(zhuǎn)化后的外點(diǎn)懲罰函數(shù)的形式為：例

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

對上式求偏導(dǎo)，得

無約束目標(biāo)函數(shù)極小化問題的最優(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)法求問題約束最優(yōu)解。首先構(gòu)造外點(diǎn)懲罰函數(shù)：用解析法求解求解得外點(diǎn)法懲罰因子按下式遞增遞增系數(shù)，通常取c=5-10。與內(nèi)點(diǎn)法相反計(jì)算r0

值。選取的r0

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