機(jī)械優(yōu)化設(shè)計(jì)講義

1、機(jī)械優(yōu)化設(shè)計(jì)講義學(xué)院： 專(zhuān)業(yè)： 姓名： 學(xué)號(hào)： 第一講 緒論一、機(jī)械優(yōu)化設(shè)計(jì)的基本概念1、什么是優(yōu)化設(shè)計(jì)在機(jī)械產(chǎn)品設(shè)計(jì)過(guò)程中，根據(jù)問(wèn)題的性質(zhì)和給定的條件，在分析的基礎(chǔ)上，綜合各方面的要求因素，從全部可行的方案中，尋找出最優(yōu)方案的方法和過(guò)程。優(yōu)化設(shè)計(jì)是利用高等數(shù)學(xué)中求極（最）值理論，以計(jì)算機(jī)為計(jì)算工具，用數(shù)值分析的方法，對(duì)機(jī)械產(chǎn)品設(shè)計(jì)問(wèn)題求出最佳設(shè)計(jì)參數(shù)的工程方法?！皟?yōu)化設(shè)計(jì)”對(duì)應(yīng)的是“經(jīng)驗(yàn)設(shè)計(jì)”。2、優(yōu)化設(shè)計(jì)的過(guò)程 A、分析設(shè)計(jì)任務(wù)的對(duì)象，提出設(shè)計(jì)思想 B、建立優(yōu)化數(shù)學(xué)模型，包括選取設(shè)計(jì)變量，建立目標(biāo)函數(shù)和約束方程 C、選擇優(yōu)化方法（自編程序或選擇商品程序），上機(jī)計(jì)算 D、對(duì)計(jì)算結(jié)果進(jìn)行分析

2、F、當(dāng)結(jié)果不甚合理時(shí)，修改數(shù)學(xué)模型，返回B。 3、優(yōu)化設(shè)計(jì)的局限 A、優(yōu)化設(shè)計(jì)過(guò)程是人和機(jī)器合作完成的，“人”在其中起著巨大作用。 B、所謂“最優(yōu)”是相對(duì)的，當(dāng)設(shè)計(jì)思想、約束條件，甚至初始方案改變時(shí)，最優(yōu)方案也要改變。 C、“最優(yōu)方案”是否合理、可行，還是要用經(jīng)驗(yàn)來(lái)判斷。PPLD0D0二、一個(gè)優(yōu)化設(shè)計(jì)實(shí)例某空心圓柱壓桿，壓力載荷為P，長(zhǎng)度L，截面外徑D0，內(nèi)徑D1。變換成中徑D和壁厚T； D= (D0+D1)/2 T = (D0-D1)/2設(shè)材料已經(jīng)選定，即材料的 彈性模量E, 許用應(yīng)力【】，密度等已確定。設(shè)計(jì)要求：1、 強(qiáng)度要求：壓 P/(DT) 【】2、 穩(wěn)定要求：壓 P/(DT) 歐拉應(yīng)

3、力3、 結(jié)構(gòu)要求： D K1 T K2 K1,K2為定值 T D/2桿的重量： W = DTL 整個(gè)問(wèn)題可以歸結(jié)為： 設(shè)計(jì)一個(gè)壓桿，在滿(mǎn)足上述5個(gè)條件的前提下，使W最小。 經(jīng)驗(yàn)設(shè)計(jì)此問(wèn)題，人工選取一對(duì)D和T，分別代入上述5個(gè)條件，都滿(mǎn)足時(shí)即可。是否重量最輕，材料最省，不予考慮，也不得而知。用優(yōu)化設(shè)計(jì)的語(yǔ)言表示上述問(wèn)題：D,T（或者D0、D1）為設(shè)計(jì)變量，表示成： X （x1, x2）W為目標(biāo)函數(shù)，是設(shè)計(jì)變量的函數(shù)，表示成： W = F(x1, x2) = F(X)5個(gè)條件叫做 約束方程，或者約束條件。表示為： gi(X) 0 i= 15一般情況下，優(yōu)化設(shè)計(jì)問(wèn)題表述為： Min F (X) =

4、目標(biāo)函數(shù) S.T gi (X) 0 i = 1,2 m 約束方程（條件） 其中： X = (x1,x2,xi,xn) 設(shè)計(jì)變量設(shè)計(jì)變量，目標(biāo)函數(shù)和約束條件，是優(yōu)化設(shè)計(jì)問(wèn)題的三要素。三、設(shè)計(jì)變量設(shè)計(jì)變量是設(shè)計(jì)中的可變化參量（因素）。當(dāng)有n個(gè)變量時(shí)，在歐氏空間里表示為：X = (x1,x2,xi,xn) XRn當(dāng)設(shè)計(jì)變量取一組定值時(shí)，在數(shù)學(xué)上是n維空間的一個(gè)點(diǎn)，在工程上是一個(gè)設(shè)計(jì)方案（在經(jīng)驗(yàn)設(shè)計(jì)中，若能滿(mǎn)足要求，就可能成為真實(shí)的工程設(shè)計(jì)方案）：X(1)= (,) 是n維空間的一個(gè)點(diǎn)，工程設(shè)計(jì)的一個(gè)方案；X(2)= (,) n維空間的另一個(gè)點(diǎn)，工程設(shè)計(jì)的第二方案。 X(k)= (,) n維空間的第k

