《優(yōu)化設計ch》PPT課件

1、第三章 優(yōu)化設計優(yōu)化設計概論 優(yōu)化設計的基本概念一維搜索方法 無約束設計的最優(yōu)化方法 有約束優(yōu)化設計的方法 優(yōu)化設計的若干問題LINGO在優(yōu)化設計中的應用1精選ppt3.1 優(yōu)化設計概論優(yōu)化設計和示例優(yōu)化設計：亦稱最優(yōu)化設計，它是以數學規(guī)劃理論為基礎，以電子計算機為輔助工具的一種設計方法。它首先將設計問題按規(guī)定的格式建立數學模型，選擇合適的優(yōu)化方法，選擇或編制計算機程序，通過計算機計算獲得最優(yōu)設計方案。優(yōu)化方法：直接法：直接計算目標函數值，比較目標函數值，并以之作為迭代、收斂根據；求導法：以多變量函數極值理論為基礎。2精選ppt3.1 優(yōu)化設計概論優(yōu)化問題的分類無約束問題單變量多變量有約束問題

2、線性約束，線性目標函數線性約束，非線形目標函數非線形約束，非線形目標函數3精選ppt3.1 優(yōu)化設計概論優(yōu)化設計的數學模型識別要確定的未知變量識別目標，寫成最小化的函數識別問題的約束或限制;寫成等式或不等式例題：容積為7850立方厘米的圓罐頭盒，用料最省。確定D和H值4精選ppt優(yōu)化設計數學模型設計變量 目標函數: 最小化約束條件： 5精選ppt3.1 優(yōu)化設計概論設計變量和設計空間設計變量：設計方案可用一組參數表示，有些參數預先給定，稱為設計常量；而另一些在設計過程中優(yōu)化選定，稱為設計變量。設計空間：某方案有n個設計變量，組成一個n維列矢量。該矢量可在以n個設計變量為坐標軸組成的n維空間中用

3、一個點來表示。這n維空間稱為設計空間，空間內任意一點稱為設計點，它代表一個設計方案。通常在保證設計精度的前提下設計變量盡量取的少些。設計變量有連續(xù)和離散兩種6精選ppt3.1 優(yōu)化設計概論約束條件和可行域約束條件：設計變量的取值范圍有限制或必須滿足一定的條件，這種對設計變量的限制，稱為約束條。約束條件的分類：等式約束與不等式約束邊界約束和性能約束:前者指取值范圍的限制；后者指力學性能要求的限制。7精選ppt3.1 優(yōu)化設計概論約束條件和可行域可行域:每個不等式約束將設計空間劃分成滿足和不滿足約束條件的兩部分，若干個不等式約束把設計空間分成兩個區(qū)域，陰影線內側區(qū)的點都滿足所有不等式約束，稱為可行

4、域。當有等式約束時，只能在可行域內的等式約束線上取值.等式約束大大縮小可行域8精選ppt二維設計問題約束的幾何關系X1X29精選ppt3.1 優(yōu)化設計概論目標函數定義：優(yōu)化設計把設計變量與某種標準的關系用函數式表達，追求該函數值最?。ɑ蜃畲螅?，以求得一組設計變量值，從而獲得一個最優(yōu)設計方案。此函數稱為目標函數。（設計中欲達到的目標）作用：衡量設計方案的標準。目標類型：產品設計：技術性能、成本、價格、壽命等；零部件設計：承載能力、可靠性、重量、體積等；機構設計：運動學和動力學性質、運動誤差等。10精選ppt3.1 優(yōu)化設計概論優(yōu)化設計的幾何解釋目標函數 ：max F(X)=60 x1+120 x

5、2約束條件材料約束：g1(X)=9x1+4x2360工時約束：g2(X)=3x1+10 x2300電力約束: g3(X)=4x1+5x2200 邊界約束: g4(X)=-x10 g5(X)=-x2011精選ppt線性規(guī)劃問題的圖解法。C是g2(X)與g3(X)的交點12精選ppt3.1 優(yōu)化設計概論優(yōu)化設計的幾何解釋目標函數 ：約束條件13精選ppt非線性優(yōu)化問題的圖解法。14精選ppt3.1 優(yōu)化設計概論目標函數的等值線（面）依次令目標函數F（X）分別等于常數C1，C2，C3等，則在目標函數曲面上，獲得等值曲線（面）族。15精選ppt3.1 優(yōu)化設計概論線形與非線性規(guī)劃線性規(guī)劃：當目標函數和

