優(yōu)化理論與最優(yōu)控制

1、優(yōu)化理論與最優(yōu)控制優(yōu)化理論與最優(yōu)控制“優(yōu)化優(yōu)化”與與“最優(yōu)化最優(yōu)化” 優(yōu)化優(yōu)化 “化化”加在名詞或形容詞后構(gòu)成動詞加在名詞或形容詞后構(gòu)成動詞, ,表示表示轉(zhuǎn)變成某種性質(zhì)或狀態(tài)。比如：綠轉(zhuǎn)變成某種性質(zhì)或狀態(tài)。比如：綠化、美化、丑化，自動化，優(yōu)化化、美化、丑化，自動化，優(yōu)化 最最優(yōu)化（值）優(yōu)化（值） 指在指在一定條件影響下一定條件影響下所能得到的最佳值。它所能得到的最佳值。它是一個(gè)相對的概念；不同于數(shù)學(xué)上的極值，是一個(gè)相對的概念；不同于數(shù)學(xué)上的極值，但在很多情況下可以用但在很多情況下可以用最大值最大值或或最小值最小值來表來表示。示。最優(yōu)化問題的控制方程最優(yōu)化問題的控制方程 調(diào)整（設(shè)計(jì)、策略、決策）

2、變量調(diào)整（設(shè)計(jì)、策略、決策）變量 設(shè)計(jì)變量的數(shù)目稱為最優(yōu)化設(shè)計(jì)的維數(shù)。設(shè)計(jì)變量的數(shù)目稱為最優(yōu)化設(shè)計(jì)的維數(shù)。 目標(biāo)函數(shù)目標(biāo)函數(shù) 在最優(yōu)化設(shè)計(jì)中，可將所追求的設(shè)計(jì)目標(biāo)（最優(yōu)在最優(yōu)化設(shè)計(jì)中，可將所追求的設(shè)計(jì)目標(biāo)（最優(yōu)指標(biāo)）用設(shè)計(jì)變量的函數(shù)（解析或隱含）形式表指標(biāo)）用設(shè)計(jì)變量的函數(shù)（解析或隱含）形式表達(dá)出來，這一過程稱為建立目標(biāo)函數(shù)。達(dá)出來，這一過程稱為建立目標(biāo)函數(shù)。 約束條件約束條件 在很多實(shí)際問題中，設(shè)計(jì)變量的取值范圍是有限在很多實(shí)際問題中，設(shè)計(jì)變量的取值范圍是有限制的或必須滿足一定的條件。以及其他方面的限制的或必須滿足一定的條件。以及其他方面的限制。制。最優(yōu)化問題的控制方程為：最優(yōu)化問題的控制方

3、程為：最優(yōu)化問題的數(shù)學(xué)模型調(diào)整參數(shù)：調(diào)整參數(shù)：目標(biāo)函數(shù)目標(biāo)函數(shù):約束條件：約束條件：X=x1 x2 x3 xnT, X Dymin或 ymax= f(X)hv(X)=0, v=1,2,pgu(X) 0, u=1,2,m幾點(diǎn)說明 調(diào)整（決策、策略）變量調(diào)整（決策、策略）變量 原則應(yīng)選擇對目標(biāo)函數(shù)影響大且獨(dú)立的變量；通常情況原則應(yīng)選擇對目標(biāo)函數(shù)影響大且獨(dú)立的變量；通常情況下，調(diào)整變量越多，優(yōu)化潛力越大，但優(yōu)化過程也越復(fù)雜。下，調(diào)整變量越多，優(yōu)化潛力越大，但優(yōu)化過程也越復(fù)雜。 目標(biāo)函數(shù)目標(biāo)函數(shù) 單目標(biāo)函數(shù)：只有一個(gè)目標(biāo)函數(shù)；單目標(biāo)函數(shù)：只有一個(gè)目標(biāo)函數(shù)； 多目標(biāo)函數(shù)：有多個(gè)目標(biāo)函數(shù)。多目標(biāo)函數(shù)：有多

4、個(gè)目標(biāo)函數(shù)。 約束條件約束條件 顯約束顯約束vs 隱約束隱約束、等式約束等式約束vs不等式約束不等式約束和和邊界約束邊界約束vs 性態(tài)約束性態(tài)約束。 控制方程的解控制方程的解 調(diào)整（設(shè)計(jì)、策略、決策）變量組合調(diào)整（設(shè)計(jì)、策略、決策）變量組合 vs 目標(biāo)函數(shù)；目標(biāo)函數(shù)； 最優(yōu)值的相對性與動態(tài)性等。最優(yōu)值的相對性與動態(tài)性等。約束條件約束條件 目標(biāo)函數(shù)取決于調(diào)整變量目標(biāo)函數(shù)取決于調(diào)整變量, ,而在工程實(shí)際問而在工程實(shí)際問題中調(diào)整變量的取值范圍是有限制的或必題中調(diào)整變量的取值范圍是有限制的或必須滿足一定的條件。須滿足一定的條件。 等式約束：對調(diào)整變量的約束嚴(yán)格，起著降等式約束：對調(diào)整變量的約束嚴(yán)格，起

5、著降低設(shè)計(jì)自由度的作用。低設(shè)計(jì)自由度的作用。 不等式約束不等式約束 邊界約束（顯約束）：對調(diào)整變量的直接限制約束的形式隱約束（性能約束）：對調(diào)整變量的間接限制分類分類p 線性規(guī)劃線性規(guī)劃：若若 都是調(diào)整變量都是調(diào)整變量 X的線性函數(shù)的線性函數(shù) ；(X),(X)(X)vufhg和p非線性規(guī)劃非線性規(guī)劃：若它們不全是調(diào)整變量若它們不全是調(diào)整變量X的線的線 性函數(shù)；性函數(shù)；0,0(1,2, ;1,2,)pmvp ump無約束規(guī)劃無約束規(guī)劃： 若若 。 參考書目參考書目劉惟信，劉惟信，機(jī)械最優(yōu)化設(shè)計(jì)機(jī)械最優(yōu)化設(shè)計(jì)，清華大學(xué)出版，清華大學(xué)出版社，社，1994年年9月，第月，第2版。版。p常規(guī)控制回路的優(yōu)

6、化調(diào)整：參數(shù)整定常規(guī)控制回路的優(yōu)化調(diào)整：參數(shù)整定320( , ,)xaxbxca b cRp方程求解方程求解： 思考題思考題p人工神經(jīng)元網(wǎng)絡(luò)的學(xué)習(xí)算法人工神經(jīng)元網(wǎng)絡(luò)的學(xué)習(xí)算法p 工業(yè)過程的優(yōu)化調(diào)整，比如電站鍋爐的燃燒工業(yè)過程的優(yōu)化調(diào)整，比如電站鍋爐的燃燒優(yōu)化優(yōu)化舉例說明（舉例說明（） 小朋友算數(shù)小朋友算數(shù) 1) 2堆蘋果，每堆有堆蘋果，每堆有3個(gè)，問個(gè)，問2堆加起來一堆加起來一 共有幾個(gè)蘋果？若有共有幾個(gè)蘋果？若有3堆，堆，1000堆這樣堆這樣 的蘋果呢？的蘋果呢？ 2）9個(gè)蘋果，個(gè)蘋果，3個(gè)小朋友分，問每人分幾個(gè)個(gè)小朋友分，問每人分幾個(gè) 蘋果？若有蘋果？若有18個(gè)，個(gè)，3000個(gè)蘋果呢？個(gè)蘋

7、果呢？觀察到什么現(xiàn)象？觀察到什么現(xiàn)象？發(fā)現(xiàn)什么問題？發(fā)現(xiàn)什么問題？得到什么結(jié)論？得到什么結(jié)論？舉例說明（舉例說明（） 一簡單的僅有兩個(gè)輸入變量一簡單的僅有兩個(gè)輸入變量x1、x2，一個(gè)輸出，一個(gè)輸出變量變量 y 的工業(yè)過程，即的工業(yè)過程，即 。在工程中，在工程中，輸入變量即運(yùn)行（工藝）參數(shù)輸入變量即運(yùn)行（工藝）參數(shù)x1、x2一般都有一般都有一定的取值范圍一定的取值范圍。不妨設(shè)其允許取值范圍分不妨設(shè)其允許取值范圍分別為別為a,b、c,d。那么，圖中藍(lán)色方框中所有那么，圖中藍(lán)色方框中所有的的x1、x2組合都能滿足系統(tǒng)正常運(yùn)行的要求。組合都能滿足系統(tǒng)正常運(yùn)行的要求。12( ,)yf x x 簡單的工業(yè)

