1、第五章 約束問題的最優(yōu)化方法,5.1 引言 5.2 內點懲罰函數(shù)法 5.3 外點懲罰函數(shù)法 5.4 混合懲罰函數(shù)法 5.5 隨機方向搜索法 5.6 復合形法,機械優(yōu)化設計中的問題，大多數(shù)屬于約束優(yōu)化設計問題，其數(shù)學模型為:,上一章討論的都是無約束條件下非線性函數(shù)的尋優(yōu)方法，但在實際工程中大部分問題的變量取值都有一定的限制，也就是屬于有約束條件的尋優(yōu)問題。,5.1 引言,與無約束問題不同，約束問題目標函數(shù)的最小值是滿足約束條件下的最小值，即是由約束條件所限定的可行域內的最小值。 只要由約束條件所決定的可行域必是一個凸集，目標函數(shù)是凸函數(shù)，其約束最優(yōu)解就是全域最優(yōu)解。否則，將由于所選擇的初始點的不

2、同，而探索到不同的局部最優(yōu)解上。 在這種情況下，探索結果經常與初始點的選擇有關。為了能得到全局最優(yōu)解，在探索過程中最好能改變初始點，有時甚至要改換幾次。,（1）直接法 直接法包括：網格法、復合形法、隨機試驗法、隨機方向法、可變容差法和可行方向法。 （2）間接法 間接法包括：內點罰函數(shù)法、外點罰函數(shù)法、混合罰函數(shù)法、廣義乘子法、廣義簡約梯度法和約束變尺度法等。,根據(jù)求解方式的不同，約束優(yōu)化設計問題可分為:直接解法、間接解法。,一.有約束問題解法分類：,二. 直接解法的基本思想：,直接解法通常適用于僅含不等式約束的問題，思路是在 m 個不等式約束條件所確定的可行域內，選擇一個初始點，然后決定可行搜

3、索方向d ,且以適當?shù)牟介L ，進行搜索，得到一個使目標函數(shù)值下降的可行的新點，即完成一次迭代。再以新點為起點，在可行域中尋優(yōu)，經過若干次迭代，收斂至最優(yōu)點。迭代公式：,步長,可行搜索方向,可行搜索方向:當設計點沿該方向作微量移動時，目標函數(shù)值將下降，且不會越出可行域。,特點：在可行域內進行； 若可行域是凸集，目標函數(shù)是定義在凸集上的凸函數(shù)，則收斂到全局最優(yōu)點；否則，結果與初始點有關。,目的：將有約束優(yōu)化問題轉化為無約束優(yōu)化問題來解決。 方法：以原目標函數(shù)和加權的約束函數(shù)共同構成一個新的目標函數(shù) ( x, r1 ,r2 )，成為無約束優(yōu)化問題 。通過不斷調整加權因子，產生一系列函數(shù)的極小點序列

4、x(k)* (r1(k),r2(k) k= 0,1,2 ，逐漸收斂到原目標函數(shù)的約束最優(yōu)解。,其中：新目標函數(shù)：,三. 間接解法的基本思想：,新目標函數(shù)： 其中： 懲罰項：,加權因子，即懲罰因子： r1 , r2,函數(shù)的極小點序列 x (k)* ( r1 (k) , r2 (k) ) k= 0,1,2 其收斂必須滿足：,無約束優(yōu)化問題：,懲罰函數(shù)法概念：通過構造罰函數(shù)把約束問題轉化為一系列無約束最優(yōu)化問題，進而用無約束最優(yōu)化方法去求解，這類方法稱為序列無約束最小化方法。簡稱為SUMT法。,5.2 內點懲罰函數(shù)法,將有約束的優(yōu)化問題轉化為無約束優(yōu)化問題來求解。前提：一是不能破壞約束問題的約束條件

5、，二是使它歸結到原約束問題的同一最優(yōu)解上去。,構成一個新的目標函數(shù)，稱為懲罰函數(shù),從而有,懲罰項必須具有以下極限性質：,求解該新目標函數(shù)的無約束極小值，以期得到原問題的約束最優(yōu)解。按一定的法則改變罰因子r1 和r2的值，求得一序列的無約束最優(yōu)解，不斷地逼近原約束優(yōu)化問題的最優(yōu)解。,根據(jù)約束形式和定義的泛函及罰因子的遞推方法等不同，罰函數(shù)法可分為內點法、外點法和混合罰函數(shù)法三種。這種方法是1968年由美國學者AVFiacco和GPMcormick提出的，把不等式約束引入數(shù)學模型中，為求多維有約束非線性規(guī)劃問題開創(chuàng)了一個新局面。,一 . 內點法基本思想,這種方法將新目標函數(shù)定義于可行域內，序列迭代

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

7、迭代，而最優(yōu)解很可能在可行域內靠近邊界處或就在邊界上，此時盡管泛函的值很大，但罰因子是不斷遞減的正值，經多次迭代，接近最優(yōu)解時，懲罰項已是很小的正值。,例. 用內點法求,的約束最優(yōu)解。,解: 用內點法求解該問題時，首先構造內點懲罰函數(shù):,用解析法求函數(shù)的極小值，運用極值條件：,聯(lián)立求解得：,時，不滿足約束條件,應舍去 。,無約束極值點為：,顯然,由公式：,求得無約束極值點為：,當,1） 初始點x0的選取,使用內點法時，初始點應選擇一個離約束邊界較遠的可行點。如太靠近某一約束邊界，構造的懲罰函數(shù)可能由于障礙項的值很大而變得畸形，使求解無約束優(yōu)化問題發(fā)生困難.,2） 懲罰因子初值r0的選取,懲罰因

8、子的初值應適當，否則會影響迭代計算的正常進行。一般而言，太大，將增加迭代次數(shù)；太小，會使懲罰函數(shù)的性態(tài)變壞，甚至難以收斂到極值點。無一般性的有效方法。對于不同的問題，都要經過多次試算，才能決定一個適當 r0,二。幾個參數(shù)的選擇：,3) 懲罰因子的縮減系數(shù)c的選取,在構造序列懲罰函數(shù)時，懲罰因子r是一個逐次遞減到0的數(shù)列，相鄰兩次迭代的懲罰因子的關系為 :,式中的c 稱為懲罰因子的縮減系數(shù)，c為小于1的正數(shù)。一般的看法是，c值的大小在迭代過程中不起決定性作用，通常的取值范圍在0.1-0.7之間。,4) 收斂條件,三。算法步驟：,選取合適的初始點 x(0) ，以及 r(0)、c、計算精度 1、2

