第16講約束優(yōu)化計(jì)算方法

1、機(jī)械現(xiàn)代設(shè)計(jì)第16講 約束優(yōu)化設(shè)計(jì)方法 外點(diǎn)法 隨機(jī)搜索法 復(fù)合型法等約束優(yōu)化設(shè)計(jì)的最優(yōu)解條件1 約束優(yōu)化設(shè)計(jì)的最優(yōu)點(diǎn)在可行域 D 中 最優(yōu)點(diǎn)是一個內(nèi)點(diǎn)，其最優(yōu)解條件與無約束優(yōu)化設(shè)計(jì)的最優(yōu)解條件相同：2 約束優(yōu)化設(shè)計(jì)的最優(yōu)點(diǎn)在可行域 D 的邊界上 設(shè) X (k) 點(diǎn)有適時約束 則，在 X (k) 點(diǎn)的可行方向 S 應(yīng)滿足 若在所有滿足式(1) 的可行方向 S 中，有可行下降方向 Si 存在，則 Si 還應(yīng)滿足約束優(yōu)化設(shè)計(jì)的最優(yōu)解條件 若在所有滿足式(1) 的可行方向 S 中，找不到滿足式(2)的可行下降方向，即：因此，目標(biāo)函數(shù) f (X) 在 X (k) 點(diǎn)的鄰域中，再也不可能下降了，即 f

2、( X (k) ) 是目標(biāo)函數(shù) f (X) 在 X (k) 附近鄰域中的極小值，X (k) 是其鄰域的極小點(diǎn)。 約束優(yōu)化設(shè)計(jì)的最優(yōu)解條件 3 Kuhn-Tucker 最優(yōu)性條件（K-T條件） 設(shè) gj (X (k) ) ， j = 1、2、 、 l ，是 X (k) 點(diǎn)的適時約束，即有則 X (k) 點(diǎn)是約束優(yōu)化問題的一個極小點(diǎn)的必要條件是注意：式(4) 中， 必須線 性無關(guān)，該條件才成立。約束優(yōu)化設(shè)計(jì)的最優(yōu)解條件不是極小點(diǎn)是極小點(diǎn)概述 懲罰函數(shù)法是一種約束優(yōu)化問題的間接解法。 約束優(yōu)化問題的間接解法的基本思想是把一個約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題。一、外點(diǎn)法的懲罰函數(shù) 對于約束優(yōu)化問題外點(diǎn)

3、法的懲罰函數(shù)為 Z0,一般Z=2.懲罰因子 r(k) 二、外點(diǎn)法的基本原理 對于式(1) 表示的約束優(yōu)化問題，外點(diǎn)法定義懲罰函數(shù)如式(2)，把式(1) 表示的約束優(yōu)化問題，轉(zhuǎn)化一系列的無約束優(yōu)化問題 外點(diǎn)法求解約束優(yōu)化問題式(1) 的過程：i. 選取初始點(diǎn) X(k) ，k = 0；ii. 選擇合適的懲罰因子 r(0) iii. 從 X(0) 出發(fā)，求解無約束優(yōu)化問題 得到 X*(r(0) ) ；iv. k = k +1 ，調(diào)整懲罰因子 r(k) ，從 X*(r(k-1) ) 出發(fā)，求解無約束優(yōu)化問題 得到 X*(r(k) )，k = 1，2， 二、外點(diǎn)法的基本原理1) 當(dāng) X*(r(k) )

4、在可行域內(nèi)，2) 當(dāng) X*(r(k) ) 在可行域外，則二、外點(diǎn)法的基本原理三、 懲罰因子 r(k) 的選擇1 r(0) 的選取 2 r(k) ( k = 1、2、) 的選取 遞增系數(shù)四、收斂條件 及 在外點(diǎn)法中，還必須判斷 X*(r(k) ) 是否到達(dá)約束面，即 為減少迭代次數(shù) k ，通常規(guī)定一個精度判據(jù) 0 = 103 105 ，要求五、外點(diǎn)法的計(jì)算步驟1 選擇初始點(diǎn) X(0) ，懲罰因子 r(0) 、遞增系數(shù) 、1、2、0、k = 02 構(gòu)造懲罰函數(shù)3 調(diào)用無約束優(yōu)化方法，求解無約束優(yōu)化問題 得到 X*(r(k) ) ；4 計(jì)算 X*(r(k) ) 違反約束條件的情況：5 判別 Q 0

