機(jī)械優(yōu)化設(shè)計(jì)總復(fù)習(xí).ppt

1、1,機(jī)械優(yōu)化設(shè)計(jì)總復(fù)習(xí),2012年6月7日,2,題型,一、名詞解釋(每小題4分，共12分) 二、選擇題(每空2分,共30分) 三、簡答題(每小題6分,共12分) 四、建模題(8分) 五、計(jì)算填表題(8分) 六、計(jì)算題(30分),3,一 設(shè)計(jì)變量 在優(yōu)化設(shè)計(jì)過程中，要優(yōu)化選擇的設(shè)計(jì)參數(shù)。 設(shè)計(jì)變量必須是獨(dú)立變量，即：在一個(gè)優(yōu)化設(shè)計(jì)問題中，任意兩個(gè)設(shè)計(jì)變量之間沒有函數(shù)關(guān)系。按照產(chǎn)品設(shè)計(jì)變量的取值特點(diǎn)，設(shè)計(jì)變量可分為連續(xù)變量（例如軸徑、輪廓尺寸等）和離散變量（例如各種標(biāo)準(zhǔn)規(guī)格等）。 小型設(shè)計(jì)問題：一般含有210個(gè)設(shè)計(jì)變量； 中型設(shè)計(jì)問題：1050個(gè)設(shè)計(jì)變量； 大型設(shè)計(jì)問題：50個(gè)以上的設(shè)計(jì)變量。,第

2、二章 優(yōu)化設(shè)計(jì)的基本要素和數(shù)學(xué)模型,4,二 設(shè)計(jì)空間 在一個(gè)優(yōu)化設(shè)計(jì)問題中，所有可能的設(shè)計(jì)方案構(gòu)成了一個(gè)向量集合?？梢宰C明，這個(gè)向量集合是一個(gè)向量空間，并且是一個(gè)歐氏空間。 一個(gè)優(yōu)化設(shè)計(jì)問題中，設(shè)計(jì)變量的個(gè)數(shù)，就是它的設(shè)計(jì)空間的維數(shù)。 三 目標(biāo)函數(shù) 優(yōu)化設(shè)計(jì)中要優(yōu)化的某個(gè)或某幾個(gè)設(shè)計(jì)指標(biāo)，這些指標(biāo)是設(shè)計(jì)變量的函數(shù)，稱為目標(biāo)函數(shù)。在構(gòu)造目標(biāo)函數(shù)時(shí)，應(yīng)注意目標(biāo)函數(shù)必須包含全部設(shè)計(jì)變量，所有的設(shè)計(jì)變量必須包含在約束函數(shù)中。,5,四 設(shè)計(jì)約束 優(yōu)化設(shè)計(jì)中設(shè)計(jì)變量必須滿足的條件，這些條件是設(shè)計(jì)變量的函數(shù)。,約束條件的分類 （1）根據(jù)約束的性質(zhì)分 邊界約束 直接限定設(shè)計(jì)變量的取值范圍的約束條件，即,性能約

3、束 由方案的某種性能或設(shè)計(jì)要求，推導(dǎo)出來的約束條件。,i 1,2, ，n,6,u=1,2, ，m,v = 1，2， ，p n,（2）根據(jù)約束條件的形式分 不等式約束,一個(gè) n 維的優(yōu)化設(shè)計(jì)問題中，等式約束的個(gè)數(shù)必須少于 n 。,顯式約束 隱式約束,等式約束,7,約束條件可以用數(shù)學(xué)等式或不等式來表示。 等式約束對設(shè)計(jì)變量的約束嚴(yán)格，起著降低設(shè)計(jì)自由度的作用，要求：設(shè)計(jì)點(diǎn)落在約束面上，pn,其形式為,等式約束降低了設(shè)計(jì)空間的維數(shù)。有一個(gè)獨(dú)立的等式約束，就可用代入法消去一個(gè)設(shè)計(jì)變量，使優(yōu)化問題降低1維。因此，等式約束的數(shù)目應(yīng)當(dāng)小于設(shè)計(jì)變量的數(shù)目。如果相等，成了既定系統(tǒng)，就沒法優(yōu)化了。 等式約束hv(

4、x)=0可看成是同時(shí)滿足：hv(x)0和hv(x)0這兩個(gè)不等式約束。 對于等式約束來說，設(shè)計(jì)變量x所代表的設(shè)計(jì)點(diǎn)必須在式(2-3)所表示的面(或線) 上這種約束又稱為起作用約束或緊約束,* 等式約束的個(gè)數(shù) p 設(shè)計(jì)變量的數(shù)目 n,8,在機(jī)械最優(yōu)化設(shè)計(jì)中不等式約束更為普遍，不等式約束的形式為,要求:設(shè)計(jì)點(diǎn)落在約束面的一側(cè)。 不等式約束在設(shè)計(jì)空間內(nèi)劃分出可行區(qū)域與不可行區(qū)域，但不降低設(shè)計(jì)空間的維數(shù)。,9,設(shè)計(jì)點(diǎn)的集臺構(gòu)成設(shè)計(jì)空間，n維設(shè)計(jì)問題屬于n維歐氏空間，如對設(shè)計(jì)點(diǎn)的取值不加以限制，則設(shè)計(jì)空間是無限的，凡屬這類的優(yōu)化設(shè)計(jì)問題稱為無約束優(yōu)化問題。但在實(shí)際問題中設(shè)計(jì)變量的取值范圍是有限制的或必須

