第5章 約束優(yōu)化方法

第五章有約束優(yōu)化方法

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

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

（2）間接法

間接法包括：罰函數(shù)法、內(nèi)點罰函數(shù)法、外點罰函數(shù)法、混合罰函數(shù)法、廣義乘子法、廣義簡約梯度法和約束變尺度法等。根據(jù)求解方式的不同，約束優(yōu)化設計問題可分為:直接解法、間接解法。

直接解法通常適用于僅含不等式約束的問題，思路是在m個不等式約束條件所確定的可行域內(nèi)，選擇一個初始點，然后決定可行搜索方向d且以適當?shù)牟介L，進行搜索，得到一個使目標函數(shù)值下降的可行的新點，即完成一次迭代。再以新點為起點，重復上述搜索過程，直至滿足收斂條件。步長可行搜索方向

可行搜索方向:當設計點沿該方向作微量移動時，目標函數(shù)值將下降，且不會越出可行域。

間接解法的基本思路是按照一定的原則構造一個包含原目標函數(shù)和約束條件的新目標函數(shù)，即將原約束優(yōu)化問題轉化成為一個或一系列的無約束優(yōu)化問題。再對新的目標函數(shù)進行無約束優(yōu)化計算，從而間接地搜索到原約束問題的最優(yōu)解?；舅枷耄和ㄟ^構造罰函數(shù)把約束問題轉化為一系列無約束最優(yōu)化問題，進而用無約束最優(yōu)化方法去求解，這類方法稱為序列無約束最小化方法。簡稱為SUMT法?！?-2懲罰函數(shù)法將有約束的優(yōu)化問題轉化為無約束優(yōu)化問題來求解。前提：一是不能破壞約束問題的約束條件，二是使它歸結到原約束問題的同一最優(yōu)解上去。

構成一個新的目標函數(shù)，稱為懲罰函數(shù)

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

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

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

根據(jù)約束形式和定義的泛函及罰因子的遞推方法等不同，罰函數(shù)法可分為內(nèi)點法、外點法和混合罰函數(shù)法三種。這種方法是1968年由美國學者A．V．Fiacco和G．P．Mcormick提出的，把不等式約束引入數(shù)學模型中，為求多維有約束非線性規(guī)劃問題開創(chuàng)了一個新局面。內(nèi)點法這種方法將新目標函數(shù)定義于可行域內(nèi)，序列迭代點在可行域內(nèi)逐步逼近約束邊界上的最優(yōu)點。內(nèi)點法只能用來求解具有不等式約束的優(yōu)化問題。對于只具有不等式約束的優(yōu)化問題：

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

罰因子的作用是：由于內(nèi)點法只能在可行域內(nèi)迭代，而最優(yōu)解很可能在可行域內(nèi)靠近邊界處或就在邊界上，此時盡管泛函的值很大，但罰因子是不斷遞減的正值，經(jīng)多次迭代，接近最優(yōu)解時，懲罰項已是很小的正值。例5-2用內(nèi)點法求的約束最優(yōu)解。解:用內(nèi)點法求解該問題時，首先構造內(nèi)點懲罰函數(shù):用解析法求函數(shù)的極小值，運用極值條件：

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

應舍去。無約束極值點為當1）

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

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

r0

3)懲罰因子的縮減系數(shù)c的選取在構造序列懲罰函數(shù)時，懲罰因子r是一個逐次遞減到0的數(shù)列，相鄰兩次迭代的懲罰因子的關系為:式中的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）當K=0轉步驟5），否則轉步驟6）；5）K←K+1，r(K+1)←r(K)，xK+10←xK*，并轉步驟3）；6）按終止準則判別，若滿足轉步驟7），否則轉步驟5）；7）輸出最優(yōu)解（X*，F(xiàn)*），停止計算。2.

外點法

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

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

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

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

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

對上式求偏導，得

無約束目標函數(shù)極小化問題的最優(yōu)解系列為：當懲罰因子漸增時，由下表可看出收斂情況。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內(nèi)點法和外點法的簡單比較

內(nèi)點法的特點：

（1）始點必須為嚴格內(nèi)點

（2）不適于具有等式約束的數(shù)學模型

（3）迭代過程中各個點均為可行設計方案

（4）一般收斂較慢

（5）初始罰因子要選擇得當