第五章

約束優(yōu)化方法第四節(jié)可行方向法

可行方向法是用梯度去求解約束優(yōu)化設計問題的一種有代表性的直接搜索方法，也是求解大型約束優(yōu)化設計問題的主要方法之一。其收斂速度快，效果較好，適用于大中型約束優(yōu)化設計問題的求解，但程序比較復雜。一、可行方向法的基本思想可行方向法的基本思想是在可行域內(nèi)選擇一個初始點，當確定了一個可行方向和適當?shù)牟介L后，按下式進行迭代計算。在不斷調(diào)整可行方向的過程中，使迭代點逐步逼近約束最優(yōu)點。二、可行方向法的基本搜索過程在可行方向法的搜索過程中，第一步迭代總是從可行的初始點出發(fā)，沿點的負梯度方向，將初始點移至某一個約束面(只有一個起作用的約束時)上或幾個約束面的交集(幾個約束同時起作用時)上，以后的搜索策略依據(jù)約束函數(shù)和目標函數(shù)的不同性質(zhì)而有所不同。第一種情況如圖(a)所示，在約束面上的迭代點處，產(chǎn)生一個可行方向，沿此方向進行一維搜索，得到的新點在可行域內(nèi)，即令迭代點，再沿點的負梯度方向繼續(xù)進行搜索。第二種情況如圖(b)所示，沿可行方向進行一維搜索，得到的新點在可行域外，則設法將新點移至約束面上，即取和約束面的交點作為新的迭代點。第三種情況是沿約束面搜索，這種搜索方法特別適用于只具有線性約束條件的非線性規(guī)劃問題，如圖(c)所示。從點出發(fā)，沿某一約束面移動至另一約束面的交線上。在有限步數(shù)內(nèi)即可搜索到約束最優(yōu)點。對于具有非線性約束函數(shù)的非線性規(guī)劃問題，沿約束面的切線方向進行搜索時，新點又將進入非可行域，如下圖所示，此時，須將進入非可行域的新點設法調(diào)整到約束面上，然后才能進行下一次迭代。解決這個問題的辦法是先規(guī)定允許進入非可行域的“深度”，即建立約束容差的邊界，然后沿目標函數(shù)的梯度方向或起作用約束函數(shù)的負梯度方向，將新點返回到約束面上，其計算公式為式中——調(diào)整步長因子，可用試探法決定，或用下式估算

盡管可行方向法有幾種不同的搜索策略，但其基本的是以下兩個決策。

(1)產(chǎn)生一個可行方向；

(2)沿可行方向確定一個不會越出可行域外的，甚至剛好移動到約束面上的適合步長因子。三、可行方向法產(chǎn)生可行方向的條件可行方向是指沿該方向做微小移動后，所得到的新點是可行點，且目標函數(shù)值有所下降，顯然，可行方向應滿足可行和下降兩個條件。

1．可行條件方向的可行條件是指沿該方向做微小移動后，所得到的新點是可行點。如下圖(a)所示，若點在一個約束面上，過點作約束面的切線，顯然，如果方向滿足可行條件，則方向與起作用約束函數(shù)在點的梯度的夾角應大于或等于，其向量關系式為若在J個起作用約束面的交集上，如下圖(b)所示，要求和J個起作用約束函數(shù)在點的梯度的夾角均應大于或等于，其向量關系式為

2．下降條件方向的下降條件是指沿該方向做微小移動后，所得到的新點目標函數(shù)值是下降的。如下圖所示，滿足下降條件的方向應和目標函數(shù)在點的梯度的夾角大于，其向量關系式為同時滿足可行條件和下降條件的方向稱可行方向。如下圖所示，它位于約束曲面在點的切線和目標函數(shù)等值線在點的切線所圍成的扇形區(qū)域內(nèi)，該扇形區(qū)域稱為可行下降方向區(qū)。綜上所述，當點位于J個起作用的約束面上時，滿足的方向稱為可行方向。四、可行方向法產(chǎn)生可行方向的方法如上所述，滿足可行、下降條件的方向位于可行下降方向區(qū)內(nèi)，在可行下降方向區(qū)內(nèi)尋找一個最有利的方向作為本次迭代的搜索方向，這個方向的產(chǎn)生方法主要有隨機產(chǎn)生法、線性規(guī)劃法和梯度投影法。