5、滿足一定條件，在優(yōu)化設(shè)計(jì)中。這種對設(shè)計(jì)變量取值的限制條件，稱為約束條件或設(shè)計(jì)約束。 約束的形式，可能是對某個(gè)或某組設(shè)計(jì)變量的直接限制(例如，若應(yīng)力為設(shè)計(jì)變量，則應(yīng)力值應(yīng)不大于其許用值，構(gòu)成直接限制)，這時(shí)稱為顯約束；也可能是對某個(gè)或某組設(shè)計(jì)變量的間接限制(例如，若結(jié)構(gòu)應(yīng)力又是某些設(shè)計(jì)變量如力和截面積的函數(shù)時(shí)，則這些設(shè)計(jì)變量間接地受到許用應(yīng)力的限制,或例中的復(fù)雜結(jié)構(gòu)的性能約束函數(shù)（變形、應(yīng)力、頻率等），需要通過有限元等方法計(jì)算求得。)，這時(shí)稱為隱約束。,10,*五 可行域 可行域 : 在設(shè)計(jì)空間中，滿足所有約束條件的所構(gòu)成的空間 。,滿足兩項(xiàng)約束條件 g1（X）=-x12-x22+16 0 g2

6、（X）x22 0 的二維設(shè)計(jì)問題的可行域D,11,約束（曲）面： 對于某一個(gè)不等式約束 gu(x) 0 中，滿足 gu(x) = 0的 x 點(diǎn)的集合構(gòu)成一個(gè)曲面，稱為約束（曲）面。,它將設(shè)計(jì)空間分成兩部分：滿足約束條件 gu(x) 0 的部分和不滿足約束條件gu(x) 0 的部分。,設(shè)計(jì)可行域（簡稱為可行域） 對于一個(gè)優(yōu)化問題，所有不等式約束的約束面將組成一個(gè)復(fù)合的約束曲面，包圍了設(shè)計(jì)空間中滿足所有不等式約束的區(qū)域，稱為設(shè)計(jì)可行域 。,記作 D =,g u(x) 0 u = 1,2,m h v (x) = 0 v = 1,2, p,問題：等式約束與約束曲面是什么關(guān)系？,D,12,可行設(shè)計(jì)點(diǎn)（內(nèi)

7、點(diǎn)）： 在可行域內(nèi)任意一點(diǎn)稱為可行設(shè)計(jì)點(diǎn)，代表一個(gè)可行方案。即位于由gu(x)0構(gòu)成的約束曲面之內(nèi)的設(shè)計(jì)點(diǎn),極限設(shè)計(jì)點(diǎn)（邊界點(diǎn)）： 在約束面上(或邊界線)的點(diǎn)稱為極限設(shè)計(jì)點(diǎn)。邊界點(diǎn)是允許的極限設(shè)計(jì)方案。,若討論的設(shè)計(jì)點(diǎn) x(k)點(diǎn)使得 gu(x(k) ) = 0，則gu(x(k) 0 稱為適時(shí)約束或起作用約束。,非可行設(shè)計(jì)點(diǎn)（外點(diǎn)）： 在可行域外的點(diǎn)稱為非可行設(shè)計(jì)點(diǎn)，代表不可采用的設(shè)計(jì)方案。,問題： 極限設(shè)計(jì)點(diǎn)是否代表可行設(shè)計(jì)方案？ 什么約束一定是適時(shí)約束？ 可行域是否一定封閉？,13,六 優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型,14,八 優(yōu)化分類及機(jī)械優(yōu)化設(shè)計(jì)的特點(diǎn),機(jī)械優(yōu)化設(shè)計(jì)基本上是非線性的、有約束的最優(yōu)化

8、問題。,15,其數(shù)學(xué)表達(dá)式：,等值線（面）： 具有相同目標(biāo)函數(shù)值的點(diǎn)集在設(shè)計(jì) 空間形成的曲線和曲面, 在極值處，函數(shù)的等值線聚成一點(diǎn)，并位于等值線 族的中心。 當(dāng)該中心為極小值時(shí)，離中心線愈遠(yuǎn)，函數(shù)值愈大。 當(dāng)目標(biāo)函數(shù)值的變化范圍一定時(shí)，等值線越稀疏， 說明函數(shù)值的變化愈平緩 函數(shù)的等值面（線）是用來描述、研究函數(shù)的整體性質(zhì)的。,總結(jié)：(2維問題3維、n維）,第三章 優(yōu)化設(shè)計(jì)的數(shù)學(xué)基礎(chǔ),16,17, 等值線的分布情況，反映了目標(biāo)函數(shù)值的變化情況； 等值線越向里，目標(biāo)函數(shù)值越??； 等值線越密的地方，其目標(biāo)函數(shù)值的變化率也越大；,對于有心的等值線族來說，等值線族的中心就是一個(gè)相對極小點(diǎn)。 不同值的

9、等值線不相交；除極值點(diǎn)外，等值線在設(shè)計(jì)空間內(nèi)不會中斷；,18,1. 無約束最優(yōu)解,若在整個(gè)設(shè)計(jì)空間內(nèi)所得點(diǎn) ，使：,則稱：,2. 約束最優(yōu)解,則稱：,若設(shè)計(jì)空間內(nèi)點(diǎn) ，使：,二、約束最優(yōu)解和無約束最優(yōu)解,19,無約束優(yōu)化設(shè)計(jì)問題最優(yōu)解：,約束優(yōu)化設(shè)計(jì)問題最優(yōu)解：,不受約束條件限制，使目標(biāo)函數(shù)達(dá)到最小值的一組設(shè)計(jì)變量，即最優(yōu)點(diǎn) x*=x1*,x2*,x n* 和最優(yōu)值 f(x*)構(gòu)成無約束問題最優(yōu)解。,滿足約束條件，使目標(biāo)函數(shù)達(dá)到最小值的一組設(shè)計(jì)變量，即最優(yōu)點(diǎn) x*=x1*,x2*,x n* 和最優(yōu)值 f(x*)構(gòu)成約束問題最優(yōu)解。,20,情況a):,情況b):,對于無約束優(yōu)化問題:當(dāng)目標(biāo)函數(shù)不

