現(xiàn)代設(shè)計方法5 優(yōu)化設(shè)計

1、優(yōu)優(yōu) 化化 設(shè)設(shè) 計計第五章第五章 優(yōu)優(yōu) 化化 設(shè)設(shè) 計計傳統(tǒng)機械設(shè)計中，存在選優(yōu)的思想，受時間、條件的限制，計算機應(yīng)用前用數(shù)學(xué)極小化處理簡單問題。隨著1946年第一臺計算機問世，傳統(tǒng)設(shè)計轉(zhuǎn)化為優(yōu)化設(shè)計方法。優(yōu)化設(shè)計是以數(shù)學(xué)規(guī)劃理論為基礎(chǔ)，以計算機為工具優(yōu)選設(shè)計參數(shù)的一種現(xiàn)代設(shè)計方法。5.1 優(yōu) 化 設(shè) 計 的 數(shù) 學(xué) 模 型v下面舉例說明： 用薄鋼板制造一體積為5m3，長度不小于4m不帶上蓋的貨箱，要求該貨箱的鋼板耗費量最小，試確定貨箱的長X1，寬X2，高X3。X2X1X3v解：鋼板的耗費量與貨箱的表面積成正比，優(yōu)化設(shè)計的目標(biāo)是鋼板的耗費量最少，即貨箱的表面積S最小，不帶蓋的貨箱表面積vS=

2、X1*X2+2(X2*X3+X1*X3)vS是X1、X2和X3的函數(shù)，稱為目標(biāo)函數(shù)。v參數(shù)X1、X2和X3稱為設(shè)計變量。v優(yōu)化設(shè)計就是恰當(dāng)?shù)剡x擇這些參數(shù)(設(shè)計變量)，使貨箱表面積S(目標(biāo)函數(shù))達到最小。v選擇這些參數(shù)受到貨箱體積和長、寬、高限制：vX1*X2*X3=5， X14,X2 0,X3 0v以上限制設(shè)計變量X1,X2,X3的表達式，稱為約束條件。v已知：傳動比i, 轉(zhuǎn)速n, 傳動功率P，大小齒輪的材料，設(shè)計該齒輪副，使其重量最輕。v分析：(1) 圓柱齒輪的體積(V)與重量(W)的表達；v (2)設(shè)計參數(shù)確定：模數(shù)(m)，齒寬(b)，齒數(shù)(z)。v (3)設(shè)計約束條件：v(a)大齒輪滿足

3、彎曲強度要求；v(b)小齒輪滿足彎曲強度要求；v(c)齒輪副滿足接觸疲勞強度要求；v(d)齒寬系數(shù)要求；v(e)最小齒數(shù)要求。例 問題的數(shù)學(xué)表達v設(shè)計變量： x = m z bTv設(shè)計目標(biāo)：min W=rpb(mz)2+(miz)2/4v約束條件： g1(x)=sF1sF10v g2(x)=sF2 sF20v g3(x)=sH sH10v g4(x)=b 1.2mz0v g5(x)=17 z0建立優(yōu)化設(shè)計問題的數(shù)學(xué)模型步驟v1)根據(jù)設(shè)計要求，應(yīng)用專業(yè)范圍內(nèi)的現(xiàn)行理論和經(jīng)驗等，對優(yōu)化對象進行分析分析。必要時，需要對傳統(tǒng)設(shè)計中的公式進行改進，并盡可以反映該專業(yè)范圍內(nèi)的現(xiàn)代技術(shù)進步的成果。v2)對結(jié)

4、構(gòu)諸參數(shù)進行分析，以確定設(shè)計的原始參數(shù)、設(shè)計常數(shù)和設(shè)計變量設(shè)計變量v3)根據(jù)設(shè)計要求，確定并構(gòu)造目標(biāo)函數(shù)和相應(yīng)的約束條約束條件件，有時要構(gòu)造多目標(biāo)函數(shù)v4)必要時對數(shù)學(xué)模型進行規(guī)范化規(guī)范化，以消除諸組成項間由于量綱不同等原因?qū)е碌臄?shù)量懸殊的影響5.1.1. 數(shù)學(xué)模型的一般形式：優(yōu)化設(shè)計的數(shù)學(xué)模型由設(shè)計變量、目標(biāo)函數(shù)和約束條件三部分組成。統(tǒng)一形式： 求變量： x1, x2, , xn使極小化函數(shù)： f (x1, x2, xn)滿足約束條件：gu(x1, x2, , xn)0 (u=1,2, ,m) 不等式約束條件 hv(x1, x2, , xn)=0 (v=1,2, ,p) 等式約束條件 v設(shè)計

5、變量可用向量表示：v X= x1, x2, , xnTv XRn 向量X屬于n維實歐氏空間v s.t. (subject to)表示 “滿足于” 。v優(yōu)化設(shè)計的數(shù)學(xué)模型可表達為如下的標(biāo)準形式： min f (X ) XRns.t. gu(X )0 (u=1,2, ,m) hv(X ) = 0 (v=1,2, ,p)v求極大時將目標(biāo)函數(shù)寫為f(X)即可。同樣，當(dāng)不等式約束條件中的不等號為“0”時，只要將不等式兩端同時乘以“1”，即可得到上述標(biāo)準形式。 v最優(yōu)化問題也稱數(shù)學(xué)規(guī)劃問題，若目標(biāo)函數(shù)和約束函數(shù)均為設(shè)計變量的線性函數(shù)時，稱此設(shè)計問題為線性優(yōu)化問題或線性規(guī)劃問題。說明：(1) 設(shè)計變量與設(shè)計