1．隨機產(chǎn)生法隨機產(chǎn)生法從原理上講與隨機方向搜索法產(chǎn)生方向的方法基本相同。先在點產(chǎn)生N個隨機單位方向向量，然后將產(chǎn)生的N個方向逐個進行可行方向檢驗，若其中有個方向滿足可行方向條件，則取可行方向為

2．線性規(guī)劃法在可行下降方向區(qū)內(nèi)沿任一方向進行搜索，都可得到一個目標函數(shù)值下降的可行點。現(xiàn)在的問題是如何在可行下降方向區(qū)內(nèi)選擇一個能使目標函數(shù)下降最快的方向作為本次迭代的搜索方向，顯然，這是一個以搜索方向為設計變量的約束優(yōu)化問題，這個新的約束優(yōu)化問題的數(shù)學模型為由于和為定值。上述各函數(shù)均為設計變量的線性函數(shù)，因此這是一個線性規(guī)劃問題，可以用線性規(guī)劃法求解，求得的最優(yōu)解。即為本次迭代的可行方向，即。

3．梯度投影法當點目標函數(shù)的負梯度方向不滿足可行條件時，可將方向投影到約束面(或約束面的交集)上，得到投影向量，如下圖所示，顯然投影向量滿足方向的可行和下降條件。梯度投影法就是取該方向作為本次迭代的可行方向，其計算公式為式中——階單位矩陣；——階起作用約束函數(shù)的梯度矩陣，即式中——點的目標函數(shù)梯度；——投影算子，為階矩陣，其計算公式為——起作用約束函數(shù)的個數(shù)。由于目標函數(shù)及約束函數(shù)的性質(zhì)不同，步長的確定方法也不同，不論是用何種方法，都應使新的迭代點為可行點，且目標函數(shù)值具有最大的下降量。確定步長主要有最佳步長和試驗步長兩種方法。五、可行方向法搜索步長的確定可行方向確定后，按下式計算新的迭代點、即

1．最住步長

如圖所示，這種方法就是從點出發(fā)，沿方向進行一維搜索，取得最佳步長，計算新的迭代點，即若為可行點，則本次迭代的步長取為。

2．試驗步長如下圖所示，若從點出發(fā)，沿方向進行一維搜索，得到的新點為不可行點，此時應根據(jù)可行方向法的搜索策略，改變步長，使新點返回到約束面上來，得到新的迭代點。使新的迭代點恰好位于約束面上的步長稱為最大步長，記作，則本次迭代的步長取為。由于不能預測出發(fā)點到另一個起作用約束面的距離，最大步長的確定較為困難，一般按試驗法確定，其步驟如下。(1)取一試驗步長，計算試驗點。應適當選取試驗步長，太大，會導致計算困難；也不能太小，太小會使計算效率降低。根據(jù)經(jīng)驗，試驗步長的值能使試驗點的目標函數(shù)值下降5％—10％為宜，即將目標函數(shù)在試驗點處展開成泰勒級數(shù)的線性式為2)在可行域外，即為非可行點；由此可得試驗步長的計算公式為(2)判別試驗點的位置。由上式確定的試驗點可能存在三種情況因為為目標函數(shù)的下降方向，即，所以試驗步長恒為正值。試驗步長選定后，按下式計算試驗點，即1)在約束面上；3)在在可行域內(nèi)。的條件時，就認為試驗點已位于約束面上。事實上，只要試驗點不在約束面上，就要設法將其調(diào)整到約束面上來。要想使試驗點準確地到達約束面是非常困難的，為此，先確定一個約束容差。當試驗點滿足若試驗點位于非可行域，則轉(zhuǎn)步驟(3)若試驗點位于可行域內(nèi)，則沿方向以2倍試驗步長，即，繼續(xù)向前搜索，直至新的試驗點到達約束面上或超出可行域，再轉(zhuǎn)步驟(3)。(3)將位于非可行域的試驗點調(diào)整到約束面上。如下圖所示，若試驗點位于，的位置，顯然應將試驗點調(diào)整到，因為對于試驗點來講，的約束違反量比大?？嘣O為約束違反量最大的約束條件，則應滿足將試驗點調(diào)整到的約束面上的方法有試探法和插值法兩種。

