1、第四章 一維搜索法由第一章關于求解最優化問題概述中我們知道，從已知迭代點出發按照基本迭代公式來求解最優化問題，其關鍵在于如何構造一個搜索方向和確定一個步長，使下一迭代點處的目標函數值下降，即現在我們來討論，當搜索方向已經確定的情況下，如何來確定步長？步長因子的選取有多種方法，如取步長為常數，但這樣選取的步長并不最好，如何選取最好步長呢？實際計算通常采用一維搜索來確定最優步長對無約束最優化問題，當已知迭代點和下降方向時，要確定適當的步長使比有所下降，即相當于對于參變量的函數要在區間上選取使，即由于這種從已知點出發，沿某一下降的探索方向來確定步長的問題，實質上是單變量函數關于變量的一維搜索選取問題

2、，故通常叫做一維搜索按這種方法確定的步長又稱為最優步長，這種方法的優點是，它使目標函數值在搜索方向上下降得最多今后為了簡便起見，我們用記號（4.1）表示從點出發沿方向對目標函數作直線搜索所得到的極小點是其中和分別是Linear search（直線搜索）兩詞的詞首在目標函數已確定的條件下（4.1）等價于如下兩式：下面進一步解釋迭代點的空間位置容易證明，若從出發，沿方向進行一維搜索得極小點，則該點處的梯度方向與搜索方向之間應滿足 (4.2)事實上，設，對求導有圖4.1令，即，所以式（4.2）的幾何意義是明顯的從某一點出發沿方向對目標函數作直線搜索，所得到的極小點為式（4.2）指出，梯度必與搜索方向

3、正交又因為與目標函數過點的等值面正交，所以進一步看到，搜索方向與這個等值面在點處相切（如圖4.1所示）4.1 搜索區間及其確定方法一、搜索區間設一維最優化問題為 （4.3）為了求解問題（4.3），我們引入如下的搜索區間概念定義4.1 設，并且，若存在閉區間使，則稱是問題（4.3）的搜索區間簡言之，一個一維最優化問題的搜索區間，就是包含該問題最優解的一個閉區間通常，在進行一維搜索時，一般要先確定出問題的一個搜索區間，然后在此區間中進行搜索求解二、加步探索法下面，介紹一個確定問題(4.3)的搜索區間的簡單方法這個方法的思想是：先選定一個初始點和初始步長然后，沿著軸的正方向探索前進一個步長，得到新點

4、若目標函數在新點處的值是下降了，即，則下一步就從新點出發加大步長，再向前探索若目標函數在新點處的 函數值上升，即，則下一步仍以為出發點以原步長開始向軸的負方向同樣探索當達到目標函數上升的點時，就停止探索，這時便得到問題（4.3）的一個搜索區間這種以加大步長進行探索來尋找探索區間的方法叫做加步探索法加步探索法算法的計算步驟：(1) 選取初始數據選取初始點，計算給出初始步長，加步系數，令(2) 比較目標函數值令，計算，若，轉(3)否則轉(4)(3)加大探索步長令，同時，令，轉(2)（4） 反向探索若，轉換探索方向，令，轉（2）否則，停止迭代，令輸出加步探索法算法的流程圖如圖4.2所示。在加步探索法

5、中，一般建議若能估計問題（4.3）的最優解的大體位置的話，初始點要盡量取接近于問題（4.3）的最優解在具體運用上述加步探索法時，有時還要考慮一些細節問題例如，當探索得到新點處的目標函數值和出發點處相同時，以及初始步長應如何選取等，都需作適當處理三、單谷區間與單谷函數由于以后要介紹的一些維搜索方法，主要適用于問題（4.3）在搜索區間中只有唯一的最優解的情況，為此，我們再給出下面單谷區間與單谷函數概念定義4.2 設，閉區間若存在點，使得在上嚴格遞減，在上嚴格遞增，則稱是函數的單谷區間，是上單谷函數開始選取初始點t0，初始步長h00，加步系數1，令k=00=(t0)，比較目標函數值tk+1=tk+h