5、?i. 是，輸出 X* = X*(r(k) ) 及 f (X*) ，結(jié)束；ii. 否，6 判斷收斂條件 及i. 否，ii. 是，輸出 X* = X*(r(k) ) 及 f (X*) ，結(jié)束。7 五、外點(diǎn)法的計(jì)算步驟例: 用外點(diǎn)法求解下列有約束優(yōu)化問題解: 懲罰函數(shù)為：用解析法求函數(shù)的極小值，運(yùn)用極值條件：注意：應(yīng)舍去在可行域的點(diǎn)。則無約束極值點(diǎn)為當(dāng)懲罰因子漸增時，由下表可看出收斂情況。六、外點(diǎn)法的優(yōu)缺點(diǎn)1 優(yōu)點(diǎn)：i. 外點(diǎn)法可用于含有等式約束的約束優(yōu)化問題；ii. 初始點(diǎn) X(0) 可以是可行點(diǎn)，也可以是非可行點(diǎn)。2 缺點(diǎn)： 外點(diǎn)法求得的最優(yōu)點(diǎn)，通常不是嚴(yán)格的可行點(diǎn)。 六、外點(diǎn)法的優(yōu)缺點(diǎn)為了獲

6、得嚴(yán)格的可行點(diǎn)，可以定義新的約束條件混合懲罰函數(shù)法內(nèi)點(diǎn)法：適于處理不等式約束優(yōu)化設(shè)計(jì)問題；外點(diǎn)法：適于處理等式約束優(yōu)化設(shè)計(jì)問題?；旌蠎土P函數(shù)法：可以處理同時含有不等式約束和等式約束的優(yōu)化設(shè)計(jì)問題。對于約束優(yōu)化問題：混合懲罰函數(shù)法構(gòu)造懲罰函數(shù)：混合懲罰函數(shù)法式(2) 對不等式約束采用的是內(nèi)點(diǎn)法，對等式約束采用的是外點(diǎn)法。另一種方法則統(tǒng)一采用外點(diǎn)法：隨機(jī)方向搜索法一、概述二、基本原理三、產(chǎn)生隨機(jī)方向的方法四、初始點(diǎn)的選擇五、隨機(jī)方向搜索法的計(jì)算步驟一、概述 在可行域內(nèi)選擇一個初始點(diǎn)； 確定第一次的搜索方向：在若干個不同的方向試探性搜索，使得函數(shù)值下降； 取適當(dāng)步長因子，在不破壞約束條件的情況下，向

7、前前進(jìn)一步得到一個新點(diǎn)： 若新點(diǎn)處函數(shù)值下降，將起始點(diǎn)移至新點(diǎn)，重復(fù)前面步驟； 否則縮小步長因子直到找到一個好的可行點(diǎn)。 重復(fù)以上步驟，直到迭代步長小于設(shè)置誤差。二、基本原理 對于約束優(yōu)化問題1. 在可行域 D 內(nèi)選擇初始點(diǎn) X (0)2. 隨機(jī)地產(chǎn)生 N 個方向 e(j) ，j = 1，2，N3. 找到 N 個點(diǎn) 4. 從上述 N 個點(diǎn)中找出滿足約束條件的可行點(diǎn) X(j) ，j = 1，2，Ns N 計(jì)算 f (X(j) )，j = 1，2，Ns 找出YL = min f (X(j) )，j = 1，2，Ns 二、基本原理可行域隨機(jī)方向二、基本原理5. 比較 YL 、 f (X(0) ) 若

8、 YL = f (X(0) ) ，則二、基本原理三、產(chǎn)生隨機(jī)方向的方法2、在 n 維設(shè)計(jì)空間中 i. 在 -1 ，1 區(qū)間內(nèi)，產(chǎn)生 n N 個均勻分布的偽隨機(jī)數(shù) ii. 計(jì)算四、初始點(diǎn)的選擇1、決定性方法 在可行域內(nèi)，確定一個可行的初始點(diǎn) X(0) ： 用傳統(tǒng)的設(shè)計(jì)方法，設(shè)計(jì)一個可行的設(shè)計(jì)方案，作為初始點(diǎn)。 適用于約束條件比較簡單的優(yōu)化問題。2、隨機(jī)選擇法i. 利用 n 個在 -1 ，1 內(nèi)均勻分布的偽隨機(jī)數(shù) 和區(qū)域約束產(chǎn)生初始點(diǎn) X(0)，ii. 檢驗(yàn) X(0) ： 否，重選； 是，選到。五、隨機(jī)方向搜索法的計(jì)算步驟1. 給定初始步長 、計(jì)算精度 、M 0、N 02. 選擇初始點(diǎn)3. 檢驗(yàn)初