10、是單峰函數(shù)時(shí)，則會有多個(gè)極值點(diǎn)，如圖：有兩個(gè)極值點(diǎn)： 和 ，它們稱為局部最優(yōu)點(diǎn)。,對于約束優(yōu)化問題:極值點(diǎn)不僅與目標(biāo)函數(shù)的性質(zhì)有關(guān)，還與約束集合的性質(zhì)有關(guān)。如圖：目標(biāo)函數(shù)是凸函數(shù)，約束集合為非凸集，則有點(diǎn)： 、 、 ，稱為局部最優(yōu)點(diǎn),整個(gè)可行域內(nèi)的最小點(diǎn)稱為全域最優(yōu)點(diǎn)。,三、局部最優(yōu)點(diǎn)和全域最優(yōu)點(diǎn),21,二、 極值點(diǎn)存在的條件,一元函數(shù) 在點(diǎn) 取極值的條件為（對于連續(xù)可微的一元函數(shù)）,必要條件：,充分條件：,當(dāng) 時(shí)取極小值 當(dāng) 時(shí)取極大值,（一） 一元函數(shù)（即單變量函數(shù)）的情況： （1）極值點(diǎn)存在的必要條件,3.2 無約束目標(biāo)函數(shù)的極值點(diǎn)存在條件,22,梯度,1、梯度的定義,n維函數(shù)的梯度是函

11、數(shù)各維一階偏導(dǎo)數(shù)組成的向量,梯度的模是函數(shù)各維一階偏導(dǎo)數(shù)平方和的開方,梯度與它的模的比值稱為梯度的單位向量,23,2、函數(shù)梯度的性質(zhì)：,1、函數(shù)的梯度 是函數(shù)在點(diǎn) 的最速上升方向，而負(fù)梯度 是函數(shù)在點(diǎn) 的最快下降方向。函數(shù)的梯度隨著點(diǎn) 在設(shè)計(jì)空間的位置不同而異，這只是反映了函數(shù)在點(diǎn) 鄰域內(nèi)函數(shù)的局部性質(zhì)，僅在該點(diǎn)附近具有這種性質(zhì)。由于梯度的模因點(diǎn)而異，即函數(shù)在不同點(diǎn)的最大增加率是不同的。故，函數(shù)在某點(diǎn)的梯度向量只是指出了在該點(diǎn)極小領(lǐng)域內(nèi)函數(shù)的最速上升方向，是函數(shù)的一種局部性質(zhì)。 。,24,2、函數(shù)梯度的模 是在點(diǎn) 處函數(shù)變化率的最大值。,3、函數(shù)的梯度 與在點(diǎn) 的函數(shù)等值面正交（函數(shù)在任意點(diǎn)處

