工程優(yōu)化第三章一維搜索

1、133第三章常用的一維搜索方法第一節(jié) 搜索算法概述一、下降迭代算法的基本不失一般性，考慮如下的優(yōu)化問題min f (x)（3.1）xS其中 f : S Rn R .下降迭代算法的的基本：給定一個初始點 x1 Rn ，按照某種迭代規(guī)則產生一個點列xk ，使得當xk 是有限點列時其最后一個點是最優(yōu)化問題的最優(yōu)解；當xk 是無窮點列時，它有極限點，且其極限點是優(yōu)化問題的最優(yōu)解.233設已迭代到點 xk 處，則下一次迭代會出現以下兩種情況之一：（1） 從 xk 出發(fā)沿任何方向移動，目標函數不再下降；（2） 從 xk 出發(fā)至少存在一個方向使目標函數 f ( x) 有所下d kd k降 . 這 時 ， 從

2、 中 選 取 一個 下 降 方 向， 即滿 足x xk d kf (xk )T d k 0 ，然后在直線上適當的確定一個新點xk 1 xk d，使得 f (xk1) f (xk d ) kkf (xk ) ，此時就說完成kk了第k 1 次迭代. xk dxk 1k基本迭代格式kkd k-搜索方向-步長因子或搜索步長333最優(yōu)化問題的求解步驟：選取初始點 x1 ，令k 1；構造搜索方向 d k .依照一定的規(guī)則，構造 f ( x) 在點處的下降方向或可行下降方向作為搜索方向d k ；xk（3）確定搜索步長k.以 xk 為起點沿搜索方向d k 選取的適當步長k ，使得目標函數值有某種意義的下降，通

3、常使f (xk d ) f (xk ) .kk xk d（4）求出新的迭代點 xk 1 .令 xk 1kk（5）檢驗終止條件.判定 xk 1 是否滿足終止條件，若滿足停止迭代， 輸出近似最優(yōu)解 xk 1 ； 否則， 令 k : k 1 ， 轉（2）.433二、直線搜索及其性質 xk dxk 1k迭代格式為k() f (xk dk )設（3.2）出發(fā)，沿方向d k 確定k ，使從 xk( ) (0) f (xk )（3.3）關于 的一維搜索問題kf (xk min f (x dk )d ) kk如果求得k ，使得k（. ） 0 (k ) min ( )或（. ） 0最優(yōu)一維搜索或精確一維搜索，

4、k 最優(yōu)步長因子533如果選取，使下降量 f (xk ) f (xk d ) 0k是可接受kk-可接受一維搜索，或不精確一維搜索若目標函數 f ( x) 具有連續(xù)的偏導數，并設定理 xk dxk 1k,其中 xk 1是從 xk 出發(fā)沿搜索方向d k 作一維精kf (xk1)T dk 0（3.5）確搜索得到的，則證明：設() f (xkdk ) ，對 求導數，有() f (xk dk )T dk.( ) dk )d ) min f (xf (xkkk x k dk 1kkxkk.由于，又 0k ( )可知，是的極小點，故() f (xk d ) d 0 ,kTkkkf (xk1)T dk 0 .

5、即633三、收斂速度與終止準則1. 收斂速度定義 設由某算法產生的迭代點列xk 收斂于 x* ，即有l(wèi)im | xk x* | 0 .k 若存在實數0及與迭代次數無關的常數q 0，使| xk1 x* | qlim x* |k | xk則稱算法產生的迭代點列xk 具有階收斂速度.當=1， q 0，稱迭代點列xk 具有線性收斂速（1）度，或該算法是線性收斂的；733（2）當 1 或=1， q =0，稱迭代點列xk 具0有超線性收斂速度，或該算法是超線性收斂的；（3）當=2，稱迭代點列xk 具有二階收斂速度，或該算法是二階收斂的.2.終止準則| xk1 xk | 1| xk | xk | 1. |

6、xk 1或1| f (xk1) f (xk ) | 12.| f (xk1) f (xk ) | 1或| f (xk ) |3. | f (xk ) | 3（無約束優(yōu)化問題）833第二節(jié)成功失敗法min (x)設問題（2.1）當a x b其它a xb(x) (x)則令min (x) min (x)顯然.xRa xbmin (x)以下，不失一般性考慮xR. ( x* ) min ( x) : R Rx* 0, )定義設，且.如果對于x0閉區(qū)間a, b 0 ，有 x* a, b，則稱a, b 是問題（2.1）的搜索區(qū)間.933算法步驟：1） 選取初始點 x R ，初始步長h 0 及精度 0, 計算

7、1 (x) ；2） 計算2 (x h) ；3） 若2 1 （此時稱搜索成功，下一步搜索就大步前進），令 x x h, 1 2 , h 2h ，轉2）；若2 1 （此時稱搜索失敗，下一步搜索就小步退步），判別| h | ? 若| h | ,h停止迭代， x x* ；否則令h 4 ，轉 2）.缺點：效率較低，h選擇要適當，初始步長不能選得太小。但改造之后用于求搜索區(qū)間比較有效?；荆簭囊稽c出發(fā)，按一定的步長，試圖確定出函數值呈現“高低高”的三個點.一個方向不成功，就退回來沿相反的方向搜索.1033“成功失敗”法（進退法）例1：設給定初始點為 a 及初始步長為 h, 求搜索區(qū)間c, d1)前進運算首

