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

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

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

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

（2）間接法

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

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

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

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

(k=0,1,2,…)

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

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

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

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

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

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

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

及次壞點XG，即2）計算除去最壞點XH

外的（k-1）個頂點的中心XC

3）從統(tǒng)計的觀點來看，一般情況下，最壞點XH和中心點XC的連線方向為目標(biāo)函數(shù)的下降方向。4）判別反射點XR的位置若XR

為可行點，則比較XR

和XH

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

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

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

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

i=1,2,…n產(chǎn)生初始復(fù)合形頂點Xj,j=1,2,…,K計算復(fù)合形各頂點的函數(shù)值F(Xj),j=1,2,…,K是是是否否否XR∈DFR<F(XH)方法特點（1）復(fù)合形法是求解約束非線性最優(yōu)化問題的一種直接方法，僅通過選取各頂點并比較各點處函數(shù)值的大小，就可尋找下一步的探索方向。但復(fù)合形各頂點的選擇和替換，不僅要滿足目標(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)化項將有約束的優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來求解。前提：一是不能破壞約束問題的約束條件，二是使它歸結(jié)到原約束問題的同一最優(yōu)解上去。

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

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

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

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

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

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

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

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

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

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

應(yīng)舍去。無約束極值點為當(dāng)1）

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

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

r0

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

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

4)收斂條件算法步驟：1）選擇可行域內(nèi)初始點X(0);2）選取初始罰因子r(0)與罰因子降低系數(shù)c，并置K←0；3）求minφ(x(K),r(K))解出最優(yōu)點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)*），停止計算。2.

外點法

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

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

r是懲罰因子

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

不可行時，懲罰項的值大于0。

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

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

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

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

無約束目標(biāo)函數(shù)極小化問題的最優(yōu)解系列為：當(dāng)懲罰因子漸增時，由下表可看出收斂情況。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用外點法求問題約束最優(yōu)解。首先構(gòu)造外點懲罰函數(shù)：用解析法求解求解得外點法懲罰因子按下式遞增遞增系數(shù)，通常取c=5-10。與內(nèi)點法相反計算r0

值。選取的r0

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