12、的梯度向量與過該點(diǎn)的等值線的切線正交。即，任意點(diǎn)的梯度方向是等值線在該點(diǎn)的法線方向）。與點(diǎn) 的函數(shù)等值面相切方向的函數(shù)變化率為零。,4、當(dāng)梯度 與方向 之間的夾角介于090之間時(shí)，該區(qū)域內(nèi)的任意方向都是使函數(shù)值增大的方向，即函數(shù)上升方向；當(dāng)梯度 與方向 之間的夾角介于90180之間時(shí)，該區(qū)域內(nèi)的任意方向都是使函數(shù)值減小的方向，即函數(shù)下降方向。,25,5、函數(shù)f（x1，x2）的梯度是一個(gè)向量，它在坐標(biāo)軸x1、x2的分量是f/x1、f/x2，梯度的符號是：f(X)f(x1，x2)，或gradf(X)grad f(x1，x2) 6、函數(shù)的方向?qū)?shù)函數(shù)的梯度與方向S的單位向量的標(biāo)量積 7、梯度方向是函

13、數(shù)具有最大變化率的方向。即：函數(shù)值沿正梯度方向增加最快，沿負(fù)梯度方向下降最快。 8、梯度的模就是函數(shù)的最大變化率。 9、對于優(yōu)化設(shè)計(jì)問題，為了盡快取得最優(yōu)解，希望每一次迭代的搜索方向S等于或者接近于目標(biāo)函數(shù)的負(fù)梯度方向。這樣才能使得函數(shù)值的下降速度最快，盡快收斂于最優(yōu)點(diǎn)。,26,10、函數(shù)在給定點(diǎn) 的梯度方向是函數(shù)等值線或等值面 在該點(diǎn)的法線方向。,上升方向,下降方向,27,例3 求二元函數(shù) 在x0 = 0 0T處函數(shù)變化率最大的方向和數(shù)值。,解：由于函數(shù)變化率最大的方向是梯度方向， 這里用單位向量p表示， 函數(shù)變化率最大的數(shù)值是梯度的模f(x0)。求f(x1,x2)在x0點(diǎn)處的梯度方向和數(shù)值

14、， 如下,28,解：,則函數(shù)在 處的最速下降方向?yàn)?29,該方向上的單位向量為,新點(diǎn),該點(diǎn)函數(shù)值,30,梯度 模：,函數(shù)的梯度方向與函數(shù)等值面相垂直，也就是和等值面上過x0的一切曲線相垂直。,由于梯度的模因點(diǎn)而異，即函數(shù)在不同點(diǎn)處的最大變化率是不同的。因此，梯度是函數(shù)的一種局部性質(zhì)。,31,即，n維函數(shù)的二階Taylor展開式可寫成：,其中：,就稱為Hesse 矩陣，是一個(gè)實(shí)對稱方陣。,32,例 5 求二元函數(shù)f(x1, x2)x12+x22-4x1-2x2+5 在X02,2處的海賽二階泰勒展開式。,解：,33,解：因?yàn)?則,又因?yàn)椋?故Hesse陣為：,34,1、正定的概念 設(shè)有二次型 ，若

15、對于任意不為“ 0 ”的矢量 ，恒有 ，則相應(yīng)的系數(shù)對稱矩陣A稱為正定矩陣,相應(yīng)的函數(shù) 為“正定二次型函數(shù)”,類似地，若對于任何矢量 ,總有 ，則稱A為負(fù)定矩陣。相應(yīng)的函數(shù) 為“負(fù)定二次型函數(shù)”,二、正定矩陣及其判別法,35,2、正定性的判別 （1）若對稱矩陣 正定，其充要條件是矩陣行列式 的各階主子式值均大于0,（2）、若矩陣A負(fù)定，其充要條件是矩陣行列式 的各階主子式值負(fù)、正相間。即：,36,37,38,四 函數(shù)的凸性 1. 凸集 2. 凸函數(shù) 如果HESSEN矩陣正定，為凸函數(shù)； 二次函數(shù),3. 凸規(guī)劃,凸規(guī)劃問題中的任何局部最優(yōu)解都是全局最優(yōu)解；,39,凸規(guī)劃,對于約束優(yōu)化問題,式中若

16、F（X）、 均為凸函數(shù)，則稱此問題為凸規(guī)劃。,40,幾個(gè)常用的梯度公式：,41,*五、優(yōu)化問題的極值條件,1、無約束優(yōu)化問題的極值條件,1）F(x)在 處取得極值，其必要條件是:,即在極值點(diǎn)處函數(shù)的梯度為n維零向量。,42,2） 處取得極值充分條件,海色（Hessian）矩陣 正定，即各階主子式均大于零，則X*為極小點(diǎn)。,海色（Hessian）矩陣 負(fù)定，即各階主子式負(fù)、正相間，則X*為極大點(diǎn)。,43,1）約束優(yōu)化設(shè)計(jì)的最優(yōu)點(diǎn)在可行域 D 中 最優(yōu)點(diǎn)是一個(gè)內(nèi)點(diǎn)，其最優(yōu)解條件與無約束優(yōu)化設(shè)計(jì)的最優(yōu)解條件相同；,2、約束優(yōu)化問題的極值條件,2）約束優(yōu)化設(shè)計(jì)的最優(yōu)點(diǎn)在可行域 D 的邊界上 設(shè) X (

17、k) 點(diǎn)有適時(shí)約束,44,45,K-T條件是多元函數(shù)取得約束極值的必要條件,以用來作為約束極值的判斷條件，又可以來直接求解較簡單的約束優(yōu)化問題。,對于目標(biāo)函數(shù)和約束函數(shù)都是凸函數(shù)的情況， 符合K-T條件的點(diǎn)一定是全局最優(yōu)點(diǎn)。這種情況K-T條件即為多元函數(shù)取得約束極值的充分必要條件。,46,K-T條件是多元函數(shù)取得約束極值的必要條件,以用來作為約束極值的判斷條件，又可以來直接求解較簡單的約束優(yōu)化問題。,47,48,49,一維搜索也稱直線搜索。這種方法不僅對于解決一維最優(yōu)化本身具有實(shí)際意義，而且也是解多維最優(yōu)化問題的重要支柱。（搜索步長求解）,一維搜索方法數(shù)值解法分類,第四章 一維搜索的最優(yōu)化方法