5、個(gè)點(diǎn)，工程設(shè)計(jì)的第k 個(gè)方案。每后一個(gè)方案都可以看成是前一個(gè)方案的改進(jìn)。即：X(2) = X(1) +X X(k) = X(k-1) +X= X(k-1)+ 其中是按照某種規(guī)則構(gòu)造的單位矢量，即搜索方向,是搜索步長(zhǎng)。四、目標(biāo)函數(shù)目標(biāo)函數(shù)是設(shè)計(jì)者設(shè)定的用于評(píng)價(jià)設(shè)計(jì)方案優(yōu)劣的參數(shù)，將它表示成設(shè)計(jì)變量的可計(jì)算函數(shù)。目標(biāo)函數(shù)值越小，對(duì)應(yīng)的工程方案就越優(yōu)；目標(biāo)函數(shù)值最小，對(duì)應(yīng)的工程方案就最優(yōu)。目標(biāo)函數(shù)的表示要盡量簡(jiǎn)單易算，或者通過(guò)查表能夠查出來(lái)。機(jī)械優(yōu)化設(shè)計(jì)的過(guò)程就是求目標(biāo)函數(shù)的最小值對(duì)應(yīng)的設(shè)計(jì)方案的過(guò)程。當(dāng)出現(xiàn)極大化時(shí)，加上負(fù)號(hào)就是最小。五、約束條件 約束條件可能很多，從數(shù)學(xué)上分類(lèi)，有等式約束和不等式

6、約束，以不等式約束為多。有些約束可能與別的約束重復(fù)，叫多余約束，應(yīng)該剔除。 等式約束是Rn內(nèi)的超曲面，不等式約束是Rn內(nèi)超曲面的某一側(cè)的空間。由滿(mǎn)足若干不等式約束構(gòu)成的空間區(qū)域，叫可行域。等式約束的可行域是其超曲面上的某部分?？尚杏騼?nèi)的點(diǎn)叫內(nèi)點(diǎn)，是可取方案的集合；可行域之外的點(diǎn)叫外點(diǎn)，為不可取方案?？尚杏蜻吔缟系狞c(diǎn)叫邊界點(diǎn)。最優(yōu)點(diǎn)經(jīng)常在幾個(gè)約束構(gòu)成的邊界上，這幾個(gè)約束叫起作用約束。其余的叫不起作用約束。六、優(yōu)化設(shè)計(jì)問(wèn)題的完整數(shù)學(xué)模型 Min F(X) = XRn S.T gu(X)0 u = 1,2,p hv(X)= 0 v = 1,2,q最優(yōu)解： ）， 最優(yōu)值： F(X*) 第二講 優(yōu)化設(shè)計(jì)

7、的數(shù)學(xué)基礎(chǔ)一、目標(biāo)函數(shù)（多元函數(shù)）的偏導(dǎo)數(shù)與梯度設(shè)目標(biāo)函數(shù)為F(X)， F(X)是n1維空間的超曲面；偏導(dǎo)數(shù)： ,；幾何意義：目標(biāo)函數(shù)沿各個(gè)坐標(biāo)軸的變化率。梯度：梯度是一個(gè)矢量，是由各個(gè)偏導(dǎo)數(shù)為元素的矢量。表示為：F(X)，F(xiàn)(X) (,)將“”叫作梯度算子（僅是一種算法），（，）梯度的幾何意義：目標(biāo)函數(shù)在點(diǎn)的數(shù)值上升最快的方向；而F(X)為目標(biāo)函數(shù)值下降最快的方向（注：此處上升和下降最快是局部最快，不是全局）。梯度的模：將梯度的每個(gè)元素都除以其模，構(gòu)成的矢量是梯度方向的單位矢量。二、方向與方向?qū)?shù)在內(nèi)表示一個(gè)方向用指向該方向的單位矢量，；為方向與坐標(biāo)軸之間的夾角。其中：叫方向余弦。顯然：方向

8、導(dǎo)數(shù)是目標(biāo)函數(shù)沿方向的變化率，方向?qū)?shù)是一個(gè)標(biāo)量（數(shù)量），引進(jìn)矢量分析中的點(diǎn)積的概念，方向?qū)?shù)為梯度與方向的點(diǎn)積：方向?qū)?shù)的值不僅隨所取點(diǎn)X變化，而且隨在點(diǎn)X不同的方向而變化，當(dāng)角時(shí)（與重合時(shí)）方向?qū)?shù)最大，且：所以說(shuō)梯度方向是目標(biāo)函數(shù)增加（上升）最快的方向。當(dāng)時(shí)，角, (與垂直時(shí))，即在目標(biāo)函數(shù)的等值面（線(xiàn)）上。三、海賽矩陣 （Hessian）海賽矩陣是由目標(biāo)函數(shù)的二階偏導(dǎo)數(shù)組成的矩陣：如果將梯度理解成目標(biāo)函數(shù)的一階“導(dǎo)數(shù)”，則海賽矩陣就是目標(biāo)函數(shù)的二階“導(dǎo)數(shù)”。因此：，若：，則海賽矩陣是一個(gè)對(duì)稱(chēng)矩陣（階）。主子式：從海賽矩陣的左上角開(kāi)始，分別取其個(gè)，個(gè)，個(gè)個(gè)元素構(gòu)成的行列式，叫海賽矩陣的主

9、子式。一階主子式：；二階主子式：；按照行列式的計(jì)算法則，可以計(jì)算海賽矩陣各階主子式的值。若各階主子式恒大于0，則稱(chēng)正定；各階主子式負(fù)、正相間，則稱(chēng)負(fù)定；各階主子式正、負(fù)不定，則稱(chēng)不定。四、目標(biāo)函數(shù)的二階泰勒展開(kāi)一元函數(shù)在點(diǎn)泰勒展開(kāi)式為：其中：泰勒展開(kāi)可以理解為在函數(shù)的某點(diǎn)附近，用一簡(jiǎn)單的多項(xiàng)式去逼近（或者代替）復(fù)雜的函數(shù)。只要所取的多項(xiàng)式的次數(shù)足夠大，就能使二者的誤差足夠小，條件是在附近連續(xù)且多階可導(dǎo)。對(duì)于多元函數(shù)，也可以在點(diǎn)處展開(kāi)成泰勒多項(xiàng)式。只要將一元函數(shù)泰勒展開(kāi)中的換成，換成，一般二階展開(kāi)式（中間的“· ”為矢量或矩陣乘）：其中，為維矢量， 為二次型函數(shù) 。五、無(wú)約束目標(biāo)函數(shù)極

