《機械優化設計》講義第一講第一課時：機械優化設計概論課程的研究對象：根據最優化原理和方法，利用計算機為計算工具，尋求最優設計參數的一種現代設計方法。目標：本課程目標體系可以分為三大塊：理論基礎、算法的分析、理解和掌握，算法的設計、實現（編程）能力的培養。將主要是對算法的學習為主，并兼顧培養一定的解決實際問題能力、上機編程調試能力。首先，幾個概念：優化（或最優化原理、方法）、優化設計、機械（工程）優化設計?，F代的優化方法，研究某些數學上定義的問題的，利用計算機為計算工具的最優解。優化理論本身是一種應用性很強的學科，而工程優化設計（特別是機械優化設計）由于采用計算機作為工具解決工程中的優化問題，可以歸入計算機輔助設計(CAD)的研究范疇。再，優化方法的發展：源頭是數學的極值問題，但不是簡單的極值問題，計算機算法和運算的引入是關鍵。從理論與實踐的關系方面，符合實踐-理論-實踐的過程。優化原理和方法的理論基礎歸根結底還是來源于實際生產生活當中，特別是工程、管理領域對最優方案的尋找，一旦發展為一種相對獨立系統、成熟的理論基礎，反過來可以指導工程、管理領域最優方案的尋找（理論本身也在實踐應用中不斷進步、完善）。解決優化設計問題的一般步驟：機械設計問題機械設計問題建立數學模型選擇或設計算法編碼調試計算結果的分析整理相關知識：數學方面：微積分、線性代數；計算機方面：編程語言、計算方法；專業領域方面：機械原理、力學等知識內容：數學基礎、一維到多維、無約束到有約束數學模型三個基本概念：設計變量、目標函數、約束條件設計變量：相對于設計常量（如材料的機械性能）在設計域中變量是否連續：連續變量、離散變量（齒輪的齒數，）。設計問題的維數，表征了設計的自由度。每個設計問題的方案（設計點）為設計空間中的一個對應的點。設計空間：二維（設計平面）、三維（設計空間）、更高維（超設計空間）。目標函數：設計變量的函數。單目標、多目標函數。等值面的概念：設計目標為常量時形成的曲面（等值線、等值面、超等值面）。幾何意義：等值線（等值線的公共中心既是無約束極小點）、等值面。約束條件： 等式約束（約數個數小于設計問題的維數） 不等式約束 滿足約束條件的設計點的集合構成可行域D：可行點、非可行點、邊界設計點 幾何意義（二維）：對于設計空間不滿足不等式約束的部分，用陰影表示。數學模型的一般形式：尋找一個滿足約束條件的設計點，使得目標函數值最小。標準形式：SKIPIF1<0優化問題的幾何描述第二章數學基礎和數值迭代法2.1函數的方向導數和梯度一、函數的方向導數SKIPIF1<0二、函數的梯度SKIPIF1<0令SKIPIF1<0為函數在X點的梯度，包含函數的一階導數信息。SKIPIF1<0即梯度方向是函數變化率最大的方向。2.2函數的泰勒展開與黑塞矩陣一、泰勒展開式SKIPIF1<0其中黑塞（hessian）矩陣:SKIPIF1<0包含函數的二階導數信息。2.3凸集、凸函數、凸規劃一、凸集SKIPIF1<0有SKIPIF1<0，則D為凸集.凸集的性質：1.若D為凸集，λ為實數，則λD仍為凸集。（凸集的實數積為凸集） 2．若D、φ均為凸集，則二者的并集（和）為凸集。（凸集的和為凸集） 3．若D、φ均為凸集，則二者的交集（積）為凸集。（凸集的積為凸集）二、凸函數En的子集D為凸集，f為D上的函數，SKIPIF1<0恒有SKIPIF1<0，則f為D上的凸函數。反之為凹函數。凸函數的性質：設f為D上的凸函數，λ為實數，則λf為D上的凸函數。設f1，f2為D上的凸函數,則f=f1+f2為D上的凸函數。若f在En一階可微，則對SKIPIF1<0，f為凸函數的充要條件：SKIPIF1<0若f在En二階可微，則對SKIPIF1<0，f為凸函數的充要條件：黑塞矩陣半正定（若正定，嚴格凸函數）。三、凸規劃SKIPIF1<0其中目標函數、不等式約束均為凸函數，則稱該問題為凸規劃。凸規劃的性質：集合SKIPIF1<0為凸集。可行域為凸集。任何局部最優解即為全域最優解。若目標函數可微，則最優解的充要條件：SKIPIF1<02.4無約束優化的極值條件 1．一階導數（梯度）為零。 2．二階導數（黑塞矩陣）正定（極小點），或負定（極大點）。2.5有約束優化的極值條件(Kuhn-Tucker條件)對優化問題SKIPIF1<0庫恩-塔克條件描述為SKIPIF1<0，即約束極小點存在的必要條件是：目標函數在該點的梯度可表示為諸約束面梯度的線性組合的負值。從幾何意義上來說，即約束極小點目標函數梯度向量的反方向必須落在諸約束面所構成的錐角范圍之內。對于凸規劃問題，K-T條件是充要條件。只能作為驗證條件，但到底是局部最優點還是全域最優點尚不能確定。2.6優化問題的數值迭代法1．迭代過程SKIPIF1<0(k=0,1,2,…)迭代的基本思想：搜索、迭代、逼近。2．迭代終止條件：點距準則：SKIPIF1<0函數值下降準則：SKIPIF1<0梯度準則：SKIPIF1<0第三章一維搜索的優化方法一維優化是多維優化的基礎。包含兩個步驟 1．確定搜索區間（進退法） 2．尋優（黃金分割法、二次差值法）3.1進退法——一維搜索區間的確定基本思想：對單峰函數（凸函數）f(x)，只要找到可行域內三個點a<b<c，滿足函數值先減小再增大的趨勢，即f(a)>f(b)且f(b)<f(c)，則可以確定區間[a,c]內必存在最優點。