6、約束條件都是設計變量的線性函數時，列出這種數學模型并求解的過程；非線性規(guī)劃：當目標函數和約束條件有一個或多個是設計變量的非線性函數時，列出這種表達式并求解的過程。16精選ppt3.2 優(yōu)化設計的基本概念函數的方向導數與梯度偏導數：一元函數中的導數：描述函數相對于自變量的變化率；多元函數中的偏導數：描述函數只相對于其中一個自變量(其余自變量保持不變)的變化率。對n函數，函數在 處沿各坐標軸的一階偏導數或變化率分別為： 17精選ppt3.2 優(yōu)化設計的基本概念函數的方向導數與梯度方向導數:函數在某點沿給定方向的變化率。18精選ppt函數的方向導數式中:cos，cos為某方向S的方向余弦19精選pp

7、tn元函數在點x0處沿S方向的方向導數 上式表明了方向導數與偏導數之間的數量關系方向導數是偏導數概念的推廣方向導數表明了函數F(X)在點X(0)沿S方向的變化率，它是一個標量 + : 函數F(X)在X(0)點處沿S方向是增加的 - : 函數F(X)在X(0)點處沿S方向是減小的20精選ppt3.2 優(yōu)化設計的基本概念函數的方向導數與梯度梯度二元函數的梯度 為函數F(x1，x2)在X0點處的梯度21精選ppt梯度的模：設:由上式可見：梯度方向和h 方向重合時，方向導數值最大。22精選ppt 梯度方向是函數值變化最快的方向，而梯度的模就是函數變化率的最大值 。 梯度方向與等值線的關系因：則有 為單

8、位方向向量。23精選ppt多元函數的梯度24精選ppt梯度 模：函數的梯度方向與函數等值面相垂直，也就是和等值面上過x0的一切曲線相垂直。 由于梯度的模因點而異，即函數在不同點處的最大變化率是不同的。因此，梯度是函數的一種局部性質。25精選ppt求函數 在點3,2T 、2,0T的梯度解 在點x(1)=3,2T, x(2)=2,0T處的梯度為：26精選ppt若函數在某點取得極值，則該點的所有一階偏導數必定為零，即梯度為零 27精選ppt3.2 優(yōu)化設計的基本概念無約束目標函數的極值條件一元函數的極值必要條件：F（x）連續(xù)可微,充分必要條件：F（x）單值連續(xù)可微，若28精選ppt3.2 優(yōu)化設計的

9、基本概念無約束目標函數的極值條件一元函數的極值多元函數的Taylor展開式：函數在某點附件的近似表達式多元函數的泰勒展開式一元函數展開成泰勒(Taylor)公式 ：二元函數展開成泰勒(Taylor)公式：n元函數展開成泰勒 (Taylor) 公式：29精選ppt一元函數泰勒Taylor展開式30精選ppt二元函數Taylor展開式對二元函數泰勒展開式只取兩項稱為海森(Hessian)矩陣，二階偏導矩陣,常用H(X)表示。31精選pptn元函數Taylor展開式當在駐點第二項為零，可得：32精選ppt3.2 優(yōu)化設計的基本概念無約束目標函數的極值條件二次型函數二次型：含有n個變量x1,x2,xn

10、的二次齊次多項式實二次型函數：若aij均為實常數，簡稱實二次型。33精選ppt1.對所有非零矢量X，若：則稱 F(X)正定的2.若對所有非零矢量X，若：則稱 F(X)負定的 34精選ppt3.2 優(yōu)化設計的基本概念無約束目標函數的極值條件多元函數的極值必要條件：實二次型函數：若aij均為實常數，簡稱實二次型。35精選ppt 當 ， 為極大值點 在 鄰域內，對所有X根據二次型函數性質，也可只用Hessian矩陣判斷。當 ， 為極小值點 當 ， 為鞍點 當H（X）正定，X為極小值點 當H（X）負定，X為極大值點 當H（X）不定，X為鞍點36精選ppt矩陣的正定條件是：其各階主子式（對應的各階行列式