10、值存在的條件先看一元函數(shù)的極值存在情況。在點(diǎn)取得極值：必要條件： 即是駐點(diǎn)。充分條件： 此條件可以推展到多元函數(shù)：在處取得極值：必要條件： 即：，（也叫駐點(diǎn)）充分條件：特別提醒 此處的“極值”與“優(yōu)化”所需要的最大或最小值并不是一回事，“極值”是局部的，“最值”是全局的； 此判定僅具有理論意義，復(fù)雜的目標(biāo)函數(shù)海賽矩陣及其正負(fù)定判斷極其困難。第三講 約束優(yōu)化極值條件尋優(yōu)過(guò)程的基本思路 一維尋優(yōu)方法一、約束優(yōu)化問(wèn)題的極值條件g31起作用約束:設(shè)最優(yōu)點(diǎn)X*，約束函數(shù)集為：，X*使約束函數(shù)變成等式的約束叫起作用約束。幾何意義：X*在中某幾個(gè)的邊界上。如右圖所示，其中：X0是無(wú)約束極值點(diǎn)；X*是約束極值

11、點(diǎn)；是起作用約束；不起作用約束。2庫(kù)恩塔克定律（KT條件）如果最優(yōu)點(diǎn)X*在可行域內(nèi)（所有約束均為不起作用約束），則約束最優(yōu)點(diǎn)與無(wú)約束最優(yōu)點(diǎn)重合；如果最優(yōu)點(diǎn)在可行域的邊界上，有起作用約束，最優(yōu)點(diǎn)與目標(biāo)函數(shù)和起作用約束都有關(guān)。A. 只有一個(gè)起作用約束的情況目標(biāo)函數(shù)的負(fù)梯度方向與約束函數(shù)的梯度方向重合，即：，幾何意義：約束函數(shù)與目標(biāo)函數(shù)的某等值線(xiàn)（面）相切。B兩個(gè)起作用約束條件目標(biāo)函數(shù)的負(fù)梯度是各起作用約束的梯度的線(xiàn)性組合（加權(quán)合成）。幾何意義：“夾”在各之間。Ci個(gè)起作用約束幾何意義；同上。DKT條件的應(yīng)用KT條件的意義不是求最優(yōu)值，而是用來(lái)檢驗(yàn)最優(yōu)值。檢驗(yàn)方法如下：設(shè)是的可能最優(yōu)值 1求出；2求

12、出起作用約束集，將代入 中，有i個(gè)約束函數(shù)值的為起作用約束（至少有一個(gè)）；3求出，4檢查：若 ，其中，至少有一個(gè)0，則是最優(yōu)點(diǎn)，否則不是。（具體檢查方法是解方程組，求出i的具體值。）二、尋優(yōu)過(guò)程的基本思路數(shù)值解法，逐步逼近若是可行域內(nèi)的一個(gè)點(diǎn)，在點(diǎn)構(gòu)造能使下降的方向 ，用一維搜索法找到在方向上最小的駐點(diǎn),有，在點(diǎn)重復(fù)上述步驟，經(jīng)過(guò)若干次迭代，即可得到最優(yōu)解。有人把這種方法叫做瞎子爬山法。涉及四個(gè)問(wèn)題：1必須找出的可行域及可行域內(nèi)至少一個(gè)初始點(diǎn)；2如何構(gòu)建能使下降的方向：構(gòu)建的不同方法，就形成了不同的尋優(yōu)方法。如最速下降法（用作方向），坐標(biāo)變換法（用各坐標(biāo)軸方向作S）,牛頓法（改進(jìn)的梯度法）3如

13、何確定尋優(yōu)步長(zhǎng)：已知和后，就點(diǎn)代入目標(biāo)函數(shù)，則變成的一元函數(shù)，可用解析法求能使在此方向的極值點(diǎn)。實(shí)際上都是數(shù)值法（如0.618法）求；4如何結(jié)束尋優(yōu)過(guò)程？一般有三個(gè)條件：ABC工程中一般只用前兩個(gè)，第三個(gè)由于要求梯度而不常用。若設(shè)計(jì)變量只有兩個(gè)，即，（或者不大于三個(gè)），可以用網(wǎng)絡(luò)法（或大海撈針?lè)ǎ┣蟪鲎钚≈?；如轉(zhuǎn)向梯形的問(wèn)題可以在其可行域的上、下、左、右邊界上劃分網(wǎng)格，分別計(jì)算并比較值。三、一維搜索法設(shè)已知和后，構(gòu)建新點(diǎn)代入目標(biāo)函數(shù) ，是步長(zhǎng)的一元函數(shù)，即，求出使最小的步長(zhǎng)的過(guò)程叫一維搜索法。1、一維搜索之前先要確定搜索區(qū)間，即找出一個(gè)包含，使最小的區(qū)間。方法是進(jìn)退法。從開(kāi)始，選定一個(gè)前進(jìn)單位

14、h,分別計(jì)算 個(gè)點(diǎn)的目標(biāo)函數(shù)值F1,F2,F2,FL,FL+1，直到出現(xiàn)目標(biāo)函數(shù)值“高低高”的三個(gè)點(diǎn)，如上圖： ，故搜索區(qū)間取為：（）為搜索區(qū)間。2黃金分割法（0.618法）黃金分割法是每次通過(guò)計(jì)算目標(biāo)函數(shù)值，通過(guò)比較，舍棄一部分區(qū)間，區(qū)間小到一定程度時(shí)，即為具體方法：在已知的搜索區(qū)間()內(nèi)，另找兩點(diǎn) ，其中：求出 ，比較 與 的大小，誰(shuí)大舍棄誰(shuí)外側(cè)的區(qū)間。i若 ,舍棄區(qū)間ii若,舍棄區(qū)間iii若 ，舍棄兩邊區(qū)間。舍棄一個(gè)區(qū)間后，補(bǔ)充一個(gè)點(diǎn)，重復(fù)上述步驟，直到 為止，從其中任取一點(diǎn)即可作為最優(yōu)點(diǎn)。第四講 習(xí)題課一、 建立優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型二、 求目標(biāo)函數(shù)的梯度及給定方向的方向?qū)?shù)三、 求目標(biāo)函