8、問題簡單的工業(yè)問題舉例說明（舉例說明（）請問在這無窮多個(gè)組合中，哪個(gè)組合請問在這無窮多個(gè)組合中，哪個(gè)組合y能能取得最大值或最小值呢？取得最大值或最小值呢？1234567891011 1312x1x2ab cd無約束目標(biāo)函數(shù)的極值點(diǎn)存在條件無約束目標(biāo)函數(shù)的極值點(diǎn)存在條件1 一元函數(shù)一元函數(shù) 任何一個(gè)單值、連續(xù)、可微分的不受任何約任何一個(gè)單值、連續(xù)、可微分的不受任何約束的一元函數(shù)束的一元函數(shù) 點(diǎn)處有極值的點(diǎn)處有極值的充分必要條件是：充分必要條件是： 0( )yf xxx在000()0;()0fxfx極小值極大值2 二元函數(shù)二元函數(shù) 若二元函數(shù)若二元函數(shù) 點(diǎn)的某個(gè)領(lǐng)域內(nèi)有點(diǎn)的某個(gè)領(lǐng)域內(nèi)有連續(xù)二階偏導(dǎo)

9、數(shù)，則在該點(diǎn)存在極值的充連續(xù)二階偏導(dǎo)數(shù)，則在該點(diǎn)存在極值的充分必要條件是：分必要條件是：00( , ),)zf x yP x y0在 (000000(,)0(,)0( , )( , )0( , )( , )xyxyxxx xyyyxy yfxyfxyfx yfx yfx yfx y00000000(,)0,)(,)0,)xxxxfxyP xyfxyP xy00時(shí)， (為極大點(diǎn)時(shí)， (為極小點(diǎn)且3 多元函數(shù)多元函數(shù) n元函數(shù)元函數(shù) 在點(diǎn)在點(diǎn)M處存在極值處存在極值的充分必要條件是：的充分必要條件是：12(X)(,)nff x xx(M)(M)(M)(M)12(X)(X)(X)(X)0000nfff

10、fxxx在點(diǎn)在點(diǎn)M處函數(shù)的梯度為零向量：處函數(shù)的梯度為零向量：Hessian矩陣為正定或負(fù)定：矩陣為正定或負(fù)定：2(M)(M)M2(M)2(M)2(M)211212(M)2(M)2(M)221222(M)2(M)2(M)212(X)H(X)H(X)(X)(X)(X)(X)(X)(X)(X)(X)nnnnnffffxx xx xfffx xxx xfffxxxxx MMMHMHMHM為正定時(shí)，為極小點(diǎn)；為負(fù)定時(shí)，為極大點(diǎn)；既非正定也非負(fù)定時(shí)，為鞍點(diǎn)。且當(dāng)且當(dāng)最優(yōu)化問題求解的數(shù)值計(jì)算方法最優(yōu)化問題求解的數(shù)值計(jì)算方法1 解析法解析法間接尋優(yōu)方法 利用數(shù)學(xué)分析的方法利用數(shù)學(xué)分析的方法, ,根據(jù)目標(biāo)函數(shù)

11、的變化規(guī)根據(jù)目標(biāo)函數(shù)的變化規(guī)律與函數(shù)極值的關(guān)系律與函數(shù)極值的關(guān)系, ,求目標(biāo)函數(shù)的極值點(diǎn)求目標(biāo)函數(shù)的極值點(diǎn). . 尋找極值點(diǎn)尋找極值點(diǎn) 需要求解由目標(biāo)函數(shù)的偏導(dǎo)數(shù)需要求解由目標(biāo)函數(shù)的偏導(dǎo)數(shù)所組成的方程組或梯度所組成的方程組或梯度 。(X)0f然后用然后用Hessian矩陣對所找到的穩(wěn)定點(diǎn)進(jìn)行矩陣對所找到的穩(wěn)定點(diǎn)進(jìn)行判斷，看它是否是最優(yōu)點(diǎn)。判斷，看它是否是最優(yōu)點(diǎn)。當(dāng)目標(biāo)函數(shù)比較簡單時(shí)，求解上述方程組且當(dāng)目標(biāo)函數(shù)比較簡單時(shí)，求解上述方程組且用用Hessian矩陣進(jìn)行判斷并不困難。但當(dāng)目矩陣進(jìn)行判斷并不困難。但當(dāng)目標(biāo)函數(shù)比較復(fù)雜時(shí)，就會遇到麻煩，甚至很標(biāo)函數(shù)比較復(fù)雜時(shí)，就會遇到麻煩，甚至很難求解各項(xiàng)

12、偏導(dǎo)數(shù)所組成的方程組，更不用難求解各項(xiàng)偏導(dǎo)數(shù)所組成的方程組，更不用說對說對Hessian矩陣進(jìn)行判斷時(shí)將遇到的困難。矩陣進(jìn)行判斷時(shí)將遇到的困難。p 此外，對目標(biāo)函數(shù)還有連續(xù)、可微分等大此外，對目標(biāo)函數(shù)還有連續(xù)、可微分等大前提條件前提條件數(shù)值計(jì)算方法數(shù)值計(jì)算方法直接尋優(yōu)方法直接尋優(yōu)方法 它是根據(jù)目標(biāo)函數(shù)的變化規(guī)律，以適當(dāng)?shù)牟剿歉鶕?jù)目標(biāo)函數(shù)的變化規(guī)律，以適當(dāng)?shù)牟介L沿著能使目標(biāo)函數(shù)值下降的方向，逐步長沿著能使目標(biāo)函數(shù)值下降的方向，逐步向目標(biāo)函數(shù)值的最優(yōu)點(diǎn)進(jìn)行探索，逐步逼向目標(biāo)函數(shù)值的最優(yōu)點(diǎn)進(jìn)行探索，逐步逼近到目標(biāo)函數(shù)的最優(yōu)點(diǎn)。近到目標(biāo)函數(shù)的最優(yōu)點(diǎn)。 步驟：步驟：(0)X初選一個(gè)可能靠近最優(yōu)點(diǎn)的初始

13、初選一個(gè)可能靠近最優(yōu)點(diǎn)的初始點(diǎn)點(diǎn) ，從，從 出發(fā)按照一定的原則尋找可行方向和出發(fā)按照一定的原則尋找可行方向和初始步長，向前跨出一步達(dá)到初始步長，向前跨出一步達(dá)到 點(diǎn)；點(diǎn)；(0)X(1)X(1)X得到新點(diǎn)得到新點(diǎn) 后再選擇一個(gè)新的使函數(shù)值迅速后再選擇一個(gè)新的使函數(shù)值迅速下降的方向及適當(dāng)?shù)牟介L，從下降的方向及適當(dāng)?shù)牟介L，從 點(diǎn)出發(fā)再點(diǎn)出發(fā)再跨出一步，達(dá)到跨出一步，達(dá)到 點(diǎn)。依此類推，一步一步點(diǎn)。依此類推，一步一步地向前探索并重復(fù)數(shù)值計(jì)算，最終逼近目標(biāo)地向前探索并重復(fù)數(shù)值計(jì)算，最終逼近目標(biāo)函數(shù)的最優(yōu)點(diǎn)。函數(shù)的最優(yōu)點(diǎn)。(2)X(1)X 中間過程中每一步的迭代形式為：中間過程中每一步的迭代形式為： 式式

14、中：中：(1)( )( )( )(1)( )XXS(X)(X)0,1,2,kkkkkkffk使 - -第第k 步迭代計(jì)算所得到的點(diǎn)；步迭代計(jì)算所得到的點(diǎn)；( )Xk - -第第k 步迭代計(jì)算的步長；步迭代計(jì)算的步長；( )k - -第第k 步迭代計(jì)算的探索方向。步迭代計(jì)算的探索方向。( )Sk以最小以最小值為例值為例每向前跨完一步，都應(yīng)檢查所得到的新點(diǎn)每向前跨完一步，都應(yīng)檢查所得到的新點(diǎn)能否滿足預(yù)定的計(jì)算精度，即能否滿足預(yù)定的計(jì)算精度，即(1)( )(X)- (X)kkff(1)Xk 如滿足，則認(rèn)為如滿足，則認(rèn)為 為局部最小點(diǎn)；為局部最小點(diǎn)；(1)Xk 否則，應(yīng)以否則，應(yīng)以 為新的初始點(diǎn)，按上

15、述方法為新的初始點(diǎn)，按上述方法繼續(xù)跨步探索。繼續(xù)跨步探索。根本目的在于設(shè)根本目的在于設(shè)置迭代終止判據(jù)置迭代終止判據(jù)幾點(diǎn)討論 迭代過程中探索方向迭代過程中探索方向S的選擇的選擇 保證沿此方向進(jìn)行探索時(shí)，目標(biāo)函數(shù)值是不斷下保證沿此方向進(jìn)行探索時(shí)，目標(biāo)函數(shù)值是不斷下 降的；降的； 應(yīng)盡可能地使其指向最優(yōu)點(diǎn)，以縮短探索的路程應(yīng)盡可能地使其指向最優(yōu)點(diǎn)，以縮短探索的路程 和時(shí)間，提高求優(yōu)過程的效率。和時(shí)間，提高求優(yōu)過程的效率。 迭代的收斂性迭代的收斂性否則，迭代是發(fā)散的。否則，迭代是發(fā)散的。 根據(jù)任意一個(gè)迭代式進(jìn)行計(jì)算，不一定都能得到逼根據(jù)任意一個(gè)迭代式進(jìn)行計(jì)算，不一定都能得到逼近精確解的近似解。近精確解