11、）均大于零；負定的條件是：其各階主子式負正相間。奇數階小于零；偶數階大于零37精選ppt無約束目標函數的極值條件例:目標函數如下，求極值點及性質。解：先求子函數的一階偏導數并其等于0，求解駐點，即 駐點為（1，1）求H（X）矩陣38精選ppt正定駐點（1，1）為極小值F（ ）=4 39精選ppt3.2 優(yōu)化設計的基本概念有約束目標函數的極值條件函數的凸性一元函數的凸性多元函數的凸性約束問題的極值條件40精選ppt3.2 優(yōu)化設計的基本概念有約束目標函數的極值條件函數的凸性一元函數的凸性：其曲線上任意兩點的連線永不在曲線下方。反之為凹曲線。凸函數 凹函數41精選ppt42精選ppt一元函數的凸性

12、在線段中任取一點x(3)，則有：或凸函數表達式：幾何意義：任意兩點間的曲線永遠在連該兩點的直線之下。43精選ppt3.2 優(yōu)化設計的基本概念有約束目標函數的極值條件函數的凸性多元函數的凸性：先研究凸集才能研究函數的凸性。凸集幾何特征：其中的任意兩點間連線都在這集合內凸集含義：區(qū)域內部無空洞區(qū)域邊界無凹陷44精選ppt凸函數 對凸集D內，任兩點X(1)、 X(2)及0D)，對任意兩點F(X)在D1上有二階的連續(xù)導數，D是D1內的一個凸集，為凸函數的充要條件為Hessian矩陣半正定，要求各階主子式的值大于或等于零。46精選ppt函數凸性的判定：若F(X)在D1上為一階連續(xù)導數，而D又是D1內部的

13、一個凸集，則F(X)為D上的凸函數的充分必要條件為：若F(X)在D1上為二階連續(xù)導數，而D又是D1內部的一個凸集，則F(X)為D上的凸函數的充分必要條件為:F(X)的 Hessian矩陣為半正定。即 H(X) 0綜上所述：若F(X)其定義域是凸集，它是該凸集內的一個凸函數，則在該凸集內最多只有一個極小值，且它一定是該集內的全局最小值。 凸規(guī)劃的局部極小點一定是全局極小點 47精選ppt48精選ppt3.2 優(yōu)化設計的基本概念有約束目標函數的極值條件約束問題的極值條件目標函數及約束函數都是凸函數目標函數及約束函數有一個為非凸函數結論庫恩-塔克條件（約束極值存在的必要條件）49精選ppt3.2 優(yōu)

14、化設計的基本概念有約束目標函數的極值條件約束問題的極值條件目標函數及約束函數都是凸函數約束最優(yōu)點不一定是自然極值點50精選ppt3.2 優(yōu)化設計的基本概念有約束目標函數的極值條件約束問題的極值條件目標函數及約束函數有一個為非凸函數可行域內可出現兩個或多個相對極小點，圖中X*是全域約束極小點。51精選ppt3.2 優(yōu)化設計的基本概念有約束目標函數的極值條件約束問題的極值條件結論:對約束優(yōu)化既要解決“約束極值存在條件”還要解決“全域最優(yōu)點”的問題。52精選ppt3.2 優(yōu)化設計的基本概念有約束目標函數的極值條件約束問題的極值條件庫恩-塔克條件KT: （約束極值存在的必要條件）不是充分條件，因不能確

15、定全局最優(yōu)解。只判斷是否是一個局部最優(yōu)解。內容：目標函數梯度可表示成諸約束面梯度線性組合的負值，亦即 q：為在該設計點X處的約束面數；：拉格朗日乘子。53精選ppt庫恩-塔克條件只有一個起作用的約束條件目標函數的負梯度方向與約束函數梯度方向一致54精選ppt庫恩-塔克條件有兩個起作用的約束條件目標函數的負梯度方向在兩個約束函數梯度的夾角內55精選ppt庫恩-塔克條件有多個起作用的約束條件目標函數梯度可表示成諸約束面梯度線性組合的負值.庫恩-塔克條件是約束優(yōu)化極值的必要條件，不是充分條件。只有當目標函數及約束函數都為凸函數時，才是充分必要條件。56精選ppt例:目標函數約束條件判斷是否為極小點解

