第四章一維搜索法

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

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

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

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

5、中，一般建議若能估計問題（4.3）的最優(yōu)解的大體位置的話，初始點要盡量取接近于問題（4.3）的最優(yōu)解在具體運用上述加步探索法時，有時還要考慮一些細節(jié)問題例如，當探索得到新點處的目標函數(shù)值和出發(fā)點處相同時，以及初始步長應如何選取等，都需作適當處理三、單谷區(qū)間與單谷函數(shù)由于以后要介紹的一些維搜索方法，主要適用于問題（4.3）在搜索區(qū)間中只有唯一的最優(yōu)解的情況，為此，我們再給出下面單谷區(qū)間與單谷函數(shù)概念定義4.2 設，閉區(qū)間若存在點，使得在上嚴格遞減，在上嚴格遞增，則稱是函數(shù)的單谷區(qū)間，是上單谷函數(shù)開始選取初始點t0，初始步長h00，加步系數(shù)1，令k=00=(t0)，比較目標函數(shù)值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易知，一個區(qū)間是某函數(shù)的單谷區(qū)間意味著，在該區(qū)間中函數(shù)只有一個“凹谷”（極小值）例如，圖4.3中的是的單谷區(qū)間，也即是上的單谷函數(shù)圖4.4中的不是的單谷區(qū)間，即不是上的單谷函數(shù)另外，從定義4.2還可知，某區(qū)間上的單谷函數(shù)在該區(qū)間上不一定是連續(xù)函數(shù)，而凸函數(shù)在所給區(qū)間上必然是單谷函數(shù)（如圖4.3所示）由定義4.1和定義4.2知，函數(shù)的單谷區(qū)間總是相應問題（4.3）的一個搜索區(qū)間（如圖4

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

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

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

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

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的比率來分割線段是最協(xié)調(diào)，勝似黃金，故稱之為黃金分割圖4.11用黃金分割法進行一維搜索，其基本思想是在單谷

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

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

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

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