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

1、一優(yōu)化模型的一般意義二非線性規(guī)劃建模無纟三 非線性規(guī)劃建模有約束非線性規(guī)戈四連續(xù)結(jié)構(gòu)體建模與優(yōu)化設(shè)計(jì)目的1. 掌握優(yōu)化問題的數(shù)學(xué)描述方法;2. 熟練掌握常用優(yōu)化算法。一優(yōu)化模型的一般意義（一）優(yōu)化模型的數(shù)學(xué)描述將一個(gè)優(yōu)化問題用數(shù)學(xué)式子來描述，即求函數(shù)U = f(x)在約束條件 人（X）= 0, / = 12昇72.和&O） <0（&（兀）二0）丿=12，P下的最大值或最小值，其中X 一設(shè)計(jì)變量（決策變量） fM目標(biāo)函數(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ù)設(shè)計(jì)變量的性質(zhì)靜態(tài)問題和動(dòng)態(tài)問題。3根據(jù)目標(biāo)函數(shù)和約束條件表達(dá)式的性質(zhì)線性規(guī)劃，非線性規(guī)劃，二次規(guī)劃，多目標(biāo)規(guī)劃等。(1)非線性規(guī)劃目標(biāo)函數(shù)和約束條件中，至少有一個(gè)非線性函數(shù)。min u = f(x) x c Q5. t.人(x) = OJ =匕2,昇72.z(x) <0(.(x)>0XZ = 1,2,.,5 /（2）線性規(guī)劃（LP）目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量的線性函數(shù)。min u = cixi/=122aikxk = bi

3、= 1,2,., n. s.t< k=xx； >0.i = 1,2,. n.V （3）二次規(guī)劃問題目標(biāo)函數(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è)計(jì)變量的允許值整數(shù)規(guī)劃（01規(guī)劃）和實(shí)數(shù)規(guī)劃。5.根據(jù)變量具有確定值還是隨機(jī)值確定規(guī)劃和隨機(jī)規(guī)劃。（三）建立優(yōu)化模型的一般步驟1確定設(shè)計(jì)變量和目標(biāo)變量;2.確定目標(biāo)函數(shù)的表達(dá)式；3 尋找約束條件o二、優(yōu)化求解的數(shù)學(xué)基礎(chǔ)函數(shù)的梯度泰勒展開二階導(dǎo)數(shù)矩陣矢量的概念.運(yùn)算牙

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

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

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

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

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

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

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

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

12、另小尸(嚴(yán))一尸(來)F(J)(3)梯度準(zhǔn)則心)后5非線性規(guī)劃建模無約束最優(yōu)化丄、了解無約束最優(yōu)化基本算法。2、掌握用數(shù)學(xué)軟件包求解無約束最優(yōu)化問題。1無約束優(yōu)化基本思想及基本算法。2. MATLAB優(yōu)化工具箱簡(jiǎn)介 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)點(diǎn)(11)初始點(diǎn)(-1 1)潴'心嚴(yán)坐標(biāo)輪換法-坐標(biāo)輪換法的迭代過程 如圖，以二次函數(shù)為例。坐標(biāo)輪換法任取一初始點(diǎn)X。作為第一輪的始點(diǎn)xj,先沿第 一坐標(biāo)軸的方向6作一維搜索，用一維優(yōu)化方法確 定最優(yōu)步長(zhǎng)aF，得第一輪的第一個(gè)迭代點(diǎn) X11=xo1+ a11e1,然后以xj為新起點(diǎn)，沿第二坐 標(biāo)軸的方向6作一維搜索，礎(chǔ)定步長(zhǎng)a，得第一 輪的第二個(gè)迭代點(diǎn)x/zzx/4- aFd第二輪迭代，需要xi1<-xo1xx2<-x02+x22=xx2+ a22 e2

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

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

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

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

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