建模仿真與優(yōu)化設計2010.

1、一優(yōu)化模型的一般意義二非線性規(guī)劃建模無纟三 非線性規(guī)劃建模有約束非線性規(guī)戈四連續(xù)結構體建模與優(yōu)化設計目的1. 掌握優(yōu)化問題的數(shù)學描述方法;2. 熟練掌握常用優(yōu)化算法。一優(yōu)化模型的一般意義（一）優(yōu)化模型的數(shù)學描述將一個優(yōu)化問題用數(shù)學式子來描述，即求函數(shù)U = f(x)在約束條件 人（X）= 0, / = 12昇72.和&O） <0（&（兀）二0）丿=12，P下的最大值或最小值，其中X 一設計變量（決策變量） fM目標函數(shù)xeQ 可行域min(f?r max)“ = f(x) x e Qs. t. /2z(x) = 0.i = 1,2., m.g,(x) SO(gO) AO)

2、, = 1,2,“ P-st. subject to “受約束于”之意(二) 優(yōu)化模型的分類1 根據(jù)是否存在約束條件有約束問題和無約束問題。2 根據(jù)設計變量的性質靜態(tài)問題和動態(tài)問題。3根據(jù)目標函數(shù)和約束條件表達式的性質線性規(guī)劃，非線性規(guī)劃，二次規(guī)劃，多目標規(guī)劃等。(1)非線性規(guī)劃目標函數(shù)和約束條件中，至少有一個非線性函數(shù)。min u = f(x) x c Q5. t.人(x) = OJ =匕2,昇72.z(x) <0(.(x)>0XZ = 1,2,.,5 /（2）線性規(guī)劃（LP）目標函數(shù)和所有的約束條件都是設計變量的線性函數(shù)。min u = cixi/=122aikxk = bi

3、= 1,2,., n. s.t< k=xx； >0.i = 1,2,. n.V （3）二次規(guī)劃問題目標函數(shù)為二次函數(shù)，約束條件為線性約束min u = /(x)=工ZNbjjXjXj i=l厶 J=152 aijxJ -bi = 1，2,.，n.s.t< 丿=ixi > O.i = 1,2,., n4.根據(jù)設計變量的允許值整數(shù)規(guī)劃（01規(guī)劃）和實數(shù)規(guī)劃。5.根據(jù)變量具有確定值還是隨機值確定規(guī)劃和隨機規(guī)劃。（三）建立優(yōu)化模型的一般步驟1確定設計變量和目標變量;2.確定目標函數(shù)的表達式；3 尋找約束條件o二、優(yōu)化求解的數(shù)學基礎函數(shù)的梯度泰勒展開二階導數(shù)矩陣矢量的概念.運算牙

4、矩陣的運算和逆矩陣芮h和亦別是函藪幾x, x22)Ex0點處沿坐標孤湎£方向的變化率(-)方向導數(shù)Iim /go 十 5心。）/（皿七） Axj-X）AX.|-m /*（旳0，*20 十 42）-/（“IO, *20）I g ->0Ar2I .1菁二、優(yōu)化求解的數(shù)學基礎故函數(shù)f(Xlf X2 沁o(X“,七/點處沿某一方向銅變化率為:（&*>Hm /Ow 屮"1 *20 + 心2）一 /（X1D，勺.）AS-K）AS稱為該函數(shù)沿此方向的方向導數(shù) 偏導數(shù)可以看作是函數(shù)沿坐標軸 方向的方向導數(shù)，并有旦 dx血 COSO?dfx COSf/j +1 dx2X

5、"A d rIZ1 X2X XII xio(二)梯度二元函數(shù)在點X。的梯度是由函數(shù)在該點的各一階偏導數(shù)組 成的向量。即:W(斗)三dx2二、優(yōu)化求解的數(shù)學基礎設S方向單位向量cosq COSoy = V/Xxo )rS= |V/(x()|cos(Vf, S) d Xo函數(shù)的梯度具有以下性質：(1) 函數(shù)在一點的梯度是一個向量。梯度的方向是該點函數(shù) 值上升最快的方向，與梯度相反的方向是該點函數(shù)值下降 的最快的方向，梯度的大小就是它的模長。(2) 一點的梯度方向是與過該點的等值線或等值面的切線或 切平面相垂直的方向，或者說是該點等值線或等值面的法 線方向。(3) 梯度是函數(shù)在一點鄰域內局

6、部形態(tài)的描述。在一點上升得快的方向，離開該領域后就不一定上升得快，甚至毋能 下降。V二、優(yōu)化求解的數(shù)學基礎(三) 泰勒展開為了便于數(shù)學問題的分析和求解，往往需要將一 復雜的非線性函數(shù)簡化成線性函數(shù)或二次函數(shù)。簡化郎 方法可以采用泰勒展開式。由高等數(shù)學可知，一元函數(shù)若在點X。的鄰域 內n階可導，則函數(shù)可在該點鄰域內作泰勒展開：f(x) = /(x0) + f (xJAr + -/7x0)Ar2 + nAx” + Rn (x)其中 X 三.二元函數(shù)3在點xo(xio, x2Oy可以作泰勒展開，展 式一般取前三項，即：1 A 喲 + 2 諾二、優(yōu)化求解的數(shù)學基礎將上式寫為矩陣形式OfAr】dx2/（

7、"）= /*（兀。）+ | 警+ 7 g 心2=/(x0) +Vf(x0)rAx + izrrG(x0)Ar + 其中，GQfo沖為函數(shù)f（xlfx2）點血處的 二階導數(shù)矩陣或海賽矩陣。二、優(yōu)化求解的數(shù)學基礎在優(yōu)化計算中，當某點附近的函數(shù)值采用泰勒展 開式作近似表達時，研究該點鄰域的極值問題需要另 析二次型函數(shù)是否正定。當對任何非零向量X使f (jc) = xrGx > O則二次型函數(shù)正定，G為正定矩陣二.優(yōu)化求解的數(shù)學基礎（四）二次函數(shù)當將函數(shù)的泰勒展開式取到二次項時得到二 次函數(shù)形式。優(yōu)化計算經(jīng)常把目標函數(shù)表示為二次 函數(shù)以使問題分析得以簡化。在線性代數(shù)中將二次 齊次函數(shù)稱

8、作二次型，其矩陣形式f（x） = xT Gx在優(yōu)化計算中，當某點附近的函數(shù)值采用泰 勒展開式作近似表達時，研究該點鄰域的極值問題 需要分析二次型函數(shù)是否正定。當對任何非零向量 X使丁y（x）= xtGx > o則二次型函數(shù)正定，G為正定矩陣二、優(yōu)化求解的數(shù)學基礎對于一般二次函數(shù)/X") = + FGx +十 C |則稱矩陣是正定的； 則稱矩陣是半正定的;則稱矩陣是負定的； 則稱矩陣是半負定的;則稱矩陣是不定的(1)(2)(3)(4)(5)矩陣有正定和負定之分。對于所有非零向量: 若有xTGx > Q 若有 x1 Gx > 0, 若有 xrGx v 0, 若有 x7G

9、x < 0> 若有 xrGx = 09二、優(yōu)化求解的數(shù)學基礎可以證明，正定二次函數(shù)具有以下性質：(1) 正定二次函數(shù)的等值線或等值面是一簇同心圓 或同心橢球。橢圓簇或橢球簇的中心就是該二次函 數(shù)的極小點。(2) 非正定二次函數(shù)在極小點附近的等值線或等值二、優(yōu)化求解的數(shù)學基礎(五) 無約束優(yōu)化問題的極值條件充分條件為：該點處海賽矩陣正定，即二次函數(shù)f(xl, x2Ex0取得極值的必要條件 為d2fd2f正定：各階主二dx dxdx2 d2fd2f>0均大于零。0xX2OX2*0二.優(yōu)化求解的數(shù)學基礎（六）下降迭代算法及其收斂性無約束最優(yōu)化問題求優(yōu)過程的 求解方法大致分為兩類。(

10、1)解析法VF(X) = OHessian矩陣正定Hessian 矩陣負定=極小值點極大值點二.優(yōu)化求解的數(shù)學基礎用迭代汁算逐步逼近是優(yōu)點搜索過程血三、優(yōu)化設計的4（一）優(yōu)化問題的求P優(yōu)化問題的本F優(yōu)化問題的本2、優(yōu)化問題的求解e.數(shù)值計算法可以較好地解決這類問題理論上解析法即應用極值理論求傑數(shù)值計算法（二）數(shù)值計算法的迭代方法1、2、數(shù)值計算法的迭代方法三.優(yōu)化設計的迭代計算三.優(yōu)化設計的迭代計算（三）迭代計算的迭代過程由選定的初始點X）某種優(yōu)化方法序 :定的搜索方向SX=乂（0）-使?jié)M足F(x(,)門J2).-J1）由于各設計點的函數(shù)值僧 次下降，可見迭代點不衣 向理論最優(yōu)點逼近，最尼 可

11、得到一定精度下的近雄 最優(yōu)皆，記作兀"。兀(Sl)=*«)+C(AOs")三.優(yōu)化設計的迭代計算三.優(yōu)化設計的迭代計算!1!)迭代計算的終止準則由于數(shù)值迭代是逐步逼近最優(yōu)點而獲得近似解的， 所以要考慮優(yōu)化問題解的收斂性及迭代過程的終止條件。1、迭代的收斂性指某種迭代印住立斗侶住和山=0,1,2,)收斂亍 恤乂*+1相鄰兩個李計點宀的距離已達到充兩迭代點的坐標2、通常采用怎分小分量之差(1)點距準“l(fā)lxk+1-Xkll<E 或_、倔化zrr相鄰迭代點的函數(shù)值下降(2)函數(shù)下降量準則畐扶創(chuàng)呑并小F(x"i)_F(+相鄰迭代點的函數(shù)值的相 對it狂到充

12、另小尸(嚴)一尸(來)F(J)(3)梯度準則心)后5非線性規(guī)劃建模無約束最優(yōu)化丄、了解無約束最優(yōu)化基本算法。2、掌握用數(shù)學軟件包求解無約束最優(yōu)化問題。1無約束優(yōu)化基本思想及基本算法。2. MATLAB優(yōu)化工具箱簡介 3.用NIAIIAB求解無約束優(yōu)化問題七）=西 +蓼2 一?:!". 參/ «纟： <算一Jimin /(%! x2) = 1 (X)(x2 -x)2 + (1 xx)2兀2f114.00-0.790.583.390.530.232.600.180.001.500.09-0.030.980.37010.470.590.330.200.800.630.050

13、.950.90().0030.990.991E-40.9990.998IE-50.99970.9998IE-8搜索過程最優(yōu)點(11)初始點(-1 1)潴'心嚴坐標輪換法-坐標輪換法的迭代過程 如圖，以二次函數(shù)為例。坐標輪換法任取一初始點X。作為第一輪的始點xj,先沿第 一坐標軸的方向6作一維搜索，用一維優(yōu)化方法確 定最優(yōu)步長aF，得第一輪的第一個迭代點 X11=xo1+ a11e1,然后以xj為新起點，沿第二坐 標軸的方向6作一維搜索，礎定步長a，得第一 輪的第二個迭代點x/zzx/4- aFd第二輪迭代，需要xi1<-xo1xx2<-x02+x22=xx2+ a22 e2

14、依次類推，不斷迭代，目標函數(shù)值不斷下降, 最后逼近該目標函數(shù)的最優(yōu)點。尋坐標輪換法二.終止準則可以采用點距準則或者其它準則O注意：若釆用點距準則或函數(shù)值準則，其中釆用的點應該是一輪迭代的始點和終點，而不是某搜索方 向的前后迭代點。鮑威爾方法一方向加速法坐標輪換法三、坐標輪換法的流程圖K=1i鮑威爾方法一方向加速法i鮑威爾方法一方向加速法坐標輪換法U!例題i鮑威爾方法一方向加速法五.小結坐標輪換法程序簡單，易于掌握。但是計算效率比牧低，尤其是當優(yōu)化問題的維數(shù)較高時更為嚴重。一般把此 種方法應用于維數(shù)小于10的低維優(yōu)化問題。對于目標函數(shù)存在“脊線”的情況，在脊線 的尖點處沒有一個坐標方 向可以使函

15、數(shù)值下降，只 有在銳角所包含的范圍搜 索才可以達到函數(shù)值下降 的目的，故坐標輪換法對 此類函數(shù)會失效。鮑威爾方法是直接利用函數(shù)值來構造共軌方向 的一種共軌方向法。這種方法是在研究具有正定矩陣 G的二次函數(shù)1 ,f(x) = xtGx + BT x + C的極小化問題時形成的。其基本思想是在不用導數(shù)的 前提下，在迭代中逐次構造砒共軌方向。一、共軌方向的概念設G為一正定對稱矩陣，若有一組非零向量勻， W，$滿足STGSj=O (i工j),則稱這組向量 關于矩陣強鈍。共軌方向對于構造一種有效的算法是很重要的。 以正定二元二次函數(shù)為例，我們進行探討。.普鮑威爾方法正定的二元二次函數(shù)的等值線為一組橢圓，

16、任 選初始點W沿某個下降方向夕作一維搜索，得疋X】+a。此時，點疋的梯度必然與方向夕唾直，即有d s1NS7VfCxpSP歹與某一等值線相切于疋點O 下一次的迭代，若選擇負梯 度方向為搜索方向，將產(chǎn)生 鋸齒現(xiàn)象。為避免鋸齒的產(chǎn) 生，我們取迭代方向歹直指 極小點X*,如圖所示。i鮑威爾方法若選定這樣的方向，則對于二元二次函數(shù)只需 進行夕和歹兩次搜索就可以求得極小點X*,即x=xx+a AS3由于 Vf(x1)=Gx1+b9 當x1a 09 由于x討 (x)的極小點，應滿足極值必要條件，故 Vf(x*)=Gx*+b=O,即Vf(x*)=G (x+a+b= Vf(x1)+ a S1=0等式兩端同乘以

17、(刃7；得(歹)TG9=0,故兩個向 量歹、歹是G的共軌向量。因此，若要使第二個迭代點成為正定二元二次 函數(shù)的極小點，只要使兩次一維搜索的方向歹、歹關 于函數(shù)的二階導數(shù)矩陣G共軌就可以了。宀鮑威爾方法一、扌上掠方向的牛成一、潑#、卅宀為從不同點出發(fā)，沿同一方向9進行 一維搜索得到的兩個極小點，如圖所示。根據(jù)梯度和 等值面的性質，和卅 哂點處的梯度嚴 之間存在如下關系(9葉=0 (9)丁嚴=0 又因為卅卅宀兩點處的梯度 可表示為gk=Gxk+b 嚴 uGZ+b 兩式相減，得 g+1 &=6(疋+丄屮)因此有(Sf(Si)T彳卅乜49=0若取方向少"+",則網(wǎng)列妙軌。這

18、說 明只要沿方向9分別對函數(shù)作兩次一維搜索，得到兩 個極小點，則這兩點的連線方向就是與。共鈍的方 向。鮑威爾方法三、鮑威爾基本算法如圖所示，以三維二次目標函數(shù)的無約束優(yōu)化問題為例。鮑威爾基本算法的步驟: 第一環(huán)基本方向組取單位坐標矢量系8丄e2e3 en,沿這些方向依次作一維搜索，然治將始末兩點相連作為新生方向，再沿新生方向作一維搜索，完成第一環(huán)的迭代。以后每環(huán)的基本方向組是將 上環(huán)的第一個方向淘汰，上環(huán)的新生方向補入本環(huán)的 最后而構成。n維目標函數(shù)完成n環(huán)的迭代過程稱為 一輪。從這一輪的終點出發(fā)沿新生方向搜索所得到的 極小點，作為下一輪迭代的始點。這樣就形成了算法 的循環(huán)。鮑威爾方法鮑威爾基本算法的缺陷，可能在某一環(huán)迭代中出現(xiàn)基本方向組為線性 相關的矢量系的情況。如第k環(huán)中，產(chǎn)生新的方向:S=x#xJ(=aS+ +a$S卜式中，S' S$、3/為第k環(huán)基本 方向組矢量，a/、af、a/為個方向的 最優(yōu)步長。若在第k環(huán)的優(yōu)化搜索過程中出現(xiàn)af =0.則 方向5*表示為冷、S$、5；啲殘性組合, 以后的各次搜索將在降維的空間進行，無法得到n 維空間的函數(shù)極小值，計算將失敗。鮑威爾方法如圖所示為一個三維優(yōu)化問題的示例，設第一環(huán)中al =O9則新生方向與e2、e戲面，隨后的各 環(huán)方向組中，各矢量必在 該平面內，使搜索局限于 二維空間，不能得到最優(yōu)