維優(yōu)化方法課件

1、維優(yōu)化方法維優(yōu)化方法3.1 概述概述xk+1 = xk + kdk (k = 0, 1, 2, )式中 dk為第k+1次迭代的搜索方向，k為沿dk搜索的最佳步長(zhǎng)因子。當(dāng)方向dk給定， 求最佳步長(zhǎng)k就是求一元函數(shù)f(xk+1)=f (xk + kdk )=(k)的極值問題。即在優(yōu)化設(shè)計(jì)的迭代運(yùn)算中，在搜索方向s(k)上尋求最優(yōu)步長(zhǎng) (k) 的方法稱一維搜索法。求多元函數(shù)極值點(diǎn)， 需要進(jìn)行一系列的一維搜索。 維優(yōu)化方法維優(yōu)化方法 可利用一元函數(shù)的極值條件(*)=0求*。把f (xk + kdk )進(jìn)行泰勒展開并取二階項(xiàng)，即上式對(duì)進(jìn)行微分并令其等于零求極值， 得得得此時(shí)需要計(jì)算函數(shù)梯度和海賽矩陣。

2、0*GddxfdTT GddxfdxfdGdxfdxfdxfTTTT22121 GddxfdTT* 解析法的缺點(diǎn)是需要進(jìn)行求導(dǎo)計(jì)算。 在優(yōu)化設(shè)計(jì)中， 求解最佳步長(zhǎng)因子主要采用數(shù)值解法，通過(guò)計(jì)算機(jī)的反復(fù)迭代計(jì)算求得最佳步長(zhǎng)因子的近似值。 數(shù)值解法的基本思路是：先確定*所在的搜索區(qū)間， 然后根據(jù)區(qū)間消去法不斷縮小此區(qū)間，從而獲得*的數(shù)值近似解。維優(yōu)化方法維優(yōu)化方法3.2 3.2 搜索區(qū)間的確定與區(qū)間消去法原理搜索區(qū)間的確定與區(qū)間消去法原理一、外推法一、外推法 在一維搜索時(shí)，需要確定一個(gè)搜索區(qū)間a,b，此區(qū)間必須包含函數(shù)的極小點(diǎn) x*，因此搜索區(qū)間必須是單谷區(qū)間單谷區(qū)間，即該區(qū)間內(nèi)的函數(shù)值呈現(xiàn)“高-

3、低-高”的趨勢(shì)。如圖所示，通過(guò)將搜索區(qū)間a,b逐漸縮小，直至足夠小，就可以得到近似最優(yōu)點(diǎn)。維優(yōu)化方法維優(yōu)化方法 從 = 0開始， 以初始步長(zhǎng)h0向前試探。如果函數(shù)值上升， 則步長(zhǎng)變號(hào)，即改變?cè)囂椒较?。如果函?shù)值下降， 則維持原來(lái)的試探方向，并使步長(zhǎng)加倍。區(qū)間的始點(diǎn)、中間點(diǎn)依次沿試探方向移動(dòng)一步。此過(guò)程一直進(jìn)行到函數(shù)值再次上升時(shí)為止，即可找到搜索區(qū)間的終點(diǎn)。最后得到的三點(diǎn)即為搜索區(qū)間的始點(diǎn)、中間點(diǎn)和終點(diǎn)，形成函數(shù)值的“高-低-高”趨勢(shì)。維優(yōu)化方法維優(yōu)化方法維優(yōu)化方法維優(yōu)化方法上述確定搜索區(qū)間的外推法，其程序框圖如圖3-4所示。維優(yōu)化方法維優(yōu)化方法二、區(qū)間消去法原理 假設(shè)在搜索區(qū)間a,b內(nèi)任取兩點(diǎn)