9、始點(diǎn) 可行性：是， 否，4. 隨機(jī)選取新的初始點(diǎn)5. 計(jì)算 產(chǎn)生隨機(jī)方向 , 6. j = 1(對所有N個隨機(jī)方向進(jìn)行循環(huán))7. 產(chǎn)生點(diǎn) 檢驗(yàn) 的可行性：否，是，8. 計(jì)算9. 若 j N， 否則五、隨機(jī)方向搜索法的計(jì)算步驟9. 選擇 YL = f ( XL ) = min Y(j) ，j = 1，2，Ns Y0 = YL 10. 判斷Y0 Y00 ?i. 否，ii. 是，11. 確定 S = XL X (0) ，H = 1.3 H0 12. 計(jì)算 X = X (0) + H S 檢驗(yàn)i. 是，ii. 否，13. 判斷 YL = n + 1 個頂點(diǎn)構(gòu)成的多面體，一般 k = 2n 。復(fù)合形的形

10、狀不受限制，可以變形，靈活得多；復(fù)合形法的收斂速度慢；復(fù)合形法對維數(shù)不高、約束條件不多，目標(biāo)函數(shù)、約束函數(shù)很復(fù)雜，且精度要求不高的優(yōu)化問題，有優(yōu)越性。 二、復(fù)合形法的基本原理 對約束優(yōu)化問題1 確定初始復(fù)合形 選擇 k = n + 2 個頂點(diǎn)，通常 k = 2n ，這 k 個頂點(diǎn)必須是可行點(diǎn)。2 確定搜索方向i. 計(jì)算 k 個頂點(diǎn)的函數(shù)值，設(shè) 記 最壞點(diǎn) X (1) 為 X (H) 次壞點(diǎn) X (2) 為 X (G) 最好點(diǎn) X (k) 為 X (L) 二、復(fù)合形法的基本原理ii. 求出 X (2)、 X (3)、 X (k-1)、 X (k) 的點(diǎn)集的中心(幾何中心)X (S) iii. 以