6、空間v選擇與目標(biāo)函數(shù)、約束函數(shù)密切相關(guān)，能表達設(shè)計對象特征的獨立參數(shù)和尺寸。vn個設(shè)計變量x1, x2, , xn，相互獨立，形成向量X=x1, x2, , xnT的全體集合構(gòu)成一個n維實歐氏空間，稱設(shè)計空間xn，n稱為設(shè)計空間的維數(shù)。n=2時設(shè)計空間為二維平面。5.1.2. 優(yōu)化設(shè)計的基本要素： 約束條件：對設(shè)計變量取值時的限制條件。分為：等式約束： hv(X)=0 (v=1,2, ,p) 不等式約束：gu(X)0 (u=1,2, ,m) 約束邊界所包圍的區(qū)域是設(shè)計空間中滿足所有不等式約束條件的部分，在這個區(qū)域中所選擇的設(shè)計變量是允許的，稱為設(shè)計可行域。 由是否滿足約束條件將設(shè)計點分為可行點

7、(內(nèi)點)和非可行點(外點)。(2)約束條件與可行域vg1(X)=x1+x220vg2(X)=x12x2+10vg3(X)=x10例：x1x2可行域可行域g2(x)g2(x) = 0g3(x) = 0g1(x) = 0將所追求的設(shè)計目標(biāo)用設(shè)計變量的形式表達出來，稱為建立目標(biāo)函數(shù)。一組設(shè)計變量值在設(shè)計空間確定一個設(shè)計點，對應(yīng)這一點有確定的函數(shù)值。反之，當(dāng)函數(shù)為某一定值時，如f (X ) = c,則可有無限多組設(shè)計變量X1, X2, , Xn值與之對應(yīng)，即有無限多個設(shè)計點時對應(yīng)著相同的函數(shù)值。因此這些點在設(shè)計空間中將組成一個點集，將此點集稱為等值曲面或等值超曲面(若為二維設(shè)計空間則稱為等值域)。(3

8、)目標(biāo)函數(shù)與等值域v簡單二維問題，在平面內(nèi)作出約束可行域，畫出目標(biāo)函數(shù)的等值域，找出最優(yōu)點。v步驟：確定設(shè)計空間約束可行域目標(biāo)函數(shù)等值線最優(yōu)點v例： min f(X)=x12+x224x1+4 s.t. g1(X) = x1+x220 g2(X) = x12x2+10 g3(X) = x105.1.3 優(yōu)化問題的圖解法圖解法vmin f (X )=x12+x22 4x1+4v s.t. g1(X) = x1+x220v g2(X) = x12x2+10v g3(X) = x10 x1x20123451234f (X ) = 16f (X ) = 1g3(x)g2(x)g1(x)f (X ) =

