第05章 一維搜索方法

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

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

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

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

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

6、高的代價，而對加速收斂作用不大。所以，不精確一維搜索方法收到廣泛的重視和歡迎。 設(shè)要求)()()(minkkfsx，在不精確一維搜索中，通過要求)1( kf x比)(kf x下降一定的數(shù)量，而且在新點)()() 1(kkksxx處沿)(ks的方向?qū)?shù)比在)(kx點沿)(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īng)驗，常取1 . 01c，5 . 02c。 不精確一維搜索算法的計算步驟： 設(shè)點)(kx， 搜索方向)(ks已求得，為書寫簡便，令)(kkffx,)1(1kkffx，)(kkf xg, ) 1(1kkf xg。求出kf，kg。 (1) 給定1 , 01c，1 ,12cc ，令0, 1, 0jba。 (2) 令kkksxx)()1(， 計算1kf，1kg， 若滿足條件 a、 b，則令k，