機(jī)械優(yōu)化設(shè)計(jì)(第3、4次課)

機(jī)械優(yōu)化設(shè)計(jì)2017年5月上

海

海

事

大

學(xué)SHANGHAIMARITIMEUNIVERSITY何軍良12:241上海海事大學(xué)ShanghaiMaritimeUniversity

1909

2009

2004

1912

19587機(jī)械優(yōu)化設(shè)計(jì)中的幾個(gè)問題1優(yōu)化設(shè)計(jì)概述2優(yōu)化設(shè)計(jì)的數(shù)學(xué)基礎(chǔ)2目錄CONTENTS3一維搜索方法4無約束優(yōu)化方法5線性規(guī)劃6約束優(yōu)化方法12:24第三章一維搜索方法

概述01

搜索區(qū)間確定與區(qū)間消去法原理

一維搜索的試探方法

一維搜索的插值方法02030412:243第三章一維搜索方法求解優(yōu)化問題的基本解法有：解析法和數(shù)值解法解析法：即利用數(shù)學(xué)分析(微分、變分等）的方法，根據(jù)函數(shù)（泛函）極值的必要條件和充分條件求出其最優(yōu)解析解的求解方法。在目標(biāo)函數(shù)比較簡單時(shí)，求解復(fù)雜度尚可接受。局限性：工程優(yōu)化問題的目標(biāo)函數(shù)和約束條件往往比較復(fù)雜，有時(shí)甚至還無法用數(shù)學(xué)方程描述，在這種情況下應(yīng)用數(shù)學(xué)分析方法就會(huì)帶來麻煩。數(shù)值迭代法的基本思路：是進(jìn)行反復(fù)的數(shù)值計(jì)算，尋求目標(biāo)函數(shù)值不斷下降的可行計(jì)算點(diǎn)，直到最后獲得足夠精度的最優(yōu)點(diǎn)。這種方法的求優(yōu)過程大致可歸納為以下步驟：3.1概述3.1.1基本思路12:2445第三章一維搜索方法3.1概述3.1.1基本思路12:24第三章一維搜索方法（1）首先初選一個(gè)盡可能靠近最小點(diǎn)的初始點(diǎn)X（0），從X（0）出發(fā)按照一定的原則尋找可行方向和初始步長，向前跨出一步達(dá)到X（1）點(diǎn)；（2）得到新點(diǎn)X（1）后再選擇一個(gè)新的使函數(shù)值迅速下降的方向及適當(dāng)?shù)牟介L，從X（1）點(diǎn)出發(fā)再跨出一步，達(dá)到X（2）點(diǎn)，并依此類推，一步一步地向前探索并重復(fù)數(shù)值計(jì)算，最終達(dá)到目標(biāo)函數(shù)的最優(yōu)點(diǎn)。3.1概述3.1.1基本思路12:246第三章一維搜索方法在中間過程中每一步的迭代形式為：式中：X（k）——第k步迭代計(jì)算所得到的點(diǎn)，

稱第k步迭代點(diǎn)，亦為第k步設(shè)計(jì)方案；

a（k）——第k步迭代計(jì)算的步長；

S（k）——第k步迭代計(jì)算的探索方向。迭代法逐步逼近最優(yōu)點(diǎn)的探索過程如圖。運(yùn)用迭代法，每次迭代所得新的點(diǎn)的目標(biāo)函數(shù)都應(yīng)滿足函數(shù)值下降的要求迭代法要解決的問題：選擇搜索方向、確定步長因子、給定收斂準(zhǔn)則3.1概述3.1.1基本思路12:24783.1概述3.1.2一維問題是多維問題的基礎(chǔ)求目標(biāo)函數(shù)f(X)的極小點(diǎn)，從理論上說需要求解方程：其中，。那么如何來求f(X)的極小點(diǎn)呢？基本思想:這種方法是逐次迭代的方法，在電子計(jì)算機(jī)上很容易實(shí)現(xiàn)。因此，它在優(yōu)化設(shè)計(jì)中被廣泛地采用。第三章一維搜索方法12:249第三章一維搜索方法一維搜索方法解析法高等數(shù)學(xué)已學(xué)過，即利用一維函數(shù)的極值條件一維搜索方法數(shù)值解法分類有試探法和插值法。

求

解析法：步驟:1.f(X(k)+αS(k)

)

沿S(k)方向在x(k)點(diǎn)進(jìn)行泰勒展開；

2.取二次近似：

對于：3.1概述3.1.2一維問題是多維問題的基礎(chǔ)12:2410第三章一維搜索方法步驟:3.對α求導(dǎo)，令其為零;

步驟:4.求的最優(yōu)步長

3.1概述3.1.2一維問題是多維問題的基礎(chǔ)12:2411dk方向上任何一點(diǎn)可以表示為，