8、先計算 f (a), f (a+h),如果 f (a) f (a+h), 則步長加倍, 計算f (a+3h). 若 f (a+h)= f (a+3h), 則c=a, d=a+3h; 否則將步長再加倍，并重復上面運算.2)后退運算如果 f (a) f (a+h), 則將步長縮為原來的1/4并改變符號，即將步長改為-h/4, 如果 f (a) f (a-h/4),則c=a-h /4,d=a+h; 否則將步長加倍，并繼續(xù)后退。注意: 1. h 選擇要適當.(太大含多個單峰區(qū)間,太小迭代次數多)；2.f (x)單調時無結果, (加迭代次數限制)；1133“成功失敗”法算例例：利用“成功-失敗”法求函數

9、fx 1的搜索區(qū)間，取初始點x 1 ，步長h 1 .2 121x h ,解：取初始點，步長22f ( x) f ( 1 ) 15 ,f ( x h) f ( 1 1 ) f (0) 1,2因為f ( x) 822f ( x h)，搜索成功， 步長加倍；f ( x 3h) f ( 1 3 1 ) 計算 f ( x h + 2h) f (1) 0,22因為f ( x h) f ( x 3h)，搜索成功，步長加倍； 計算 f ( x 3h +4h) f ( x 7 h) f ( 1 7 1 ) f (3) 22,22因為 x 3hx 7 h ，搜索失敗，停止迭代； 得到搜索區(qū)間為 x h, x 7

10、h 0, 3.1233第三節(jié)0.618 法（黃金分割法）設 ( x) 是定義在a, b 上的函數，若定義min (x) (x )*x a, b*） 存在，使；1xa,b(x ) (x )2） 對任意的a x x b ，當 x x*時，2；當1221(x ) (x )x x* ( x)a, b時，2，則稱是上的單峰函數.11注：a, b 上的嚴格凸函數是單峰函數.單峰函數與非單峰函數1333性質 設 ( x) 在a, b 上是單峰函數，最小點為 x* .在(a, b) 內(x ) (x ) xxa, x*2 ，且 x2 ；若任取兩點 x和 x2 .若2，則111(x ) (x )x x , b*

11、.2，則11可敘述如下：在搜索區(qū)間a, b 內適當的0.618 法的基本兩點 x1 和 x2 ，這兩點把a, b 分為三段，通過比較這兩點處的函數值，根據單峰函數的性質，刪去最左段或者最右段區(qū)間，在保留下來的區(qū)間上作同樣的處理.如此迭代下去，可將搜索區(qū)間不斷縮小，當區(qū)間長度縮小到一定的程度時，可取當前區(qū)間上任一點作為極小點的近似.1433設 (x) 在a, b 上是單峰函數，最小點為 x* .在(a, b) 內任取 x2 ，并計算(x1),(x2 ) .0.618兩點 x1 和 x2 ，且 x1規(guī)則如下：法使用的主要“去壞留好原則” 、對稱原則、等比收縮原則主要公式：x1 a b x2x1 a

12、 (1 w)(b a) a 0.382(b a)x2 a b x1 a w(b a) a 0.618(b a)設每次函數計算后搜索區(qū)間的縮短率為 w ，初始區(qū)間為，因此最終區(qū)間長度為wn1 (b a) .a,b算法框圖 P481533例 用 0.618 法求解問題minx 1初始區(qū)間a1,b1 1,1 ，精度 0.16 .根據算法步驟進行迭代，計算結果如下表經 6 次迭代達到b7 a7 0.111 0.16x 0.168 0.279.滿足精度要求，極小點x 0.168 0.279 0.23 0.25 .可取實際上，最優(yōu)解 x*優(yōu)解.2作為近似最1633第四節(jié) 對分法（二分法）對分法適用對象：單

13、峰函數、連續(xù)可導優(yōu)點：每迭代一次可去掉區(qū)間的二分之一。如果找到一個區(qū)間a,b，具有性質(a) 0,(b) 0 ，則在a,b 之間必有(x) 的極小點 x* ，且(x*) 0 .算法步驟：已知a,b 且a b ，(a) 0,(b) 0 及 0 .c a b21），轉 2）；2）若b a ，轉 4）；否則，轉 3）；17334）；若(c) 0 ，則令a c ，轉3）計算(c) .若(c) 0 ，轉1）；若 (c) 0 ，則令b c ，轉 1）；4）令t* c ，停止迭代.設 ( 24x 8 ，求(x) 的極小點. 30 x2x3x2例解 5x 2) .x260又 (0) 24,(3) 48 ，故在