18、,50,只有一個(gè)變量的搜索求優(yōu)，稱為一維最優(yōu)化方法，也稱為單變量優(yōu)化。,對于多維優(yōu)化問題求極值，就可以處 理成： 將一個(gè)多維優(yōu)化問題轉(zhuǎn)化成了一個(gè)一維優(yōu)化問題。,該問題就變成了一個(gè)從已知點(diǎn) 出發(fā)，沿著給定方向 求最優(yōu)步長 使 為最小的一系列一維優(yōu)化問題。,：一維搜索的最優(yōu)步長因子。,51,1、一維搜索是多維求優(yōu)問題的基礎(chǔ)； 2、一維搜索的好壞直接影響到優(yōu)化問題的求解速度。,意義：,1、解析解法：,步驟：, 在點(diǎn) 處沿著方向 展開成二階 Taylor展開式；,最優(yōu)步長 的求解方法：,52,1、單谷(峰）區(qū)間 在給定區(qū)間內(nèi)僅有一個(gè)谷值的函數(shù)稱為單谷數(shù)，其區(qū)間稱為單谷區(qū)間。,確定搜索區(qū)間的外推法,函數(shù)

19、值：“大小大” 圖形：“高低高”,53,二、確定初始單谷區(qū)間的外推法,基本思想： 對f(x)任選一個(gè)初始點(diǎn)a1及初始步長h， 通過比較這兩點(diǎn)函數(shù)值的大小，確定第三點(diǎn)位置，比較這三點(diǎn)的函數(shù)值大小，確定是否為 “高低高” 形態(tài)。,步驟：,（1）選定初始點(diǎn)a1, 初始步長hh0 0，計(jì)算 y1f(a1)， y2f(a1h)。 （2）比較y1和y2。 （a）如y1y2, 向右前進(jìn)；加大步長 h2 h ，轉(zhuǎn)（3）向前； （b）如y1y2, 向左后退；h h0， 將a1與a2，y1與y2的 值互換。轉(zhuǎn)（3）向后探測； （c）如y1y2，極小點(diǎn)在a1和a1h之間。,54,(3）產(chǎn)生新的探測點(diǎn)a3，y3f(a

20、3); (4) 比較函數(shù)值 y2與y3： （b）如y2y3, 加大步長 h2 h(也可不變) ， a1=a2, a2=a3, 轉(zhuǎn)（3）繼續(xù)探測。 （a）如y2y3, 則初始區(qū)間得到： a=mina1,a3， b=maxa3,a1，函數(shù)最小值所在的區(qū)間為a， b 。,55,56,一、序列消去法基本原理,逐步縮小搜索區(qū)間，直至最小點(diǎn)存在的范圍達(dá)到允 許的誤差范圍。,57,58,59,黃金分割法要求插入兩點(diǎn)：,黃金分割法區(qū)間消去示意：,掌握該方法的關(guān)鍵在于： 一，確定黃金分割點(diǎn)； 二，清楚區(qū)間的取舍原則，,黃金分割法程序簡單，可靠性好，但搜索速度慢，計(jì)算量較大。適用于維數(shù)不多的優(yōu)化問題中作為一維搜索

21、方法。,60,例 1 用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點(diǎn)，給定 x0=0, h=1, =0.2。,解： 1）確定初始區(qū)間 x1=x0=0, f1=f(x1)=2 x2=x0+h=0+1=1, f2=f(x2)=1 由于f1f2, 應(yīng)加大步長繼續(xù)向前探測。,x3= x0+2h=0+2=2, f3=f(x3)=18 由于f2f3,可知初始區(qū)間已找到，即a,b=x1,x2=0,2,2）用黃金分割法縮小區(qū)間 第一次縮小區(qū)間： x1=0+0.382X(2-0)=0.764, f1=0.282 x2=0+0.618 X(2-0)=1.236, f2=2.72 f10.2,61,第二次縮小

22、區(qū)間： 令 x2=x1=0.764, f2=f1=0.282 x1=0+0.382X(1.236-0)=0.472, f1=0.317 由于f1f2, 故新區(qū)間a,b=x1,b=0.472, 1.236 因?yàn)?b-a=1.236-0.472=0.7640.2, 應(yīng)繼續(xù)縮小區(qū)間。,第三次縮小區(qū)間： 令 x1=x2=0.764, f1=f2=0.282 x2=0.472+0.618X(1.236-0.472)=0.944, f2=0.747 由于f10.2, 應(yīng)繼續(xù)縮小區(qū)間。,62,第四次縮小區(qū)間： 令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382X(0.944-

23、0.472)=0.652, f1=0.223 由于f10.2, 應(yīng)繼續(xù)縮小區(qū)間。,第五次縮小區(qū)間： 令 x2=x1=0.652, f2=f1=0.223 x1=0.472+0.382X(0.764-0.472)=0.584, f1=0.262 由于f1f2, 故新區(qū)間a,b=x1,b=0.584, 0.764 因?yàn)?b-a=0.764-0.584=0.180.2, 停止迭代。,極小點(diǎn)與極小值： x*=0.5X(0.584+0.764)=0.674, f(x*)=0.222,63,64,65,66,67,68,4.4 多項(xiàng)式近似法二次插值法 (微分法),（一）基本思想,對形式復(fù)雜的函數(shù)，數(shù)學(xué)運(yùn)算

