最優(yōu)化理論與方法 課件 9 一維搜索

一維搜索(linesearch)如果求得的

k，使得則稱該一維搜索為精確一維搜索，稱

k為最優(yōu)步長(zhǎng)。1精確一維搜索通常有兩種實(shí)現(xiàn)方式：（1）試探法：按某種方式找試探點(diǎn)，通過(guò)一系列試探點(diǎn)來(lái)確定極小點(diǎn)。（2）函數(shù)逼近法（插值法）：用某種較簡(jiǎn)單的曲線逼近原來(lái)的函數(shù)曲線，通過(guò)求逼近函數(shù)的極小點(diǎn)來(lái)估計(jì)目標(biāo)函數(shù)的極小點(diǎn)。20.618法（黃金分割法）

0ax1x2x*x’1

x’2

b

xf(x)(a)0a

x*

x1

x2

b

xf(x)f(x)f(x)(b)3定義:設(shè)f(x)是定義在閉區(qū)間[a,b]上的一元函數(shù)，x*是f(x)在[a,b]上的極小點(diǎn)，并且對(duì)任意的x1,x2

[a,b],x1<x2，有當(dāng)x2≤x*時(shí)，f(x1)>f(x2),當(dāng)x*≤x1時(shí)，f(x2)>f(x1),則稱f(x)是閉區(qū)間[a,b]上的單峰函數(shù)。4性質(zhì)：通過(guò)計(jì)算區(qū)間[a,b]內(nèi)兩個(gè)不同點(diǎn)處的函數(shù)值，就能確定一個(gè)包含極小點(diǎn)的子區(qū)間。定理：設(shè)f(x)是[a,b]上的單峰函數(shù)，x1,x2

[a,b]且x1<x2，若f(x1)>f(x2)，則對(duì)任意x

[a,x1]，有f(x)>f(x2)，若f(x1)≤f(x2)，則對(duì)任意x

[x2,b]，有f(x)≥f(x1)。50.618法的基本思想：

通過(guò)取試探點(diǎn)使包含極小點(diǎn)的區(qū)間不斷縮短，當(dāng)區(qū)間長(zhǎng)度小到一定程度時(shí)，區(qū)間上各點(diǎn)的函數(shù)值均接近極小值，因此任意一點(diǎn)都可以作為極小點(diǎn)的近似。6計(jì)算公式：f在[a,b]上單峰，極小點(diǎn)x*[a,b]，設(shè)進(jìn)行第k次迭代時(shí)，有x*[ak,bk]，取試探點(diǎn)

k,μk[ak,bk]，規(guī)定

k<μk，計(jì)算f(

k),f(μk)。若f(

k)>f(μk)，則有x*[

k,bk],令ak

+1=

k,bk

+1=bk;若f(

k)≤f(μk)，則有x*[ak,μk],令ak

+1=ak,bk

+1=μk.7確定

k,μk使它們滿足：（1）

k,μk在[ak

,bk]中的位置是對(duì)稱的，即

bk-μk=k-ak.（2）每次迭代區(qū)間長(zhǎng)度縮短比例相同，即bk+1-ak+1=

(bk-ak).8當(dāng)f(

k)>f(μk)時(shí)，ak

+1=

k,bk

+1=bk，代入(2)得：bk

–

k=

(bk-ak)；當(dāng)f(

k)≤f(μk)時(shí)，ak

+1=ak,bk

+1=μk，代入(2)得：μk–

ak=

(bk-ak)；

k=ak+(1-

)(bk-ak)μk=ak+(bk-ak)設(shè)在第k次迭代得出f(

k)≤f(μk)，則[ak

+1,bk+1]=[ak

,μk]在第k+1次迭代中，需要取試探點(diǎn)

k+1,μk+1μk+1=ak+1+(bk+1-ak+1)=ak+(μk-ak)=

ak+(ak+(bk

–ak)

-ak)=ak+2(bk

-ak)若令

2=1-

，則μk+1=

k，因此μk+1可以不必重新計(jì)算。9

k=ak+(1-

)(bk-ak)μk=ak+(bk-ak)10當(dāng)f(

k)>f(μk)時(shí)，用類似方法，可以推出同樣結(jié)論，即

=0.618，此時(shí)取