16、的近似解。( ),1,2,kixin( )*lim,(1,2, )kiikxxin如果能夠計(jì)算出逼近精確解的近似解，即近似解如果能夠計(jì)算出逼近精確解的近似解，即近似解序列序列 有極限有極限 ，則迭代是收斂的。，則迭代是收斂的。 對于實(shí)際工程問題有時(shí)很難判斷其目標(biāo)函數(shù)對于實(shí)際工程問題有時(shí)很難判斷其目標(biāo)函數(shù)的最小值，而只能根據(jù)計(jì)算中的具體情況的最小值，而只能根據(jù)計(jì)算中的具體情況來進(jìn)行判斷。來進(jìn)行判斷。依迭代過程真實(shí)逼近最優(yōu)點(diǎn)所呈現(xiàn)的特征來依迭代過程真實(shí)逼近最優(yōu)點(diǎn)所呈現(xiàn)的特征來構(gòu)建判據(jù)構(gòu)建判據(jù) 判斷是否應(yīng)終止迭代的依據(jù)有三種形式判斷是否應(yīng)終止迭代的依據(jù)有三種形式 當(dāng)調(diào)整變量在相鄰兩點(diǎn)之間的移動距離已

17、當(dāng)調(diào)整變量在相鄰兩點(diǎn)之間的移動距離已 充分小時(shí)，可用相鄰兩點(diǎn)的向量差的模作為充分小時(shí)，可用相鄰兩點(diǎn)的向量差的模作為終止迭代的判據(jù)：終止迭代的判據(jù)：(1)( )1X-Xkk終止迭代的判斷依據(jù)終止迭代的判斷依據(jù) 或用向量或用向量 的所有坐標(biāo)分量之差表示：的所有坐標(biāo)分量之差表示：(1)( )X,Xkk(1)( )-,(1,2, )kkiiixxin 當(dāng)相鄰兩點(diǎn)目標(biāo)函數(shù)值之差已達(dá)充分小時(shí)，當(dāng)相鄰兩點(diǎn)目標(biāo)函數(shù)值之差已達(dá)充分小時(shí)，即移動該步后目標(biāo)函數(shù)值的下降量已充分小即移動該步后目標(biāo)函數(shù)值的下降量已充分小時(shí)，可用兩次迭代的目標(biāo)函數(shù)值之差作為終時(shí)，可用兩次迭代的目標(biāo)函數(shù)值之差作為終止迭代的判據(jù)：止迭代的判據(jù)

18、：(1)( )2(X)- (X)kkff 上述上述3種任何一種得到滿足，則認(rèn)為目標(biāo)函數(shù)種任何一種得到滿足，則認(rèn)為目標(biāo)函數(shù)值已收斂于該函數(shù)的最優(yōu)值。值已收斂于該函數(shù)的最優(yōu)值。 當(dāng)?shù)c(diǎn)逼近極值點(diǎn)時(shí)，目標(biāo)函數(shù)在該點(diǎn)當(dāng)?shù)c(diǎn)逼近極值點(diǎn)時(shí)，目標(biāo)函數(shù)在該點(diǎn)的梯度將變得充分小，故目標(biāo)函數(shù)在迭代點(diǎn)的梯度將變得充分小，故目標(biāo)函數(shù)在迭代點(diǎn)處的梯度達(dá)到充分小時(shí)，也可作為終止迭代處的梯度達(dá)到充分小時(shí)，也可作為終止迭代的判據(jù)：的判據(jù)：(1)3(X)kf？幾點(diǎn)討論 （2種特殊情況種特殊情況） 函數(shù)變化劇烈函數(shù)變化劇烈 函數(shù)變化緩慢函數(shù)變化緩慢(1)Xk*X 為了防止當(dāng)函數(shù)變化緩慢時(shí)，判據(jù)雖已得到滿為了防止當(dāng)函數(shù)變化緩慢

19、時(shí)，判據(jù)雖已得到滿足，而所求得的最優(yōu)點(diǎn)足，而所求得的最優(yōu)點(diǎn) 與真正最優(yōu)點(diǎn)與真正最優(yōu)點(diǎn) 仍仍相距較遠(yuǎn)，往往將判據(jù)、結(jié)合起來使用。相距較遠(yuǎn)，往往將判據(jù)、結(jié)合起來使用。 (1)(X)kf*(X )f 為了防止當(dāng)函數(shù)變化劇烈時(shí)，判據(jù)雖已得到滿為了防止當(dāng)函數(shù)變化劇烈時(shí)，判據(jù)雖已得到滿足，而所求得的最優(yōu)值足，而所求得的最優(yōu)值 與真正最優(yōu)值與真正最優(yōu)值 仍相差較大；仍相差較大；無約束最優(yōu)化方法的特點(diǎn)及應(yīng)用范圍無約束最優(yōu)化方法的特點(diǎn)及應(yīng)用范圍最優(yōu)化方法特點(diǎn)及應(yīng)用范圍坐標(biāo)輪換法(變量輪換法或降維法)不需求導(dǎo)數(shù)，方法易懂，程序設(shè)計(jì)容易，但迭代過程較長，收斂速度較慢，且問題的維數(shù)n愈多求解效率愈低，適用于n10的小

20、型無約束最優(yōu)化問題，當(dāng)函數(shù)的等值線為圓或?yàn)殚L短軸都平行于坐標(biāo)軸的橢圓時(shí)此法很有效。最速下降法(一階梯度法) 效率高于上法，尤其最初幾步迭代函數(shù)值下降很快，但愈靠近極值點(diǎn)愈慢。迭代計(jì)算簡單，占用計(jì)算機(jī)單元少，對初始點(diǎn)的選擇要求低。常與其它方法混用。 牛頓法(Newton-Raphson法或二階梯度法)當(dāng)初始點(diǎn)選得合適時(shí)是目前算法中收斂得最快的一種(尤其對二次函數(shù))，但當(dāng)初始點(diǎn)選擇不當(dāng)會影響到能否收斂或?qū)е率?。?jì)算較繁且要求Hessian矩陣是非奇異的。計(jì)算量和存貯量都以維數(shù)n的平方 (n2)比例增加，故當(dāng)函數(shù)變量較多和因次較高時(shí)不宜采用此法。修正牛頓法(廣義牛頓法)即使初始點(diǎn)選擇不當(dāng)，此法亦會

21、成功，其它特點(diǎn)與牛頓法相同。共軛梯度法是對最速下降法在收斂速度上的重大改進(jìn)，其收斂速度比最速下降法大為加快，而計(jì)算又比牛頓法大為簡化。計(jì)算簡單，所需的存儲量少，收斂速度快，常用于多變量的最優(yōu)化設(shè)計(jì)。共軛方向法及其改進(jìn)Powell法 不需求導(dǎo)數(shù)只需計(jì)算函數(shù)值，適用于中、小型問題的無約束最優(yōu)化問題。Powell法是一種求無約束最優(yōu)化問題較為有效的方法，適用于中小型無約束最優(yōu)化問題，但對于多維問題收斂速度較慢。無約束最優(yōu)化方法的特點(diǎn)及應(yīng)用范圍無約束最優(yōu)化方法的特點(diǎn)及應(yīng)用范圍(續(xù)表續(xù)表)最優(yōu)化方法特點(diǎn)及應(yīng)用范圍變尺度法(DFP法及BFGS法)為求解無約束極值問題最有效的算法之一，可以用到維數(shù)n100的

22、問題。對于高維的大型問題，(n100)，由于收斂快，效果好，被認(rèn)為是最好的優(yōu)化方法之一，但計(jì)算A(k)的程序較復(fù)雜，且需要較大的存貯量。DFP法也存在數(shù)值穩(wěn)定性不夠理想等情況，而BFGS法則有較好的數(shù)值穩(wěn)定性。單純形法單純形法不需求導(dǎo)數(shù)，只需計(jì)算函數(shù)值。屬直接求優(yōu)法，這類不需求導(dǎo)數(shù)，只需計(jì)算函數(shù)值。屬直接求優(yōu)法，這類方法甚至適用于未知目標(biāo)函數(shù)的數(shù)學(xué)表達(dá)式而只知道方法甚至適用于未知目標(biāo)函數(shù)的數(shù)學(xué)表達(dá)式而只知道它的具體算法的情況、程序簡單、收斂快、效果好，它的具體算法的情況、程序簡單、收斂快、效果好，適用于中小型設(shè)計(jì)問題。適用于中小型設(shè)計(jì)問題。Hooke-Jeeves法程序簡單，當(dāng)變量較少時(shí)比較有

23、效，適應(yīng)性較強(qiáng)，收斂速度比坐標(biāo)輪換法有所改善但仍較慢，不適于高維數(shù)的問題。Rosenbrock法可看成是對Hooke-Jeeves法的進(jìn)一步改善與發(fā)展，比坐標(biāo)輪換法顯著地提高了迭代效率和解題效能，同樣不適用于高維數(shù)的問題。Marquardt法集中了最速下降法及牛頓法的優(yōu)點(diǎn)，且算法簡單，接近極小點(diǎn)時(shí)收斂得非?？?，不需要一維探索。常用于求函數(shù)平方和的極小值的問題。最小二乘法(Gauss-Newton法)常用于求函數(shù)平方和的極小值問題，且不必計(jì)算二階偏導(dǎo)數(shù)矩陣，為線性收斂速度。單純形法單純形法基本思想：基本思想： 不需要計(jì)算目標(biāo)函數(shù)的導(dǎo)數(shù)；不需要計(jì)算目標(biāo)函數(shù)的導(dǎo)數(shù)； 實(shí)際的最優(yōu)化工程中，目標(biāo)函數(shù)的導(dǎo)