16、：目標函數和約束函數在X點的梯度57精選ppt 得1=1，2=1 ，3=0滿足庫恩-塔克條件，X*是約束極小值。g1(X), g2(X)起作用58精選ppt一、一維搜索和一維搜索最優(yōu)化方法當采用數學規(guī)劃法尋求多元函數的極值點時，一般要進行一系列如下格式的迭代計算:當方向 給定，求最佳步長因子 就是求一元函數 :的極值問題，這一過程被稱為一維搜索(單變量優(yōu)化).為求得值而采用的方法，稱為一維搜索最優(yōu)化方法。3.3一維搜索方法59精選ppt一維搜索60精選ppt3.3一維搜索方法0618法：又稱黃金分割法試探法單谷(峰）區(qū)間:在給定區(qū)間內僅有一個谷值(極大或極小)的函數稱為單峰函數，其區(qū)間稱為單谷

17、區(qū)間.單峰函數的特點：函數值:”大小大”，圖形：“高低高”,單谷區(qū)間中一定能求得一個極小點.試探法原理： F(X)在區(qū)間a,b是單峰凸函數，為縮小該區(qū)間，在中間任取兩點a1, a2。比較F(a1), F(a2)的大小，即可縮小搜索區(qū)，從而精確估出 的位置。61精選ppt(1)如F(a1)F(a2)，則縮小的新區(qū)間為a1,b;(3)如F(a1) = F(a2), 則縮小的新區(qū)間為a1, a2消去原則：消除大函數值一邊的區(qū)間。62精選ppt3.3一維搜索方法0618法：又稱黃金分割法0618法黃金分割律：是公元前六世紀，希臘的大數學家畢達哥拉斯發(fā)現的：如果把一條線段分成兩部分，長段和短段的長度之比

18、是1:0.618，整條線段和長段的比也是1:0.618時，才是和黃金一樣最完美的分割，進行分割的這個點就叫黃金分割點基本思想:在待定的單峰區(qū)間內，不斷消去一部分區(qū)間，把區(qū)間越縮越小，且每次區(qū)間縮短率都相等，新區(qū)間長度為原區(qū)間長度的0.618，直到極小點所在的區(qū)間小至滿足精度要求，再取最后區(qū)間的中點作為近似最優(yōu)點。對函數的要求：單峰.63精選ppt 將區(qū)間分成三段 黃金分割法還要求在保留下來的區(qū)間內再插入一點所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布。64精選ppt3.3一維搜索方法插值法(二次插值法，亦稱拋物線法)基本思想：在選定的單峰區(qū)內取一點，連同兩端點，用這三點函數值構成一個

19、二次多項式，做原函數的近似，求出該二次多項式的極小值做原函數的近似最優(yōu)值。65精選ppt 1、二次多項式 P(x) 的構成及其極小點設原目標函數的初始單峰區(qū)間為x1, x3 。函數在x1, x2, x3 3點處函數值分別為F1, F2,F3， 求待定系數a,b和c, 并代入上式，得：66精選ppt計算步驟1)確定單峰區(qū)x1，x32)選定x2。可為單峰區(qū)中點，或不等間距點常用3)求4)判定是否終止計算5)縮小搜索區(qū)67精選ppt縮短區(qū)間 假若F(x)本身為二次函數，則在理論上按前式一次求值就可找到最優(yōu)點 。 若F(x)為高于二次的函數或為其他函數 ,可采用區(qū)間消去法逐步縮小區(qū)間 。 根據xp*

