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

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

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

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

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

6、k, k+1=(tk+1) a=mint，tk+1b=maxt，tk+1結(jié)束NYNYk+1khk+1=hk,t=tk ,tk=tk+1 ,k=k+1,k=k+1k=0hk = hk ,k=k+1圖4.2由定義4.2易知，一個(gè)區(qū)間是某函數(shù)的單谷區(qū)間意味著，在該區(qū)間中函數(shù)只有一個(gè)“凹谷”（極小值）例如，圖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ū)間總是相應(yīng)問題（4.3）的一個(gè)搜索區(qū)間（如圖4

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

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

9、因?yàn)槊看蔚际乖瓍^(qū)間縮短一半，所以稱為對分法或二分法Y開始確定a，b，要求c=(a+b)/2b=ct*=(a+b)/2輸出t*結(jié)束t*=cNa=cNYNY圖4.64.3 Newton切線法一、Newton切線法基本原理設(shè)在已獲得的搜索區(qū)間內(nèi)具有連續(xù)二階導(dǎo)數(shù)，求因?yàn)樵谏峡晌ⅲ试谏嫌凶钚≈担钕旅娌环猎O(shè)在區(qū)間中經(jīng)過次迭代已求得方程的一個(gè)近似根過作曲線的切線，其方程是 （4.4）然后用這條切線與橫軸交點(diǎn)的橫坐標(biāo)作為根的新的近似（如圖4.7所示）它可由方程（4.4）在令的解出來，即這就是Newton切線法迭代公式圖4.7二、Newton切線法迭代步驟已知，表達(dá)式，終止限(1) 確定初始搜索區(qū)間，要

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

11、必須適當(dāng)在圖4.10（a）的情況下，曲線上凹，應(yīng)選點(diǎn)b作為初始點(diǎn)；而在圖4.10（b）的情況下，曲線下凹，應(yīng)選點(diǎn)a為初始點(diǎn)否則都可能失敗圖4.9圖4.8圖4.10 4.4 黃金分割法一、黃金分割法基本原理要介紹黃金分割法有必要回顧一下古老的黃金分割問題所謂黃金分割就是將一線段分為二段時(shí)，要求整段長L與較長段x的比值正好等于較長段x與較短段的比值（如圖4.11所示），即于是有，解出其正根由此可見長段的長度應(yīng)為全長的0.618倍，而短段的長度應(yīng)為全長的0.382倍因?yàn)楣糯娜藗冋J(rèn)為按0.618的比率來分割線段是最協(xié)調(diào)，勝似黃金，故稱之為黃金分割圖4.11用黃金分割法進(jìn)行一維搜索，其基本思想是在單谷

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

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

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

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