算法流程：SKIPIF1<03.2一維優化方法——黃金分割法一維搜索的基本思想：在確定了搜索區間的前提下，不斷縮小搜索區間，直到區間的寬度小于預定的精度。黃金分割法的基本思想：黃金分割點的計算：SKIPIF1<0算法流程：SKIPIF1<03.3一維優化方法——二次插值法首先，10分鐘回顧上次課的內容，并講解作業：進退法、黃金分割法概要、 103頁作業（程序演示）30分鐘：基本思路：類似于二次曲線擬合。以搜索區間三個點構造一個二次曲線（拋物線），并以該二次曲線的極值點替代目標函數的最優點，若不滿足迭代中止條件，縮短搜索區間，反復迭代，直到相近兩次二次曲線極值滿足精度要求（點距準則）。3.3.1基本原理搜索區間[a1，a3]及其中間某一點（a2）這三個點構造一個二次曲線。這三個點構成一個三元線性方程組,可求得該二次曲線極值點a*p作為a4。其中a*p=0.5(a1+a3-C1/C2) C1=(f3-f1)/(a3-a1) C2=[(f2-f1)/(a2-a1)-C1]/(a2-a1)若a2與a4之間趨于重合，則迭代結束；否則比較這四點的函數值，并在其中選擇三點，滿足函數值“先遞增再遞減”的趨勢，構成新的a1、a2、a3。開始新一輪迭代。3.3.2迭代過程和算法流程例題本周五，p24,p29本周五，p24,p29SKIPIF1<0