15、數(shù)的海賽矩陣及其逆四、 求目標(biāo)函數(shù)在給定點(diǎn)的泰勒展開(kāi)式五、 用K-T條件驗(yàn)證某點(diǎn)為約束最值點(diǎn)六、 用黃金分割法一維搜索求極值第五講 無(wú)約束問(wèn)題的優(yōu)化方法（一）最速下降法 牛頓法 改進(jìn)牛頓法無(wú)約束優(yōu)化問(wèn)題：in F(X) ， X設(shè)F(X)至少二階可導(dǎo)，即存在：一、梯度法最速下降法基本思路：每次以點(diǎn)的負(fù)梯度方向?yàn)樗阉鞣较?，即：，或，。因?yàn)樨?fù)梯度方向是函數(shù)值在該點(diǎn)下降最快的方向，所以此法又叫最速下降法。這里“最速”只是在點(diǎn)這一局部最速，在整體上并不一定最速。實(shí)踐中表明，此法在尋優(yōu)初期效果不錯(cuò)，往后越來(lái)越慢。此外，需要反復(fù)求梯度，實(shí)際的工程問(wèn)題常不能滿(mǎn)足。所以用得不廣泛。但其基本思想正確，對(duì)尋求其它方

16、法有啟發(fā)作用。梯度法尋優(yōu)的步驟框圖見(jiàn)陳立周第二版69頁(yè)。例：Min 解：第一輪： 取, 代入F(X)，得： 求步長(zhǎng)可以用黃金分割法。但此處為2次函數(shù)，可以直接寫(xiě)出來(lái)： （至此，應(yīng)該檢驗(yàn)X（1）是否為最優(yōu)值。由于它顯然不是，省略。）第二輪：代入F(X)，得：（至此，也應(yīng)該檢驗(yàn)X（2）是否為最優(yōu)值。由于它顯然不是，檢驗(yàn)省略。）如此繼續(xù)下去，經(jīng)若干步以后，可得最優(yōu)點(diǎn).二、牛頓法牛頓法是為了改善梯度法收斂越來(lái)越慢的缺點(diǎn)而改善搜索方法。其基本思路是用F(X)在處的泰勒展開(kāi)式代替F(X)，用的極值去逼近F(X)的極值，取=，開(kāi)始下一輪尋優(yōu)。F(X)在X(k)點(diǎn)的泰勒展開(kāi)式為：F(X)= 此二次函數(shù)取得極值

17、的必要條件是展開(kāi)函數(shù)的梯度等于0（駐點(diǎn)）：即：解此方程，得：其中：是海賽矩陣的逆矩陣。?。?= 作為下一輪尋優(yōu)的起點(diǎn)。（注意：這里是減號(hào)?。⑸鲜脚c尋優(yōu)迭代的一般形式 相比，牛頓法的本質(zhì)，是以負(fù)梯度方向?yàn)樗阉鞣较?、以海賽矩陣的逆為步長(zhǎng)的搜索方法。優(yōu)點(diǎn)：不需要一維搜索，對(duì)真正的二次函數(shù)一步到達(dá)最優(yōu)點(diǎn)。缺點(diǎn)：要求海賽矩陣及其逆。例： Min 解：仍取為初始點(diǎn)，因F(X)是二次函數(shù)，其泰勒展開(kāi)式與F(X)完全相同，只需求其和H(X), 就行了.如前： 這就是最優(yōu)值，因是二次函數(shù)，所以一步到達(dá)。是的行列式。是的伴隨矩陣。伴隨矩陣的各元素是原矩陣中各對(duì)應(yīng)元素乘以其代數(shù)余子式，再經(jīng)轉(zhuǎn)置而來(lái)。代數(shù)余子式是去

18、掉該元素所在行和列，剩下的元素組成的行列式，其符號(hào)是，轉(zhuǎn)置是。三、改進(jìn)牛頓法上述牛頓法可以認(rèn)為是搜索方向?yàn)榍业牡．?dāng)遇到F(X)非線(xiàn)性嚴(yán)重時(shí)，不一定收斂。此外牛頓法對(duì)初始點(diǎn)的要求較嚴(yán)，因此有人對(duì)牛頓法作了修正。取作搜索方向。但不假定為1，而是由一維搜索決定，即：這種方法叫改進(jìn)牛頓法，或者修正牛頓法。它保持了牛頓法收斂快的特點(diǎn)，對(duì)起始點(diǎn)放寬了要求。對(duì)目標(biāo)函數(shù)二階可導(dǎo)，海賽矩陣可逆的尋優(yōu)問(wèn)題非常有效。但這樣的優(yōu)化問(wèn)題在工程中極少出現(xiàn)。但其思想具有重要的理論意義。后人在此基礎(chǔ)上發(fā)明了變尺度法（也叫DFP法）。變尺度法的基本思路是構(gòu)造一個(gè)代替改進(jìn)牛頓法中的。取單位矩陣。的構(gòu)造雖不需要求及其逆了，但構(gòu)

19、造方法仍很繁，見(jiàn)陳立周的第二版77頁(yè)，本課忽略。第六講 無(wú)約束問(wèn)題的優(yōu)化方法（二）坐標(biāo)輪換法，共軛方向法x1x2X（0）一、坐標(biāo)輪換法的基本思路將1個(gè)多維的無(wú)約束優(yōu)化問(wèn)題轉(zhuǎn)變成一系列一維優(yōu)化問(wèn)題來(lái)求解。基本做法：在n個(gè)變量中，保持其中n-1個(gè)變量不變，選擇變量x1作為搜索方向。一維搜索得到最優(yōu)點(diǎn)，再沿x2方向一維搜索，得到最優(yōu)點(diǎn)，再沿xn方向搜索，得到最優(yōu)點(diǎn)。至此即完成了第一輪的搜索。如果未達(dá)到最優(yōu)條件，將前一輪的終點(diǎn)作為新的起點(diǎn)，再進(jìn)行第二輪沿各個(gè)變量的一維搜索，分別得到，。如此繼續(xù)下去，直到最優(yōu)。坐標(biāo)輪換法增加了“輪”的概念，每一輪里包含n次一維搜索，每次的搜索方向是： i=1,2,，n