24、時(shí)不方便,復(fù)雜函數(shù) f(x),極小點(diǎn)x*,函數(shù)近似， 最優(yōu)點(diǎn)也應(yīng)近似,一次多項(xiàng)式 二次多項(xiàng)式 三次多項(xiàng)式,? 如何構(gòu)造符合要求的多項(xiàng)式 ?,69,一、基本原理,它是屬于曲線擬合方法的范疇，是利用一個(gè)多項(xiàng)式來逼近原函數(shù)的一種近似方法。,即，構(gòu)造一個(gè)低次插值函數(shù) 來逼近原函數(shù) ， 用 的最優(yōu)點(diǎn) 來近似 的最優(yōu)點(diǎn) 。,若插值函數(shù) 為二次多項(xiàng)式：稱為二次插值法； 若插值函數(shù) 為三次多項(xiàng)式：稱為三次插值法；,二次插值法又稱拋物線法，它是以目標(biāo)函數(shù)的二次插值函數(shù)的極小點(diǎn)作為新的中間插入點(diǎn)，進(jìn)行區(qū)間縮小的一維搜索算法。,70,情況分析：,）,即：,71,）,情況分析：,即：,即：,72,73,74,75,7

25、6,77,目前已研究出很多種無約束優(yōu)化方法，它們的主要不同點(diǎn)在于構(gòu)造搜索方向上的差別。,（1）間接法要使用導(dǎo)數(shù)，如梯度法、（阻尼）牛頓法、變尺度法、共軛梯度法等。 （2）直接法不使用導(dǎo)數(shù)信息，如坐標(biāo)輪換法、鮑威爾法單純形法等。,無約束優(yōu)化問題是：,求n維設(shè)計(jì)變量,使目標(biāo)函數(shù),第 五 章 無約束最優(yōu)化方法,搜索方向的構(gòu)成問題乃是無約束優(yōu)化方法的關(guān)鍵。,78,本章應(yīng)掌握內(nèi)容： 1）梯度法的特點(diǎn) 2）無約束優(yōu)化方法有幾種 3）各種無約束方法由哪些特點(diǎn)： 4）用DFP變尺度法求算目標(biāo)函數(shù)的極值,79,無約束優(yōu)化方法的基本步驟 1選擇初始點(diǎn)。 2確定迭代方向（搜索方向）目標(biāo)函數(shù)值的下降方向。 3確定迭代

26、步長，使得迭代點(diǎn)的函數(shù)值具有下降性。 如何確定迭代方向？是各種無約束優(yōu)化方法之根本。 各無約束優(yōu)化方法的區(qū)別，主要在于迭代方向的不同。 可以把初始點(diǎn) 、搜索方向 、迭代步長 稱為優(yōu)化方法算法的三要素。其中以搜索方向 更為突出和重要，它從根本上決定若一個(gè)算法的成敗、收斂速率的快慢等。所以一個(gè)算法的搜索方向成為該優(yōu)化方法的基本標(biāo)志，分析、確定搜索方向 是研究優(yōu)化方法的最根本的任務(wù)之一。各種無約束優(yōu)化方法的區(qū)別就在于確定其搜索方向 的方法不同,80,*一、 梯度法,負(fù)梯度方向 是函數(shù)最速下降方向。 梯度法就是以負(fù)梯度方向作為一維搜索的方向，即 k=1,2, ,n,基本思想：函數(shù)的負(fù)梯度方向是函數(shù)值在