1）試探法的基本思想是當試驗點位于非可行域時，將試驗步長縮短；當試驗點位于可行域內(nèi)時，將試驗步長增加，即通過不斷調(diào)整的大小，將試驗點調(diào)整到約束面上。試探法調(diào)整試驗步長的過程如圖所示

2）插值法是利用線性插值將位于非可行域的試驗點調(diào)整到約束面上。設試驗步長為時，求得可行試驗點，即當試驗步長為時，求得非可行試驗點，即并設試驗點和的約束函數(shù)分別為和，它們的位置關系如下圖所示若考慮約束容差，并按容差作線性內(nèi)插，可以得到將非可行試驗點調(diào)整到約束面上的步長。按下式計算：則本次迭代的步長取為六、可行方向法的終止準則可行方向法的迭代終止準則有以下兩種。條件時，迭代終止。

(1)設計點及約束容差滿足

(2)設計點滿足庫思—塔克條件時，迭代終止。七、可行方向法的計算步驟(1)在可行域內(nèi)選擇一個初始點，給出約束容差和收斂精度值，。(3)計算試驗步長，得試驗點(4)計算值，并確定當時，，轉(zhuǎn)向步驟(3)。(2)一般迭代格式為(5)若，則用試探法或插值方法確定調(diào)整步長，直到將調(diào)整到約束面上，求得，令。

(6)若，則加大試驗步長，重新計算新的試驗點，直到越出可行域，轉(zhuǎn)向步驟(4)。(7)若，則轉(zhuǎn)向步驟(8)。(8)在新的設計點處產(chǎn)生新的可行方向。則計算終止，約束最優(yōu)解為，。否則，改變約束容差的值，即令(9)若點滿足收斂條件當

時;

當

時;

轉(zhuǎn)向步驟(2)。

例：用可行方向法求約束優(yōu)化問題的最優(yōu)解

。第五節(jié)懲罰函數(shù)法

目前，對于無約束優(yōu)化方法的研究要比對約束優(yōu)化方法的研究更為完善和成熟，并建立起了許多有效的、可靠的算法。如果能通過某種辦法對約束條件加以處理，將約束優(yōu)化問題轉(zhuǎn)化成無約束優(yōu)化問題，這樣就可以直接用無約束優(yōu)化方法來求解約束優(yōu)化問題，但是，這種轉(zhuǎn)化必須滿足如下兩個前提條件。

(1)不能破壞原約束優(yōu)化問題的約束條件；

(2)最優(yōu)解必須歸結(jié)到原約束優(yōu)化問題的最優(yōu)解上。這種將約束優(yōu)化問題轉(zhuǎn)化成無約束優(yōu)化問題，然后用無約束優(yōu)化方法來求解約束優(yōu)化問題的方法稱為約束優(yōu)化設計問題求解的間接解法。

懲罰函數(shù)法是一種使用很廣泛、很有效的求解約束優(yōu)化問題的間接解法，其特點是基本構(gòu)思簡單，可求解等式約束、不等式約束以及兩種約束兼有的優(yōu)化問題。一、懲罰函數(shù)法的基本原理懲罰函數(shù)法的基本原理是將約束優(yōu)化問題中的不等式和等式約束函數(shù)經(jīng)過加權(quán)轉(zhuǎn)化后，和原目標函數(shù)結(jié)合成新的目標函數(shù)——懲罰函數(shù)，即即將約束優(yōu)化問題轉(zhuǎn)化成的無約束優(yōu)化問題，通過求解上式的無約束優(yōu)化問題，以期得到原約束優(yōu)化問題的最優(yōu)解。為此，需按—定的法則改變加權(quán)因子和的值，構(gòu)成一系列無約束優(yōu)化問題，求得一系列的無約束最優(yōu)解，并不斷地逼近原約束優(yōu)化問題的最優(yōu)解。即要求滿足因此懲罰函數(shù)法又稱序列無約束極小化方法和，根據(jù)它們在懲罰函數(shù)中的作用，分別稱為障礙項和懲罰項。障礙項的作用是當?shù)c在可行域內(nèi)時，在迭代過程中將阻止迭代點超出可行域；懲罰項的作用是當?shù)c在非可行域或不滿足等式約束條件時，在迭代過程中將迫使迭代點逼近約束邊界或等式約束面。根據(jù)懲罰函數(shù)在迭代過程中迭代點是否為可行點，懲罰函數(shù)法又分為內(nèi)點懲罰函數(shù)法，外點懲罰函數(shù)法和混合懲罰函數(shù)法。一、內(nèi)點懲罰函數(shù)法內(nèi)點懲罰函數(shù)法(簡稱內(nèi)點法)將懲罰函數(shù)定義于可行城內(nèi)，序列迭代點在可行域內(nèi)逐步逼近約束邊界上的最優(yōu)點。內(nèi)點法只能求解具有不等式約束的優(yōu)化問題。