9、 9X* = 0.58, 1.34T65.2 優(yōu)化方法的數(shù)學(xué)基礎(chǔ)5.2.1 梯度(求解出數(shù)的最速下降方向)v定義下列向量： 為函數(shù)f(X)在X(k)點的梯度，簡記為f，也可記作grad f(X(k)。TnkkkkxXfxXfxXfXf)(,.,)(,)()()(2)(1)()(v(1)函數(shù)在一點的梯度是對設(shè)計變量Xi(i=1, 2, n)一階偏導(dǎo)組成的列向量。表示函數(shù)在X(k)點的最陡上升方向，是函數(shù)的一種局部性質(zhì)。反映X(k)鄰近函數(shù)的性質(zhì)，梯度大小是其模長。v(2)梯度向量f (X(k)與過X(k)點的等值線(或等值面)的切線是正交的。函數(shù)的梯度f具有如下幾個性質(zhì)：函數(shù)的梯度f具有如下幾個

10、性質(zhì)：v(3)負梯度向量f (X(k)是函數(shù)在X(k)點的最速下降方向。v例：求二元函數(shù)f (x1, x2)= x12+x224x1+2x2+5在 X0=2，2T處的梯度及梯度的模。vf(X) 的泰勒二階近式。v其中2f(X(k)是由函數(shù)在點X(k)的所有二階偏導(dǎo)組成的矩陣，稱為函數(shù)f(X)在點X(k)的二階導(dǎo)數(shù)矩陣或Hessian矩陣H(X(k)。( )( )( )( )2( )( )()()() )1)()2kkTkkTkkf Xf Xf XXXXXf XXX 5.2.2 多元函數(shù)的泰勒展開(函數(shù)的近似表達式)v函數(shù)的二階偏導(dǎo)值對于變量的偏導(dǎo)次序無關(guān)，是一nn階實對稱矩陣。取其前二項，可得

11、函數(shù)的泰勒線性近似式：v f(X)f(X(k)+f(X(k)TXX(k)2( )2( )2( )211212( )2( )2( )2( )221222( )2( )2( )212()()()()()()()()()()kkknkkkknkkknnnf Xf Xf Xxx xx xf Xf Xf Xf Xx xxx xf Xf Xf Xxxxxx v 解：f (X(1) = 3211(1)212213690()336xxf Xxx 12(1)12166 012 0()0660 0 xf Xx 11(1)221111xxXXxx 例：用泰勒展開將函數(shù)f(X)=x13x23+3x12+3x229x1

12、在點X(1)=1，1T 簡化成線性函數(shù)和二次函數(shù)。v代入得簡化的線性函數(shù)：二次項：(1)(1)(1)122()()()130 3136Tf Xf Xf XXXxxx (1)2(1)(1)1122211()2112011110026(1)TXXfXXXxxxxx v 簡化的二次函數(shù)：vf(X)=3x26+6(x11)2=6x1212x1+3x2vX(1)=1,1T代入線性二次函數(shù)都等于3，與原函數(shù)相等。5.2.3.二次函數(shù)：v形式：f (X ) = X T H X / 2 + B X + CvH22階常數(shù)矩陣vC常數(shù)向量vXTHX稱為二次型，H稱二次型矩陣，相當(dāng)于函數(shù)的二階導(dǎo)數(shù)矩陣。v對于非零向

13、量X： 若 XTHX 0 H 正定 XTHX0 H 半正定 XTHX0v各階主子式大于0是正定矩陣。*20()02H x20002v在 X*處取得極值，其必要條件是:v即在極值點處函數(shù)的梯度為n維零向量。v為了判斷從上述必要條件求得的 X*是否是極值點，需建立極值的充分條件。v根據(jù)函數(shù)在 X*點處的泰勒展開式，考慮上述極值必要條件，可得相應(yīng)的充分條件。12()0TXnffff Xxxxv即要求H(X*)各階主子式均大于零。2*2*2*211212*2*2*2*221222*2*2*212()()()()()()()()()()nnnnnf Xf Xf Xxx xx xf Xf Xf Xf Xx

14、 xxx xf Xf Xf Xxxxxx 正定(1)概念：v對于多變量、多約束非線性優(yōu)化問題，采用數(shù)值迭代法；對于極小化問題，采用下降迭代法。初始X(0)產(chǎn)生點列： X(0), X(1), X(2), X(k), X(k+1)v對應(yīng)目標(biāo)函數(shù)： f(X(0) f(X(1) f(X(k) f(X(k+1) (下降) 且 lim X(k)= X*(目標(biāo)函數(shù)極小點)滿足此條件的下降迭代算法具有收斂性，稱點列收斂于極小點X*。5.2.4 下降迭代法：v 優(yōu)化迭代算法格式： X (k+1) = X (k) + a S(k)式中 S(k)搜索方向 a 步長因子 (2)格式：vX(k+1)取S(k)上的一維極

15、小點，對應(yīng)于最優(yōu)步長因子ak。(1)給定初始點 X(k) 和收斂精度e；(2)選取搜索方向S(k);(3)確定步長因子ak得到X(k+1);(4)收斂判斷 X(k+1)滿足收斂精度， X(k+1)作為最優(yōu)點終止，否則重復(fù)(2)。故迭代算法的核心在于：v(1)確定搜索方向S(k) ;v(2)確定步長因子a；v(3)給定收斂準則。5.3 一 維 搜 索 法 v求解一維目標(biāo)函數(shù)f(a)的極小點和極小值的數(shù)值迭代方法稱為一維搜索方法。v從點X(k)出發(fā)，在方向S(k)上的一維搜索數(shù)學(xué)表達式： min f(X(k)+ a S(k) ) =f(X(k) +ak S(k) ) X(k+1)=X(k)+ ak

16、 S(k) X(k)akS(k)X(k+1)v一維優(yōu)化目的是在既定的X(k)和S(k)下尋求最優(yōu)步長a(k)使迭代產(chǎn)生新點X(k+1)的函數(shù)值最小。v一維優(yōu)化一般分為兩大步：(1).確定初始搜索區(qū)間a,b,該區(qū)間應(yīng)是包括一維函數(shù)極小值點的單峰區(qū)間。(2).在搜索區(qū)間a,b內(nèi)尋找極小點。v進退法思路： 由單峰函數(shù)性質(zhì)可知，在極小點a*左邊函數(shù)值應(yīng)嚴格下降，在極小值點右邊函數(shù)值應(yīng)嚴格上升。由此，可以某一個給定的初始點x0出發(fā)，以初始步長h0沿著目標(biāo)函數(shù)值下降方向，逐步前進(或后退)，直至找到相繼的3個試點的函數(shù)值按大小大變化為止。5.3.1.確定搜索區(qū)間的方法：進退法進退法確定搜索區(qū)間的步驟如下：

17、(1)給定初始點x0和初始步長h；(2)令x1=x0 , x2=x1+h 得兩試點x1，x2計算函數(shù)值 f1=f(x1) f2=f(x2);(3)比較f1和f2 ，存在兩種情況：F f1 f2F f1f2若存在f1f2 ，取第3個試點x3=x2+h ，計算函數(shù)值 f3=f(x3)，比較f2 與f3 ：若f2 f3 ，則找到了x1，x2，x3的函數(shù)值按大小大變化的要求。故有搜索區(qū)間a, b= x1, x3；f3x1xf(x)0hhf2f1x3x2 若f2 f3，將步長加倍，令h=2h ，x1=x2 , x2=x3 , x3=x2+h ，如此重復(fù)該過程，總能找到相繼3試點的函數(shù)值符合“大-小-大”

18、變化的要求。取左端點為a,右端點為b,從而找到搜索區(qū)間a, b。f3x1xf(x)0hhf2f1x3x22h 若f2 f3，將步長加倍，令h=2h ，x1=x2 , x2=x3 , x3=x2+h ，如此重復(fù)該過程，總能找到相繼3試點的函數(shù)值符合“大-小-大”變化的要求。取左端點為a,右端點為b,從而找到搜索區(qū)間a, b。f3x1xf(x)0hhf2f1x3x22h若f2f1 作后退計算。令h=h,將x1，f1 與x2 ，f2 對調(diào)，并取第3個試點x3=x2+h ，計算其函數(shù)值f3= f(x3),比較對調(diào)后的f2 與f3 ：x1xf(x)0hf2f1x2f3hx3v若f2f3，a,b= x3,

19、 x1;v若f2 f3，將步長加倍，繼續(xù)作后退運算，令h=2h，x1=x2, x2=x3, x3=x2+h，繼續(xù)比較f2與f3，直到相繼3個試點的函數(shù)值按“大-小-大”變化為止，相應(yīng)的區(qū)間為x3, x1。f3x1xf(x)0hhf2f1x3x22h找到搜索區(qū)間后，便可運用一維優(yōu)化算法在區(qū)間內(nèi)找到極小點。例： 用進退法確定f(x)=x27x+10 的初始搜索區(qū)間。設(shè)初始點x0=0 ,初始步長h=1。解： x1=x0=0 f1= f(x1)=10 x2=x1+h=1 f2= f(x2)=4 比較f1 ，f2 ，因f2 f3 ,作前進運算 h=21=2 x1=x2=1 f1 = f2 =4 x2=x

20、3=2 f2 = f3=0 x3=x2+h=4 f3= f(x3) = 2 比較f2 ，f3 ，因f2 f3 ,作前進運算 h=22=4 x1=x2=2 f1 =f2=0 x2=x3=4 f2 =f3=2 x3=x2+h=8 f3=f(x3)=18 此時：x1, x2, x3 三點的函數(shù)值出現(xiàn)了大小的變化，故a=x1=2, b=x3=8 求得初始搜索區(qū)間a,b=2,8v是通過不斷縮短搜索區(qū)間的長度來尋求一維函數(shù)f(x)的極小點。v原理是：在搜索區(qū)間a,b內(nèi)取兩點x1和x2 (x1 x2)： f(x1) f(x2)，極小點在x1和b間，消去區(qū)間a, x1，得到縮小后新區(qū)間x1,bv不斷重復(fù)上述過

21、程，當(dāng)區(qū)間長度baf2 。極小點必在區(qū)間x1 ,b內(nèi)，消去區(qū)間a,x1,令a=x1，產(chǎn)生新區(qū)間x1,b，區(qū)間收縮了一次。新區(qū)間的x1點與原區(qū)間x2點重合，令x1=x2，f1=f2 ，這樣可節(jié)省一次函數(shù)計算。ax1bf1f2x2 (2) 若f1f2。極小值點在區(qū)間a,x2內(nèi)，消去區(qū)間x2,b，令b=x2產(chǎn)生新區(qū)間a,b，區(qū)間縮短一次。同時，新區(qū)間x2點與原區(qū)間的x1點重合，令x2=x1，f2 =f1。當(dāng)縮短的新區(qū)間長度小于等于某一精度e，即bae 時取為近似極小點x*=(a+b)/2。ax1bx2f1f2L(1l)LlLabx1x2(1l)LLabx1x2lLLabx1x2(II) 黃金分割法的

22、區(qū)間收縮率lv每次縮小所得的新區(qū)間長度與縮小前區(qū)間長度之比，稱為區(qū)間收縮率，以l表示。v黃金分割法收縮率保持不變，0.618v0.618n(ba)ev 解： (1)采用上節(jié)所求初始區(qū)間a,b=2,8取兩計算點并計算出數(shù)值。 x1=a+0.382(ba)=4.292 f1= f(x1)=1.622736 x2=a+0.618(ba)=5.708 f2= f(x2)=2.625264 (2)比較函數(shù)值，縮短搜索區(qū)間 f1e不滿足，繼續(xù)縮短區(qū)間。 各次縮短區(qū)間有關(guān)計算數(shù)據(jù)如下表：abx1 x2f1f2ba0284.292 5.708 1.6227 2.6253 6125.708 3.416 4.29

23、2 2.24302 1.623 3.708 224.292 2.976 3.416 1.975 2.243 2.29232.975544 4.292 3.414 3.789 2.243 2.166 1.31642.975544 3.7891143.286 3.416 2.2043 2.243 0.813653.286328 3.789114 3.416 3.597 2.2430 2.241 0.502863.286328 3.59705 3.405 3.416 2.24098 2.243 0.3107(3)判斷迭代終止條件 可見，區(qū)間縮短6次后： 區(qū)間長度為：ba=0.3107f2 加大步長向

24、前探測。令 x3=x0+2h=2 f3= f(x3)=18 f2f3，初始區(qū)間找到a,b=0,2。 (2) 用黃金分割法縮小區(qū)間 1) 第一次 x1=0+0.382(20)=0.764 f1=0.282 x2=0+0.618(20)=1.236 f2=2.72 由于f10.2 應(yīng)繼續(xù)縮小。 2) 第二次 x2=x1=0.764 f2 =f1=0.282 x1=0+0.382(1.2360)=0.472 f1=0.317 由于f1 f2 ， a,b=x1 ,b=0.472,1.236 ba=1.2360.472=0.7640.2 應(yīng)繼續(xù)縮小。3) 第三次 f1f2 x1=x2=0.764 f2

25、=f1=0.28 x2=0.472+0.618(1.2360.472)=0.944 f2=0.747 f10.2 4) 第四次 x2=x1=0.764 f2 =f1=0.282 x1=0.472+0.382(0.9440.472)=0.652 f1=0.223 f10.2 5 )第五次 x2=x1=0.652 f2 =f1=0.223 x1=0.472+0.382(0.7640.472)=0.584 f1=0.262 f1f2 故a,b=x1, b=0.584, 0.764 ba=0.7640.584=0.18f2 f2xpx2x1x3f pf 2x1fp f2(1)確定初始搜索區(qū)間a,b和精

26、度e； (2)在區(qū)間a,b內(nèi)取3點：x1=a, x2=0.5(a+b), x3=b計算它們的函數(shù)值f1= f(x1), f2= f(x2), f3= f(x3)構(gòu)成 3個插值點p1(x1, f1), p2(x2, f2)和p3(x3, f3)。(3)計算二次插值函數(shù)的極小值點xp，計算fp= f(xp)。若本步驟為第一次插值或x2點為初始給定點時，說明x2和xp不代表前后兩次插值函數(shù)的極小點，不能進行終止判斷，進行下一步；否則轉(zhuǎn)(5)。(II)二次插值法的迭代過程(4)縮小搜索區(qū)間v比較f2 、fp ，取其小者所對應(yīng)點為新的x2點，以此點左右鄰點為新的x1 、x3 ，構(gòu)成新的搜索x1, x3x

27、3xpx2x1f pf 2x2x3fpf2xpx2x1x3f pf 2x1x2fpf2(a)xpx2x1x3f pf 2x3fp f2xpx2x1x3f pf 2x1fp f2(b)(5)判斷是否滿足精度要求v|x2 xp |e , |f2 fp|e停止，取x2與xp 中原函數(shù)值較小的點作為極小點，否則返回(4)縮短區(qū)間直至滿足要求。v例：用二次插值法求f(x)=x27x+10的最優(yōu)解，已知初始區(qū)間為2, 8，取終止迭代點距精度e =0.01。 解: (1)確定初始插值結(jié)點 x1=a=2， f1= f(x1)=0 x3=b=8, f3= f(x3)=18 x2=4, f2= f(x2)=2 (

28、2) 計算插值函數(shù)極小點 xp=0.5(x1+ x3c1/c2)=3.5 fp= f(xp) =2.25 |xp x2|e (需要再次迭代)v(3)縮短搜索區(qū)間 由于f2 fp , xp x2 故x3=x2=5 f3 =2 x2=xp=3.5 f2=2.25 x1=2 f1=0 計算xp=3.5 fp=2.25 xp x2=0e x*= xp=3.5 f*= f(xp)=2.25 二次函數(shù)用二次插值，只需一次計算。v 收斂速度快，有效性好，程序復(fù)雜，可靠性差，適應(yīng)于多值優(yōu)化的一維搜索迭代。v例5.6 用二次插值法求解f(x)=3x34x+2的極小點，x0=0, h=1, e =0.2 解：(1

29、)初始區(qū)間0, 2，另取中點x2=1。 (2)用二次插值法逼近最小點。 x1=0, x2=1, x3=2 得： f1= 2, f2= 1, f3=18得 xp=0.555 fp=0.292 ：v fpf2 , xp0.2, 作二次插值。 在新的區(qū)間內(nèi): x1=0, x2=0.555, x3=1, f1= 2, f2=0.292, f3=1 將其代入得： xp=0.607 fp=0.243 fpx2 a, b=x2, b=0.555, 1 |x2xp| = |0.5550.607|=0.0520.2 故極小值和極小值點為： x*= xp=0.607 f*=0.243 二次插值的收斂速度比黃金分割

30、快得多。5.4 多 維 優(yōu) 化 方 法v多維優(yōu)化方法是進行多變量優(yōu)化設(shè)計的數(shù)值迭代法，有無約束優(yōu)化和約束優(yōu)化兩方面內(nèi)容。v無約束優(yōu)化方法可分為兩類：利用目標(biāo)函數(shù)的一階和二階導(dǎo)數(shù)的信息構(gòu)造搜索方向的算法，稱為導(dǎo)數(shù)法，如梯度法、共軛梯度法。另一類是通過已知點上函數(shù)值的比較構(gòu)造搜索方向的算法，稱為模式法，如Powell法 v約束優(yōu)化方法分為直接法和間接法： 迭代過程逐點考察約束，使迭代點始終局限于可行域內(nèi)的算法稱為直接法，如可行方向法、復(fù)合形法等； 將約束條件引入目標(biāo)函數(shù)，將約束優(yōu)化問題轉(zhuǎn)化為無約束問題求解的算法稱為間接法，如懲罰函數(shù)法。5.4.1 梯 度 法 vI.基本原理v 在迭代過程的某一點X

31、(k)處，目標(biāo)函數(shù)的負梯度方向f(X(k)是函數(shù)的最速下降方法，利用這一性質(zhì)，將n維無約束極小化問題轉(zhuǎn)化為一系列沿目標(biāo)函數(shù)負梯度方向進行一維搜索尋優(yōu)的一種方法，即是在每一迭代點X(k)，選取搜索方向S(k)為負梯度方向： S(k)=f(X(k)或)()()()()(kkkXfXfSv沿S(k)進行一維搜索，以確定步長因子a(k)，找到新的設(shè)計點X(k+1)=X(k)+a(k)S(k)v梯度法的迭代公式可寫成：v X(k+1) = X(k)a(k) f(X(k)v 或v按照上述迭代公式進行一維搜索；每次迭代的初始點取上次迭代的終點，即可使迭代點逐步逼近目標(biāo)函數(shù)極小點。)()()()()()()1

32、(kkkkkXfXfXXaII.梯度法的特點)0(X)1(X)2(X)3(X*X*x)()0(xf)0(x v每次沿迭代點函數(shù)值下降最快的方向搜索，稱最速下降法。v缺點：曲折，收斂速度慢。v 對于圓一次可達。v 不是圓時，負梯度方向不指向圓心，迭代次數(shù)增加，偏心嚴重，迭代次數(shù)多，形成“鋸齒現(xiàn)象”，開始步長大，愈接近極小點步長小，收斂慢。v優(yōu)點：迭代過程簡單，對初始點要求不高，只要計算導(dǎo)數(shù)，只求一階，存儲單元少。5.4.2 共 軛 梯 度 法 vI. 共軛方向的概念與性質(zhì)v 設(shè)H為一正定對稱矩陣，若有一組非零向量S1 , S2 , Sn滿足：SiTHSj=0稱這組向量關(guān)于矩陣H共軛。若H為單位陣

33、，SiTSj=0 (ij)稱向量Si (i=1,2,n)正交。v X=x1 , x2T 任選初始點X(0)并沿梯度方向S(0)作一維搜索得： X(1)= X(0)+a0 S(0) X(1)的梯度與S(0)垂直，故： f(X(1)T S(0)=0 (1) 求式(1)點X(1)的梯度 f(X(1)=HX(1)+B 從X(1)沿某一下降方向S(1)作一維搜索，同理可得： X(2)= X(1)+a1S(1) f(X(2)=HX(2) +BCXBHXXxfTT21)(例v欲使X(2)成為極小點，則根據(jù)極值必要條件，有： f(X(2)=HX(2)+B=0 H(X(1)+a1S(1)+B=0 f(X(1)+

34、 a1HS(1)=0 上式左乘 S(0)Tf(X(1)+ a1S(0)T HS(1)=0 由a10得： S(0)T HS(1)=0 即要使迭代點X(2)成為正定二元二次函數(shù)的極小點，只需使兩次一維搜索方向S(0)和S(1)關(guān)于函數(shù)的二階導(dǎo)數(shù)矩陣H為共軛。v(1)若S(i) (i=1,2,n)是以H共軛的n個向量，則對于正定二次函數(shù)以任意初始點X(0)出發(fā)，依次沿n個方向進行一維搜索，最多n次即可達到極小點。 v(2)以任意兩個點X1(0) 與X2(0)出發(fā)，沿同一方向S(0)進行一維搜索，可得到兩個一維極小點X1(1)與X2(1) ，則兩點構(gòu)成向量v S(1)= X1(1) X2(1)與原方向

35、S(0)關(guān)于該函數(shù)的二階導(dǎo)數(shù)共軛。 共軛方向性質(zhì)：共軛方向性質(zhì)：a0 S(0)X(1)S(1)a1S(1)f(X(1)S(1)S(0)X(0)v由X(k)出發(fā)，負梯度方向作一維搜索:v S(k) = f(X(k) v X(k+1) = X(k) + akS(k)v設(shè)與S(k)共軛的一個方向S(k+1)由S(k)和X(k+1)的負梯度方向的線性組合而成，故有：v S(k+1)=f(X(k+1)+ bkS(k) (3)令 f (X) = XTHX/2+BTX+C為函數(shù)的二次展開式。 II. 共軛梯度方向v則： f(X(k)=HX(k)+Bv f(X(k+1)=HX(k+1)+B （4）v相減代入

36、X(k+1)= X(k) + akS(k)，得：v akHS(k)= f(X(k+1)f(X(k)v 將(3)式與上式兩邊相乘，由共軛條件得：vf(X(k+1)+ bk f(X(k)Tf(X(k+1)f(X(k)=0v展開由相鄰兩點梯度的正交關(guān)系，整理得：v共軛梯度法迭代基本式v以相鄰兩點的梯度可以構(gòu)造一個共軛方向。以這種方式產(chǎn)生共軛方向并進行迭代運算的算法稱為共軛梯度法。2)(2)1()()()1()1()()()()()()(kkkTkkTkkXfXfXfXfXfXfb(1)( )( )2(1)2( )(1)(1)( )()()()kkkkkkkkkkkXXSf Xf XSf XSabb

37、v(1)給定初始點給定初始點X(0)和收斂精度和收斂精度e e。 v(2)取取X(0)的負梯度作為搜索方向的負梯度作為搜索方向S(0)= f(X(0)，置置k = 0。 v(3)沿方向沿方向S(k)作一維搜索得：作一維搜索得：v X(k+1)= X(k)+ a akS(k)v(4)收斂判斷：若收斂判斷：若 f(X(k+1)e e 則令：則令：v X*= X(k+1), f(X*)=f(X(k+1) v結(jié)束迭代；否則轉(zhuǎn)結(jié)束迭代；否則轉(zhuǎn)(5)。III. 共軛梯度法的迭代步驟(5)若若k+1=n(檢驗迭代次數(shù)，對于檢驗迭代次數(shù)，對于n值目標(biāo)函數(shù)，值目標(biāo)函數(shù)，理論上通過理論上通過n次可得最優(yōu)點，由于計

38、算機舍入誤次可得最優(yōu)點，由于計算機舍入誤差及目標(biāo)函數(shù)性態(tài)的特殊性。往往迭代差及目標(biāo)函數(shù)性態(tài)的特殊性。往往迭代n次達不次達不到精度要求。此時將到精度要求。此時將X(n)作為作為X(0)返回從第一步計返回從第一步計算，有助于消除累積計算誤差的影響，并且對非算，有助于消除累積計算誤差的影響，并且對非二次目標(biāo)函數(shù)值保證具有良好的收斂性二次目標(biāo)函數(shù)值保證具有良好的收斂性)，則令，則令X(0)= X(k+1)轉(zhuǎn)轉(zhuǎn)(2)，否則轉(zhuǎn)，否則轉(zhuǎn)(6)。v v S(k+1)= f(X(k+1)+b bkS(k)v 令令k=k+1 轉(zhuǎn)轉(zhuǎn)(3)。2)(2)1()()(kkkxfxfb(6)構(gòu)造新的共軛構(gòu)造新的共軛 例：用

39、共軛梯度法求解下列無約束優(yōu)化問題X(0)=1,1T，e =0.1v min f(X)=x12 +2x22 2x1x2 4x1v解：2424422)()0(1221) 0(XxxxxXf24)()0()0(XfS aaa2141)0()0()0()1(SXXv第一次沿S(0)方向進行一維搜索，求近似極值點v代入f(X)=(1+4a(0)2+2(12a(0)22(1+4a(0)(12a(0)4(1+4a(0) v令df(a(0)/da(0)=0，得a(0)=0.25。v由此得：5 . 02)1(X2124422)()1(1221)1(XxxxxXf進行第二次搜索的共軛方向為：41205)()(2)

40、0(2)1(0 xfxfbv再沿S(1)方向進行一維搜索得：5 . 12244121)()0()0()1()1(SXfSb)1()1()1()1()1()1()2(5 . 15 . 0225 . 125 . 02aaaaSXXv代入f(x) ，令df(a(1)/da(1)=0，得a(1)=1 0024442)(24)2(1221)2()2(XxxxxXfXv因f(X(k+1)e， X(2)滿足極值條件，X(2)是極小點， f(X*)=8v共軛梯度法兩次迭代可求得二元二次優(yōu)化問題極小點。5.4.3 鮑鮑 威威 爾爾 法法v 兩次平行搜索產(chǎn)生一個共軛方向，Powell法就是利用平行搜索逐漸構(gòu)造共軛

41、方向和共軛方向組的方法，能在有限步長內(nèi)極小化一個二次函數(shù)，是直接搜索方法中使用效果最佳的一種方法。對于維數(shù)n20的目標(biāo)函數(shù)求最優(yōu)化問題。此法可獲得滿意效果。v 原始的Powell法是沿著逐步產(chǎn)生的共軛方向進行一維搜索的。v 以二維二次目標(biāo)函數(shù)為例來說明。選定初始點X0(1)，初始方向e(0)=1,0T, e(1)= 0,1T，從X0(0)出發(fā)依次沿e(0)、e(1)進行一維搜索，求得各自方向上的極值點X0(1)，X0(2)，連接點X0(0)和最后一個極值點X0(2) ，構(gòu)成第三個新方向： S(0)= X0(2)X0(0)I.基本迭代格式、原理：S(1)S(0)e(1)S(0)e(1)e(0)x

42、1x2X0(1)X0(2)X0(3)X1(0)X1(1)X1(2)X1(3)X0(0)vS(0)稱為模式方向稱為模式方向，再沿，再沿S(0)方向進行一維搜方向進行一維搜索得該方向上的近似極值點索得該方向上的近似極值點X0(3) ，搜索過程，搜索過程就完成了一個循環(huán)。就完成了一個循環(huán)。v以第一循環(huán)迭代的終點以第一循環(huán)迭代的終點X0(3)作為第二循環(huán)迭作為第二循環(huán)迭代的起點代的起點X1(0) ，棄去上一個循環(huán)向量組中的棄去上一個循環(huán)向量組中的第一個方向第一個方向e(0)，將新方向，將新方向S(0)補在最后，構(gòu)成補在最后，構(gòu)成第二個循環(huán)的搜索方向組第二個循環(huán)的搜索方向組e(1), S(0)。v分別沿

43、分別沿e(1), S(0)一維搜索一維搜索求得近似極值點求得近似極值點X1(1), X1(2) ，連接連接X1(0)與與X1(2)，構(gòu)成第二個循環(huán)的一個新方向：，構(gòu)成第二個循環(huán)的一個新方向： S(1)= X1(2)X1(0)v沿沿S(1) 方向作一維搜索所得的近似極值點方向作一維搜索所得的近似極值點X1(3)即為即為第二循環(huán)的最終迭代點，也是下一次迭代的起始點。第二循環(huán)的最終迭代點，也是下一次迭代的起始點。由由圖可知點圖可知點X0(3)(X1(0)，X1(2)是先后兩次沿是先后兩次沿S(0)方向方向一維搜索的極小點。由共軛性質(zhì)知：連接一維搜索的極小點。由共軛性質(zhì)知：連接X1(0) ，X1(2)

44、構(gòu)成的矢量構(gòu)成的矢量S(1) 與與S(0)相共軛。相共軛。v 經(jīng)過二次循環(huán)后，迭代點由初始點經(jīng)過二次循環(huán)后，迭代點由初始點X0(0)依依次沿次沿S(0) ，S(1)方向一維搜索，經(jīng)方向一維搜索，經(jīng)X0(3)(X1(0)到到達達X1(3) ，從理論上講，二維二次正定函數(shù)經(jīng)，從理論上講，二維二次正定函數(shù)經(jīng)過這組共軛方向的一維搜索，迭代點已達到過這組共軛方向的一維搜索，迭代點已達到函數(shù)的極小點函數(shù)的極小點X*。將此結(jié)構(gòu)推廣至。將此結(jié)構(gòu)推廣至n維二次正維二次正定函數(shù)，即依次沿定函數(shù)，即依次沿n個個(S(0) ，S(1)，S(n1)共軛方向一維搜索就能達到極小點。共軛方向一維搜索就能達到極小點。Pk:e

45、(k)e(k+1)e(k+2)e(n-1)S(0)S(0)S(k-1)Pk+1: e(k+1)e(k+2)e(n-1)S(0)S(0)S(k-1)S(k)e(1)e(2)e(3)X0(2)X0(0)X0(1)X0(3)S(0)e(1)e(2)e(3)X0(2)X0(0)X0(1)X0(3)S(0)退化原始Powell法存在的問題：v 目前使用目前使用修正算法修正算法，和原始，和原始Powell法的法的主要區(qū)別：主要區(qū)別：在構(gòu)成第在構(gòu)成第k+1次循環(huán)方向組時，不用淘汰前一循環(huán)中次循環(huán)方向組時，不用淘汰前一循環(huán)中的第一個方向的第一個方向S1(k)的辦法，而是首先解決是否要替換的辦法，而是首先解決是

46、否要替換和替換哪個方向的問題。和替換哪個方向的問題。v為此，在得到新方向為此，在得到新方向v Sk(n)= Xk(n)Xk(0) 后后v沿沿Sk(n)找出找出Xk(0) 的的反射點反射點Xk(n+2)： Xk(n+2)=2Xk(n) Xk(0)Xk(0)f3D2Xk(1)Xk(n)Xk(n+2)f2f1x1Sk(n)x2D1v計算三點的函數(shù)值：計算三點的函數(shù)值：f1=f(Xk(0)；f2=f(Xk(n)；f3=f(Xk(n+2)v找出前一輪迭代法中找出前一輪迭代法中函數(shù)值下降最多的方向函數(shù)值下降最多的方向m及及下降下降量量m，即：即： vm = max f(Xk(i) f(Xk(i+1) =

47、f(Xk(m1) f(Xk(m)v可以證明：若可以證明：若 f3f1 與與 (f12f2+f3)(f1f2m)20.5m(f1f3)2同時成立。同時成立。則表明方向則表明方向Sk(n)與原方向組成線性無關(guān)，與原方向組成線性無關(guān)，可可以用來替換以用來替換。替換對象就是替換對象就是m所對應(yīng)的方向所對應(yīng)的方向Sk(m)。Xk(0)f3D2Xk(1)Xk(n)Xk(n+2)f2f1x1Sk(n)x2D1Pk:Sk(0)Sk(1)Sk(m-1)Sk(m)Sk(m+1)Sk(n-1)Pk+1:Sk+1(0)Sk+1(1)Sk+1(m-1)Sk+1(m)Sk+1(n-2)Sk(n)v替換算式替換算式: Sk

48、+1(i)= Sk(i) (im) Sk+1(i-1)= Sk(i) (i=m+1, m+2, n-1,) Sk+1(n-1)= Sk(n)v新一輪迭代起點：新一輪迭代起點： Xk+1(0) = Xk(n+1)Sk+1(n-1)Xk(0)f3D2Xk(1)Xk(n)Xk(n+1)Xk(n+2)f2f1X1Sk(n)X2D1v上述兩個條件上述兩個條件不不成立，則表明與原方向組中某些方成立，則表明與原方向組中某些方向線性相關(guān)，因此向線性相關(guān)，因此不不進行方向替換。此時仍用原方進行方向替換。此時仍用原方向組進行第向組進行第k+1輪搜索。輪搜索。v Sk+1(i)= Sk(i) (i=0, 1, n-

49、1,)v第第k+1輪搜索初始點的取法？輪搜索初始點的取法？ 若若 f2f3，Xk+1(0) = Xk(n)； 否則，否則，Xk+1(0) = Xk(n+2)；v步驟：步驟：P177頁頁Xk(0)f3D2Xk(1)Xk(n)Xk(n+2)f2f1X1Sk(n)X2D1v例：試用Powell法求f(X)=x12+2x22 4x1 2x1x2的最優(yōu)解。X0=1,1T ,收斂精度e =0.05。 110111) 0(0) 0(0) 0() 0(0) 0(0) 1 (0aaaeXX110)0(0XXv解： f1=f(X0(0)=3 v第一次循環(huán)：沿坐標(biāo)軸方向e(0)進行一維搜索：v代入f(X), f(X

50、)=(1+a0(0)2+24(1+a0(0)2(1+a0(0)v令df(X)/da0(0)=0，得a0(0)=2 則有 v f(X0(1)=713)1(0X1013) 1 (0) 1 () 1 (0) 1 (0)2(0aaeXXv以X0(1)為起點，沿坐標(biāo)軸方向e(1)進行一維搜索：v代入f(X)， f(X)=32+2(1+a0(1)24323(1+a0(1)v令df(X)/da0(1)=0,得a0(1)=0.5, 則有5 . 13)2(0Xf(X0(2)=7.5F計算各個方向的函數(shù)下降量： 1= f(X0(0) f(X0(1)=3(7)=4 2= f(X0(1) f(X0(2)=7(7.5)

51、=0.5 m=max1, 2=1=425115 . 1322)0(0)2(0)4(0XXX映射點：f1=f(X0(0)=3;f2=f(X0(2)=7.5f3=f(X0(4)=7;v檢驗是否滿足終止迭代條件替換條件：f3 f1; (f12f2+f3)(f1f2m)2=1.25f1, 替換條件不成立，繼續(xù)迭代時取搜索方向仍為原方向e(1), S(0)。由于f2 f3，取X2(0)=X1(2)=3.96, 1.94T 以X2(0)為新起點，方向 e(1), S(0)，進行第三循環(huán)迭代。 f(X2(0)=7.996=f198. 196. 3)1(2X沿e(1)方向進行一維搜索，得以X2(1)為起點沿S

52、(0)方向進行搜索，得988. 19992. 3)2(2X9997. 7)()2(22Xffe0620. 0)0(2)2(2XX收斂判定：不收斂，繼續(xù)迭代。f(X2(1)=7.9992036. 20384. 42)0(2)2(2)4(2XXX996. 7;9987. 7)(13)4(2ffXf映射點： 1= f(X2(0) f(X2(1)=7.996(7.9992)=0.00322= f(X2(1) f(X2(2)=7.9992(7.9997)=0.0005m=max1, 2=1=0.0032判斷搜索方向是否替換： f3f1(f12f2+f3)(f1f2m)2=1.17510-90時，設(shè)計點違時，設(shè)計點違反了約束，在目標(biāo)函