第四章（多維）無約束優化方法概述：工程優化問題通常都是多維有約束優化問題，但需從一維無約束問題到多維無約束優化問題再到多維約束優化問題的由簡單到復雜的循序漸進的學習研究過程。無約束優化問題數學模型：SKIPIF1<0分類，從是否利用目標函數的導數信息，分直接法和間接法直接法：坐標輪換法、共軛方向法、鮑威爾法直接法：坐標輪換法、共軛方向法、鮑威爾法間接法：梯度法、牛頓法、變尺度法4.1坐標輪換法4.1.1坐標輪換法基本原理將多維無約束優化問題分解、轉化為一系列一維優化問題，輪換沿各個坐標軸一維搜索，直到求得最優點。在每次迭代內部，要依次沿各坐標軸進行N次（N為優化問題的維數）一維搜索。這種一維搜索是固定其它N-1維變量，視為常量，然后進行一維搜索，SKIPIF1<0，對于第k輪迭代，須重復N次該式的一維搜索，搜索的參數為ajk（即要優化的參數是ajk），為相對第j維變量的搜索步長，搜索方向為第j維空間坐標的方向。當k輪迭代結束后，本輪搜索的重點作為下一輪的起點，即SKIPIF1<0，然后投入下一輪迭代。4.1.2該方法特點不考慮目標函數本身的變化情況（函數特點），簡單、效率低、收斂速度慢。4.2共軛方向法4.2.1共軛方向對于N維正定二次函數SKIPIF1<0(當N=2，為同心橢圓族)，[H]為函數f的黑塞矩陣(正定對稱陣)。若存在兩個方向向量SKIPIF1<0，SKIPIF1<0，滿足SKIPIF1<0，則稱SKIPIF1<0與SKIPIF1<0為共軛方向。如何構造共軛方向（二維）？對于某兩點SKIPIF1<0，沿方向SKIPIF1<0（SKIPIF1<0不平行）一維搜索得到兩個最優點SKIPIF1<0，構成方向SKIPIF1<0，則可以證明SKIPIF1<0與SKIPIF1<0為共軛方向，即SKIPIF1<0（對于二維問題，可以簡單證明）當然，這個結論可以從2維推廣到N維。同樣，說明對于N維函數，有N個共軛方向。對于二次函數，只要經過N個一維搜索即可到達最優點（即N維空間內完成一輪迭代）。對于大于二次的函數，則可能需要將上一輪迭代的終點作為新一輪迭代的起點。在構造迭代方程式時，可以用二次泰勒展開式來近似目標函數的等值面。第二課時：4.2.2共軛方向法基本原理第一輪迭代與坐標輪換法相同。將起點和N次一維搜索的末點組成一個新的方向，沿這個方向一維搜索，得到本輪迭代的終點。從第二輪起，舍去前一輪的第一個一維搜索方向，將前一輪的后N個一維搜索方向作為本輪迭代的前N個方向，這N個方向的一維搜索終點與本輪搜索的起點構成第N+1個一維搜索方向，沿這個方向做一維搜索，得到本輪搜索的終點。若不滿足精度要求，則重復迭代。4.2.3共軛方向法的特點收斂速度比坐標輪換法有明顯的提高，但前提是每次迭代所產生的新的方向與原來的N-1個方向之間要保持線性無關，若這些方向之間線性相關，則降低了搜索空間的維數，導致不能完全窮盡對設計空間每個方向的搜索，從而不能收斂于真正的最優解。

上機調試內容：SKIPIF1<04.3鮑威爾法4.3.1鮑威爾法基本原理共軛方向法的前提是每一輪迭代中新生成的第N+1個方向（共軛方向）與其它方向線性無關，如果出現線性相關，則導致算法不能正確收斂。鮑威爾為了解決該問題，加入了對共軛方向的判斷，如果線性無關則采用該方向，但并不是機械的替換上一輪第一個方向，而是替換函數值下降最多的方向；如果相關，則還是用上一輪迭代的方向。對于共軛方向法的判別準則。SKIPIF1<0（4-2）其中：f1 ——本輪迭代起點函數值f2 ——本輪迭代終點函數值f3 ——映射點函數值Δkm——函數值下降最大的一步一維搜索SKIPIF1<0若滿足公式（4-2）則去掉第m個方向，下一輪的m到N方向采用本輪次第m+1到N+1個方向；若不滿足，則本輪迭代結束，以本輪終點為下一輪起點，仍采用本輪的N個方向進行迭代。4.3.2迭代步驟（1）給定初始點和計算精度。（2）置k=1，取N個坐標軸的單位向量為搜索方向SKIPIF1<0（i=0,1,…,N-1），,SKIPIF1<0（3）從SKIPIF1<0出發，沿SKIPIF1<0一維搜索，得到N個極小點SKIPIF1<0（i=1,2,…,N）,找到函數值下降最快的一次一維搜索的函數下降值和方向，記作Δkm，SKIPIF1<0（4）計算反射點SKIPIF1<0，計算f1，f2，f3。（5）若滿足（4-2）式，構造本輪迭代第N+1個方向SKIPIF1<0，由N次一維搜索的終點沿SKIPIF1<0一維搜索得到本輪迭代終點，作為下一輪迭代（k+1輪）起點；去掉SKIPIF1<0方向，將SKIPIF1<0作為下一輪迭代的第N個方向。 否則，保留前N個搜索方向到下一輪迭代，取min(f2，f3)對應的點作為下一輪起點。（6）若滿足迭代終止條件SKIPIF1<0，終止迭代，輸出優化結果，否則kk+1,返回（3）。4.3.3算法流程（見下頁）共軛方向法習題課：用共軛方向法和鮑威爾法求解優化問題SKIPIF1<0，初始點[0,0]T,精度ε=0.01。解：共軛方向法： 鮑威爾法：