1．內(nèi)點法懲罰函數(shù)的形式對于只有不等式約束的優(yōu)化問題轉(zhuǎn)化后的懲罰函數(shù)的形式為或式中——懲罰因子，它滿足如下關系：或——障礙項。由于內(nèi)點法的迭代過程在可行域內(nèi)進行，障礙項的作用是阻止迭代點超出可行域。由障礙項的函數(shù)形式可知，當?shù)c趨向于邊界時，起作用約束函數(shù)的值趨近于0，導致障礙項的值陡然增加、并趨近于無窮大，這就好像在可行域邊界上筑起了一道“圍墻”，使迭代點始終在可行城內(nèi)，因此，也只有當懲罰因子趨近于0時，才能求得約束邊界上的最優(yōu)解。

2．內(nèi)點法的基本原理

例:用內(nèi)點法求約束優(yōu)化問題最優(yōu)解。解：如下圖所示，通過圖解法可得，該約束優(yōu)化問題的最優(yōu)點為，它是目標函數(shù)等值線()和約束函數(shù)直線()的切點，最優(yōu)值為。用內(nèi)點法求解該約束優(yōu)化問題時，首先構(gòu)造內(nèi)點懲罰函數(shù)，即聯(lián)立求解得對于任意給定的懲罰因子，懲罰函數(shù)為凸函數(shù)，可以用解析法求的極小值，即令。得由于不滿足約束條件，應舍去，所以無約束最優(yōu)點為當時，，；當時，，；當時，，；當時，，；由計算可知，當值逐漸減小，直至趨近于0時，逼近原問題的約束最優(yōu)解。下圖給出了懲罰因子時，懲罰函數(shù)的等值錢。從圖中可以清楚地看出，當值逐漸減小時，無約束最優(yōu)點的序列，是在可行域內(nèi)逐步逼近原問題的約束最優(yōu)解。

3．應用內(nèi)點法應注意的幾個問題

(1)初始點的選擇。因為內(nèi)點法將懲罰函數(shù)定義于可行城內(nèi)，故要求初始點嚴格滿足全部約束條件，且應避免位于邊界上，即應使。這樣做的目的是為了避免由于構(gòu)造的懲罰函數(shù)中的障礙項的值很大而變得畸形，使求解無約束優(yōu)化問題發(fā)生困難。在機械優(yōu)化設計中，只要不顧及懲罰函數(shù)值的大小，人為確定滿足上述條件的初始點是可以做到的。例如在對原有機械進行優(yōu)化改進設計時，可以以原有機械的有關參數(shù)作為初始點。對于較復雜的新產(chǎn)品的優(yōu)化設計，當約束條件較多且函數(shù)性態(tài)較復雜時，人為確定一個嚴格的可行內(nèi)點就比較因難，此時常利用隨機數(shù)來生成初始點，該方法在本章已介紹過。1)取，根據(jù)試算結(jié)果，決定增加或減小的值。2)按經(jīng)驗公式