20、每次搜索后得到新點(diǎn)： i=1,2,，n 其余方法均與前述方法相同。二、共軛方向的概念共軛是正交概念推廣。設(shè), 是內(nèi)的兩方向（矢量）若,則, 是垂直的，即正交的。在三維空間內(nèi)正交與垂直是相同的。此式也可寫(xiě)成 。 I：?jiǎn)挝痪仃嚠?dāng)時(shí)，若。則稱(chēng), 在n維空間內(nèi)正交。但這樣正交的方向不止兩個(gè)，若存在一組方向：，若 ，. .即：，則這組方向都是正交的。n維空間內(nèi)的一組正交方向有而且只有n個(gè)。共軛方向的意義：設(shè)矩陣A是階對(duì)稱(chēng)正定矩陣，另有一組n個(gè)方向，若存在，則稱(chēng)方向組是關(guān)于矩陣A共軛的。這是矩陣A的“對(duì)稱(chēng)”，“正定”兩個(gè)條件是必不可少的。在2維空間內(nèi)，A為對(duì)稱(chēng)正定矩陣，關(guān)于A的共軛方向（矢量）每組含兩個(gè)。

21、例：設(shè), 方向，關(guān)于A共軛： 此外：關(guān)于A也是共軛的；可見(jiàn)：關(guān)于一個(gè)對(duì)稱(chēng)正定矩陣，存在不止一組（實(shí)際有無(wú)數(shù)組）共軛方向（矢量）。如何理解共軛方向的幾何意義？是對(duì)做線(xiàn)性變換。因此共軛可以理解為：經(jīng)過(guò)線(xiàn)性變換后與正交，則二者關(guān)于線(xiàn)性變換矩陣共軛。三共軛梯度法共軛梯度法是為了解決最速下降法（梯度法）在接近極值點(diǎn)時(shí)收斂太慢而提出的。因?yàn)槟繕?biāo)函數(shù)在接近極值點(diǎn)附近，變化很平坦，太小，所以進(jìn)步也很緩慢。但在接近極值附近時(shí)，目標(biāo)函數(shù)在極值點(diǎn)的泰勒展開(kāi)是的很好近似，而對(duì)的最佳搜索的方向是牛頓方向：用此方向搜索的極值可以一步到達(dá)極點(diǎn)。但求目標(biāo)函數(shù)的逆也不是很容易的事情。能否用較為簡(jiǎn)單的辦法求出此，或者構(gòu)造一個(gè)與及

22、其接近的方向來(lái)，能達(dá)到求泰勒展開(kāi)函數(shù)的極值一步到位的效果。 可以證明，用本次尋優(yōu)的負(fù)梯度方向與上次尋優(yōu)方向的線(xiàn)性組合而構(gòu)成的與牛頓方向非常接近。即： 或者： 其中系數(shù)： 此即共軛梯度法的尋優(yōu)方向的構(gòu)造方法。用共軛梯度法尋優(yōu)時(shí)，取第一次的搜索方向?yàn)椋旱诙我约耙院螅蒙鲜龉綐?gòu)造。例：Min ，（見(jiàn)陳立國(guó)教材第二版72頁(yè)，劉維信教材第一版84頁(yè)。注：陳立國(guó)教材33頁(yè)倒數(shù)第6行多一個(gè)“”號(hào)，倒數(shù)第5行的根號(hào)和平方可以約去。也可以用0.618法求出來(lái)。）由例可見(jiàn)，共軛梯度法每次都要用梯度方向和梯度的模來(lái)構(gòu)造新方向。四共軛方向法以二維目標(biāo)函數(shù)尋優(yōu)，來(lái)說(shuō)明共軛方向法的思路。設(shè)從出發(fā)，首先沿坐標(biāo)軸搜索，（

23、即搜索方向?yàn)?上標(biāo)表示第一輪，下標(biāo)表示第一個(gè)坐標(biāo)軸方向）。得優(yōu)點(diǎn)；在點(diǎn)沿第二坐標(biāo)軸搜索（即?。?得到優(yōu)點(diǎn)。至此完成了第一輪的坐標(biāo)輪換法的搜索。然后構(gòu)造出一個(gè)新的搜索方向：，沿此方向做第2+1=3次的搜索，得到新優(yōu)點(diǎn)作為第二輪尋優(yōu)的起點(diǎn)。這第2+1次的搜索是為下一輪（第二輪）的搜索打基礎(chǔ)的，即提供起點(diǎn)的。第二輪的搜索方向是第一輪的搜索方向丟棄第一個(gè)，但取用第一輪的第2個(gè)和第3個(gè)方向，即取，和。從出發(fā)沿搜索得到點(diǎn)，從出發(fā)沿搜索得點(diǎn)。然后再構(gòu)造一個(gè)新方向，即第二輪搜索的首尾點(diǎn)相連方向作為第二輪的第2+1次搜索，即可得到一個(gè)新點(diǎn)，作為第三輪搜索的起點(diǎn)。由此可以看到，共軛方向法搜索時(shí)，存在“輪”的概念，

24、每輪包含2+1次一維搜索，下輪的2+1次搜索方向是上輪的后n個(gè)方向，再加一個(gè)本輪首尾點(diǎn)相連方向。第一輪搜索的方向：第二輪搜索的方向：第三輪搜索的方向：注意：這里的共軛方向只有是共軛的。n維尋優(yōu)問(wèn)題方法與工作的相同，不再贅述。 例題： Min 略。第七講 無(wú)約束問(wèn)題優(yōu)化方法(三)Powell 法 DFP變尺度法一、 Powell 法（改進(jìn)的共軛方向法）1、共軛方向法的缺陷第k輪的共軛方向：，其中，。第k+1輪去掉第一個(gè)方向，剩下的n個(gè)方向可能線(xiàn)性相關(guān)，引起實(shí)際上少了一維，導(dǎo)致收斂不到真正的最優(yōu)點(diǎn)上。2、Powell 法提出的改進(jìn)在完成一輪的尋優(yōu)后，不一定去掉，而是有選擇的去掉一個(gè)，確保剩下的n個(gè)