24、數(shù)往實(shí)際的最優(yōu)化工程中，目標(biāo)函數(shù)的導(dǎo)數(shù)往往很難求出甚至根本無法求出。往很難求出甚至根本無法求出。在在n維空間中由維空間中由n+1+1個(gè)線性獨(dú)立的點(diǎn)構(gòu)成一個(gè)凸個(gè)線性獨(dú)立的點(diǎn)構(gòu)成一個(gè)凸 多面體；多面體；求出這些頂點(diǎn)處的目標(biāo)函數(shù)值并加以比較，確定求出這些頂點(diǎn)處的目標(biāo)函數(shù)值并加以比較，確定它們當(dāng)中有最大值的點(diǎn)以及函數(shù)值的下降方向，它們當(dāng)中有最大值的點(diǎn)以及函數(shù)值的下降方向，再設(shè)法找到一個(gè)新的比較好的點(diǎn)替換那個(gè)最差點(diǎn)，再設(shè)法找到一個(gè)新的比較好的點(diǎn)替換那個(gè)最差點(diǎn)，從而構(gòu)成新的單純形；從而構(gòu)成新的單純形；隨著這種取代過程的不斷進(jìn)行，新的單純隨著這種取代過程的不斷進(jìn)行，新的單純形將向著極小點(diǎn)收縮。經(jīng)過一定次數(shù)的

25、迭形將向著極小點(diǎn)收縮。經(jīng)過一定次數(shù)的迭代，即可得到滿足收斂準(zhǔn)則的近似解。代，即可得到滿足收斂準(zhǔn)則的近似解。 設(shè)有一個(gè)二維目標(biāo)函數(shù)設(shè)有一個(gè)二維目標(biāo)函數(shù) ，在平面中，在平面中 為線性獨(dú)立（不在同一直線上）的三個(gè)為線性獨(dú)立（不在同一直線上）的三個(gè) 點(diǎn)，并以它們?yōu)轫旤c(diǎn)構(gòu)造單純形（三角形）。點(diǎn)，并以它們?yōu)轫旤c(diǎn)構(gòu)造單純形（三角形）。 計(jì)算這三個(gè)頂點(diǎn)處的函數(shù)值計(jì)算這三個(gè)頂點(diǎn)處的函數(shù)值 并作比并作比 較：若較：若 ，則說明，則說明 點(diǎn)最差，點(diǎn)最差， 最最 好。故應(yīng)該拋棄好。故應(yīng)該拋棄 點(diǎn)并形成新的單純形。點(diǎn)并形成新的單純形。12(X)( ,)yff x xX ,X ,Xhlg(X )(X )(X )hglff

26、f(X ),(X ),(X )hglfffXhXlXh算法思路算法思路：（3 3種類型的步驟種類型的步驟反射、擴(kuò)張和壓縮）反射、擴(kuò)張和壓縮） 為此要找出除為此要找出除 以外的所有頂點(diǎn)的形心點(diǎn)以外的所有頂點(diǎn)的形心點(diǎn) ，并在，并在 和和 連線的延長線上取一點(diǎn)連線的延長線上取一點(diǎn) ，使，使XhXhXcXcXrXX(XX )(1)rcch最差點(diǎn)的反射點(diǎn)最差點(diǎn)的反射點(diǎn)反射系數(shù)，一般取為反射系數(shù)，一般取為1.0關(guān)于反射點(diǎn)的選取：關(guān)于反射點(diǎn)的選?。喝舴瓷潼c(diǎn)的函數(shù)值若反射點(diǎn)的函數(shù)值 小于最好點(diǎn)的函數(shù)值小于最好點(diǎn)的函數(shù)值 ，即，即 時(shí)，則表明所取的探索時(shí)，則表明所取的探索 方向正確，可進(jìn)一步擴(kuò)大效果，繼續(xù)沿方向

27、正確，可進(jìn)一步擴(kuò)大效果，繼續(xù)沿 向向 前進(jìn)行擴(kuò)張，在更遠(yuǎn)處取一點(diǎn)前進(jìn)行擴(kuò)張，在更遠(yuǎn)處取一點(diǎn) ，并使，并使(X )(X )rlffXX(XX )(2)ecrcXeX Xhr(X )lf(X )rf擴(kuò)展系數(shù)，大小一般在擴(kuò)展系數(shù)，大小一般在1.22.0之間之間圖示圖示 若若 ，說明擴(kuò)張有利，就用，說明擴(kuò)張有利，就用 代替最代替最 差點(diǎn)差點(diǎn) ，構(gòu)造新的單純形，構(gòu)造新的單純形 ； 若若 不成立，則不能擴(kuò)張。此時(shí)，如果不成立，則不能擴(kuò)張。此時(shí)，如果 則用反射點(diǎn)則用反射點(diǎn) 替換最差點(diǎn)替換最差點(diǎn) 而形成新的單純形而形成新的單純形 。 (X )(X )elffXeXhXhXrX ,X ,Xgle(X )(X )

28、rlff(X )(X )(3)rgffX ,X ,Xglr若下式成立，即若下式成立，即 則表示則表示 點(diǎn)走得太遠(yuǎn)，應(yīng)該縮回一些，需要進(jìn)點(diǎn)走得太遠(yuǎn)，應(yīng)該縮回一些，需要進(jìn) 行壓縮，且得到的壓縮點(diǎn)應(yīng)為：行壓縮，且得到的壓縮點(diǎn)應(yīng)為：(X )(X )(X )(4)grhfffXrXX(XX )(5)scrc壓縮系數(shù)，常取壓縮系數(shù)，常取0.5圖示圖示 若若 則用壓縮點(diǎn)則用壓縮點(diǎn) 代替代替 ，形成新的單純形，形成新的單純形(X )(X )(6)shffXsX ,X ,XglsXh若反射點(diǎn)的函數(shù)值若反射點(diǎn)的函數(shù)值 大于最差點(diǎn)的函數(shù)值，大于最差點(diǎn)的函數(shù)值， 即即 時(shí)，應(yīng)該壓縮得更多些，即將新點(diǎn)壓縮至?xí)r，應(yīng)該壓縮

29、得更多些，即將新點(diǎn)壓縮至 與與 之間，這時(shí)所得的壓縮點(diǎn)應(yīng)為：之間，這時(shí)所得的壓縮點(diǎn)應(yīng)為：Xh(X )rf(X )(X )(7)rhffXcXX(XX )X(XX )(8)scchchc(X )hf如果在如果在 方向上所有點(diǎn)的函數(shù)值方向上所有點(diǎn)的函數(shù)值 都大于都大于 ，或式（，或式（6）不成立，則不能沿此方向探索。）不成立，則不能沿此方向探索。 這時(shí)應(yīng)使單純形向最好點(diǎn)進(jìn)行收縮，即最好點(diǎn)這時(shí)應(yīng)使單純形向最好點(diǎn)進(jìn)行收縮，即最好點(diǎn) 不動，其余各頂點(diǎn)不動，其余各頂點(diǎn) ， 皆向皆向 移近為原距離的移近為原距離的 一半，由原單純形一半，由原單純形 收縮成新單純形收縮成新單純形 。X XhcX ,X ,Xhg

30、l(X)f(X )hfXlXgXhXlX ,X ,Xhgl 從以上各步得到新的單純形后，再重新開始從以上各步得到新的單純形后，再重新開始各步，逐漸縮小單純形直至滿足精度要求為止。各步，逐漸縮小單純形直至滿足精度要求為止。0 x1x2XhXgXlXcXrXeXsXs返回返回返回返回單純形法的計(jì)算步驟單純形法的計(jì)算步驟 設(shè)目標(biāo)函數(shù)設(shè)目標(biāo)函數(shù) 為為n元函數(shù)，即元函數(shù)，即X為為n維向量，因此單維向量，因此單純形應(yīng)有純形應(yīng)有n+1個(gè)頂點(diǎn)個(gè)頂點(diǎn) 。(X)f121X ,X ,Xn(0)(0)1XXejih一般取值范圍為一般取值范圍為0.515.0; 構(gòu)成初試單純形時(shí)構(gòu)成初試單純形時(shí),h=1.61.7. 構(gòu)造