27、該點(diǎn)下降最快的方向。將n維問題轉(zhuǎn)化為一系列沿負(fù)梯度方向用一維搜索方法尋優(yōu)的問題，利用負(fù)梯度作為搜索方向，故稱最速下降法或梯度法。,81,在最速下降法中，相鄰兩個(gè)迭代點(diǎn)上的函數(shù)梯度相互垂直。而搜索方向就是負(fù)梯度方向，因此相鄰兩個(gè)搜索方向互相垂直。,圖4-2 最速下降法的搜索路徑,*會證明：,82,方法特點(diǎn) （1）初始點(diǎn)可任選，每次迭代計(jì)算量小，存儲量少，程序簡短。即使從一個(gè)不好的初始點(diǎn)出發(fā)，開始的幾步迭代，目標(biāo)函數(shù)值下降很快，然后慢慢逼近局部極小點(diǎn)。 （2）任意相鄰兩點(diǎn)的搜索方向是正交的，它的迭代路徑為繞道逼近極小點(diǎn)。當(dāng)?shù)c(diǎn)接近極小點(diǎn)時(shí)，步長變得很小，越走越慢。,83,二、 牛頓法及其改進(jìn),8

28、4,牛頓法的迭代公式 阻尼牛頓法的迭代公式 牛頓方向,85,方法特點(diǎn) （1） 初始點(diǎn)應(yīng)選在X*附近，有一定難度； （2） 若迭代點(diǎn)的海賽矩陣為奇異，則無法求逆矩陣，不能構(gòu)造牛頓法方向； （3）不僅要計(jì)算梯度，還要求海賽矩陣及其逆矩陣，計(jì)算量和存儲量大。此外，對于二階不可微的F(X)也不適用。 雖然阻尼牛頓法有上述缺點(diǎn)，但在特定條件下它具有收斂最快的優(yōu)點(diǎn)，并為其他的算法提供了思路和理論依據(jù)。,86,87,88,2 坐標(biāo)輪換法,坐標(biāo)輪換法的基本思想：是將一個(gè)n維優(yōu)化問題轉(zhuǎn)化為依次沿n個(gè)坐標(biāo)方向反復(fù)進(jìn)行一維搜索問題。這種方法的實(shí)質(zhì)是把n維問題的求優(yōu)過程轉(zhuǎn)化為對每個(gè)變量逐次進(jìn)行一維求優(yōu)的循環(huán)過程。每次

29、一維搜索時(shí)，只允許n個(gè)變量的一次改動，其余(n-1)個(gè)變量固定不變。 該方法是將一個(gè)多維無約束優(yōu)化問題轉(zhuǎn)化成了一系列的一維問題來求解，因此該方法也稱為“變量輪換法”或“降維法”。,89,90,91,92,若： ，則有 。 若： ，也可認(rèn)為向量 通過矩陣A進(jìn)行線性變換后與 正交。 共軛是正交的推廣，正交是共軛的特例,一、共軛方向,1. 定義：,設(shè)A為 的實(shí)對稱正定陣，而 中兩個(gè)非 零 維列向量，如果滿足： ，則稱向量關(guān)于實(shí) 對稱正定陣A是共軛的。簡稱為 關(guān)于A共軛。,舉例：,判斷 、 是否關(guān)于矩陣A共軛。,三、 共軛方向法,93,“共軛方向”定義推廣為：,如果非零的n維向量組 ，且這個(gè)向 量組中

30、的任意兩個(gè)向量關(guān)于A矩陣共軛，即滿足： ，則稱向量組 關(guān)于矩 陣A共軛。,1. 定義：,*注意： n維空間中，相互共軛的非零向量的個(gè)數(shù)不超過維數(shù)n。,舉例：,即對于矩陣A來說， 和 不是唯一的。,；,94,正定二元二次函數(shù)：,共軛方向的幾何意義,95,連接兩切 點(diǎn)構(gòu)成的矢量：,96,2 二次收斂性 定義：對于一個(gè) n 維的二次函數(shù) 若應(yīng)用某種優(yōu)化方法，經(jīng)過有限次（一般不超過 n 次）一維搜索，就能找到極小點(diǎn)，則稱該優(yōu)化方法具有二次收斂性質(zhì)。 定理：共軛方向法具有二次收斂性。,97,1. 基本原理：,由于共軛方向法中新一輪的搜索方向組是：,不論方向 的“好、壞”，都將被舍去，因此可能造成新的方向

31、組線性相關(guān)或近似相關(guān)。,Powell法對這點(diǎn)進(jìn)行了改進(jìn)：有選擇性地去掉第k輪 中的某個(gè)方向，或者不更換原方向，以避免產(chǎn)生線性相 關(guān)性。,98,方向 為：與 相對應(yīng)的搜索方向，即函數(shù)值下降最大的方向。,是否用方向 替換第k輪中的某一方向，形成新的方向組，通過判別條件：,其中：,99, 如果這兩個(gè)條件有一個(gè)成立：則第k1輪的搜索方向仍用第k輪的基本方向組：,1. 基本原理：, 如果這兩個(gè)條件均不成立：則去掉第k輪方向組中的 函數(shù)值下降最大的方向 ，再將新生成的方向 補(bǔ)在最后，構(gòu)成第k1輪的基本方向組：,第k+1輪迭代初始點(diǎn) 取第k 輪方向 上的一維極小點(diǎn)。,第k+1輪迭代初始點(diǎn) 取第k輪中 和 中