(2)初始懲罰因子的選擇。初始懲罰因子值的確定應適當，否則會影響迭代計算的正常進行。一般來說，當值很小時，由上圖（c）可見，其懲罰函數(shù)的等值線在約束邊界附近會出現(xiàn)狹窄“谷地”。在這種情況下，無論采用什么樣的無約束優(yōu)化方法，懲罰函數(shù)都難于收斂于最優(yōu)點；相反，若值選得很大時，又會增加懲罰函數(shù)的無約束求解次數(shù)。事實上，由于懲罰函數(shù)的多樣化，使得的取值相當困難，目前尚無一定的有效方法。對于不同的懲罰函數(shù)，都要經(jīng)過多次試算，才能確定一個適當?shù)摹Ｏ旅鎯煞N方法可以作為試算取值的方法。計算值。這樣確定的，可使懲罰函數(shù)中的障礙項和原目標函數(shù)的值大致相等，不會因障礙項的值太大而起主導作用，也不會因障礙項的值太小而被忽略。

(3)懲罰因子遞減系數(shù)c的選擇。在構(gòu)造序列懲罰函數(shù)時，懲罰因子是一個逐次遞減到0的數(shù)列，相鄰兩次迭代的懲罰因子之間關系為式中c——懲罰因子遞減系數(shù)，。一般認為c值的大小在迭代過程中不起決定性作用，但也不可以掉以輕心。若c值太小，懲罰因子會下降過快，前后兩次無約束最優(yōu)點之間間距較大，有可能使后一次無約束優(yōu)化本身的迭代次數(shù)增加，且序列最優(yōu)點的距離過大，對向約束最優(yōu)點逼近不利；若c值太大，懲罰因子下降過慢，無約束求解次數(shù)將增多，建議取。

(4)終止準則。內(nèi)點法的終止準則為

第一個式子說明相鄰兩次迭代的最優(yōu)點己充分接近，即小于。下面的式子說明相鄰兩次迭代的懲罰函數(shù)值的相對變化量充分小，即小于。滿足終止準則的無約束最優(yōu)點已逼近原問題的約束最優(yōu)點，終止迭代。原約束優(yōu)化問題的最優(yōu)解為

4．內(nèi)點法的計算步驟

(1)選取適當?shù)某跏紤土P因子，遞減系數(shù)c，計算精度、。

(2)在可行域內(nèi)選擇一個初始點，令。

(4)判斷迭代是否終止，若滿足終止淮則，則終止迭代計算，并以，作為原問題的約束最優(yōu)解；否則，轉(zhuǎn)向下一步。的最優(yōu)點。

(3)構(gòu)造懲罰函數(shù)，選擇適當?shù)臒o約束優(yōu)化方法，從點出發(fā)，求

(5)計算，，，轉(zhuǎn)向步驟(3)。

內(nèi)點法有一個突出的優(yōu)點，就是當給定一可行方案之后，通過迭代計算，可給出一系列逐步改進的可行設計方案。因此，只要實際設計要求允許，就可以選擇其中任何一個無約束最優(yōu)點作為原問題的設計方案，而不一定選取最后的約束最優(yōu)點作為原問題的設計方案，這樣，一方面擴大了設計人員選擇方案的余地，另一方面也可使所選的設計方案留有一定的儲備能力。二、外點懲罰函數(shù)法外點懲罰函數(shù)法(簡稱外點法)，與內(nèi)點法相反，懲罰函數(shù)定義在可行域之外，序列迭代點從可行域之外逐漸逼近約束邊界上的最優(yōu)點。外點法可以用來求解含有不等式和等式約束的優(yōu)化問題。

1．外點法懲罰函數(shù)的形式對于一般約束優(yōu)化問題轉(zhuǎn)化后的懲罰函數(shù)的形式為式中——懲罰因子，它滿足如下關系：或——分別為對應于不等式約束和等式約束的懲罰項。由于外點法的迭代過程在可行域之外進行，懲罰項的作用是迫使迭代點逼近約束邊界或等式約束面。由懲罰項的形式可知，當?shù)c不可行時，懲罰項的值大于0，使得懲罰函數(shù)大于原目標函數(shù)，這可看成是對迭代點不滿足約束條件的一種懲罰。迭代點離約束邊界越遠，懲罰項的值越大，懲罰越重。但當?shù)c不斷接近約束邊界和等式約束面時，懲罰項的值減小。且趨近于0，懲罰項的懲罰作用逐漸消失，迭代點也就趨近于約束邊界的最優(yōu)點了。