31、初始單純形時(shí)，先在構(gòu)造初始單純形時(shí)，先在n維空間中選取初始點(diǎn)維空間中選取初始點(diǎn) （盡量靠近最優(yōu)點(diǎn)），然后從（盡量靠近最優(yōu)點(diǎn)），然后從 出發(fā)沿各坐標(biāo)軸出發(fā)沿各坐標(biāo)軸方向方向 ，以步長，以步長h找到其余找到其余n個(gè)頂點(diǎn)個(gè)頂點(diǎn) ；(0)1X(0)1X(0)X(2,3,1)jjnei0 x1x2XhXgXlXgXh 表示第表示第k輪探索時(shí)的最好點(diǎn)輪探索時(shí)的最好點(diǎn), ,即即并令并令: : 為第為第k輪探索的第輪探索的第j頂點(diǎn)頂點(diǎn), ,其函數(shù)值為其函數(shù)值為 ; ; 表示第表示第k輪探索時(shí)所有頂點(diǎn)中函數(shù)值最大的輪探索時(shí)所有頂點(diǎn)中函數(shù)值最大的 頂點(diǎn)頂點(diǎn), ,即最差點(diǎn)即最差點(diǎn): : 為次差點(diǎn)為次差點(diǎn), ,即即

32、比比 小小, ,但比其余但比其余 各頂點(diǎn)的函數(shù)值各頂點(diǎn)的函數(shù)值 都大都大; ; 為除最差點(diǎn)外為除最差點(diǎn)外, ,其余所有頂點(diǎn)的形心其余所有頂點(diǎn)的形心, ,其坐其坐標(biāo)標(biāo) 可以按下式計(jì)算可以按下式計(jì)算: :( )(X)kjf( )Xkj( )Xkh( )Xkg( )(X)kgf( )(X)kjf( )2Xkn( )Xkl( )( )( )( )121(X)max(X),(X),(X)kkkkhnffff1( )( )( )2,11nkkknijihijxxxn( )( )( )( )121(X)min(X),(X),(X)kkkklnffff( )(X)khf1( )( )( )211XXXnkkk

33、njhjn( )( )( )( )322XXXXkkkknnnh式中，式中，i=1,2,n為各坐標(biāo)方向的序號；為各坐標(biāo)方向的序號；j為頂點(diǎn)為頂點(diǎn)號，或號，或構(gòu)成初始單純形后，即可進(jìn)行以下步驟構(gòu)成初始單純形后，即可進(jìn)行以下步驟：計(jì)算各頂點(diǎn)的函數(shù)值并進(jìn)行比較，找出最好點(diǎn)計(jì)算各頂點(diǎn)的函數(shù)值并進(jìn)行比較，找出最好點(diǎn) ，最差點(diǎn)，最差點(diǎn) ，次差點(diǎn)，次差點(diǎn) ，以及除最差點(diǎn)，以及除最差點(diǎn) 以外其余各頂點(diǎn)的形心以外其余各頂點(diǎn)的形心 。求。求 對形心對形心 的反射點(diǎn)：的反射點(diǎn)：( )Xkl( )Xkh( )Xkg( )2Xkn( )2Xkn( )Xkh( )( )( )( )4232XXXXkkkknnnn比較比較

34、 和和 ，如果反射點(diǎn)，如果反射點(diǎn) 比最好點(diǎn)比最好點(diǎn) 還要好，即還要好，即 時(shí)，則進(jìn)行擴(kuò)張，得時(shí)，則進(jìn)行擴(kuò)張，得 擴(kuò)張點(diǎn)為（按式擴(kuò)張點(diǎn)為（按式（2）：）：( )Xkl( )3Xkn( )3Xkn( )Xkl( )( )3(X)(X)kknlff將反射點(diǎn)將反射點(diǎn) 與次差點(diǎn)與次差點(diǎn) 比較，若比較，若 ，則用，則用 代替最差點(diǎn)代替最差點(diǎn) ，并轉(zhuǎn)入步驟；，并轉(zhuǎn)入步驟； 若若 ，則用，則用 代替代替 后后 進(jìn)行壓縮進(jìn)行壓縮, ,否則直接進(jìn)行壓縮，得壓縮點(diǎn)為否則直接進(jìn)行壓縮，得壓縮點(diǎn)為：( )Xkg( )Xkh( )3Xkn( )( )3(X)(X)kkngff( )3Xkn( )( )( )3(X)(X)

35、(X)kkkgnhfff( )3Xkn( )Xkh 得到擴(kuò)張點(diǎn)得到擴(kuò)張點(diǎn) 后，如果后，如果 ，則用，則用 代替代替 后轉(zhuǎn)入。后轉(zhuǎn)入。否則用否則用 代替轉(zhuǎn)入。代替轉(zhuǎn)入。( )Xkh( )4Xkn( )( )4(X)(X)kknlff( )4Xkn 若若 ，即反射點(diǎn)比最好點(diǎn)差，則轉(zhuǎn)，即反射點(diǎn)比最好點(diǎn)差，則轉(zhuǎn) 下一步。下一步。( )( )3(X)(X)kknlff( )3Xkn( )( )( )( )522XXXXkkkknnhn( )( )( )( )XX0.5 XX1,2,1kkkkjljljn進(jìn)行收斂性檢驗(yàn)進(jìn)行收斂性檢驗(yàn). .若若則停止迭代并輸出則停止迭代并輸出 及及 , ,否則否則 后轉(zhuǎn)后轉(zhuǎn)

36、第步。第步。( )Xklf1kk1122( )( )211XX1nkkjnjffn( )Xkl將壓縮點(diǎn)將壓縮點(diǎn) 與最差點(diǎn)與最差點(diǎn) 比較，若比較，若 ，則用，則用 代替最差點(diǎn)代替最差點(diǎn) 以后轉(zhuǎn)入下一步以后轉(zhuǎn)入下一步; ;否否 則使單純形向最好點(diǎn)則使單純形向最好點(diǎn) 收縮收縮, ,收縮后的單純形收縮后的單純形 頂點(diǎn)為頂點(diǎn)為: :( )Xkl( )Xkh( )5Xkn( )( )5(X)(X)kknhff( )5Xkn( )Xkh逐漸縮小單純形直逐漸縮小單純形直至至滿足精度要求為止。滿足精度要求為止。單純形程序框圖單純形程序框圖思考題思考題基于單純形算法的基本框架，設(shè)計(jì)其具體的尋優(yōu)思基于單純形算法的基

37、本框架，設(shè)計(jì)其具體的尋優(yōu)思路（請以程序框圖的形式描述）。路（請以程序框圖的形式描述）。如何設(shè)計(jì)單純形算法的收斂準(zhǔn)則？在程序調(diào)試過程如何設(shè)計(jì)單純形算法的收斂準(zhǔn)則？在程序調(diào)試過程中，應(yīng)該如何觀察、判定其尋優(yōu)過程是否已收斂？中，應(yīng)該如何觀察、判定其尋優(yōu)過程是否已收斂？單純形算法有哪些控制參數(shù)，它們對算法有何種影單純形算法有哪些控制參數(shù)，它們對算法有何種影響？響？復(fù)合形法復(fù)合形法 復(fù)合形法是求解約束非線性最優(yōu)化問題的一種重復(fù)合形法是求解約束非線性最優(yōu)化問題的一種重 要的直接方法。要的直接方法。 它來源于用于求解約束非線性最優(yōu)化問題的單純它來源于用于求解約束非線性最優(yōu)化問題的單純形法，實(shí)際上是單純形法在

38、約束問題中的發(fā)展。形法，實(shí)際上是單純形法在約束問題中的發(fā)展。 初始復(fù)合形的產(chǎn)生方法：初始復(fù)合形的產(chǎn)生方法：(0)=-jiijiiixarba 設(shè)在可行域內(nèi)先給定復(fù)合形的一個(gè)初始頂點(diǎn)設(shè)在可行域內(nèi)先給定復(fù)合形的一個(gè)初始頂點(diǎn) ，則，則其余其余n個(gè)頂點(diǎn)個(gè)頂點(diǎn) 由下式確定：由下式確定：(0)1X(0)X(2,3,1)jjn 調(diào)整變量調(diào)整變量 的解域或上下界；的解域或上下界；其中其中: : 為復(fù)合形頂點(diǎn)的標(biāo)號為復(fù)合形頂點(diǎn)的標(biāo)號 ; ; 為調(diào)整變量的標(biāo)號為調(diào)整變量的標(biāo)號 ； 為為 區(qū)間內(nèi)服從均勻分布的偽隨機(jī)數(shù)。區(qū)間內(nèi)服從均勻分布的偽隨機(jī)數(shù)。2,3,1jnjijir0,1,iia b(0)(0)111,2,q

39、ijijxxinq1,2,in1,2,ix in這樣產(chǎn)生的頂點(diǎn)雖能滿足調(diào)整變量的邊界約束條這樣產(chǎn)生的頂點(diǎn)雖能滿足調(diào)整變量的邊界約束條件，但不一定能滿足性能約束條件。假定其中件，但不一定能滿足性能約束條件。假定其中 等等q個(gè)點(diǎn)個(gè)點(diǎn) 滿足全部約束條件，滿足全部約束條件，而其余點(diǎn)而其余點(diǎn) 不滿足，為了使它們也能滿不滿足，為了使它們也能滿足，則可先求出所有滿足點(diǎn)的形心點(diǎn)：足，則可先求出所有滿足點(diǎn)的形心點(diǎn)： (0)(0)(0)12X,X,Xq(1)qn(0)(0)11X,Xqn(0)(0)(0)(0)11(0)(0)(0)(0)11XXXXXXXXqqnn然后將然后將 這些不滿足約束條件的點(diǎn)向形這些不滿