SKIPIF1<04.4梯度法（最速下降法）4.4.1梯度法基本原理無約束優化的直接法（坐標輪換法和共軛方向法、鮑威爾法）沒有考慮無約束優化最優解存在的必要條件（梯度為零），使用這一條件，可以設計出更為高效的算法，所謂間接法（梯度法、牛頓法、變尺度法）。梯度方向是函數值變化最快的方向，那么負梯度方向便是函數值下降最快的方向。從這一點受啟發，可以使迭代方向沿梯度方向進行一維搜索來再多維空間尋優。即搜索方向為梯度方向：SKIPIF1<0，或SKIPIF1<0，則迭代公式為SKIPIF1<0。4.4.2梯度法的特點前提是梯度存在。優點是算法簡單。相鄰兩次迭代的搜索方向垂直。即SKIPIF1<0證明：SKIPIF1<0，即k輪迭代經過一次一維搜索由k點到達k+1點，那么SKIPIF1<0，對于一維優化有SKIPIF1<0，所以SKIPIF1<0可見，相鄰兩輪迭代的搜索方向并不一致，為相互垂直的鋸齒形過程。剃度法對于迭代出發點目標函數等值面偏心率為零時很有效，但對于有偏心的其效率就低了，隨偏心率的增加，迭代終止的難度也在增加?？梢娺@種搜索在接近目標時的收斂是比較慢（缺點）的，效率也就不會高了。剃度法一般并不作為工程中實際應用的方法，常用于其他方法的初始迭代（類似于坐標輪換法）。4.5牛頓法4.5.1牛頓法基本原理類似二次插值法，將目標函數在某一點附近二階泰勒展開，用這個二次函數的最優點近似目標函數的最優點；若不滿足精度要求，在上一輪得到的最優點最為本輪起點，再次用上述方法求最優點；直到滿足精度要求。4.5.2牛頓法迭代公式目標函數在的二次展開SKIPIF1<0，求近似目標函數的最優解，即SKIPIF1<0，有SKIPIF1<0即SKIPIF1<0，所以牛頓法迭代公式為SKIPIF1<0。從牛頓法的原理分析，如果目標函數為二次函數，有SKIPIF1<0，即牛頓法一輪迭代的終點就是最優解，而且是精確解。因此，牛頓法解決了二次函數非球面時的搜索方向問題，找到了一個可以消除偏心存在對采用梯度方向為搜索方向時的影響，直接給出了搜索二次函數最優點的方向?；蛘哒f，牛頓法對偏心率進行了變化，消除了二次曲面的偏心率，對于更高次曲面，也可以減小這種偏心。從而在一定程度上解決了梯度發收斂慢的缺點。4.5.3牛頓法的特點（1）由于采用了目標函數二階導數信息，收斂速度比梯度法快。（2）牛頓法迭代公式與一般迭代公式的區別在于，沒有步長系數。這使得在接近最優點時由于步長不能調節，可能會錯過最優點，造成算法的穩定性欠佳，甚至造成不能收斂而導致計算失敗。為了克服這一點提出阻尼牛頓法，添加阻尼因子，迭代公式為SKIPIF1<0。（3）需要計算黑塞矩陣及其逆矩陣，內存占用、計算量大；此外二階導數不存在，或者逆矩陣不存在的情況不能應用。4.6變尺度法4.6.1變尺度法基本原理牛頓法的缺點集中在黑塞矩陣及其逆的計算上，解決的方法是保留牛頓迭代法的迭代公式的形式，但不計算黑塞矩陣的逆，而是用一個矩陣去近似和逼近[H]-1,以減少計算量。4.6.2變尺度法迭代公式SKIPIF1<0[Ak]——稱為變尺度矩陣對第一輪迭代，[A0][I],即SKIPIF1<0，也就是梯度法當迭代過程逼近最優點，[Ak][H]-1,迭代公式變成SKIPIF1<0，也就是阻尼牛頓法。所以，可以把變尺度法看作梯度法和牛頓法的改進算法?；蛘咛荻确ê团ｎD法是變尺度法的特例。至于變尺度矩陣[Ak]如何構造，才能達到預期的效果，方法很多，主要介紹DFP法和BFGS法。思路為：為了使變尺度矩陣隨著迭代過程逐漸逼近黑塞矩陣的逆，構造SKIPIF1<0，其中SKIPIF1<0為k次迭代的修正矩陣。4.6.2DFP變尺度法變尺度矩陣的修正是變尺度法區別于牛頓法之處：修正矩陣SKIPIF1<0其中SKIPIF1<0，相鄰兩迭代點之間的變化量 SKIPIF1<0，相鄰兩迭代點之間梯度的變化量4.6.3BFGS變尺度法修正矩陣SKIPIF1<04.6.4變尺度法迭代步驟和算法流程迭代步驟（1）給定初始點，精度，維數N；（2）置k0，[Ak][I],計算初始點梯度；（3）計算搜索方向SKIPIF1<0；（4）從k點開始一維搜索，得到k+1點；（5）迭代終止條件SKIPIF1<0，若滿足，輸出最優點和最優解；否則下一步；（6）檢驗迭代次數，若為N,置k+1點為初始點，轉（2）重新構造變尺度矩陣；否則下一步；（7）計算SKIPIF1<0、SKIPIF1<0，修正矩陣SKIPIF1<0、變尺度矩陣SKIPIF1<0，置kk+1,轉（3）。算法流程圖：SKIPIF1<0