k+1=μk，不必重新計(jì)算

k+1。11因?yàn)椋?/p>

k=ak+(1-

)(bk-ak)；μk=ak+(bk-ak).所以：

k=ak+0.382(bk-ak)；μk=ak+0.618(bk-ak).計(jì)算步驟：置初始區(qū)間[a1

,b1]及精度要求L>0，計(jì)算

1=a1+0.382(b1-a1)；μ1=a1+0.618(b1-a1)，計(jì)算f(

1)和f(μ1)。令k=1。2.若bk-ak<L，停止計(jì)算；否則若f(

k)>f(μk)，轉(zhuǎn)3；若f(

k)≤f(μk)，轉(zhuǎn)4。3.置ak

+1=

k

,

bk

+1=bk

,

k+1=μk,

μk+1=ak+1+0.618

(bk+1-ak+1)，計(jì)算f(μk+1)，轉(zhuǎn)5。12134.置ak

+1=ak

,

bk

+1=μk,

μk+1=

k,

k+1=ak+1+0.382

(bk+1-ak+1)，計(jì)算f(

k+1)，轉(zhuǎn)5。5.置k=k+1，返回2。缺點(diǎn)：14優(yōu)點(diǎn):不要求函數(shù)可微，甚至當(dāng)函數(shù)不連續(xù)時(shí)，0.618法仍可應(yīng)用。缺點(diǎn)：收斂比較慢，0.618法只適用于單峰函數(shù)，所以需要先確定單峰區(qū)間，再使用0.618法的計(jì)算公式。例：12a1b1=b2a2a3b315定義：設(shè)有數(shù)列{Fn}滿足條件：

(1)F0=F1=1(2)Fk+1=Fk+Fk-1,k=1,2,…則稱數(shù)列{Fn}為Fibonacci數(shù)列。n01234567…Fn1123581321…19

Fibonacci法Fabonacci法在迭代計(jì)算試探點(diǎn)的公式：其中n為計(jì)算函數(shù)值的次數(shù)（不包括初始區(qū)間端點(diǎn)的計(jì)算），需要事先給出。20結(jié)論21只要給出初始區(qū)間長(zhǎng)度b1-a1及精度要求L，就可以求出計(jì)算函數(shù)值的次數(shù)n（不包括初始區(qū)間端點(diǎn)函數(shù)值的計(jì)算）。第k次迭代區(qū)間長(zhǎng)度的縮短比率為：22第一次迭代計(jì)算有兩個(gè)試探點(diǎn)（

1,μ1）以后每次計(jì)算1個(gè)，經(jīng)過(guò)n-1次迭代有n個(gè)試探點(diǎn)。但是，在第n-1次迭代中，根據(jù)

k,μk的計(jì)算公式有：

n-1=μn-1

=

?(an-1+bn-1)而

n-1

和μn-1中的一個(gè)取自第n-2次迭代中的試探點(diǎn)。23為了在第n-1次迭代中能夠縮短區(qū)間，可在第n-2次迭代后，此時(shí)已經(jīng)確定出

n-1=μn-1,在

n-1的左邊或右邊取一點(diǎn)，令

n=

n-1，

μn

=

n-1+δ，

δ>0為辨別常數(shù)。24計(jì)算步驟:置初始區(qū)間[a1,b1]及最終區(qū)間長(zhǎng)度L>0，先求計(jì)算函數(shù)值的次數(shù)n，使Fn≥(b1-a1)/L。置辨別常數(shù)δ>0，計(jì)算

求得f(

1),f(μ1),令k=1。25若f(

k)>f(μk),則轉(zhuǎn)3；若f(

k)≤f(μk),轉(zhuǎn)4。置ak

+1=

k

,bk

+1=bk

,

k+1=μk,

若k=n-2，轉(zhuǎn)6；否則計(jì)算f(μk+1)，轉(zhuǎn)5.4.置ak

+1=ak

,bk

+1=μk

,μk+1=

k,若k=n-2，轉(zhuǎn)6；否則計(jì)算f(

k+1)，轉(zhuǎn)5.26置k=k+1，返回2。

令

n=

n-1

,μn=

n-1+δ,計(jì)算f(

n)和f(μn)。

若f(

n)>f(μn)，則令an=

n,

bn=

bn-1;

若f