20、，x2，F(xp* )和F(x2)的相互關系，分6種情況進行區(qū)間縮小。 在已有的四x1，x2，x3，xp* 中選擇新的三個點x1，x2，x3，再進行二次插值。 選點要求： x1x2F2，F2F3 （高低高形態(tài)） 如果 ，以x2,xp* 中函數值較小的點作為最優(yōu)點x*。68精選ppt二次插值法區(qū)間縮短的幾種情況69精選ppt二次插值法新區(qū)間的取舍70精選ppt二次插值法區(qū)間縮短的幾種情況71精選ppt二次插值法區(qū)間縮短的幾種情況72精選ppt例：從初始點沿給定方向搜索，求最優(yōu)步長目標函數 的極小值初始點為： 搜索方向：73精選ppt3.4 無約束的優(yōu)化方法兩大類方法：1、只利用目標函數值本身；

21、2、利用函數的一階導數甚至二階導數。Powell法梯度法共軛梯度法:解決梯度法變尺度法74精選ppt3.4 無約束的優(yōu)化方法Powell法：直接利用函數值來構造共軛方向的一種方法 共軛方向的概念定義:設A為實對稱正定n階方陣，若有兩個n維矢量S1與S2滿足 時，稱矢量S1與S2對于實對稱正定矩陣A共軛。若A為單位矩陣，則兩矢量正交（即相互垂直）。共軛方向是正交方向的推廣。性質：對n維二次目標函數，從任意點出發(fā)，可找到n個共軛矢量，依次對這些矢量分別進行一維搜索，就可找到該n維二次目標函數的極小點。對二元函數：若其Hessian矩陣為正定，其目標函數的等值線是同心橢圓族。二次收斂性75精選ppt

22、對二元函數特性任意兩條平行切線與橢圓族的切點的連線，一定通過橢圓族的中心。對一個正定的二元函數，只要沿兩個相互共軛的方向進行一維搜索，便可找到極小點。76精選ppt3.4 無約束的優(yōu)化方法Powell法共軛方向的形成選任意初始點X(0) 依次沿各坐標方向進行一維搜索。構成第一個共軛方向 ，再沿S(1) 進行一維搜索得極小點 。進行第二輪搜索，獲第二個共軛方向。搜索時去掉e1，從e2方向開始，將 加到最后。 再沿此方向進行搜索得極小點 X 。此兩方向共軛77精選ppt多維無約束優(yōu)化方法算法的基本過程是: 從選定的某初始點x(k)出發(fā)，沿著以一定規(guī)律產生的搜索方向S(k) ,取適當的步長a(k)

23、,逐次搜尋函數值下降的新迭代點x(k+1),使之逐步通近最優(yōu)點x* 。 可以把初始點x(k) 、搜索方向S(k) 、迭代步長a(k) 稱為優(yōu)化方法算法的三要素。其中以搜索方向S(k)更為突出和重要，它從根本上決定若一個算法的成敗、收斂速率的快慢等。 一個算法的搜索方向成為該優(yōu)化方法的基本標志，分析、確定搜索方向S(k)是研究優(yōu)化方法的最根本的任務之一。78精選ppt共軛方向的形成過程79精選ppt3.4 無約束的優(yōu)化方法Powell法Powell法的基本步驟選任意初始點X(0) 依次沿各坐標方向進行一維搜索。進行第二輪搜索,構成第一個共軛方向. 進行第二輪搜索，構成 第二個共軛方向。以后各輪，

24、均以新獲得的共軛方向替換前一輪搜索的第一個搜索方向。經n輪搜索后，構成n個相互共軛的方向。對n維二次正定函數，相繼沿n個共軛方向做一維搜索，即可得到極值點。80精選ppt3.4 無約束的優(yōu)化方法Powell法Powell法的基本步驟為防止線性相關，第k輪新算出的共軛方向要滿足下式，否則拋棄該方向：令k輪搜索出的共軛方向及其反映點分別為:式中：81精選ppt3.4 無約束的優(yōu)化方法梯度法基本思想:梯度方向是函數變化率最大的方向;負梯度方向是目標函數下降最快的方向。迭代公式最佳步長因子采用一維搜索的方法決定。終止條件:點距準則；梯度準則；相對準則82精選ppt3.4 無約束的優(yōu)化方法梯度法迭代步驟