25、方向線(xiàn)性無(wú)關(guān)。判定條件如下：第k輪尋優(yōu)的方向：，其中，；第k輪尋優(yōu)得到的點(diǎn)： ；計(jì)算3個(gè)點(diǎn)的目標(biāo)函數(shù)：。其中，點(diǎn)叫做反射點(diǎn)；若存在：，且：其中， （即相鄰尋優(yōu)中目標(biāo)函數(shù)下降最大的一個(gè)）則，第k+1輪尋優(yōu)去掉對(duì)應(yīng)的方向 。保留：為第k+1輪的搜索方向。3、Powell 法的尋優(yōu)步驟與共軛方向法基本相同，只增加了在每一輪（或每一次）尋優(yōu)搜索后計(jì)算目標(biāo)函數(shù)值，以及與上次目標(biāo)函數(shù)的差，并在一輪的目標(biāo)函數(shù)中找出下降最大的第m次及對(duì)應(yīng)的方向S，并舍棄。例題：用Powell法求函數(shù)的最優(yōu)點(diǎn)。計(jì)算精度要求。解：取初始點(diǎn)。時(shí)，第一輪迭代的搜索方向取兩個(gè)坐標(biāo)的單位向量，從出發(fā)，先從方向進(jìn)行一維最優(yōu)搜索，由第三講所

26、學(xué)知識(shí)可得，由此得最優(yōu)點(diǎn)：同理，沿方向進(jìn)行一維搜索可得，從而得最優(yōu)點(diǎn)：計(jì)算第個(gè)方向計(jì)算方向上的反射點(diǎn)：計(jì)算相鄰二點(diǎn)函數(shù)值的下降量：檢驗(yàn)判別條件成立，故應(yīng)以方向代替，并求方向上的極小點(diǎn)。同上，可求得至此，完成第一輪的第次搜索。時(shí)，二、 DFP變尺度法1、變尺度法的基本思路DFP變尺度法又叫改進(jìn)的牛頓法或改進(jìn)的擬牛頓法。牛頓法和擬牛頓法的搜索方向：，即要求Hessian矩陣及其逆，又要求梯度，很繁。DFP變尺度法是設(shè)法構(gòu)造一個(gè)對(duì)稱(chēng)正定矩陣來(lái)代替，并在迭代過(guò)程中逐漸逼近，使搜索在接近極值點(diǎn)附近時(shí)收斂速度加速。2、近似矩陣的構(gòu)造方法其中，。注：這里的不是海塞矩陣，而是構(gòu)造的矩陣。詳細(xì)推導(dǎo)過(guò)程參考陳立周

27、主編的機(jī)械優(yōu)化設(shè)計(jì)方法第二版76-77頁(yè)。3、變尺度法的步驟(1)選取初始點(diǎn)，確定計(jì)算精度要求。(2)令計(jì)算和擬牛頓方向(3)進(jìn)行一維搜索求使，得(4)檢驗(yàn)精度，計(jì)算,若，則停止，其最小點(diǎn)為。若否，則進(jìn)行下一步。(5)檢查迭代次數(shù)，若，則重置，從負(fù)梯度方向開(kāi)始，并取。否則進(jìn)行下一步。(6)構(gòu)造新的擬牛頓方向而 令，轉(zhuǎn)向(3)。4、變尺度法的優(yōu)缺點(diǎn)(1) DFP變尺度法不需要求海塞矩陣及其逆陣，但需利用一階導(dǎo)數(shù)信息。由于DFP法開(kāi)始時(shí)是梯度法，所以從任一初始點(diǎn)通過(guò)梯度方向找到一個(gè)比較好的迭代點(diǎn)，這位以后的逐次迭代創(chuàng)造了有利的條件。(2) DFP法的收斂速度介于梯度法和牛頓法之間。大量計(jì)算實(shí)踐證明

28、，DFP方法是目前無(wú)約束優(yōu)化方法中一種比較有效的算法。(3) 計(jì)算實(shí)踐表明，一維搜索的精度對(duì)收斂速度影響不大。但如果精度太低，也有可能會(huì)使計(jì)算失效，因此對(duì)一維搜索的精度要求一般不低于終止計(jì)算的精度。第八講 習(xí)題課（二）一已知目標(biāo)函數(shù)： 用最速下降法優(yōu)化第一輪，用牛頓法優(yōu)化第二輪，用改進(jìn)牛頓法求出最優(yōu)值。二已知目標(biāo)函數(shù)： 用坐標(biāo)輪換法優(yōu)化第一輪；構(gòu)造出一組共軛方向，優(yōu)化第二輪，再用Powell法優(yōu)化第三輪。三已知目標(biāo)函數(shù)： 用共軛梯度法和DFP變尺度法各優(yōu)化一輪。第九講 約束優(yōu)化問(wèn)題的直接解法約束優(yōu)化問(wèn)題分為直接解法和間接解法兩類(lèi)。直接解法是首先在Rn空間內(nèi)找到滿(mǎn)足不等式約束的可行域，每次搜索都

29、在可行域內(nèi)進(jìn)行，直到找到最優(yōu)解和最優(yōu)值。間接式解法是將約束優(yōu)化問(wèn)題轉(zhuǎn)變成一系列的無(wú)約束優(yōu)化問(wèn)題來(lái)解。直接解法主要有隨機(jī)方向搜索法、復(fù)合形法、可行方向法、梯度投影法等；間接解法主要有拉格朗日乘子法和懲罰函數(shù)法。本課只講復(fù)合形法和拉格朗日乘子法，以及懲罰函數(shù)法。一、 約束優(yōu)化問(wèn)題的直接解法對(duì)約束問(wèn)題： Min S. T n此模型雖為n維約束問(wèn)題中，但含有q個(gè)等式約束。如果這些等式約束都是線(xiàn)性無(wú)關(guān)的，將它們帶入到目標(biāo)函數(shù)，則該問(wèn)題的實(shí)際維數(shù)是n-q。既消除了等式約束，又降低了優(yōu)化維數(shù)。因此約束優(yōu)化問(wèn)題一般只研究不等式約束即可。直接解法的每一步求解過(guò)程都是在可行域內(nèi)進(jìn)行，其基本思路與無(wú)約束優(yōu)化基本相同