6、k, k+1=(tk+1) a=mint，tk+1b=maxt，tk+1結束NYNYk+1khk+1=hk,t=tk ,tk=tk+1 ,k=k+1,k=k+1k=0hk = hk ,k=k+1圖4.2由定義4.2易知，一個區間是某函數的單谷區間意味著，在該區間中函數只有一個“凹谷”（極小值）例如，圖4.3中的是的單谷區間，也即是上的單谷函數圖4.4中的不是的單谷區間，即不是上的單谷函數另外，從定義4.2還可知，某區間上的單谷函數在該區間上不一定是連續函數，而凸函數在所給區間上必然是單谷函數（如圖4.3所示）由定義4.1和定義4.2知，函數的單谷區間總是相應問題（4.3）的一個搜索區間（如圖4

7、.3所示），但反之不然（如圖4.4所示）圖4.3 圖4.4單谷區間和單谷函數有如下有用的性質：定理4.1 設是的單谷區間，任取并且（1）若有，則是的單谷區間（2）若有，則是的單谷區間證明略定理4.1說明，經過函數值的比較可以把單谷區間縮短為一個較小的單谷區間換句話說，利用這個定理可以把搜索區間無限縮小，從而求出極小點以下介紹的幾種，一維搜索方法都是利用這個定理通過不斷地縮短搜索區間的長度，來求得一維最優化問題的近似最優解4.2 對分法一、對分法基本原理求解一維最優化問題一般可先確定它的一個有限搜索區間，把問題化為求解問題，然后通過不斷縮短區間的長度，最后求得最優解設在已獲得的搜索區間內具有連續

8、的一階導數因為在上可微，故在上連續，由此知在上有最小值令，總可求得極小點不妨設在上是單減函數；在上是單增函數所以時，故；當時，亦即對分法的原理如圖4.5所示圖4.5二、對分法迭代步驟已知，表達式，終止限(1) 確定初始搜索區間，要求(2) 計算的中點(3) 若，則，轉(4)；若，則，轉(5)；若，則，轉(4)(4) 若，則，轉(5)；否則轉(2)(5) 打印，結束對分法的計算流程如圖4.6所示三、對分法有關說明對分法每次迭代都取區間的中點若這點的導數值小于零，說明的根位于右半區間中（如圖4.5所示），因此去掉左半區間；若中點導數值大于零，則去掉右半區間；若中點導數值正好等于零，則該點就是極小點

9、因為每次迭代都使原區間縮短一半，所以稱為對分法或二分法Y開始確定a，b，要求c=(a+b)/2b=ct*=(a+b)/2輸出t*結束t*=cNa=cNYNY圖4.64.3 Newton切線法一、Newton切線法基本原理設在已獲得的搜索區間內具有連續二階導數，求因為在上可微，故在上有最小值，令下面不妨設在區間中經過次迭代已求得方程的一個近似根過作曲線的切線，其方程是 （4.4）然后用這條切線與橫軸交點的橫坐標作為根的新的近似（如圖4.7所示）它可由方程（4.4）在令的解出來，即這就是Newton切線法迭代公式圖4.7二、Newton切線法迭代步驟已知，表達式，終止限(1) 確定初始搜索區間，要

10、求(2) 選定(3) 計算(4) 若，則，轉（3）；否則轉（5）(5) 打印，結束Newton切線法的計算流程如圖4.8所示三、Newton切線法有關說明這種方法如果初始點選得適當，收斂速度很快，通常經過幾次迭代就可以得到滿足一般精度要求的結果，但是它也有缺點第一，需要求二階導數如果在多維最優化問題的一維搜索中使用這種方法，就要涉及Hesse矩陣，一般是難于求出的第二，當曲線在上有較復雜的彎曲時，這種方法 輸出開始結束YN選定t0,確定a b,要求也往往失效如圖4.9所示的迭代：，結果跳出迭代或者發散，或者找到的根并不是我們想要的結果第三，即使曲線比較正常，在中或者上凹或者下凹，初始點的選取也