其中α是步長因子，為實(shí)系數(shù)，此時(shí)dk方向上任何一點(diǎn)的目標(biāo)函數(shù)值為。那么在沿dk方向求f(X)的極小點(diǎn)，這就是求一元函數(shù)的極小問題，它可表示為：這個(gè)過程稱為一維搜索過程。如：則：當(dāng)：

第三章一維搜索方法3.1概述3.1.2一維問題是多維問題的基礎(chǔ)12:24一維搜索示意圖12:2412133.1.2α的確定方法（1）取下降步長--能使目標(biāo)函數(shù)值下降的步長。上例中：F0=52,取α

=3，得F1=10<F0。故α

=3是下降步長。（2）取最優(yōu)步長上例中：令，

α*是最優(yōu)步長。（3）最優(yōu)步長直接解析求法對α求導(dǎo)并令其等于0，給出極值點(diǎn)α*應(yīng)滿足條件：直接利用f(X)函數(shù)而不需要把它化成步長因子α的φ(α)函數(shù)。第三章一維搜索方法3.1概述12:24143.1概述3.1.3一維搜索的基本思想（1）確定一個(gè)包含最優(yōu)點(diǎn)的初始搜索區(qū)間特點(diǎn)：高--低--高（2）將含最優(yōu)點(diǎn)的區(qū)間不斷縮小當(dāng)該區(qū)間的長度小于預(yù)先給定的一個(gè)很小的正數(shù)ε，則可認(rèn)為該區(qū)間中的某點(diǎn)(如中點(diǎn))是最優(yōu)點(diǎn)。*區(qū)間縮短率：λ=新區(qū)間長度/原區(qū)間長度第三章一維搜索方法12:24153.2搜索區(qū)間的確定與區(qū)間消去法原理3.2.1確定搜索區(qū)間的進(jìn)退法（外推法）（1）基本思想--試探后作前進(jìn)或后退計(jì)算設(shè)函數(shù)f(α)存在極小點(diǎn)α*，則初始區(qū)間為包含極小點(diǎn)α*的區(qū)間[a,b]。假設(shè)f(α)為單谷連續(xù)函數(shù)，通過進(jìn)退搜索方式確定相鄰的三個(gè)迭代點(diǎn)α1、α2、α3，若其函數(shù)值f1、f2、f3呈現(xiàn)大、小、大的變化趨勢，便可以定義出初始區(qū)間[α1,α3]。第三章一維搜索方法12:2416第三章一維搜索方法3.2搜索區(qū)間的確定與區(qū)間消去法原理3.2.1確定搜索區(qū)間的進(jìn)退法（外推法）12:2417（2）進(jìn)退法的計(jì)算步驟1.給定初始迭代點(diǎn)α0及初始步長h0，令α1←α0、h←h0、f1←f(α1)；2.計(jì)算新的試探點(diǎn)α2=α1+h，計(jì)算f2←f(α2)；3.比較函數(shù)值f1和f2的大小，確定是前進(jìn)探測還是后退探測。若f1>f2，則h←h0,向前探測；否則，令h←-h0，使α1和α2交換位置,向后探測；4.產(chǎn)生新的試探點(diǎn)α3=α2+h，令f3←f(α3)；5.比較函數(shù)值f2和f3的大小，確定初始區(qū)間。若f3>f2，則初始區(qū)間已經(jīng)得到；否則，倍增步距，令h=2h,繼續(xù)進(jìn)行搜索，直到產(chǎn)生的新探測點(diǎn)α3滿足f3>f2，則初始區(qū)間為[a,b]=[α1,α3]。向后探測時(shí)，若f3>f2，則初始區(qū)間為[a,b]=[α3,α1]。第三章一維搜索方法3.2搜索區(qū)間的確定與區(qū)間消去法原理3.2.1確定搜索區(qū)間的進(jìn)退法（外推法）12:24右圖表示沿α的正向試探。每走一步都將區(qū)間的始點(diǎn)、中間點(diǎn)沿試探方向移動(dòng)一步（進(jìn)行換名）。經(jīng)過三步最后確定搜索區(qū)間[α1，α3]，并且得到區(qū)間始點(diǎn)、中間點(diǎn)和終點(diǎn)α1

<α2<α3

及所對應(yīng)的函數(shù)值y1

>

y2<y3y1y3→y2y2→y1a3→a2a2→a1a1Oaa3h0h02h0正向搜索的外推法3.2搜索區(qū)間的確定與區(qū)間消去法原理3.2.1確定搜索區(qū)間的進(jìn)退法（外推法）第三章一維搜索方法y1←y2a2←a3a1←a2←a1Oaa32h0h0h0y3y1←y2←y1y2←y3a1←a2反向搜索的外推法3.2搜索區(qū)間的確定與區(qū)間消去法原理3.2.1確定搜索區(qū)間的進(jìn)退法（外推法）第三章一維搜索方法右圖表示開始沿α的正向試探，但由于函數(shù)值上升而改變試探方向，最后得到了區(qū)間始點(diǎn)、中間點(diǎn)和終點(diǎn)α1