9、，令 k=0；,2. 構造懲罰（新目標）函數(shù) min (x , r ) ；,3. 調用無約束優(yōu)化方法，求新目標函數(shù)的最優(yōu)解 xk* 和 (xk , r(k) ) ；,4. 判斷是否收斂：運用終止準則 ,若均滿足，停止迭代，有約束優(yōu)化問題的最優(yōu)點為 x* = xk*； 若有一個準則不滿足，則令 并轉入第 3 步，繼續(xù)計算。,開始,結束,是,否,滿足收斂條件？,舉例：蓋板問題,b,h,ts,tf,設計一個箱形截面的蓋板。 已知：長度 l0= 600cm，寬度 b = 60cm，側板厚度 ts = 0.5cm，翼板厚度為 tf(cm)，高度為 h(cm)，承受最大的單位載荷 q = 0.01Mpa。

10、,要求：在滿足強度、剛度和穩(wěn)定性等條件下，設計一個最輕結構。,設計分析：（略）,數(shù)學模型：,優(yōu)化方法： 選用內點懲罰法，懲罰函數(shù)形式為：,調用 Powell 法求序列無約束優(yōu)化極值，以逐漸逼近原問題的極值點。,4. 求解過程分析：,5.3 外點懲罰函數(shù)法 (衰減函數(shù)法）,一. 基本思想：,外點法將新目標函數(shù) ( x , r ) 構筑在可行域 D 外，隨著懲罰因子 r(k) 的不斷遞增，生成一系列新目標函數(shù) (xk ,r(k)，在可行域外逐步迭代，產生的極值點 xk*(r(k) 序列從可行域外部趨向原目標函數(shù)的約束最優(yōu)點 x* 。,4,二.外點懲罰函數(shù)的形式為：,r 是懲罰因子 ,(,),(,)

11、,(,),(,),(,),(,),(,),(,),(,),(,),(,),(,),(,),(,),(,),(,),可用于處理等式約束。,處于適時約束面，,數(shù)值衰減到零，,各項違反約束的約束函,時，,代，當,在可行域外，則繼續(xù)迭,若,。,，,為零，,在可行域內，則懲罰項,若,。,時，得到最優(yōu)解：,當,為遞增系數(shù)，,，,是遞增的，,懲罰因子,=,=,F,=,=,+,*,*,*,*,*,*,*,lim,x,r,r,x,r,x,x,x,f,r,x,r,x,r,x,r,a,a,r,a,r,r,k,k,k,k,k,k,k,k,k,k,k,1,1,三. 幾個參數(shù)的選擇：,r (0) 的選擇: r (0) 過

12、大，會使懲罰函數(shù)的等值線變形或偏心，求極值困難。 r (0) 過小，迭代次數(shù)太多。,x(0) 的選擇： 基本上可以在可行域內外，任意選擇。,遞增系數(shù)a 的選擇： 通常選擇 5 10，可根據(jù)具體題目，進行試算調整。,四. 步驟：,2. 構造懲罰（新目標）函數(shù)，調用無約束優(yōu)化方法，求新目標函數(shù) 的最優(yōu)解 xk* 和 (xk , r(k) ) ；,3.,4. 判斷是否收斂：運用終止準則 ,若均滿足，停止迭代，有約束優(yōu)化問題的最優(yōu)點為 x* = xk*； 若有一個準則不滿足，則令 并轉入第 2 步，繼續(xù)計算。,1. 選擇合適的初始點x(0)，并選擇 r(0), a, 1, 2, 0，令 k=0 ；,五

13、. 方法評價：,初始點原則上可任意選擇; 能解決等式約束問題; 由于優(yōu)化過程是在可行域外進行，故在解決工程問題時，過程解均不可行。,5.4 混合懲罰函數(shù)法,一. 基本思想：,采用內點法和外點法相結合的混合懲罰函數(shù)法，以發(fā)揮內點法和外點法的特點，處理既有等式約束，又有不等式約束的優(yōu)化設計問題。,二. 懲罰函數(shù)的形式：,一般既包括障礙項，也包括衰減項。,5.5 隨機方向搜索法,一. 基本思想：,隨機產生初始點，隨機產生搜索方向 S(k) ，進行搜索。 但要確保： 新迭代點在可行域中； 目標函數(shù)值的下降性。,二. 隨機數(shù)的產生：,1. 偽隨機數(shù)： 用數(shù)學模型，從計算機（的隨機數(shù)發(fā)生器）中產生的隨機數(shù)

14、。,隨機數(shù)的特性 有較好的概率統(tǒng)計特性 抽樣的隨機性； 分布的均勻性； 前后數(shù)之間的獨立性； 周期性長。, 給出隨機數(shù) t 0 = 2z 1; 用遞推公式：ti = ti-1 (mod M)，產生隨機數(shù)列 t0, t1, t2 其中：乘子； mod M整除 M 取余數(shù)； ti = ti-1 乘以后除以 M 所得的余數(shù)。,3. 乘同余法：,4. 產生任意區(qū)間內的偽隨機數(shù)列：,三. 隨機產生初始點：, 估計設計變量的上、下限： xil x i xiu ，i=1,2,n； 在區(qū)間0,1中產生偽隨機數(shù)列 ri ， xi(0) = xil + ri ( xiu - xil )； 判斷是否 gu (xi(

15、0) ) 0；若滿足，則 x(0) = xi(0) 若不滿足，則轉向。,四. 隨機產生搜索方向：,x(0),x(m),x(1),x(2),x(j),x(l),H(0),五. 步驟：,X (k+1) ,均是，轉判2,六. 方法評價：,優(yōu)點：,對目標函數(shù)無性態(tài)要求； 收斂快（當m足夠大時）； 不受維數(shù)影響，維數(shù)愈高，愈體現(xiàn)優(yōu)點。,缺點：,對于嚴重非線性函數(shù)，只能得近似解； 當m不夠大時，解的近似程度大； 對于非凸函數(shù)，有可能收斂于局部解。,4.6 復合形法,一. 單純形法：,定義：,基本思想：,以一個目標函數(shù)值較小的新點，代替原單純形中目標函數(shù)值最大的頂點，組成新的單純形，這樣不斷地迭代，單純形逐

16、漸逼近最優(yōu)點。,以二維空間中的映射法為例：,X(1)=X(H),X(2),X(3),X(S),X(R)=X(4),X(5),X(6),在 n 維空間中，由n+1個點組成的圖形稱單純形。,X*,二. 復合形法：,定義： 在 n 維空間中，由 kn+1 個點組成的多面體稱為復合形。,基本思想：,以一個較好的新點，代替原復合形中的最壞點，組成新的復合形，以不斷的迭代，使新復合形逐漸逼近最優(yōu)點。,說明：,單純形是無約束優(yōu)化方法，而復合形可用于約束優(yōu)化的方法。 因為頂點數(shù)較多，所以比單純形更靈活易變。 復合形只能解決不等式約束問題。 因為迭代過程始終在可行域內進行，運行結果可靠。,三. 迭代方法：,1. 映射法：,例：二維空間中，k=4，復合形是四面體 x(1)x(2)x(3)x(4)，計算得： f (x(1) ) f (x(2) ) f (x(3) ) f (x(4) ),確定最壞點 x(H)= x(4) ，次壞點 x(G) = x(3) ，最好點 x(L) = x(1) 。 x(S)為除x(H)以外，各點的幾何中心。,搜索方向：沿 x(H) x(S) 的方向。 步長因子（映射系數(shù)）： 1，建議先取1.3。 映射迭代公式： x(R) = x(S) + (x(S) x(H) ) 若求得的 x(R) 在可行域內，