03一維搜索方法

1、1第三章一維優(yōu)化方法一維優(yōu)化方法2 數(shù)值迭代算法的過(guò)程可表示為：數(shù)值迭代算法的過(guò)程可表示為： 當(dāng)搜索方向一定后，目標(biāo)函數(shù)成為當(dāng)搜索方向一定后，目標(biāo)函數(shù)成為k的一元函數(shù)，即在直的一元函數(shù)，即在直線上求函數(shù)的極小點(diǎn)，這種運(yùn)算過(guò)程稱為一維搜索，或線性搜線上求函數(shù)的極小點(diǎn)，這種運(yùn)算過(guò)程稱為一維搜索，或線性搜索索(linear search)。v一維優(yōu)化問(wèn)題是基礎(chǔ)，大多數(shù)多維問(wèn)題可以是一系列一維一維優(yōu)化問(wèn)題是基礎(chǔ)，大多數(shù)多維問(wèn)題可以是一系列一維問(wèn)題的搜索。問(wèn)題的搜索。v一維優(yōu)化方法可分為兩類(lèi)：直接法和解析法一維優(yōu)化方法可分為兩類(lèi)：直接法和解析法)()()1()()()()(xx)x()x(minkkkk

2、kkkkkssfsf ks kx ks1kx33.1 3.1 確定初始區(qū)間的進(jìn)退法確定初始區(qū)間的進(jìn)退法 首先保證搜索區(qū)間函數(shù)具有單峰性，也就是在區(qū)間首先保證搜索區(qū)間函數(shù)具有單峰性，也就是在區(qū)間a, b中，函數(shù)是凸函數(shù)，具有高中，函數(shù)是凸函數(shù)，具有高低低高或低高或低高高低的特性，在區(qū)間低的特性，在區(qū)間a, b上有惟一的極小值或極大值。上有惟一的極小值或極大值。 1.1.基本思想基本思想x)(xfiii1a2a3a42.2.程序流程圖程序流程圖初始步長(zhǎng)初始步長(zhǎng)h取的過(guò)大，有取的過(guò)大，有可能出現(xiàn)不收斂的情況，可能出現(xiàn)不收斂的情況，初始步長(zhǎng)值一般應(yīng)給出較初始步長(zhǎng)值一般應(yīng)給出較小的值，如取收斂精度的小的

3、值，如取收斂精度的1010倍左右。倍左右。53.2 3.2 黃金分割法黃金分割法( (golden section method) ) 1.1.基本思想基本思想 黃金分割法是通過(guò)不斷縮短單峰區(qū)間的長(zhǎng)度來(lái)搜索黃金分割法是通過(guò)不斷縮短單峰區(qū)間的長(zhǎng)度來(lái)搜索極小點(diǎn)的一種有效方法，它是搜索區(qū)間按比例縮小，極小點(diǎn)的一種有效方法，它是搜索區(qū)間按比例縮小，通過(guò)計(jì)算和比較函數(shù)值，以確定取舍區(qū)間，因按黃通過(guò)計(jì)算和比較函數(shù)值，以確定取舍區(qū)間，因按黃金分割原理，故此法又稱金分割原理，故此法又稱0.6180.618法。法。n區(qū)間變化圖區(qū)間變化圖: :abcd)(a)(babcd)(cabcd6n黃金分割比例黃金分割比例

4、=0.6180.618n黃金比例應(yīng)用廣泛黃金比例應(yīng)用廣泛 2.2.迭代公式及迭代過(guò)程迭代公式及迭代過(guò)程 c=a+0.382(b-a) d=a+0.618(b-a) xfaxcdb終止條件：終止條件：(b-a)ex*=(a+b)/2 xfaxc)(cd)(dbf(c)f(d)(dc xf)(caxdbf(c)f(d)7 3.3.程序流程圖程序流程圖83.3 3.3 牛頓法牛頓法 (newtons method) 一一. .基本思想基本思想 牛頓法在一維探索中的應(yīng)用，是用切線代替弧逐漸牛頓法在一維探索中的應(yīng)用，是用切線代替弧逐漸逼近函數(shù)根值的方法。當(dāng)目標(biāo)函數(shù)逼近函數(shù)根值的方法。當(dāng)目標(biāo)函數(shù)f (x)

5、有一階連續(xù)導(dǎo)有一階連續(xù)導(dǎo)數(shù)且二階導(dǎo)數(shù)大于零時(shí)，在曲線數(shù)且二階導(dǎo)數(shù)大于零時(shí)，在曲線y= = f (x)上作一系列上作一系列切線，使之與切線，使之與x軸的交點(diǎn)軸的交點(diǎn)x(0)(0), , x(1)(1), , x(3)(3), , , ,逐漸趨逐漸趨于于f (x)=0的根。的根。)(xf )()0()0(xfx*x)2(xxa) 1 (x)0(xbo9 二二. .迭代公式迭代公式 三三. .程序流程圖程序流程圖 )()()( )()(1kkkkxfxfxx 四四. .特點(diǎn)特點(diǎn) 1.1.牛頓法的優(yōu)點(diǎn)是收斂快，牛頓法的優(yōu)點(diǎn)是收斂快，尤其在開(kāi)始的時(shí)候。尤其在開(kāi)始的時(shí)候。 2.2.需計(jì)算函數(shù)的一階、二需計(jì)

6、算函數(shù)的一階、二階導(dǎo)數(shù)，因而增加了每次迭代階導(dǎo)數(shù)，因而增加了每次迭代的工作量。的工作量。 3.3.另外另外, ,要求初始點(diǎn)選擇不要求初始點(diǎn)選擇不能離極值點(diǎn)太能離極值點(diǎn)太“遠(yuǎn)遠(yuǎn)”。 103.4 3.4 二次插值法二次插值法 (quadratic interpolation method) 一一. .基本思想基本思想 插值法是多項(xiàng)式逼近法的一種。是利用目標(biāo)函數(shù)在若干點(diǎn)的插值法是多項(xiàng)式逼近法的一種。是利用目標(biāo)函數(shù)在若干點(diǎn)的信息（包括函數(shù)值、導(dǎo)數(shù)值等），構(gòu)成一個(gè)與原目標(biāo)函數(shù)值相信息（包括函數(shù)值、導(dǎo)數(shù)值等），構(gòu)成一個(gè)與原目標(biāo)函數(shù)值相接近的低次插值多項(xiàng)式，然后用該多項(xiàng)式的最優(yōu)解作為函數(shù)的接近的低次插值多項(xiàng)

7、式，然后用該多項(xiàng)式的最優(yōu)解作為函數(shù)的近似最優(yōu)解，隨著區(qū)間的逐次縮短，多項(xiàng)式函數(shù)的最優(yōu)點(diǎn)與原近似最優(yōu)解，隨著區(qū)間的逐次縮短，多項(xiàng)式函數(shù)的最優(yōu)點(diǎn)與原函數(shù)的最優(yōu)點(diǎn)之間的距離漸減小，直到滿足一定的精度要求時(shí)函數(shù)的最優(yōu)點(diǎn)之間的距離漸減小，直到滿足一定的精度要求時(shí)迭代終止。迭代終止。 二、二次插值法的公式推導(dǎo)二、二次插值法的公式推導(dǎo) 二次插值法是用區(qū)間二次插值法是用區(qū)間a, b上的三個(gè)點(diǎn)的函數(shù)值構(gòu)成二次多上的三個(gè)點(diǎn)的函數(shù)值構(gòu)成二次多項(xiàng)式去逼近原函數(shù)，項(xiàng)式去逼近原函數(shù)，如果函數(shù)性態(tài)接近拋物線，能夠比較快的如果函數(shù)性態(tài)接近拋物線，能夠比較快的收斂，也稱收斂，也稱拋物線法拋物線法。 11 xf xp xp xf

8、2xmx3xxo1x*x 目標(biāo)函數(shù)在三個(gè)點(diǎn)目標(biāo)函數(shù)在三個(gè)點(diǎn)x1, x2, x3的函數(shù)值為的函數(shù)值為f1, f2, f3滿足滿足 x1x2f2 f3 利用利用x1, x2, x3三點(diǎn)作二次多項(xiàng)式三點(diǎn)作二次多項(xiàng)式 p(x)=a0+a1x+a2x2 式中式中, a0,a1,a2為待定系數(shù)。為待定系數(shù)。332323103222222102112121101)()()()()()(fxfxaxaaxpfxfxaxaaxpfxfxaxaaxp)()()()()()()()()()(13322121313232121332212221321232232211xxxxxxxxfxxfxxfaxxxxxxxxf

9、xxfxxfa12 插值多項(xiàng)式插值多項(xiàng)式p(x) 的極值點(diǎn)滿足的極值點(diǎn)滿足 p (x)=a1+2 a2x=0 可求得極小點(diǎn)可求得極小點(diǎn) 代入代入a1,a2可得到可得到 三、迭代過(guò)程及程序框圖三、迭代過(guò)程及程序框圖 四、其它插值法四、其它插值法 元代朱世杰的插值公式：元代朱世杰的插值公式： f(nf(n)=n)=n+n(n-1)+n(n-1)2 2+n(n-1)(n-2)+n(n-1)(n-2)3 3+n(n-1)(n-2)(n-+n(n-1)(n-2)(n-3)3)4 4+ 212aaxm)()()( 2213132321222132123223221xxfxxfxxfxxfxxfxxfxm13 五、一維搜索方法的比較五、一維搜索方法的比較 牛頓法收斂快牛頓法收斂快, ,但要求其一階、二階導(dǎo)數(shù)但要求其一階、二階導(dǎo)數(shù), ,對(duì)初始點(diǎn)的選擇要對(duì)初始點(diǎn)的選擇要求較高求較高; ;二次插值法充分利用了函數(shù)的性態(tài)二次插值法充分利用了函數(shù)的性態(tài), ,如目標(biāo)函數(shù)本身就如目標(biāo)函數(shù)本身就具有良好的性質(zhì)具有良好的性質(zhì)( (如二次，三次曲線等如二次，三次曲線等) )能夠很快的收斂能夠很