03一維搜索方法

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

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

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

4、=0.6180.618n黃金比例應(yīng)用廣泛黃金比例應(yīng)用廣泛 2.2.迭代公式及迭代過程迭代公式及迭代過程 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ù)根值的方法。當目標函數(shù)逼近函數(shù)根值的方法。當目標函數(shù)f (x)

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

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

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

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

9、xxfxxfa12 插值多項式插值多項式p(x) 的極值點滿足的極值點滿足 p (x)=a1+2 a2x=0 可求得極小點可求得極小點 代入代入a1,a2可得到可得到 三、迭代過程及程序框圖三、迭代過程及程序框圖 四、其它插值法四、其它插值法 元代朱世杰的插值公式：元代朱世杰的插值公式： 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 五、一維搜索方法的比較五、一維搜索方法的比較 牛頓法收斂快牛頓法收斂快, ,但要求其一階、二階導數(shù)但要求其一階、二階導數(shù), ,對初始點的選擇要對初始點的選擇要求較高求較高; ;二次插值法充分利用了函數(shù)的性態(tài)二次插值法充分利用了函數(shù)的性態(tài), ,如目標函數(shù)本身就如目標函數(shù)本身就具有良好的性質(zhì)具有良好的性質(zhì)( (如二次，三次曲線等如二次，三次曲線等) )能夠很快的收斂能夠很