14、0,3 內有 (x) 的極小點 x*，取a 0,b 3， 0.1 .第一次迭代：c 0 3 322 ；1）2） b a 3 ，轉 3）；a 32 ，此時區(qū)間332 ，令3() a, b , 3223）迭代.，進入第二次1833第二次迭代：c 3 3 2 924 ；1）b a 3 3 322 ，轉 3）；2）9b 94 ，此時區(qū)間39() 4.68a, b ,2443），令，進入第三次迭代.第三次迭代：c 9 4 3 2 15 1.875281）；b a 9 3 3424 ，轉 3）；2）1933a 15815 9a, b ,84 ，進入第.875) 1.0284 ，令3），此時四次迭代.第四次

15、迭代：c 9 4 15 8 2.06252b a 9 15 31）；488 ，轉 3）；2）(2.0625) 0.8472b 2.06253），令，此時區(qū)間15 , 2.0625a, b 8，進入第五次迭代.第五次迭代：c 2.0625 15 8 1.9687521）；2033b a 2.0625 15 0.18758(1.9875) 0.351962），轉 3）；a 1.968753)，令，此時區(qū)間a,b 1.96875, 2.0625 ，進入第六次迭代.第六次迭代：c 2.0625 1.96875 2.015625, t* 22則此時2.0625 1.96875 0.09375 ，所以可取

16、t* 2.016平分法的優(yōu)點是，收斂于一個局部極小點.一步計算量小，程序簡單，且總能2133第五節(jié)法：在搜索區(qū)間中根據目標函數(x) 在某些點的信插值法的基本息，構造一個與它近似的低次（通常不超過三次）多項式函數 (x) ，在一定的條件下，期望 (x) 的極小點接近(x) 的極小點.min (x)考慮問題xR x )(x x)2kk令xk )(x xk ) 0又令得到 (x) 的駐點，記作 xk 1 ，則k )( k )迭代公式2233到一個序列 xk .可以證明，在一定條利用迭代公式件下，這個序列收斂于問題的最優(yōu)解，且是二階局部收斂的( x ) 僅當 ( x 0 ) 注意：二次函數0 時才有

17、極小點存在.法本質：一點二次插值法（一點處的函數值、一階和二階導數值）算法步驟：1）給定初始點 x 0 ，允許誤差0 0，置k；2）若| ( xk ) | ，則停止迭代，得到 x k ；)k3）計算 xk 1 ，( xk ) k 1 ，轉 2）；，置k2333例用法求解問題min( 6x2 16x 4x2x3 2x 1)x2(3解易于求出， ( x) 只有一個零點 x 4 .給定初始點 x0 3 ，控制誤差 0.001 ，計算結果見下表2433第六節(jié)三點二次插值法：用三點處的函數值構造二次函數 (x)基本近目標函數(x) ，并以 (x) 的極小點作為(x) 的近似極小點。具體做法如下：令 (x

18、) 與(x) 在三點x3 , (3 處有相同的函數值，并假設x2 ) (x3 )2 ,（即兩頭大，中間?。^點物線來擬合 (x) ，即令 (x) a bx cx2作拋3(c 0)2533又令 (x ) a bx c(x )2 (x ) 11111 (x ) a bx c(x )2 (x ) 22222 (x ) a bx c(x )2 (x ) 33333則 (x) 的極小點1(x )(x )2111(x )2(x221 (x )(x )23(x1 )x2(x2 )x3(x3 )112633記 x xk，這樣，將 xk 作為(x) 的極小點的一個估計.再從x 中選擇目標函數值最小的點及其左、

19、右兩點，給予相應的上標，代入上式，求出極小點的新的估計值 xk1 ，以此類推，產生點列xk .可以證明，在一定的條件下，這個點列收斂于問題的解，其收斂階約為 1.3.特別的，當3 三點等距，即x1 xx x1 2x ，代入 x 表達式中，則(2( (xx x2x )3作業(yè)：本章例題及對本章介紹的一維搜索方法進行編程（至少三個）2733非精確一搜索簡介考慮從點 xk 出發(fā)，沿方向dk 尋找迭代點 xk 1 ，要求： f (xk1) f (xk ) 且不能太小。k一、 ArmijoGoldstein 準則Armijo（1966）和 Goldstein（1965）分別提出了不精確一維搜索過程。設J

20、0 | f (xk dk ) f (xk )是一個區(qū)間。在下圖中，區(qū)間 J (0, a) 。28332933f (xk ) (gk )T d k f (xk1) k（1） b, c ，f (x ) (1 ) (gk )T d kk ) 1kf (xk滿足上述兩式要求的k了區(qū)間 J21其中0 2可寫為：記() dk ) ，則上述準則f (xk(k ) (0) k(0)( ) (0) (1 ) (0)（2）kk上述準則稱為 ArmijoGoldstein 非精確線性3033索準則（ArmijoGoldstein inexact liarchcriterion），簡稱 ArmijoGoldstein 準則。將滿足 b, c 稱為可接受區(qū)（1）（或（2）要求的區(qū)間 J2間， J2 中的點稱為可接受步長。幾何含義：可接