4、a1、b1, a1b1，并計(jì)算函數(shù)值f(a1)、 f(b1)?？赡苡腥缦氯N情況 1） f(a1) f(b1),如圖3-5b所示。由于函數(shù)的單谷性，極小點(diǎn)在區(qū)間a1,b內(nèi)。 3) f(a1)= f(b1),極小點(diǎn)在區(qū)間a1,b1內(nèi)。2)、3）可合并為一種情況，即f(a1) f(b1),極小點(diǎn)在區(qū)間a1,b內(nèi)。維優(yōu)化方法維優(yōu)化方法三、一維搜索方法的分類 分為兩類： 一類稱做試探法， 按某種給定的規(guī)律來(lái)確定區(qū)間內(nèi)插入點(diǎn)的位置， 如黃金分割法等； 一類稱為插值法或函數(shù)逼近法，這類方法是根據(jù)某些點(diǎn)處的某些信息， 如函數(shù)值、一階導(dǎo)數(shù)、二階導(dǎo)數(shù)等， 構(gòu)造一個(gè)插值函數(shù)來(lái)逼近原來(lái)函數(shù)， 用插值函數(shù)的極小點(diǎn)作為

5、區(qū)間的極小點(diǎn)， 如二次插值法， 三次插值法等。維優(yōu)化方法維優(yōu)化方法3.3 3.3 一維搜索的試探方法一維搜索的試探方法 黃金分割法適用于a,b區(qū)間上的任何單峰函數(shù)求極小值問題。對(duì)函數(shù)除要求單峰外不作其它要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面相當(dāng)廣。黃金分割法也是建立在區(qū)間消去法原理基礎(chǔ)上的試探方法。一、黃金分割法的原理一、黃金分割法的原理 在搜索區(qū)間a, b內(nèi)適當(dāng)插入兩點(diǎn)1,2 ，12,且在區(qū)間內(nèi)對(duì)稱位置，1 = b (b - a)2 = a + (b - a)計(jì)算其函數(shù)值。 y1 = f(1) y2 = f(2) 1)若y1y2則極小點(diǎn)必在區(qū)間a,2內(nèi)，令b =2，新區(qū)間為a，2 2)

6、若y1y2則極小點(diǎn)必在區(qū)間1,b內(nèi)，令a = 1，新區(qū)間為1，b 經(jīng)過(guò)函數(shù)值比較，區(qū)間縮短一次。新區(qū)間只保留1，2中的一個(gè)。圖3-6 黃金分割法維優(yōu)化方法維優(yōu)化方法圖3-6 黃金分割法維優(yōu)化方法維優(yōu)化方法黃金分割法的搜索過(guò)程黃金分割法的搜索過(guò)程，維優(yōu)化方法維優(yōu)化方法維優(yōu)化方法維優(yōu)化方法維優(yōu)化方法維優(yōu)化方法維優(yōu)化方法維優(yōu)化方法假定我們給定的問題是在某一確定區(qū)間內(nèi)尋求函數(shù)的極小點(diǎn)的位置，但是沒有函數(shù)表達(dá)式，只有若干試驗(yàn)點(diǎn)處的函數(shù)值。我們可以根據(jù)這些函數(shù)值，構(gòu)成一個(gè)與原目標(biāo)函數(shù)相接近的低次插值多項(xiàng)式，用該多項(xiàng)式的最優(yōu)解作為原函數(shù)最優(yōu)解的近似解，這種方法是用低次插值多項(xiàng)式逐步逼近原目標(biāo)函數(shù)的極小點(diǎn)的近

7、似求解方法，稱為插值方法或函數(shù)逼近法。二、插值法與試探法的異同點(diǎn)二、插值法與試探法的異同點(diǎn) 相同點(diǎn)相同點(diǎn)：都是利用區(qū)間消去法原理將初始搜索區(qū)間不斷縮短，從而求得極小點(diǎn)的數(shù)值近似解。 不同點(diǎn)不同點(diǎn)試驗(yàn)點(diǎn)位置的確定方法不同。維優(yōu)化方法維優(yōu)化方法 不同點(diǎn)不同點(diǎn)在試探法中試驗(yàn)點(diǎn)的位置是由某種給定的規(guī)律確定的，并未考慮函數(shù)值的分布。 例如：黃金分割法黃金分割法是按照等比例0.618縮短率確定的。 插值法插值法中，試驗(yàn)點(diǎn)的位置是按函數(shù)值近似分布的極小點(diǎn)確定的。 試探法試探法僅僅利用了試驗(yàn)點(diǎn)函數(shù)值進(jìn)行大小的比較，而插值法還要利用函數(shù)值本身或其導(dǎo)數(shù)信息。插值法插值法是利用函數(shù)在已知試驗(yàn)點(diǎn)的值（或?qū)?shù)值）來(lái)確定