11、 X (H) 指向 X (S) 的方向作為尋優(yōu)的方向，沿此方向?qū)ふ乙粋€較好的點(diǎn) X (R) 。二、復(fù)合形法的基本原理二、復(fù)合形法的基本原理4 變形i. 擴(kuò)張:若f ( X (R) 1 ； 則擴(kuò)張成功，以 X (E) 代替 X (H) ，構(gòu)成新的復(fù)合形；否則，仍以 X (R) 代替 X (H) 。ii. 收縮:若在 X (S) 以外找不到好的映射點(diǎn)，則向 X (S) 以內(nèi)收縮，即 式中， 為收縮系數(shù)，0 1 ； 則以 X (K) 代替 X (H) ； 否則，仍以 X (R) 代替 X (H) 。二、復(fù)合形法的基本原理若上述措施無效，則向最好點(diǎn) X (L) 靠攏： 然后，再重新尋找新頂點(diǎn)。三、初始

12、復(fù)合形的構(gòu)成1 給定 k 個初始頂點(diǎn) 即選擇 k 個可行的設(shè)計(jì)方案，適用于設(shè)計(jì)變量不多、約束函數(shù)不太復(fù)雜的優(yōu)化問題。2 給定一個初始頂點(diǎn)，隨機(jī)產(chǎn)生其它頂點(diǎn) 按傳統(tǒng)的設(shè)計(jì)方法設(shè)計(jì)一個可行的設(shè)計(jì)方案，作為一個頂點(diǎn)，其它 k-1個頂點(diǎn)用隨機(jī)方法產(chǎn)生：式中 為第 i 個設(shè)計(jì)變量的上、下限； 為 0 ，1 中服從均勻分布的隨機(jī)數(shù)。 滿足區(qū)域約束，但不一定滿足性能約束，故必須檢驗(yàn)其可行性，若 不在可行域內(nèi)，可把它移到可行域內(nèi)。三、初始復(fù)合形的構(gòu)成設(shè) 則 通常取3 隨機(jī)產(chǎn)生所有( k 個) 頂點(diǎn) 四、復(fù)合形法的計(jì)算步驟1 給定復(fù)合形的頂點(diǎn)數(shù) k ，收斂精度 ，= 10-52 產(chǎn)生 k 個頂點(diǎn) X(i) ，i

13、=1，2，k ，檢驗(yàn) 若 ，重新產(chǎn)生 X(i) 3 計(jì)算中心點(diǎn) X(C) 4 計(jì)算復(fù)合形頂點(diǎn) X(i) ，i=1，2，k 及中心點(diǎn) X(C) 的函數(shù)值5 比較 f ( X(i) ) ，i=1，2，k ，選出6 判別 或四、復(fù)合形法的計(jì)算步驟是，輸出 X* = X(L) ，f (X*) = f (X(L) )，結(jié)束否，7 計(jì)算除最壞點(diǎn)以外的 k-1 個頂點(diǎn)的幾何中心點(diǎn) 檢驗(yàn)i. 是，ii. 否，利用 X(S) 和 X(L) 確定一個區(qū)間，在此區(qū)間內(nèi)重新產(chǎn)生 k-1 個頂點(diǎn)，與 X(L) 一起構(gòu)成新的復(fù)合形：若 否則，取產(chǎn)生新頂點(diǎn)檢驗(yàn)否，重新產(chǎn)生。四、復(fù)合形法的計(jì)算步驟8 找映射點(diǎn) 檢驗(yàn) 否， 是

14、，計(jì)算 X(R) 比較 f (X(R) ) f (X(H) ) ? 否， 是，以 X(R) 代替 X(H) ，構(gòu)成新的復(fù)合形，9 取 若 ，則以 X(G) 代替 X(H) ， 否則，四、復(fù)合形法的計(jì)算步驟四、復(fù)合形法的計(jì)算步驟構(gòu)造初始復(fù)合形構(gòu)造新的映射點(diǎn)用新映射點(diǎn)代替最壞點(diǎn)可行方向法一、概述二、可行方向法的搜索路線三、產(chǎn)生可行下降方向的方法四、步長的確定五、確定調(diào)整步長六、可行方向法的終止準(zhǔn)則七、可行方向法的算法步驟（從一個約束面到另一個約束面）一、概述 可行方向法是一種求解有約束、非線性最優(yōu)化問題的直接搜索法，也是求解大型約束優(yōu)化問題的主要方法之一?？尚蟹较蚍ǖ幕舅枷耄?在可行域內(nèi)，沿著可

15、行下降方向，尋找目標(biāo)函數(shù)的極小點(diǎn)?？尚蟹较蚍▽ふ壹s束優(yōu)化問題最優(yōu)解的基本要求：（1）沿著可行下降方向?qū)?yōu)，而且希望沿著目標(biāo)函數(shù)值下降最快的可行方向?qū)?yōu)；（2）沿著可行下降方向作一維搜索時，希望以較大的步幅前進(jìn)，同時要求：不越過極小點(diǎn)不越出可行域邊界 二、可行方向法的搜索路線 可行方向法的尋優(yōu)路線：（1）從可行域內(nèi)的一個初始點(diǎn) X(0) 出發(fā)，沿 方向搜索，到達(dá)可行域邊界上的一點(diǎn) X(k) ；()kX二、可行方向法的搜索路線（2）此后的搜索路線可分為三種類型：I. 從邊界點(diǎn) X(k) 出發(fā)，沿可行下降方向 S(k) 作一維優(yōu)化搜索到達(dá) X(k+1) ：a X(k+1) 在可行域內(nèi) ，尋優(yōu)結(jié)束；

16、，沿 方向作一維優(yōu)化搜索；b X(k+1) 不在可行域內(nèi)，把 X(k+1) 調(diào)整到約束面上若 X(k+1) 滿足 K-T 條件，尋優(yōu)結(jié)束；否則，重復(fù) I 步驟 ；二、可行方向法的搜索路線二、可行方向法的搜索路線II. 從邊界點(diǎn) X(k) 出發(fā)，沿可行下降方向，以最大步長從一個約束面移到另一個約束面，如此反復(fù)進(jìn)行，直至滿足 K-T 條件；二、可行方向法的搜索路線III. 從邊界點(diǎn) X(k) 出發(fā)，沿著約束面進(jìn)行搜索，直至滿足 K-T 條件。三、產(chǎn)生可行下降方向的方法I. X(k) 是可行域的內(nèi)點(diǎn) 從 X(k) 點(diǎn)出發(fā)，沿 方向搜索。II. X(k) 是一個邊界點(diǎn)，有適時約束 從 X(k) 點(diǎn)出發(fā)