40、足約束條件的點(diǎn)向形心點(diǎn)心點(diǎn) 靠攏，得新點(diǎn)：靠攏，得新點(diǎn)：(0)X(0)(0)11X,Xqn(0)1(0)1X01,2,X0uqungumg只要系數(shù)只要系數(shù) 選擇得當(dāng)（一般取選擇得當(dāng)（一般取 ），總可以使），總可以使新點(diǎn)新點(diǎn) 滿足全部約束條件，即滿足全部約束條件，即(0)(0)11X,Xqn0.5這樣就可求得另外這樣就可求得另外n-q+1 個(gè)滿足全部約束條件個(gè)滿足全部約束條件的初始頂點(diǎn)。的初始頂點(diǎn)。取得取得n+1個(gè)頂點(diǎn)后便可構(gòu)成一個(gè)有個(gè)頂點(diǎn)后便可構(gòu)成一個(gè)有n+1頂點(diǎn)的多頂點(diǎn)的多面體面體復(fù)合形。然后如下進(jìn)行迭代計(jì)算：復(fù)合形。然后如下進(jìn)行迭代計(jì)算：計(jì)算復(fù)合形各頂點(diǎn)的目標(biāo)函數(shù)值，找出其中的計(jì)算復(fù)合形各

41、頂點(diǎn)的目標(biāo)函數(shù)值，找出其中的 最差點(diǎn)最差點(diǎn) ： 找出次差點(diǎn)找出次差點(diǎn) : : 找出最好點(diǎn)找出最好點(diǎn) : :XlXgX=maxX1,2,1hjffjnXhX=maxX1,2,1,gjffjnjh但X=minX1,2,1ljffjn計(jì)算除最差點(diǎn)計(jì)算除最差點(diǎn) 外其它各頂點(diǎn)的形心外其它各頂點(diǎn)的形心 : : 或或 檢查檢查 點(diǎn)的可行性點(diǎn)的可行性。cXXc11X =XncjjjhnXh11=1,2, ;ncijijxxin jhn如果如果 點(diǎn)在可行域內(nèi)，則沿點(diǎn)在可行域內(nèi)，則沿 方向求反射方向求反射 點(diǎn)點(diǎn): : 式中式中 ，可取，可取 ，若，若 為非可行點(diǎn)，則為非可行點(diǎn)，則 應(yīng)將應(yīng)將 值減半，繼續(xù)計(jì)算，直至

42、值減半，繼續(xù)計(jì)算，直至 滿足全部滿足全部 約束條件為止。約束條件為止。XXchXcX =X +XXrcch11.3XrXr如果如果 點(diǎn)不在可行域內(nèi)，為了將點(diǎn)不在可行域內(nèi)，為了將 點(diǎn)移進(jìn)可行點(diǎn)移進(jìn)可行 域內(nèi)，可在以域內(nèi)，可在以 點(diǎn)和點(diǎn)和 點(diǎn)為界，重新利用偽隨點(diǎn)為界，重新利用偽隨 機(jī)數(shù)產(chǎn)生機(jī)數(shù)產(chǎn)生n+1個(gè)新的頂點(diǎn)，構(gòu)成新的復(fù)合形。此個(gè)新的頂點(diǎn)，構(gòu)成新的復(fù)合形。此 時(shí)變量的上下界改為：時(shí)變量的上下界改為： 若若 ，則取，則取 否則相反。重復(fù)步驟、，直至否則相反。重復(fù)步驟、，直至 點(diǎn)進(jìn)入可點(diǎn)進(jìn)入可 行域?yàn)橹?。行域?yàn)橹埂cXc1,2,iliiciaxinbx1,2,licixxinXcXcXl計(jì)算計(jì)算

43、 點(diǎn)的目標(biāo)函數(shù)值，如果點(diǎn)的目標(biāo)函數(shù)值，如果 時(shí)，時(shí)， 則用反射點(diǎn)則用反射點(diǎn) 替換最差點(diǎn)替換最差點(diǎn) 組成新的復(fù)合形，組成新的復(fù)合形， 完成一次迭代并轉(zhuǎn)入步驟，否則轉(zhuǎn)入步驟。完成一次迭代并轉(zhuǎn)入步驟，否則轉(zhuǎn)入步驟。 XrXXrhffXrXh如果如果 則將則將 值減半，重新計(jì)算反射值減半，重新計(jì)算反射 點(diǎn)點(diǎn) ，這時(shí)若，這時(shí)若 且且 為可行點(diǎn)，則轉(zhuǎn)向?yàn)榭尚悬c(diǎn)，則轉(zhuǎn)向 步驟；否則應(yīng)再將步驟；否則應(yīng)再將 值減半，如此反復(fù)。如果值減半，如此反復(fù)。如果 經(jīng)過若干次減半經(jīng)過若干次減半 值的計(jì)算并使值的計(jì)算并使 值已縮小到給值已縮小到給 定的一個(gè)很小的正數(shù)定的一個(gè)很小的正數(shù) （例如（例如 ）以下仍無）以下仍無 效，

44、則可使復(fù)合形向最好點(diǎn)效，則可使復(fù)合形向最好點(diǎn) 收縮，還可在收縮，還可在 三點(diǎn)所決定的平面中，將三點(diǎn)所決定的平面中，將 點(diǎn)繞點(diǎn)繞 點(diǎn)旋轉(zhuǎn)某一角度點(diǎn)旋轉(zhuǎn)某一角度 ，并向最好點(diǎn)，并向最好點(diǎn) 靠攏，得靠攏，得 到新的到新的 點(diǎn)后構(gòu)成新的復(fù)合形并轉(zhuǎn)入步驟，重點(diǎn)后構(gòu)成新的復(fù)合形并轉(zhuǎn)入步驟，重 新進(jìn)行迭代計(jì)算，直到滿足計(jì)算精度為止。新進(jìn)行迭代計(jì)算，直到滿足計(jì)算精度為止。 XrXrXXrhffXXrhff( )Xkh05010( )Xkl( )( )( )X,X,Xkkkhcl( )Xkl( )Xkl( )Xkh若同時(shí)滿足收斂準(zhǔn)則若同時(shí)滿足收斂準(zhǔn)則、時(shí)，則停止迭代，并時(shí)，則停止迭代，并 取復(fù)合形的最小函數(shù)值的

45、頂點(diǎn)作為最優(yōu)解。取復(fù)合形的最小函數(shù)值的頂點(diǎn)作為最優(yōu)解。復(fù)合形程序復(fù)合形程序框圖框圖復(fù)合形程序框圖復(fù)合形程序框圖思考題思考題基于復(fù)合形算法的基本框架，設(shè)計(jì)其具體的尋優(yōu)思基于復(fù)合形算法的基本框架，設(shè)計(jì)其具體的尋優(yōu)思路（請以程序框圖的形式描述）。路（請以程序框圖的形式描述）。如何設(shè)計(jì)復(fù)合形算法的收斂準(zhǔn)則？在程序調(diào)試過程如何設(shè)計(jì)復(fù)合形算法的收斂準(zhǔn)則？在程序調(diào)試過程中，應(yīng)該如何觀察、判定其尋優(yōu)過程是否已收斂？中，應(yīng)該如何觀察、判定其尋優(yōu)過程是否已收斂？復(fù)合形算法有哪些控制參數(shù)，它們對算法有何種影復(fù)合形算法有哪些控制參數(shù)，它們對算法有何種影響？響？編程實(shí)現(xiàn)編程實(shí)現(xiàn) Generalized Rosen br

46、ocks valley Function Generalized Rastrigins Function Schaffers Function122211max( )100 ()(1)2.0482.048niiiiifxxxxx21min( )(10 cos(2)+10)5.125.12niiiifxxxx2221212222120.5min0.5sin,10.010.01 0.001ifxxx xxxx Rosen Brocks valley Function Rastrigins Function Schaffers Function它有無限個(gè)局部極大點(diǎn)，只有一個(gè)全局最大值點(diǎn)它有無限個(gè)局部

47、極大點(diǎn)，只有一個(gè)全局最大值點(diǎn) f(0,0)=1，此，此函數(shù)最大值峰周圍有一圈脊，它們的取值均為函數(shù)最大值峰周圍有一圈脊，它們的取值均為0.990283.Schaffers Function-1-0.500.511.522.533.54-3-2.5-2-1.5-1-0.500.51尋優(yōu)過程中復(fù)合尋優(yōu)過程中復(fù)合形的演變軌跡形的演變軌跡Rosen brocks valley Function尋優(yōu)過程中一些重要信息的顯示尋優(yōu)過程中一些重要信息的顯示多目標(biāo)函數(shù)的最優(yōu)化方法前面介紹的最優(yōu)化方法，可直接用于前面介紹的最優(yōu)化方法，可直接用于僅含一個(gè)目標(biāo)函數(shù)的所謂僅含一個(gè)目標(biāo)函數(shù)的所謂“單目標(biāo)函單目標(biāo)函數(shù)的最優(yōu)