8、新試驗(yàn)點(diǎn)的位置。所以，當(dāng)函數(shù)具有當(dāng)函數(shù)具有 多項(xiàng)式是函數(shù)逼近的一種常用工具。在搜索區(qū)間內(nèi)我們可以利用若干試驗(yàn)點(diǎn)處的函數(shù)值來(lái)構(gòu)造低次多項(xiàng)式， 用它作為函數(shù)的近似表達(dá)式，并用這個(gè)多項(xiàng)式的極小點(diǎn)作為原函數(shù)極小點(diǎn)的近似。牛頓法、拋物線法維優(yōu)化方法維優(yōu)化方法一、牛頓法（切線法） 對(duì)于一維搜索函數(shù)y = f(), 假定已給出極小點(diǎn)的一個(gè)較好的近似點(diǎn)0，因?yàn)橐粋€(gè)連續(xù)可微的函數(shù)在極小點(diǎn)附近與一個(gè)二次函數(shù)很接近， 所以可在0點(diǎn)附近用一個(gè)二次函數(shù)()來(lái)逼近f ()，即在0點(diǎn)將f () 進(jìn)行泰勒展開并保留到二次項(xiàng)：f() () = f (0) + f (0)( 0) +0.5f (0)( 0) 2然后以二次函數(shù) (

9、) 的極小點(diǎn)作為f()極小點(diǎn)的一個(gè)新近似點(diǎn)1。于是 (1)=0f (0)+f (0)( 0) =01 = 0 f (0)/ f (0)依次計(jì)算下去， 可得牛頓法迭代公式k+1 = k f (k)/ f (k) k = 0, 1, 2, 維優(yōu)化方法維優(yōu)化方法牛頓法的計(jì)算步驟：給定初始點(diǎn)0，控制誤差，令k = 0;1) 計(jì)算f (k)、 f (k) 2）求k+1 = k f (k)/ f (k) 3）若k+1 - k 則求得近似解*= k+1 ，停止結(jié)算， 否則4）4）令kk+1轉(zhuǎn)步驟1.維優(yōu)化方法維優(yōu)化方法例3-2 給定f ()= 4 43 62 16+4，使用牛頓法求其極小點(diǎn)*。解： f ()

10、 = 4(3 32 3-4) f () = 12(2 2-1)給定初始點(diǎn)0 = 3， 控制誤差 = 0.001，計(jì)算結(jié)果如下表所示。 牛頓法最大的優(yōu)點(diǎn)是收斂速度快， 但是在每一點(diǎn)處都需計(jì)算函數(shù)的二階導(dǎo)數(shù)， 工作量較大。特別是用數(shù)值微分代替二階導(dǎo)數(shù)時(shí)，舍入誤差會(huì)影響收斂速度，當(dāng)f ()很小時(shí)候這個(gè)問題跟嚴(yán)重。另外， 該方法對(duì)于初始點(diǎn)要求選的比較好， 否則有可能是極小化序列發(fā)散或收斂到非極小點(diǎn)。 維優(yōu)化方法維優(yōu)化方法利用原目標(biāo)函數(shù)上的三個(gè)插值點(diǎn)，構(gòu)成一個(gè)二次插值多項(xiàng)式，用該多項(xiàng)式的最優(yōu)解作為原函數(shù)最優(yōu)解的近似解，逐步逼近原目標(biāo)函數(shù)的極小點(diǎn)，稱為二次插值方法或拋物線法。 設(shè)一維目標(biāo)函數(shù)的搜索區(qū)間為a,b，取三點(diǎn)x1、x2、x3，其中x1、x3取區(qū)間的端點(diǎn)，即x1a ， x3 b 而x2為區(qū)間內(nèi)的一個(gè)點(diǎn)，開始可以取區(qū)間的中點(diǎn)，即