17、，沿可行下降方向 S 搜索，S 應(yīng)滿足： （1） 確定可行下降方向 S 的三種方法：1)、 隨機(jī)法i. 在 X(k) 點(diǎn)產(chǎn)生 N 個隨機(jī)搜索方向 S(j) ，j = 1，2，lii. 按式(1) 對此 N 個方向逐個進(jìn)行檢驗(yàn)，滿足式(1) 的方向 S(j) 取為可行下降方向；iii. 若共有 q 個可行下降方向，則取 S(j) 為搜索方向 三、產(chǎn)生可行下降方向的方法2)、 線性規(guī)劃法 此方法適用與只有不等式約束和線性等式約束的優(yōu)化問題（不能用于含有非線性的等式約束的優(yōu)化問題）。 線性規(guī)劃法的基本原理對于約束優(yōu)化問題 把 f (X) 在 X(k) 點(diǎn)附近用泰勒公式展開成近似的線性函數(shù)，即 原問題

18、轉(zhuǎn)化為： 三、產(chǎn)生可行下降方向的方法 若上式可改為 還應(yīng)滿足式即： 所以，尋找 X(k) 點(diǎn)的可行下降方向 S(k) 的問題歸結(jié)為i. 線性約束的非線性優(yōu)化問題 設(shè)約束函數(shù)為三、產(chǎn)生可行下降方向的方法三、產(chǎn)生可行下降方向的方法 由式(3) 可得：三、產(chǎn)生可行下降方向的方法則優(yōu)化問題的數(shù)學(xué)模型可寫成三、產(chǎn)生可行下降方向的方法 設(shè)在 X(k) 點(diǎn)有適時約束 gj (X(k) ，j = 1，2，l ，記 顯然有三、產(chǎn)生可行下降方向的方法三、產(chǎn)生可行下降方向的方法三、產(chǎn)生可行下降方向的方法 于是，式(2) 描述的具有線性約束的優(yōu)化問題，在 X(k) 點(diǎn)尋找可行下降方向 S(k) 的問題，歸結(jié)為下述線性

19、規(guī)劃問題： ii. 非線性不等式約束的優(yōu)化問題 非線性不等式約束的優(yōu)化問題 設(shè)在 X(k) 點(diǎn)有適時約束gj (X(k) ，j = 1，2，l 則 X(k) 點(diǎn)的可行下降方向 S 應(yīng)滿足令三、產(chǎn)生可行下降方向的方法 于是，在 X(k) 點(diǎn)尋找可行下降方向 S(k) 的問題，歸結(jié)為線性規(guī)劃問題： 對于式(6) ，S = 0 總是一個可行解，所以 min Z(S) 0 若 min Z(S) = 0 ，則 X(k) 點(diǎn)已經(jīng)是滿足 Kuhn-Tucker 條件的一個極小點(diǎn)；若 min Z(S) 0 此時，需要把 X(t) 退回到約束面上；iii. X(t) 點(diǎn)在可行域內(nèi)，則 X(t) 點(diǎn)滿足 gu(X(t) 0 ，(u = 1，2，m)以試驗(yàn)步長 at沿 S(k) 方向再前進(jìn)一步；從 X(t) 點(diǎn)出發(fā)，沿 方向搜索。 直至 X(t) 點(diǎn)越出可行域，再把它調(diào)整到約束面上。四、步長的確定 最大步長只能通過試探求得。 為了減少試探次數(shù)，一般可給約束面規(guī)定一個適當(dāng)?shù)娜莶顜?(0.0010.01) 當(dāng)新點(diǎn)進(jìn)入規(guī)定的容差帶 之內(nèi)，即可認(rèn)為已到達(dá)了約束面。 五、確定調(diào)整步長 當(dāng)新點(diǎn) X(k+1) 越過可行域邊界，進(jìn)入非可行域，則必須把它調(diào)整到約束容差帶內(nèi).1. 試探法五、確定調(diào)整步長