2．外點法的基本原理

例:用外點法求約束優(yōu)化問題最優(yōu)解。解：如右圖所示，通過圖解法可得，該約束優(yōu)化問題的最優(yōu)點為，它是目標函數(shù)等值線()和約束函數(shù)直線()的切點，最優(yōu)值為。用外點法求解該約束優(yōu)化問題時，首先構(gòu)造外點懲罰函數(shù)，即對于任意給定的懲罰因子，懲罰函數(shù)為凸函數(shù)，可以用解析法求的極小值，即令。得聯(lián)立求解得當時，，；當時，，；當時，，；當時，，；由計算可知，當值逐漸增大，直至趨近于時，逼近原問題的約束最優(yōu)解。下圖給出了懲罰因子時，懲罰函數(shù)的等值錢。從圖中可以清楚地看出，當值逐漸增大時，無約束最優(yōu)點的序列，是在可行域之外逐步逼近原問題的約束最優(yōu)解。

3．應用外點法應注意的幾個問題

(1)初始點的選擇。外點法的初始點可以任意選擇，因為不論初始點選在可行域內(nèi)還是在可行域之外，只要目標函數(shù)的無約束極值點不在可行域內(nèi)，其懲罰函數(shù)的極值點均在可行域之外。這樣，當懲罰因子增大的倍數(shù)不是太大時，用前一次求得的無約束極值點作為下次求的初始點，對于加快搜索速度是很有好處的，特別是對于采用具有二次收斂的無約束最優(yōu)化方法，若初始點離極值點越近，則其收斂速度越快。

(2)初始懲罰因子的選擇。初始懲罰因子值選擇得適當與否．對于順利使用外點法求解約束優(yōu)化問題是有影響的。如果一開始就選擇相當大的值，會使懲罰函數(shù)的等值線形狀變形或偏心，造成求懲罰函數(shù)的極值很困難。因為在這種情況下，任何微小步長的誤差和搜索方向的變動，都會使計算過程很不穩(wěn)定，甚至找不到最優(yōu)點。若值取得過小，雖然可以使求解極值點變得容易些，但由于是趨近于相當大值時才能達到約束邊界，取得約束最優(yōu)解，這就會增加迭代次數(shù)，便收斂速度減慢。經(jīng)驗表明，取常常可以取得滿意的結(jié)果，有時也按下式計算：式中

(3)懲罰因子遞增系數(shù)C的選擇。在外點法中，懲罰因子是一個逐漸遞增的數(shù)列，相鄰兩次迭代的懲罰因子之間的關系為式中C——懲罰因子遞增系數(shù)，。

(4)終止準則。外點法的終止準則為

第一個式子說明無約束最優(yōu)點離起作用約束面的最大距離已充分小，即小于。下面的式子說明相鄰兩次迭代的最優(yōu)點已充分接近，即小于。滿足終止準則的無約束最優(yōu)點已逼近原問題的約束最優(yōu)點，終止迭代。原約束優(yōu)化問題的最優(yōu)解為

(5)約束容差帶。由于外點法懲罰函數(shù)的無約束最優(yōu)點序列為是從可行域之外向約束最優(yōu)點逼近的，即所以按前面的終止準則來結(jié)束計算過程，只能取得一個接近于可行域的非可行設計方案。當要求嚴格滿足不等式約束條件(加強度、剛度等性能約束)時，為了最終能取得一個可行的最優(yōu)設計方案，必須在約束邊界的可行域一例加一條容差帶——，這就要定義新的約束條件，即如圖所示，這樣可以用新的約束函數(shù)來構(gòu)造懲罰函數(shù)，求其最優(yōu)點，取得最優(yōu)設計方案，可以使原不等式約束條件得到嚴格的滿足，即。值不宜選取過大，以免所得結(jié)果與約束最優(yōu)點相差過遠，一般取。

4．外點法的計算步驟

(1)選取適當?shù)某跏紤土P因子，遞增系數(shù)c，初始點計算精度