11、必須適當在圖4.10（a）的情況下，曲線上凹，應選點b作為初始點；而在圖4.10（b）的情況下，曲線下凹，應選點a為初始點否則都可能失敗圖4.9圖4.8圖4.10 4.4 黃金分割法一、黃金分割法基本原理要介紹黃金分割法有必要回顧一下古老的黃金分割問題所謂黃金分割就是將一線段分為二段時，要求整段長L與較長段x的比值正好等于較長段x與較短段的比值（如圖4.11所示），即于是有，解出其正根由此可見長段的長度應為全長的0.618倍，而短段的長度應為全長的0.382倍因為古代的人們認為按0.618的比率來分割線段是最協調，勝似黃金，故稱之為黃金分割圖4.11用黃金分割法進行一維搜索，其基本思想是在單谷

12、區間內適當插入兩點，由此把區間分為三段，然后再通過比較這兩點函數值大小，就可以確定是刪去最左段還是最右段，或者同時刪去左右兩段保留中間段如此繼續下去可將單谷區間無限縮小 二、黃金分割法迭代步驟現在提出一個問題，就在上如何選取二點使得迭代次數最小而區間縮短最快？要解決這個問題，人們想到對區間選二點等價于將區間長度進行黃金分割，也就是將第一個搜索點取在的0.618處，第二個搜索點取成的對稱點即的0.382處（如圖4.12所示），亦即，計算與的值，并根據與的值的大小關系分情況討論：（1） 若，說明是好點，于是把區間劃掉，保留，則內有一保留點，置新的區間；（2）若，說明是好點，于是應將劃掉，保留，則內

13、有保留點，置新的區間圖4.12（3）若，則應具體分析，看極小點可能在哪一邊再決定取舍在一般情況下，可同時劃掉和，僅保留中間的，置新的區間 接下來是在留下的區間內找好點重復上面的步驟，直到搜索區間小于給定的允許誤差為止這樣就得到黃金分割法迭代算法：已知，常數0.382，終止限(1)確定的初始搜索區間(2)計算(3)計算(4) 若，則打印，結束；否則轉(5)(5) 判別是否滿足：若滿足，則置， 然后轉(3)；否則，置，然后轉(4)黃金分割法算法流程如圖4.13所示三、黃金分割法有關說明黃金分割法是通過所選試點的函數值而逐步縮短單谷區間來搜索最優點該方法適用于單谷區間上的任何函數，甚至可以是不連續函

14、數，因此這種算法屬于直接法，適用相當廣泛開始確定a,b 結束NYNY圖4.134.5 拋物線插值法一、拋物線插值法基本原理考慮一維搜索問題，假設其中是定義在區間上的單谷函數首先用試探法在上找一點，使之滿足通過目標函數曲線上的三個點，作它的二次擬合曲線（如圖4.14所示）圖4.14由于上述三個點既是目標函數曲線上的點，又是二次擬合曲線上的點，故有方程組 （4.5）將方程組（4.5）中的消去，得 （4.6）從方程組（4.6）可解出待定系數，（4.7）（4.8）對于二次擬合函數，我們很容易求得它的極小值點令，即，從中解出（4.9）即為二次擬合函數的極小值點將式（4.7）與式（4.8）代入式（4.9）

15、得 （4.10）用區間上二次擬合函數的這個極小值點作為目標函數在該區間極小值點的一個估計值若和已充分接近，即對給定的允許誤差使（4.11）成立時，就可被看作是在區間內近似最優解；否則應縮短區間，按照值保持兩頭大、中間小的原則構成新的三點，繼續上述過程，直至不等式（4.11）成立為止二、拋物線插值法迭代步驟下面具體介紹一下縮短區間，構成新三點的方法由式（4.15）得到的點，在區間內既可能在點的左側（即），又可能在的右側（即），分別對應這兩種情形比較和的大小，又有，及等三種情形，故共有如下六種情況（如圖4.15與圖4.16所示）： （1）對于圖4.15（a）的情況：因，所以相對來說是好點，故劃掉區間，保留為新區間，故置，保持不變；（2）對于圖4.15（b）的情況：因，所以相對來說是好點，故劃掉，保留為新區間，故置，與保持不變；（3）對于圖4.15（c）的情況：因，所以相對來說是好點， 圖4.15 圖4.16故劃掉，保留為新區間，故置，保持不變； （4）