30、。所不同的有如下幾個(gè)關(guān)鍵問(wèn)題：A. 首先要找到（或者建立）可行域D，對(duì)于維數(shù)較高時(shí)，較為困難；B. 所選的初始點(diǎn)及每次的尋優(yōu)點(diǎn)必須在可行域內(nèi)（每次都要驗(yàn)證）。C. 每次構(gòu)造的搜索方向必須是可行方向（即沿此方向搜索，目標(biāo)函數(shù)值一定下降的方向），且要驗(yàn)證。D. 一維搜索得到的步長(zhǎng)也必須是可行步長(zhǎng)（沒(méi)有超出可行域），才能保證搜索到的新點(diǎn) 也在可行域內(nèi)。E. 如果可行域D不是凸集，尋優(yōu)的結(jié)果可能與起始點(diǎn)的選擇有關(guān)。因此要選擇不同的起始點(diǎn)多優(yōu)化幾次。二、 復(fù)合形法 復(fù)合形，就是在n維空間內(nèi)由m個(gè)頂點(diǎn)構(gòu)成的不規(guī)則多面體，其中，其本質(zhì)是在可行域D內(nèi)的一個(gè)子域。2.1 復(fù)合形法的基本思路復(fù)合形法也與其他方法一

31、樣，關(guān)鍵是確定搜索方向和搜索步長(zhǎng)。其搜索方向是根據(jù)復(fù)合形的各個(gè)頂點(diǎn)的目標(biāo)函數(shù)值的大小關(guān)系、利用統(tǒng)計(jì)規(guī)律（函數(shù)值下降的概率大）來(lái)確定的。搜索步長(zhǎng)也是經(jīng)驗(yàn)選取的，不一定使用一維搜索。以2維問(wèn)題為例：建立可行域后，在其內(nèi)找3點(diǎn)（或者4點(diǎn)），建立一個(gè)三角形（或者四邊形），即復(fù)合形。分別求出各頂點(diǎn)的目標(biāo)函數(shù)值，按照函數(shù)值大小分出最壞點(diǎn)X(H)（函數(shù)值最大點(diǎn)）、次壞點(diǎn)X(C)（函數(shù)值次大點(diǎn)），和最好點(diǎn)X(L)（函數(shù)值最小點(diǎn)）。然后求出除最壞點(diǎn)外其余各點(diǎn)的幾何中心X(S)，取最壞點(diǎn)X(H)與幾何中心X(S)的連線(xiàn)X(S- X(H)為搜索方向S（k），沿S（k）搜索得到一個(gè)更好的點(diǎn)X(R)（叫映射點(diǎn)），用X(

32、R)代替X(H)組成新的復(fù)合形，進(jìn)行下一輪尋優(yōu)。顯然，X(R)必須滿(mǎn)足如下兩個(gè)條件：1. F(X(R)F( X(H)，2. X(R)也在可行域內(nèi)。如此循環(huán)，直至找到最優(yōu)點(diǎn)X(*)。2.2 復(fù)合形法直接尋優(yōu)的步驟（1）分析約束方程，建立可行域；（2）在可行域內(nèi)選擇m個(gè)頂點(diǎn)（），組成復(fù)合形；（3）計(jì)算各個(gè)頂點(diǎn)的目標(biāo)函數(shù)值，按照大小排隊(duì)，選出最壞點(diǎn)X(H)、次壞點(diǎn)X(C)、和最好點(diǎn)X(L)；（4）計(jì)算除最壞點(diǎn)外的m-1 個(gè)頂點(diǎn)的幾何中心點(diǎn)X(S)，并驗(yàn)證其是否在可行域內(nèi)， ； 但（5）若X(S)在可行域內(nèi)，構(gòu)建搜索方向 S（k）= X(S- X(H)，求映射點(diǎn)： ?？梢杂靡痪S搜索求出，也可以用經(jīng)驗(yàn)給

33、出。例如取，若越出可行域，將其減半；還不行，繼續(xù)減半，直至映射點(diǎn)X(R)在可行域內(nèi)為止。若幾何中心點(diǎn)X(S)不在可行域內(nèi)，說(shuō)明可行域?yàn)榉峭辜?，返回?），重新組建復(fù)合形；（6）計(jì)算映射點(diǎn)的目標(biāo)函數(shù)值F(X(R)，并與最壞值F( X(H) 比較。若F(X(R)F( X(H)，用映射點(diǎn)代替最壞點(diǎn)，組成新的復(fù)合形，完成一次迭代。若F(X(R)F( X(H)，將減半后再計(jì)算映射點(diǎn)X(R)及其對(duì)應(yīng)的目標(biāo)函數(shù)值F(X(R)，若既滿(mǎn)足X(R)為可行點(diǎn)（在可行域），又滿(mǎn)足F(X(R)F( X(H)，用映射點(diǎn)代替最壞點(diǎn)，組成新的復(fù)合形，完成一次迭代。否則，繼續(xù)將再減半，。（7）每完成一次迭代，要檢驗(yàn)終止條件。反

34、復(fù)迭代若干次后，復(fù)合形越來(lái)越小，逐漸向最優(yōu)點(diǎn)逼近。檢驗(yàn)方法是：所有頂點(diǎn)的目標(biāo)函數(shù)值與各頂點(diǎn)幾何中心點(diǎn)的目標(biāo)函數(shù)值的差平方和小于設(shè)定值即結(jié)束，即復(fù)合形的“體積”小于設(shè)定值。 其中：F(X(j) 是復(fù)合形各頂點(diǎn)的目標(biāo)函數(shù)值，F(xiàn)(X(c)是頂點(diǎn)的幾何中心目標(biāo)函數(shù)值。由上面的步驟可以看出，復(fù)合形法最突出的優(yōu)點(diǎn)是不需要求導(dǎo)，僅僅計(jì)算映射點(diǎn)及其目標(biāo)函數(shù)值即可。只要反復(fù)迭代，復(fù)合形就會(huì)逐漸“收縮”到最優(yōu)點(diǎn)，其缺點(diǎn)是：當(dāng)可行域?yàn)榉峭辜瘯r(shí)，會(huì)出現(xiàn)映射點(diǎn)越出可行域，或者映射點(diǎn)的目標(biāo)函數(shù)值大于最壞點(diǎn)。遇到這兩種情況，幾乎前功盡棄，都要重新組成新的復(fù)合形，從頭再來(lái)。例題：用復(fù)合形法求解汽車(chē)轉(zhuǎn)向梯形的優(yōu)化設(shè)計(jì)方案。解法

35、：劉惟信 機(jī)械最優(yōu)化設(shè)計(jì) 第一版 P123； 陳立周 機(jī)械優(yōu)化設(shè)計(jì)方法 第二版 P95第十講 約束最優(yōu)化問(wèn)題的間接解法(1)一、約束優(yōu)化的基本方法約束優(yōu)化分為間接解法和直接解法兩種基本方法。直接解法的基本思路是：通過(guò)對(duì)個(gè)不等式約束進(jìn)行分析，找出其可行域D。在可行域內(nèi)找一起始點(diǎn)和可行方向，采用無(wú)約束方法進(jìn)行尋優(yōu)。其基本方法有隨機(jī)方向搜索法、復(fù)合形法、可行方向法等。間接解法的基本思路是：將一個(gè)有約束的問(wèn)題直接轉(zhuǎn)化成一個(gè)或一系列無(wú)約束問(wèn)題來(lái)求解。即構(gòu)造一個(gè)新的目標(biāo)函數(shù)，該新目標(biāo)函數(shù)包含原目標(biāo)函數(shù)和全部的不等式及等式約束，從而消除了約束。對(duì)新目標(biāo)函數(shù)尋優(yōu)，即可得到原目標(biāo)函數(shù)。常用的方法有：拉格朗日乘子

36、法、懲罰函數(shù)法（包括內(nèi)點(diǎn)懲罰函數(shù)法和外點(diǎn)懲罰函數(shù)法）。直接解法只適用于不等式約束問(wèn)題，間接解法適用于等式和不等式約束問(wèn)題。二、拉格朗日乘子法(間接解法之一)1、只有等式約束的優(yōu)化問(wèn)題的拉格朗日乘子法約束優(yōu)化： Min s.t: , 構(gòu)造一個(gè)拉格朗日函數(shù)作為新目標(biāo)函數(shù)，包含目標(biāo)函數(shù)和約束函數(shù)：Min 式中：，叫拉格朗日乘子。拉格朗日函數(shù)中包含n個(gè)設(shè)計(jì)變量xi和q個(gè)待定系數(shù)i，共（n+q）個(gè)未知變量。它存在極值的條件為：解此方程，可得： ， ，其中極為原目標(biāo)函數(shù)在約束條件下的最優(yōu)解。*的各項(xiàng)值可為正，亦可為負(fù)。為便于在計(jì)算機(jī)上直接尋優(yōu)，拉格朗日函數(shù)常常改變?yōu)椋篗in 求函數(shù)Z的極小值，也就是原等式

37、約束的目標(biāo)函數(shù)的最優(yōu)解。2、只有不等式約束的優(yōu)化問(wèn)題的拉格朗日乘子法 約束優(yōu)化： Min s.t: , 構(gòu)造一個(gè)拉格朗日函數(shù)作為新目標(biāo)函數(shù)：Min 意義同上，叫松弛變量。引入松弛變量是為了讓各個(gè)非負(fù)項(xiàng)與總小于0的約束項(xiàng)相加后變成等式約束。上式存在極值點(diǎn)的條件是：解上述聯(lián)立方程式，得到X*極為原不等式約束問(wèn)題的最優(yōu)解。同樣，由于解多個(gè)偏導(dǎo)數(shù)組成的方程組比較麻煩，在使用計(jì)算機(jī)尋優(yōu)時(shí)，常將拉格朗日函數(shù)變換為：求Z的無(wú)約束最優(yōu)值，即為原目標(biāo)函數(shù)的最優(yōu)值。3、既有等式又有不等式約束的拉格朗日乘子法 約束優(yōu)化： Min s.t: , , 構(gòu)造拉格朗日函數(shù)： Min 此拉格朗日函數(shù)取得極值的條件依然是其對(duì)三

38、組變量的偏導(dǎo)數(shù)為零：解此方程（共個(gè)未知數(shù)），得到X*即為原約束問(wèn)題的最優(yōu)解。同樣可以將解聯(lián)立方程轉(zhuǎn)變?yōu)閷?duì)下式求無(wú)約束優(yōu)化問(wèn)題： 求出Z的無(wú)約束最優(yōu)值，即為原目標(biāo)函數(shù)的最優(yōu)值。例題：第11講 約束優(yōu)化問(wèn)題的間接解法 （2）三、內(nèi)點(diǎn)懲罰函數(shù)法間接解法之二 約束優(yōu)化： Min s.t: , , 構(gòu)造新目標(biāo)函數(shù)：其中：r1，r2：加權(quán)因子，又叫懲罰因子；：由不等式約束構(gòu)成的復(fù)合函數(shù)，也叫懲罰函數(shù)；：由等式約束構(gòu)成的復(fù)合函數(shù)，也叫懲罰函數(shù)。對(duì)尋優(yōu)，即可得到的最優(yōu)解。構(gòu)造新目標(biāo)函數(shù)，涉及兩個(gè)問(wèn)題：A：加權(quán)因子（懲罰因子）如何取？B：由約束方程（條件）怎樣構(gòu)成復(fù)合函數(shù)？先看一個(gè)實(shí)例：Min s.t ：該問(wèn)題很簡(jiǎn)單（見(jiàn)右