32、函數(shù)值小的點(diǎn)。,100,101,102,2、變尺度法的基本思想,1.基本思想：,它是通過構(gòu)造一個(gè)對稱正定陣 ，在迭代過程中不 斷修正改變，逐漸逼近 ，一旦達(dá)到極值點(diǎn)附近， 就可望達(dá)到牛頓法的收斂速度。,它既可以通過初始的梯度方向來產(chǎn)生一個(gè)較好的迭 代點(diǎn)；又可以避免計(jì)算二階導(dǎo)數(shù)及其逆矩陣，而在極值 點(diǎn)附近又具有牛頓法收斂快的特點(diǎn)。,當(dāng)： ，該迭代公式變成了牛頓法的迭代公式。,當(dāng)： ，該迭代公式變成了梯度法的迭代公式。,：稱為變尺度矩陣。,103,Ak 是需要構(gòu)造nn的一個(gè)對稱方陣 ，,如Ak=I, 則得到梯度法 ；,變尺度法的關(guān)鍵在于尺度矩陣Ak的產(chǎn)生 。,搜索方向：,104,105,106,1

33、07,108,109,110,有約束優(yōu)化方法,隨機(jī)方向法 復(fù)合形法 懲罰函數(shù)法,111,第六章 約束優(yōu)化方法 機(jī)械優(yōu)化設(shè)計(jì)中的問題，大多數(shù)屬于約束優(yōu)化設(shè)計(jì)問題，其數(shù)學(xué)模型為：,112,（1）直接法 直接法包括：網(wǎng)格法、復(fù)合形法、隨機(jī)試驗(yàn)法、隨機(jī)方向法、可變?nèi)莶罘ê涂尚蟹较蚍ā?（2）間接法 間接法包括：罰函數(shù)法、內(nèi)點(diǎn)罰函數(shù)法、外點(diǎn)罰函數(shù)法、混合罰函數(shù)法、廣義乘子法、廣義簡約梯度法和約束變尺度法等。 約束優(yōu)化問題間接解法的基本迭代過程,根據(jù)求解方式的不同，約束優(yōu)化設(shè)計(jì)問題可分為:直接解法、間接解法。,113,約束最優(yōu)化間題有解的條件為： (1）目標(biāo)函數(shù)和約束函數(shù)為連續(xù)、可微函數(shù)，且存在一個(gè)有界的

34、可行域； (2）可行域，應(yīng)是一個(gè)非空集，即存在滿足約束條件的點(diǎn)列： 約束問題最優(yōu)解的求解過程，可歸結(jié)為： 尋求一組設(shè)計(jì)變量 在滿足約束方程： 的條件下，使目標(biāo)函數(shù)最小，即使：,114,62 約束隨機(jī)方向搜索法,一、基本原理,約束隨機(jī)方向搜索法是解決小型約束最優(yōu)化問題的一種較為有效的直接求解方法。 基本思想：利用計(jì)算機(jī)產(chǎn)生的隨機(jī)數(shù)所構(gòu)成的隨機(jī)方向進(jìn)行搜索，產(chǎn)生的新點(diǎn)必須在可行域內(nèi)，即滿足直接法的特性。 隨機(jī)方向法，一種數(shù)值迭代解法，是約束最優(yōu)化問題的一種常用的直接求解方法。它和隨機(jī)梯度法、GaussSeidel法等都屬于約束隨機(jī)法。 其基本思想可用二維最優(yōu)化問題來進(jìn)行說明,115,1、基本思想 1）從可行域內(nèi)某一點(diǎn)出發(fā)，沿某一給定步長，并隨機(jī)產(chǎn)生搜索方向，直到該方向同時(shí)滿足可行性和下降性要求，沿著這個(gè)方向以該步長繼續(xù)搜索，直到不滿足可行性及下降性條件為止。 2）把上述滿足要求的終點(diǎn)作為新的起點(diǎn)，重新產(chǎn)生隨機(jī)方向，如果能夠找到一個(gè)合適的方向，同時(shí)滿足條件，則沿該方向以原步長繼續(xù)搜索；如若找不到適合的方向，則將步長減半，仍以該點(diǎn)為起點(diǎn)隨機(jī)搜索，如果能找到新的方向，則沿該方向繼續(xù)，如果不能，步長再減半。直到找不到新的搜索方向，且步長滿足精度要求，則以該起點(diǎn)為最優(yōu)點(diǎn)。,116,117,118,119,120,在可行