48、化問題數(shù)的最優(yōu)化問題”。但在許多實(shí)際工程問題中，常常期望但在許多實(shí)際工程問題中，常常期望同時(shí)有幾項(xiàng)指標(biāo)同時(shí)有幾項(xiàng)指標(biāo)整體整體達(dá)到最優(yōu)值，這達(dá)到最優(yōu)值，這就是所謂就是所謂“多目標(biāo)函數(shù)的最優(yōu)化問多目標(biāo)函數(shù)的最優(yōu)化問題題”，其數(shù)學(xué)模型的一般表達(dá)式為，其數(shù)學(xué)模型的一般表達(dá)式為:各個(gè)分目標(biāo)各個(gè)分目標(biāo)f1(X)，f2(X)，fn(X)的優(yōu)化的優(yōu)化往往是互相矛盾的，即不能期望同時(shí)實(shí)現(xiàn)它往往是互相矛盾的，即不能期望同時(shí)實(shí)現(xiàn)它們的最優(yōu)解；們的最優(yōu)解；甚至有時(shí)還會產(chǎn)生完全對立的情況，即對一甚至有時(shí)還會產(chǎn)生完全對立的情況，即對一個(gè)目標(biāo)函數(shù)是最優(yōu)點(diǎn)，對另一目標(biāo)函數(shù)卻是個(gè)目標(biāo)函數(shù)是最優(yōu)點(diǎn)，對另一目標(biāo)函數(shù)卻是最劣點(diǎn)。最劣

49、點(diǎn)。這就需要在各個(gè)分目標(biāo)的最優(yōu)解之間進(jìn)行協(xié)這就需要在各個(gè)分目標(biāo)的最優(yōu)解之間進(jìn)行協(xié)調(diào)，相互間作出適當(dāng)調(diào)，相互間作出適當(dāng)“讓步讓步”，以便取得，以便取得整整體體最優(yōu)方案。由此也可以看出多目標(biāo)函數(shù)的最優(yōu)方案。由此也可以看出多目標(biāo)函數(shù)的最優(yōu)化問題要比單目標(biāo)函數(shù)的最優(yōu)化問題復(fù)最優(yōu)化問題要比單目標(biāo)函數(shù)的最優(yōu)化問題復(fù)雜得多，求解難度也更大。雜得多，求解難度也更大。統(tǒng)一目標(biāo)法統(tǒng)一目標(biāo)法的實(shí)質(zhì)就是將控制方程中的各個(gè)統(tǒng)一目標(biāo)法的實(shí)質(zhì)就是將控制方程中的各個(gè)目標(biāo)函數(shù)目標(biāo)函數(shù)( (或稱分目標(biāo)函數(shù)或稱分目標(biāo)函數(shù)) ) f1(X)，f2(X)，fn(X) 統(tǒng)一到一個(gè)總的統(tǒng)一到一個(gè)總的“統(tǒng)一目標(biāo)函數(shù)統(tǒng)一目標(biāo)函數(shù)” f(X)中

50、，即令中，即令從而把多目標(biāo)函數(shù)的最優(yōu)化問題轉(zhuǎn)變?yōu)閱文繌亩讯嗄繕?biāo)函數(shù)的最優(yōu)化問題轉(zhuǎn)變?yōu)閱文繕?biāo)函數(shù)的最優(yōu)化問題。標(biāo)函數(shù)的最優(yōu)化問題。 12(X)(X),(X),(X)qfffff 在極小化在極小化“統(tǒng)一目標(biāo)函數(shù)統(tǒng)一目標(biāo)函數(shù)”f(X) 的過程中，為的過程中，為了使各個(gè)分目標(biāo)函數(shù)能均勻一致地趨向各自的了使各個(gè)分目標(biāo)函數(shù)能均勻一致地趨向各自的最優(yōu)值，可采用如下的一些方法：最優(yōu)值，可采用如下的一些方法：(1)加權(quán)組合法加權(quán)組合法(2)目標(biāo)規(guī)劃法目標(biāo)規(guī)劃法(3)功效系數(shù)法功效系數(shù)法(4)乘除法乘除法加權(quán)組合法又稱線性組合法或加權(quán)因子法，即在將各個(gè)又稱線性組合法或加權(quán)因子法，即在將各個(gè)分目標(biāo)函數(shù)組合為總的分

51、目標(biāo)函數(shù)組合為總的“統(tǒng)一目標(biāo)函數(shù)統(tǒng)一目標(biāo)函數(shù)”的的過程中，引入加權(quán)因子，以考慮各個(gè)分目標(biāo)過程中，引入加權(quán)因子，以考慮各個(gè)分目標(biāo)函數(shù)在相對重要程度方面的差異以及在量級函數(shù)在相對重要程度方面的差異以及在量級和量綱上的差異。如和量綱上的差異。如1(X)(X)qiiifw f 第第i項(xiàng)分目標(biāo)函數(shù)項(xiàng)分目標(biāo)函數(shù)fi(X)的加權(quán)因子，的加權(quán)因子，是一個(gè)大于零的數(shù)。是一個(gè)大于零的數(shù)。在將各個(gè)分目標(biāo)函數(shù)加權(quán)組合成總的統(tǒng)一目標(biāo)在將各個(gè)分目標(biāo)函數(shù)加權(quán)組合成總的統(tǒng)一目標(biāo)函數(shù)的過程中，加權(quán)組合法又分為函數(shù)的過程中，加權(quán)組合法又分為: : 直接加權(quán)法直接加權(quán)法(X)(1,2, )iiifiq采用直接加權(quán)法來建立總的統(tǒng)一目

52、標(biāo)函數(shù)時(shí)，采用直接加權(quán)法來建立總的統(tǒng)一目標(biāo)函數(shù)時(shí)，其加權(quán)因子其加權(quán)因子wi的選取方法如下：的選取方法如下： 若已知某分目標(biāo)函數(shù)若已知某分目標(biāo)函數(shù)fi(X)的變動范圍為的變動范圍為直接加權(quán)法直接加權(quán)法; ; 轉(zhuǎn)化設(shè)計(jì)指標(biāo)法。轉(zhuǎn)化設(shè)計(jì)指標(biāo)法。則稱則稱為該指標(biāo)的的容限，于是可取該項(xiàng)指標(biāo)的加為該指標(biāo)的的容限，于是可取該項(xiàng)指標(biāo)的加權(quán)因子為權(quán)因子為(X)0.5()(1,2, )iiifiq21/(X)(1,2, )iiwfiq這種取法是基于要求在統(tǒng)一目標(biāo)函數(shù)中的各項(xiàng)這種取法是基于要求在統(tǒng)一目標(biāo)函數(shù)中的各項(xiàng)指標(biāo)指標(biāo)(分目標(biāo)函數(shù)分目標(biāo)函數(shù))趨于在數(shù)量級上達(dá)到統(tǒng)一平趨于在數(shù)量級上達(dá)到統(tǒng)一平衡。因此，當(dāng)某項(xiàng)指標(biāo)的

53、數(shù)值變化范圍愈寬時(shí)，衡。因此，當(dāng)某項(xiàng)指標(biāo)的數(shù)值變化范圍愈寬時(shí)，其目標(biāo)的容限就愈大，加權(quán)因子就取較小值；其目標(biāo)的容限就愈大，加權(quán)因子就取較小值；而數(shù)值變化范圍愈窄時(shí)，目標(biāo)的容限就愈小，而數(shù)值變化范圍愈窄時(shí)，目標(biāo)的容限就愈小，加權(quán)因子就取大值，以達(dá)到平衡各分目標(biāo)函數(shù)加權(quán)因子就取大值，以達(dá)到平衡各分目標(biāo)函數(shù)量級的作用。量級的作用。直接加權(quán)方法應(yīng)該把加權(quán)因子分為兩部分，即直接加權(quán)方法應(yīng)該把加權(quán)因子分為兩部分，即第第i項(xiàng)設(shè)計(jì)指標(biāo)的加權(quán)因子項(xiàng)設(shè)計(jì)指標(biāo)的加權(quán)因子wi為為式中式中 wi1反映第反映第i項(xiàng)目標(biāo)項(xiàng)目標(biāo)( (設(shè)計(jì)指標(biāo)設(shè)計(jì)指標(biāo)) )相對重要性的加相對重要性的加 權(quán)因子，稱作本征權(quán)因子；權(quán)因子，稱作本征