>α2>α3

及所對應(yīng)的函數(shù)值y1

>

y2<y3，從而形成的單谷區(qū)間為一維搜索區(qū)間[α3，α1]

12:2419khx1x2x30h0初始點(diǎn)初始點(diǎn)+h01h0初始點(diǎn)初始點(diǎn)+h0初始點(diǎn)+2h022h0初始點(diǎn)+h0初始點(diǎn)+2h0初始點(diǎn)+4h034h0初始點(diǎn)+2h0初始點(diǎn)+4h0初始點(diǎn)+8h0（3）前進(jìn)搜索步驟表3.2搜索區(qū)間的確定與區(qū)間消去法原理3.2.1確定搜索區(qū)間的進(jìn)退法（外推法）第三章一維搜索方法12:2420khx1x2x30h0初始點(diǎn)初始點(diǎn)+h01h0初始點(diǎn)+h0初始點(diǎn)初始點(diǎn)-h022h0初始點(diǎn)初始點(diǎn)-h0初始點(diǎn)-3h034h0初始點(diǎn)-h0初始點(diǎn)-3h0初始點(diǎn)-7h0（4）后退搜索步驟表3.2搜索區(qū)間的確定與區(qū)間消去法原理3.2.1確定搜索區(qū)間的進(jìn)退法（外推法）第三章一維搜索方法22第三章一維搜索方法進(jìn)退法確定區(qū)間的算法框圖3.2搜索區(qū)間的確定與區(qū)間消去法原理3.2.1確定搜索區(qū)間的進(jìn)退法（外推法）（4）算法程序12:242312:2424例3-1用進(jìn)退法確定函數(shù)f(x)=3x3-8x+9的一維優(yōu)化初始區(qū)間，給定初始x1=0，初始化進(jìn)退距h0=0.1。解：khx1y1x2y2x3y310.10.1090.18.2030.27.42420.20.18.2030.27.4240.45.99230.40.27.4240.45.9920.84.13640.80.45.9920.84.1361.68.488可得，初始搜索區(qū)間[a,b]=[0.4,1.6]。第三章一維搜索方法3.2搜索區(qū)間的確定與區(qū)間消去法原理3.2.1確定搜索區(qū)間的進(jìn)退法（外推法）12:2425例3-2用進(jìn)退法確定函數(shù)f(x)=3x3-8x+9的一維優(yōu)化初始區(qū)間，給定初始x1=1.8，初始化進(jìn)退距h0=0.1。解：可得，初始搜索區(qū)間[a,b]=[0.3,1.5]。khx1y1x2y2x3y310.1-0.11.812.0961.914.3771.914.3771.812.0961.710.1392-0.21.812.0961.710.1391.57.1253-0.41.710.1391.57.1251.14.1934-0.81.57.1251.14.1930.36.681運(yùn)用進(jìn)退法確定出初始搜索區(qū)間[a,b]后，便可采用一維優(yōu)化方法來求出函數(shù)f(x)在區(qū)間內(nèi)的最優(yōu)點(diǎn)x*。第三章一維搜索方法3.2搜索區(qū)間的確定與區(qū)間消去法原理3.2.1確定搜索區(qū)間的進(jìn)退法（外推法）12:2426搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，從而找到極小點(diǎn)的數(shù)值近似解。假定在搜索區(qū)間內(nèi)[a,b]任取兩點(diǎn)a1，b1，對應(yīng)函數(shù)值為f(a1)，f(b1)。第三章一維搜索方法3.2搜索區(qū)間的確定與區(qū)間消去法原理3.2.2區(qū)間消去法12:2427存在三種可能情況：第三章一維搜索方法3.2搜索區(qū)間的確定與區(qū)間消去法原理3.2.2區(qū)間消去法12:24283.3一維搜索的試探法（黃金分割法）3.3.1基本思路該法適用于[a,b]區(qū)間上單谷函數(shù)極小值問題。在搜索區(qū)間[a,b]內(nèi)適當(dāng)加入兩點(diǎn)α1,α2，并計(jì)算其函數(shù)值。α1,α2將區(qū)間分成三段，然后利用區(qū)間消去法，通過比較函數(shù)值大小刪除其中一段，使搜索區(qū)間縮短，在保留區(qū)間進(jìn)行同樣處理，直到搜索區(qū)間縮小到指定精度為止。它適用于[a,b]區(qū)間上的任何單谷函數(shù)求極小值問題。對函數(shù)除要求“單谷”外不作其他要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面相當(dāng)廣。第三章一維搜索方法12:2429黃金分割法對插入點(diǎn)的要求：1、插入點(diǎn)

