1、第4章 一維搜索方法 14.1 一維搜索方法 對n元函數, 給定點x(k), 向量pk, 則f(x)從x(k), 出發沿方向pk的直線上函數值的變化可以表示為一元函數: 該函數只有一個變量, 且每一個值都對應著直線上一個點。 求函數f(x)的解, 就轉化為沿直線 求一元函數 的極小值點, 因此本節先介紹一元函數f(x)的極小問題。 24.2 二分法 當f(x)連續可導時, 在極小點x*處有 , 因此求一元函數f(x)的極小值點問題就轉化為求解方程 的根的問題。稱 的點為函數f(x)的駐點。 設根 , 且 , 則有算法 3算法4.1(二分法) 1輸入a, b及精度0。2. 3若 或 , 輸出x*

2、=x。否則轉4。 4求 , 若 , 則 , 否則5輸出超過最大迭代次數的信息, 停機。 44.3 Newton法 假設f(x)二階連續可導, 對 在xk處展開為Taylor公式 由此有迭代公式： 算法4.2(Newton法求 的根) 1對 ; 做到第6步。 2 3若d=0停止計算。 4計算 5若 或 , 輸出x, 停機。 67若迭代N0次后仍達不到精度要求, 停機。 5 定義4.4.1 設f(x): a, bR 若存在點x*(a, b)使f(x)在a, x*上是單調減小, 在x*, b上是單調增加, 則稱a,b 是f(x)的單峰區間。f(x)是a, b上的單峰函數如圖所示。其中圖(a), 圖(

3、c)是單峰函數, 圖(b)不是單峰函數。 (a)(b)(c) 64.4 0.618法(黃金分割法) 假設f(x)是單峰函數, 但不知道極小點x*的位置。任取x1, x2a, b, 且x1x2, 則有以下三種情況存在： (2)f(x1)f(x2)此時 x*f(x2)此時 x* x1 , 即x*x1, b見圖(c)。 為計算方便可將情況(1)歸結到情況(2)或情況(3)。為了尋找x*, 在初始區間a1, b1內任取兩點 ; 且 , 通過比較函數值 , 從而確定極小點x*是在 或者x1, b1內。取小區間代替a1, b1 得新的x*的存在區間, 記為a2, b2, 又任取 且 , 通過比較函數值得新

4、的小區間a3, b3 x*的存在區間不斷縮小, 最后便可確定出近似的極小點, 為了節省計算函數值的工作量, 永遠保證新區間的一個端點和原區間的一個端點重合。 8 設每次迭代的區間長度按比例縮小(00,(2) (3)若 , 轉(4); 否則轉(2)。(4) 17(5)若 轉(6); 若 轉(7)。(6) 若k=n-2則轉(9); 否則計算f(x)轉(8)。(7)若k=n-2則轉(9); 否則計算f(x)轉(8)。(8) , 轉(5)。(9) , 若 , 則 ; 否則(10)輸出例4.1分別用二分法、Newton法、0.618法求解 解: 取精度 , 初值 Newton法的迭代公式為： 計算結果如

5、下表 18迭代次數二分法Newton法02.252.2511.8752.071428622.06252.008403431.968752.000137842.01562551.992187562.003906271.998361882.00113991.99975040.618法的計算結果如下表 20迭代次數ak, bkxkf(xk)00, 31.1458981.8541020.988936830.1042317211.145898, 31.8541022.2917960.104231720.7313779421.145898, 2.2917961.5836291.8541020.552945

6、090.1042318531.158359, 2.2917961.8541022.0212860.104231850.0279636341.854102, 2.2917962.0212862.1246120.027963630.1093716551.854102, 2.1246121.9574282.0212860.02670890.0027963661.975743, 2.1246122.0212862.0607530.027963630.398031271.957428, 2.0212861.9968942.0212860.000576320.0027963681.996894, 2.02

7、12861.9818191.9968940.00193550.0005763291.981819, 2.0212861.9968942.0062110.000576320.0012228Fibonacci法的計算結果如下表 21迭代次數ak, bkxkf(xk)00, 31.1460761.8539330.988899840.10444482911.1460673, 31.8539332.2921350.104448290.7333586921.146067, 2.2921351.8539331.8539330.551791690.10444482931.584270, 2.2921351.8

8、539332.0224720.104448290.0031214441.893933, 2.2921352.0224722.1284340.003121440.1167360951.853933, 2.1284341.9568702.0224720.010557980.0031214461.956870, 2.0598082.0224722.0590800.003121440.0021215671.956870, 2.0598081.9911832.0224720.000460970.0021214481.956870, 2.0224721.9787381.9911830.002632760.

9、0004609791.978738, 2.0224721.9911832.0063250.00460970.00002744 22若是無約束非線性規劃問題, 其一維搜索是使 一維搜索和有效一維搜索可分為兩種類型:最優一維搜索和可接受一維搜索。在 上選取步長因子 使f(x(k+1)f(x(k) 若考慮的是約束非線性規劃問題, 其一維搜索所得步長因子 , 不僅要滿足函數的下降性, 還需保證所得 仍是可行點。即步長因子應在某一有效區間 上選取，稱之為有效其一維搜索。 23(1)最優一維搜索(精確一維搜索)這類搜索所得步長因子 使即由于這類搜索是以取得最優步長為目的, 因此稱為最優一維搜索或精確一維搜索, 簡稱為一維搜索, 所得步長稱為最優步長。(2)可接受一維搜索(不精確一維搜索) 其特點:不是求精確的最優步長或其近似值, 而是按某一規則選取的步長, 使目標函數f從x(k)沿方向pk能取得可接受的下降量。 常見的一維搜索法還有多項式插值法中的二次插值法和三次插值法, 可接受搜索法