54、權(quán)因子； wi2第第i項(xiàng)目標(biāo)的校正權(quán)因子，用于調(diào)整各目標(biāo)項(xiàng)目標(biāo)的校正權(quán)因子，用于調(diào)整各目標(biāo) 間在量級差別方面的影響、并在迭代過程間在量級差別方面的影響、并在迭代過程 中逐步加以校正的加權(quán)因子。中逐步加以校正的加權(quán)因子。12(1,2, )iiiwwwiq若用梯度若用梯度 來反映各個(gè)分目標(biāo)函數(shù)來反映各個(gè)分目標(biāo)函數(shù)fi(X)隨隨設(shè)計(jì)變量變化而有不同函數(shù)值的情況，則其設(shè)計(jì)變量變化而有不同函數(shù)值的情況，則其校正權(quán)因子可取校正權(quán)因子可取即：即： fi(X)的函數(shù)值變化愈快，加權(quán)值愈應(yīng)取的函數(shù)值變化愈快，加權(quán)值愈應(yīng)取小些；反之則應(yīng)取大些。這樣就可使變小些；反之則應(yīng)取大些。這樣就可使變化快慢不等的目標(biāo)一起調(diào)整

55、好。化快慢不等的目標(biāo)一起調(diào)整好。(X)if 221/(X)(1,2, )iiwfiq轉(zhuǎn)化設(shè)計(jì)指標(biāo)法先將各項(xiàng)設(shè)計(jì)指標(biāo)都轉(zhuǎn)化為統(tǒng)一的無量綱值，先將各項(xiàng)設(shè)計(jì)指標(biāo)都轉(zhuǎn)化為統(tǒng)一的無量綱值，并且將量級也限于某一規(guī)定范圍之內(nèi)，使目并且將量級也限于某一規(guī)定范圍之內(nèi)，使目標(biāo)規(guī)格化，然后再根據(jù)各個(gè)目標(biāo)標(biāo)規(guī)格化，然后再根據(jù)各個(gè)目標(biāo)( (設(shè)計(jì)指標(biāo)設(shè)計(jì)指標(biāo)) )的重要性用加權(quán)因子來組合的重要性用加權(quán)因子來組合“統(tǒng)一目標(biāo)函統(tǒng)一目標(biāo)函數(shù)數(shù)”。(X)(1,2, )iiifiq例如，若能預(yù)計(jì)各項(xiàng)設(shè)計(jì)指標(biāo)的變動范圍，即已知例如，若能預(yù)計(jì)各項(xiàng)設(shè)計(jì)指標(biāo)的變動范圍，即已知則可用右圖所示的正弦函則可用右圖所示的正弦函數(shù)將各項(xiàng)設(shè)計(jì)指標(biāo)數(shù)將

56、各項(xiàng)設(shè)計(jì)指標(biāo)( (分目標(biāo)分目標(biāo)函數(shù)函數(shù)) )都轉(zhuǎn)換到在都轉(zhuǎn)換到在01的范的范圍內(nèi)取值，使各目標(biāo)規(guī)格圍內(nèi)取值，使各目標(biāo)規(guī)格化。當(dāng)然也可以用其它合化。當(dāng)然也可以用其它合適的函數(shù)作為轉(zhuǎn)換函數(shù)。適的函數(shù)作為轉(zhuǎn)換函數(shù)。(X)2(1,2, )iiiiifxiq 轉(zhuǎn)換函數(shù)中自變量的上下界應(yīng)與原設(shè)計(jì)指轉(zhuǎn)換函數(shù)中自變量的上下界應(yīng)與原設(shè)計(jì)指標(biāo)的上下界相對應(yīng)。即標(biāo)的上下界相對應(yīng)。即0與與2應(yīng)分別對應(yīng)于應(yīng)分別對應(yīng)于i及及i，則相應(yīng)于，則相應(yīng)于fi(X)值轉(zhuǎn)換函數(shù)的自變量值轉(zhuǎn)換函數(shù)的自變量值為值為令設(shè)計(jì)指標(biāo)令設(shè)計(jì)指標(biāo)fi(X)在轉(zhuǎn)化后為在轉(zhuǎn)化后為fiT(X) ，則，則 因此，因此，“統(tǒng)一目標(biāo)函數(shù)統(tǒng)一目標(biāo)函數(shù)”為為 式中

57、的加權(quán)因子式中的加權(quán)因子wi (i=1,2,q)，是根據(jù)該是根據(jù)該項(xiàng)項(xiàng)( (第第i項(xiàng)項(xiàng)) )設(shè)計(jì)指標(biāo)在最優(yōu)化設(shè)計(jì)中所占的設(shè)計(jì)指標(biāo)在最優(yōu)化設(shè)計(jì)中所占的 重要程度來確定。重要程度來確定。(X)sin(1,2, )2iiTixfxiq 1(X)(X)qiiTifw f 通過上述換算，可使各項(xiàng)設(shè)計(jì)指標(biāo)都轉(zhuǎn)化通過上述換算，可使各項(xiàng)設(shè)計(jì)指標(biāo)都轉(zhuǎn)化為無量綱且等量級的一個(gè)數(shù)。為無量綱且等量級的一個(gè)數(shù)。(2)目標(biāo)規(guī)劃法先分別求出各個(gè)分目標(biāo)函數(shù)的最優(yōu)值先分別求出各個(gè)分目標(biāo)函數(shù)的最優(yōu)值fi(X*)，然后根據(jù)多目標(biāo)函數(shù)最優(yōu)化設(shè)計(jì)的總體要求，然后根據(jù)多目標(biāo)函數(shù)最優(yōu)化設(shè)計(jì)的總體要求，作適當(dāng)調(diào)整，制定出理想的最優(yōu)值作適當(dāng)調(diào)

58、整，制定出理想的最優(yōu)值fi(o) 。則統(tǒng)。則統(tǒng)一目標(biāo)函數(shù)可按如下的平方和法來構(gòu)成：一目標(biāo)函數(shù)可按如下的平方和法來構(gòu)成：2(o)(o)1(X)(X)qiiiiffff 這意味著當(dāng)各項(xiàng)分目標(biāo)函數(shù)分別達(dá)到各自的理這意味著當(dāng)各項(xiàng)分目標(biāo)函數(shù)分別達(dá)到各自的理想最優(yōu)值時(shí)，統(tǒng)一目標(biāo)函數(shù)想最優(yōu)值時(shí)，統(tǒng)一目標(biāo)函數(shù) f(X) 為最小。此為最小。此法的關(guān)鍵在于選擇恰當(dāng)?shù)姆ǖ年P(guān)鍵在于選擇恰當(dāng)?shù)膄i(o) (i=1,2,q)值。值。(3)功效系數(shù)法如果每個(gè)分目標(biāo)函數(shù)如果每個(gè)分目標(biāo)函數(shù)fi(X) 都用一個(gè)稱為功效系都用一個(gè)稱為功效系數(shù)數(shù)i (i=1,2,q)并定義于并定義于0i1間的函數(shù)來表間的函數(shù)來表示該項(xiàng)設(shè)計(jì)指標(biāo)的好壞

59、示該項(xiàng)設(shè)計(jì)指標(biāo)的好壞(當(dāng)當(dāng)i=1時(shí)表示最好，時(shí)表示最好，i=0時(shí)表示最壞時(shí)表示最壞)，那么被稱作總功效系數(shù)，那么被稱作總功效系數(shù)的的這些系數(shù)這些系數(shù)(1,2,q)的幾何平均值的幾何平均值12qq12maxqq即表示該設(shè)計(jì)方案的好壞。因此，最優(yōu)設(shè)計(jì)方即表示該設(shè)計(jì)方案的好壞。因此，最優(yōu)設(shè)計(jì)方案應(yīng)是案應(yīng)是這樣，當(dāng)這樣，當(dāng)=1時(shí)，表示取得最理想的設(shè)計(jì)方案；時(shí)，表示取得最理想的設(shè)計(jì)方案；反之，當(dāng)反之，當(dāng)= 0時(shí)則表明這種設(shè)計(jì)方案不能接時(shí)則表明這種設(shè)計(jì)方案不能接受，這時(shí)必有某項(xiàng)分目標(biāo)函數(shù)的功效系數(shù)受，這時(shí)必有某項(xiàng)分目標(biāo)函數(shù)的功效系數(shù)i= 0 。fi(X)ii01.0ifi(X)ii01.0ii1.0fi(

60、X)i0i功效系數(shù)的函數(shù)曲線功效系數(shù)的函數(shù)曲線用總功效系數(shù)用總功效系數(shù)作為作為“統(tǒng)一目標(biāo)函數(shù)統(tǒng)一目標(biāo)函數(shù)” f(X) ：12(X)maxqqf這樣，雖然計(jì)算稍繁，但方法較為有效。因這樣，雖然計(jì)算稍繁，但方法較為有效。因?yàn)樗容^直觀且調(diào)整容易；其次是不論各個(gè)為它比較直觀且調(diào)整容易；其次是不論各個(gè)分目標(biāo)的量級及量綱如何，最終都轉(zhuǎn)化為分目標(biāo)的量級及量綱如何，最終都轉(zhuǎn)化為01間的數(shù)值，而且一旦有一項(xiàng)分目標(biāo)函數(shù)值不間的數(shù)值，而且一旦有一項(xiàng)分目標(biāo)函數(shù)值不理想理想(i= 0 )時(shí)，其總功效系數(shù)時(shí)，其總功效系數(shù)必為零，表明必為零，表明設(shè)計(jì)方案不可接受，需重新調(diào)整約束條件或設(shè)計(jì)方案不可接受，需重新調(diào)整約束條件或