α1、α2

的位置相對于區(qū)間[a,b]兩端具有對稱性，即：為待定常數(shù)；2、在保留下來的區(qū)間內(nèi)再插入一點(diǎn)所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布。1）為預(yù)先給定的誤差限。2）縮短區(qū)間的總次數(shù)第三章一維搜索方法3.3一維搜索的試探法（黃金分割法）3.3.1基本思路12:2430（1）關(guān)于λ=0.618證明證：其正根為：第三章一維搜索方法3.3一維搜索的試探法（黃金分割法）3.3.1基本思路12:2431（2）縮小區(qū)間總次數(shù)的證明證：即：或第三章一維搜索方法3.3一維搜索的試探法（黃金分割法）3.3.1基本思路12:2432第三章一維搜索方法黃金分割法要求插入的兩點(diǎn)：

黃金分割法區(qū)間消去示意：f(a1)f(a2)f(a1)f(a2)a1

a1

a2abab

a23.3一維搜索的試探法（黃金分割法）3.3.1基本思路12:24333.3一維搜索的試探法（黃金分割法）3.3.2基本步驟1.給出搜索區(qū)間[a,b]，收斂精度ε，λ=0.6182.計(jì)算α1，α2以及對應(yīng)的函數(shù)值f(α1)、

f(α2)；3.根據(jù)區(qū)間消去法原理縮短搜索區(qū)間，為了能用原來的坐標(biāo)點(diǎn)計(jì)算公式，需進(jìn)行區(qū)間名稱的代換，并在保留區(qū)間中計(jì)算一個(gè)新的試驗(yàn)點(diǎn)及其函數(shù)值。如果f(α1)<f(α2)，則新區(qū)間＝[α,α2]

令b=α2,α2=α1,f(α2)=

f(α1)，記N0=0；如果f(α1)≥f(α2)，則新區(qū)間＝[α1,b]

令a=α1,

α1=α2,f(α1)=

f(α2)，記N0=0；

第三章一維搜索方法12:24344.檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠精度，如果收斂條件滿足，則取最后兩試驗(yàn)點(diǎn)的平均值作為極小點(diǎn)的數(shù)值近似解，如果條件不滿足則轉(zhuǎn)向步驟（5）。5.產(chǎn)生新的插入點(diǎn)：N0=0，則取N0=1，則取第三章一維搜索方法

轉(zhuǎn)向步驟(3)進(jìn)行新的區(qū)間縮小。3.3一維搜索的試探法（黃金分割法）3.3.2基本步驟12:2435這種方法的基本原理是：在搜索區(qū)間[a,b]內(nèi)按照如下規(guī)則對稱地取兩點(diǎn)a1和a2：α1=a+0.382(b-a)，α2=a+0.618(b-a)。計(jì)算它們的函數(shù)值f1=f(a1),f2(a2),比較兩者大小。有兩種可能：若f1≥f2,如圖（a）所示。極小值點(diǎn)必在區(qū)間[α1,b]內(nèi)，消去區(qū)間[a,a1]，令a=α1，產(chǎn)生新區(qū)間[α1,b]。新區(qū)間α1與原區(qū)間α2重合，可令α1=α2，f1=f2，這樣可少找一個(gè)新點(diǎn)和節(jié)省一次函數(shù)值計(jì)算。第三章一維搜索方法3.3一維搜索的試探法（黃金分割法）3.3.2基本步驟12:2436若f1<f2,如圖（b）所示。極小值點(diǎn)必在區(qū)間[a,a2]內(nèi)，消去區(qū)間[α2,b]，令b=α2，產(chǎn)生新區(qū)間[a,

α2]。同樣，新區(qū)間α2與原區(qū)間α1重合，可令α2=α1，f2=f1，這樣可少找一個(gè)新點(diǎn)和節(jié)省一次函數(shù)值計(jì)算。第三章一維搜索方法3.3一維搜索的試探法（黃金分割法）3.3.2基本步驟12:2437第三章一維搜索方法3.3一維搜索的試探法（黃金分割法）3.3.2基本步驟12:2438第三章一維搜索方法3.3一維搜索的試探法（黃金分割法）3.3.2基本步驟12:2439第三章一維搜索方法3.3一維搜索的試探法（黃金分割法）3.3.2基本步驟12:2440第三章一維搜索方法12:2441第三章一維搜索方法3.3一維搜索的試探法（黃金分割法）3.3.2基本步驟12:2442例3-3用黃金分割法求f(α)=α2+2α的極小值α*，搜索區(qū)間是-3≤α≤5。解：迭代序號aα1α2by1比較y20-30.0561.94450.115<7.6671-3-1.1110.0561.944-0.987<0.1152-3-1.832-1.1110.056-0.306>-0.9873-1.832-1.111-0.6650