25、：給定初始點X(0) ，允差，置k=0。計算迭代點的梯度和負梯度方向。計算最優(yōu)步長因子迭代計算檢查是否滿足終止條件令k=k+1轉下一步計算特點:只需求一階導數，迭代計算簡單，存儲單元少，對初始點要求不高。開始收斂快，接近極小點時收斂慢。83精選ppt3.4 無約束的優(yōu)化方法共軛梯度法:解決梯度法接近最優(yōu)點時收斂慢的缺點.基本原理：利用目標函數的梯度確定共軛方向.為避免梯度方向后期收斂慢，用新搜索方向使之與所算出的梯度方向共軛。其共軛矩陣為該點的海森矩陣。海森矩陣及逆陣難求，需找新路目標函數不是二階，海森矩陣因點而異，要順序地求解84精選ppt共軛梯度法基本原理85精選ppt3.4 無約束的優(yōu)化

26、方法共軛梯度法共軛方向的形成：若A已知，可直接求。一般將共軛方向寫成該點負梯度矢量與前一步搜索方向的線性組合.新的共軛方向應滿足: (1)要寫成如下形式： (2)共軛系數求法：將（2）代入（1）: (3)86精選ppt因相鄰兩次迭代的負梯度方向正交，故有:式(3)簡化為：結論：87精選ppt選初始點X(0) ，允差，維數n。計算初始點負梯度方向 為搜索方向。求最優(yōu)步長并計算新點的梯度。精度判斷 判斷k+1是否等于n，若相等令X(0) = X(k+1) ,并轉回步驟1；否則轉入下一步.計算共軛方向令k=k+1轉入步驟 2.3. 迭代步驟88精選ppt3.4 無約束的優(yōu)化方法共軛梯度法特點：二次收

27、斂，程序簡單，存儲量小適用于多變量優(yōu)化；但目標函數必可求一階導數。89精選ppt3.4 無約束的優(yōu)化方法變尺度法基本思想和公式:加速收斂，避免求二階導數矩陣及其逆陣。將負梯度方向乘一個對稱正定矩陣（變尺度矩陣）修正后做為搜索方向。迭代步驟90精選ppt對二次函數難求，且所以實際運算中求E有許多公式:常用的有DFP法和BFGS法 91精選ppt迭代步驟給定初始點，允差和維數設變尺度矩陣的初值為單位矩陣，置k=0求搜索方向和最優(yōu)步長：求出下一個迭代點:檢驗終止條件， 終止，否則轉下一步檢查迭代次數；若k=n則X(0) = X(k+1) ，轉步驟2，否則轉下一步構造新的搜索方向：令k=k+1轉入步驟

28、392精選ppt3.5 有約束優(yōu)化設計的方法 直接法與間接法：前者設法使每次迭代點在可行域內；后者將約束問題通過一定形式的變換，轉化成無約束問題。復合形法基本思想：在可行域內選k個設計點，作為初始復合形的頂點，構成一個多面體。經各頂點比較，找出目標函數最大的為壞點，按一定規(guī)則以新點代替壞點，構成新的多邊形。多次重復，使復合性向最優(yōu)點靠近，最后以頂點中目標函數最小的做最優(yōu)點。93精選ppt3.5有約束優(yōu)化設計的方法 復合形法頂點數目：為克服退化頂點數n+1k2n。以二維函數為例：3k4。具體方法：三個復合形頂點構成一個三角形，Xh是最壞點，Xc是除最壞點外的形心，沿Xh，Xc方向取Xr為映射點Xr=Xc+a(Xc-Xh),映射系數=1.3。首先檢查Xr是否在可行域內，若不在將減半再檢查，直至退入可行域；再檢查函數值，若F(Xr)F(Xh)，將減半，直至滿足。若過小(10-5 )，用次壞點代替壞點。終止迭代：若取頂點中目標函數最小者為最優(yōu)點。 。98精選ppt3.5 有約束優(yōu)化設計的方法 罰函數法基本思想：把一個有約束的問題轉化為無約束問題求解，逐漸逼近于目標函數的最優(yōu)值。轉化方法：在原目標函數中加一些與約束條件有關的項，形成新