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

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

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

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

0ax1x2x*x’1

x’2

b

xf(x)(a)0a

x*

x1

x2

b

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

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

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

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

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

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

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

k<μk，計算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]中的位置是對稱的，即

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

(bk-ak).8當f(

k)>f(μk)時，ak

+1=

k,bk

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

–

k=

(bk-ak)；當f(

k)≤f(μk)時，ak

+1=ak,bk

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

ak=

(bk-ak)；

k=ak+(1-

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

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

+1,bk+1]=[ak

,μk]在第k+1次迭代中，需要取試探點

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可以不必重新計算。9

k=ak+(1-

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

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

=0.618，此時取

k+1=μk，不必重新計算

k+1。11因為：

k=ak+(1-

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

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

,b1]及精度要求L>0，計算

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

1)和f(μ1)。令k=1。2.若bk-ak<L，停止計算；否則若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)，計算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)，計算f(

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

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

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

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

k,μk的計算公式有：

n-1=μn-1

=

?(an-1+bn-1)而

n-1

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

n-1=μn-1,在

n-1的左邊或右邊取一點，令

n=

n-1，

μn

=

n-1+δ，

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

求得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；否則計算f(μk+1)，轉(zhuǎn)5.4.置ak

+1=ak

,bk

+1=μk

,μk+1=

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

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

令

n=

n-1

,μn=

n-1+δ,計算f(

n)和f(μn)。

若f(

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

n,

bn=

bn-1;

若f