第五章約束優化方法前言：實際工程優化問題大多數為設計空間多維且帶有約束條件的非線性優化問題。其數學模型為SKIPIF1<0根據對約束條件處理方法的不同：直接法（約束坐標輪換法、隨機方向法、復合形法、可行方向法）間接法（簡約梯度法、懲罰函數法等）。直接法可以直接從可行域中找到最優解；將問題分解為一系列比較簡單的子問題，用子問題的解逼近原問題的解。直接法簡單直觀、對目標函數要求不高；計算量大、收斂慢，因此效率低。5.1約束隨機方向搜索法（隨機方向法）5.1.1基本原理從可行域內某一點出發，沿某一給定步長，并隨機產生搜索方向，直到該方向同時滿足可行性和下降性要求，沿著這個方向以該步長繼續搜索，直到不滿足可行性及下降性條件為止。把上述滿足要求的終點作為新的起點，重新產生隨機方向，如果能夠找到一個合適的方向，同時滿足條件，則沿該方向以原步長繼續搜索；如若找不到適合的方向，則將步長減半，仍以該點為起點隨機搜索，如果能找到新的方向，則沿該方向繼續，如果不能，步長再減半。直到找不到新的搜索方向，且步長滿足精度要求，則以該起點為最優點。一個需要說明的問題：從某一點出發，如何判斷沿某一給定步長找不到可行的方向呢？如果不靠目標函數和約束條件中隱含的指引信息，那么只有對搜索空間進行機械的排查，對隨機方向搜索法而言，就是在產生并搜索了足夠多方向之后，認為可以近似的得出這個結論。那么，到底隨機搜索了多少個方向才能得出結論呢？一般取50~500個方向，當然，如果不考慮計算的速度和效率，這個最大的方向數大一些更好，而且設計空間維數越大，這個數也應越大。5.1.2初始點的選取SKIPIF1<0其中ri為隨機數，對C語言，有函數rand()產生一個0到RAND_MAX的偽隨機整數，則SKIPIF1<05.1.3隨機搜索方向的產生SKIPIF1<0。通過該變換，使搜索方向的每個分量為-1到1之間的隨機值，從而確保對每個坐標方向的正負兩方向的搜索。之后可以進行標準化處理SKIPIF1<05.1.4算法流程（下一頁）5.1.5隨機法的特點算法簡單，對目標函數要求不高；由于隨機搜索帶有盲目性，效率低，速度慢，可能不收斂。

SKIPIF1<0

5.2復合形法5.2.1基本原理在設計空間找到K個可行點構成多面體（復合形），一般N+1≤K≤2N。不斷使復合形向著約束內最優點移動和收縮。更具體一些，根據目標函數值的大小找出這K個點中的最壞