第05章 一維搜索方法

1、優(yōu)化設(shè)計(jì)方法(Optimization Method)交通與車輛工程學(xué)院交通與車輛工程學(xué)院 剛憲約剛憲約2022年年4月月2日日 本節(jié)要討論的問題是求解一元函數(shù)的極小值問題 )(min 當(dāng))(可微時(shí)，理論上說，這個(gè)問題的最優(yōu)解可由方程式0)( 求得。但是，這個(gè)方程往往是高度非線性的，很難求出解析解，更嚴(yán)重的是在很多實(shí)際問題中，)(不可微，或無法寫出其導(dǎo)數(shù)表達(dá)式， 因此一般地說就要用迭代的方法數(shù)值求解上列極小化問題，這就是所謂的一維搜索。 如果對于給定的初始點(diǎn)1，已經(jīng)求出)(1、)( 1和)( 1，則在1鄰近可以用二次函數(shù))(q近似)(，且保證)(q近似)(在1點(diǎn)有相同的函數(shù)及一、二階導(dǎo)數(shù)值：

2、211111)( 21)( )()(q 代替求)(的極小點(diǎn)。我們來求)(q的極小點(diǎn)2，它應(yīng)滿足 0)( )( )( 111q 由此 )( )( 1112 當(dāng)?shù)玫?后又可以計(jì)算利用同樣的方法計(jì)算3、4，直至收斂。 主要優(yōu)點(diǎn)：收斂速度快，在最優(yōu)解附近至少是二階收斂。 主要缺點(diǎn)：初始點(diǎn)選擇對收斂影響很大，需要計(jì)算二階導(dǎo)數(shù)。如果必須用數(shù)值方法求二階導(dǎo)數(shù)，則計(jì)算時(shí)的舍入誤差和近似誤差就會對算法的效率影響很大。 假定我們已經(jīng)定出一個(gè)區(qū)間21,，已知 0)( 1，0)( 2 兩點(diǎn)格式的核心就是逐步縮小區(qū)間21,，直到以足夠的精度求出目標(biāo)函數(shù)的最小值。縮小區(qū)間的方法是每次迭代時(shí)利用下列公式求得一個(gè)最小值的新估

3、計(jì)： )(1223 式中， 1 , 0是根據(jù)所采用的插值公式而決定的實(shí)數(shù)。 決定的方法常見的有弦位法和兩分法 弦位法是利用1點(diǎn)的)( 1和2點(diǎn)的)( 2，在1和2之間對)( 進(jìn)行線性插值，即 )()( )( )( )( 112121 該式給出0)( 的點(diǎn)*的近似值3 )()( )( )( 1212223 由此可見)( )( )( 122。 0.618 法又叫做黃金分割法，是不用導(dǎo)數(shù)的一維搜索方法中比較常用的一種方法。 設(shè)0為允許的最后的搜索區(qū)間長度， 令618. 0， 則 0.618法的計(jì)算步驟如下： (1) 計(jì)算 )(1 (1111aba，)(1 )(1111aba，)(1 令1k。 2)

4、若kkab，則計(jì)算結(jié)束，最優(yōu)解,*kkab，可取2/ )(*kkab ； 否 則 ， 若)()(kk， 則 轉(zhuǎn) 3) ，)()(kk，則轉(zhuǎn) 4） 。 3) 令kka1，kkbb1，再令kk1，)(1111kkkkaba，計(jì)算)(1k，轉(zhuǎn) 5)。 4) 令kkaa1，kkb1，再令kk1，)(1 (1111kkkkaba，計(jì)算)(1k，轉(zhuǎn) 5)。 5) 令1 kk，返回 2)。 41664)( min234xxxxxf 前面講的一維搜索方法，有的需要從一個(gè)初始的搜索區(qū)間出發(fā)，逐次進(jìn)行迭代計(jì)算；大多數(shù)算法，都要從一個(gè)初始點(diǎn)出發(fā)，逐次進(jìn)行迭代。下面給出一種進(jìn)退算法，它可以同時(shí)確定初始的搜索區(qū)間和初始

5、點(diǎn)。 (1) 選定初始點(diǎn)的一個(gè)估計(jì)值0t，初始步長0h，計(jì)算)(0t； (2) 令htt02，計(jì)算)(2t； (3) 若)()(02tt，轉(zhuǎn)第 4 步；否則，若)()(02tt，令hh，轉(zhuǎn)第 4 步； (4) 令htt01，計(jì)算)(1t； (5) 若)()(01tt，則令hh2，02tt ，10tt ，轉(zhuǎn)第 4 步；否則，若)()(01tt，轉(zhuǎn)第 6 步。 (6) 令),min(21tta ，),max(21ttb ，則,ba即為所求的初始區(qū)間，而2/ )(0abt可作為所求的初始點(diǎn)，計(jì)算結(jié)束。 在實(shí)際計(jì)算中，一般做不到精確的一維搜索，實(shí)際上，也沒有必要做到這一點(diǎn)。因?yàn)榫_的一維搜索需要付出較

6、高的代價(jià)，而對加速收斂作用不大。所以，不精確一維搜索方法收到廣泛的重視和歡迎。 設(shè)要求)()()(minkkfsx，在不精確一維搜索中，通過要求)1( kf x比)(kf x下降一定的數(shù)量，而且在新點(diǎn))()() 1(kkksxx處沿)(ks的方向?qū)?shù)比在)(kx點(diǎn)沿)(ks的方向?qū)?shù)值大一定的數(shù)量。 通常采用的是 Wolfe-Powell 不精確一維搜 索 準(zhǔn) 則 ， 簡 稱 Wolfe-Powell 準(zhǔn) 則 ， 即 對 給 定 的 常 數(shù)1,021cc，要求k滿足如下條件： a. )()(1) 1()(kkkkkfcffsxxxT b. )()(2)()1(kkkkfcfsxsxTT 根據(jù)計(jì)算經(jīng)驗(yàn)，常取1 . 01c，5 . 02c。 不精確一維搜索算法的計(jì)算步驟： 設(shè)點(diǎn))(kx， 搜索方向)(ks已求得，為書寫簡便，令)(kkffx,)1(1kkffx，)(kkf xg, ) 1(1kkf xg。求出kf，kg。 (1) 給定1 , 01c，1 ,12cc ，令0, 1, 0jba。 (2) 令kkksxx)()1(， 計(jì)算1kf，1kg， 若滿足條件 a、 b，則令k，