第三章一維搜索

1、3.13.23.33.4重點q回顧 當采用數(shù)學規(guī)劃法尋求多元函數(shù) 的極值點 時一般要進行一系列迭代計算： 其中 為第 次迭代的搜索方向， 為沿 搜索的最佳步長因子（通常也稱作最佳步長）。 當方向 給定，求最佳步長 就是求一元函數(shù) 的極值問題，它稱作一維搜索。q 求多元函數(shù)極值點，需要進行一系列的一維搜索。可見一維搜索是優(yōu)化搜索方法的基礎。q 求解一元函數(shù) 的極小點 ，可采用解析解法，在用函數(shù) 的導數(shù)求 時，所用的函數(shù) 是僅以步長因子 為變量的一元函數(shù)，而不是以設計點 為變量的多元函數(shù) 。 利用一元函數(shù)的極值條件 求 。 為了直接利用 的函數(shù)式求解最佳步長因子 ?？砂?或它的簡寫形式 進行泰勒展

2、開，取到二階項，即 將上式對 進行微分并令其等于零，給出 極值點 應滿足的條件 從而求得這里是直接利用函數(shù) 而不需要把它化成步長因子 。的函數(shù) 。不過，此時需要計算 點處的梯度 和海賽矩陣 。 解析解法的缺點需要進行求導計算。對于函數(shù)關系復雜、求導困難或無法求導的情況，使用解析法將是非常不便的。q因此，在優(yōu)化設計中，求解最佳步長因子 主要采用數(shù)值解法，利用計算機通過反復迭代計算求得最佳步長因子的近似值。 數(shù)值解法的基本思路是：首先確定 所在的搜索區(qū)間，然后根據(jù)區(qū)間消去法原理不斷縮小此區(qū)間，從而獲得 的數(shù)值近似解。q 欲求一元函數(shù) 的極小點 ，首先必須先確定 所在的區(qū)間。確定搜索區(qū)間的外推法在一

3、維搜索時，我們假設函數(shù) 具有如右圖所示的單谷性，即在所考慮的區(qū)間內部，函數(shù) 有唯一的極小點 。為了確定極小點 所在的區(qū)間 ，應使函數(shù) 的 值在 區(qū)間里形成“高低高”趨勢。從 開始，以初始步長 向前試探。如果函數(shù)值上升，則步長變號，即改變試探方向。如果函數(shù)值下降，則維持原來的試探方向，并將步長加倍。區(qū)間的始點、中間點依次沿試探方向移動一步。此過程一直進行到函數(shù)值再次上升時為止，即可找到搜索區(qū)間的終點。最后得到的三點即為搜索區(qū)間的始點、中間三點和終點，形成函數(shù)值的“高低高”趨勢。單谷區(qū)間q外推法（進退法）確定搜索區(qū)間的步驟：q 1）試探搜索q 2）前進搜索q 3）后退搜索右圖表示沿 的正向試探。每

4、走一步都將區(qū)間的始點、中間點沿試探方向移動一步（進行換名）。經(jīng)過三步最后確定搜索區(qū)間 ，并且得到區(qū)間始點、中間點和終點 所對應的函數(shù)值 。正向搜索的外推法右圖所表示的情況是：開始是沿 的正方向試探，但由于函數(shù)值上升而改變了試探方向，最后得到始點，中間點和終點 及它們的對應函數(shù)值 ，從而形成單谷區(qū)間為一維搜索區(qū)間 。上述確定搜索區(qū)間的外推法，其程序框圖如下圖所示（P50）q 要求一元函數(shù) 的極小點 ，在確定 所在的區(qū)間之后，就需要不斷的縮小這個區(qū)間，直到確定 的近似解。區(qū)間消去法原理在搜索區(qū)間 內任取兩點 ，并計算函數(shù)值 。于是將有下列三種可能情形： ，如下圖（a）所示。由于函數(shù)為單谷，所以極小

5、點必在區(qū)間 內。 ，如下圖（b）所示。同理，極小點應在區(qū)間 內。 ，如下圖（c）所示，這時極小點應在 內。 根據(jù)以上所述，只要在區(qū)間 內取兩個點，算出它們的函數(shù)值并加以比較，就可以把搜索區(qū)間 縮短成 或 。對于第一種情況，我們已算出區(qū)間 內 點的函數(shù)值，如果要把搜索區(qū)間 進一步縮短，只需在其內再取一點算出函數(shù)值并與 加以比較，即可達到目的。對于第二種情況，同樣只需再計算一點函數(shù)值就可以把搜索區(qū)間繼續(xù)縮短。 第三種情形與前面兩種情形不同，因為在區(qū)間 內缺少已算出的函數(shù)值。要想把區(qū)間 進一步縮短，需在其內部取兩個點（而不是一個點）計算出相應的函數(shù)值再加以比較才行。 如果經(jīng)常發(fā)生這種情形，為了縮短搜

6、索區(qū)間，需要多計算一倍數(shù)量的函數(shù)值，這就增加了計算工作量。程序設計技巧為了避免多計算函數(shù)值，我們把第三種情形合并到前面兩種情形中去。例如，可以把前面三種情形改為下列兩種情形：若 ，則取 為縮短后的搜索區(qū)間。若 ，則取 為縮短后的搜索區(qū)間。從上述的分析中可知，為了每次縮短區(qū)間，只需要在區(qū)間內再插入一點并計算其函數(shù)值。如此反復進行下去，當搜索區(qū)間長度足夠小時，可用區(qū)間內的某點作為極小點的近似值。q一維搜索方法的分類可以用不同的方法來確定的插入點的位置，這樣就形成了不同的一維搜索方法。概括起來，可將一維搜索方法分成兩大類： 試探法（直接法）按某種給定的規(guī)律來確定區(qū)間內插入點的位置。此點位置的確定僅僅

7、按照區(qū)間縮短如何加快，而不顧及函數(shù)值的分布關系。屬于試探法一維搜索的有黃金分割法，裴波納契（Fibonacci）法等。 插值法（函數(shù)逼近法、間接法）根據(jù)某些點處的某些信息，如函數(shù)值、一階導數(shù)、二階導數(shù)等，構造一個插值函數(shù)來逼近原來函數(shù)，用插值函數(shù)的極小點作為區(qū)間的插入點。屬于插值法一維搜索的有牛頓法（切線法）、二次插值法（拋物線法）、三次插值法等。以下我們分別討論這兩類一維搜索方法。q概述 在搜索區(qū)間 內適當插入兩點 ，并計算其函數(shù)值。 將區(qū)間分成三段。應用函數(shù)的單谷性質，通過函數(shù)值大小的比較，刪去其中一段，使搜索區(qū)間得以縮短。然后再在保留下來的區(qū)間上作同樣的處置，如此迭代下去，使搜索區(qū)間無限

8、縮小，從而得到極小點的數(shù)值近似解。 在實際計算中，最常用的一維搜索試探方法是黃金分割法，又稱作0.618法。我們可以通過學習黃金分割法來了解一維搜索試探方法的基本思想。q黃金分割法 黃金分割法是建立在區(qū)間消去法原理基礎上的試探方法。適用于 區(qū)間上的任何單谷函數(shù)求極小值問題。對函數(shù)除要求“單谷”外不作其它要求，甚至可以不連續(xù)。因此，這種方法的適應面相當廣。 黃金分割法對插入點的要求： 1）要求插入點 的位置相對于區(qū)間 兩端點具有對稱性，即 其中 為待定常數(shù)。2）黃金分割法還要求在保留下來的區(qū)間內再插入一點所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布。 即每次縮小所得的新區(qū)間長度與縮小前

9、區(qū)間長度之比（即：區(qū)間收縮率）為定值。設原區(qū)間 長度為1如下圖所示，保留下來的區(qū)間 長度為 ，區(qū)間縮短率為 。為了保持相同的比例分布，新插入點 應在 位置上， 在原區(qū)間的 位置應相當于在保留區(qū)間的 位置。故有 取方程正數(shù)解，得若保留下來的區(qū)間為 ，根據(jù)插入點的對稱性，也能推得同樣的 值。所謂“黃金分割”是指將一線段分成兩段的方法，使整段長與較長段的長度比值等于較長段與較短段長度的比值，即 算得 。黃金分割法能使相鄰兩次搜索區(qū)間都具有相同的縮短率0.618，所以黃金分割法又被稱作0.618法。黃金分割法的搜索過程 給出初始搜索區(qū)間 及收斂精度 ，將 賦以0.618。 按坐標點計算公式計算 和 ，

10、并計算其對應的函數(shù)值 。 根據(jù)區(qū)間消去法原理縮短搜索區(qū)間程序設計技巧 為了能用原來的坐標點計算公式，需進行區(qū)間名稱的代換，并在保留區(qū)間中計算一個新的試驗點及其函數(shù)值。 檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠近，如果條件不滿足則返回到步驟2。 如果條件滿足，則取最后兩試驗點的平均值作為極小點的數(shù)值近似解。黃金分割法的程序框圖如右圖所示（P52）。例子q概述 插值法和試探法都是利用區(qū)間消去法原理將初始搜索區(qū)間不斷縮短，從而求得極小點的數(shù)值近似解。 一維搜索問題是在某一確定區(qū)間內尋求一元函數(shù)的極小點的位置，在某些情況下，如果沒有函數(shù)表達式，但能夠給出若干試驗點處的函數(shù)值，就可以根據(jù)這些點處的函數(shù)

11、值，利用插值法建立函數(shù)的某種近似表達式，進而求出函數(shù)的極小點，并用它作為原來函數(shù)極小點的近似值。這種方法稱作插值法，又稱作函數(shù)逼近法。多項式是函數(shù)逼近的一種常用工具。在搜索區(qū)間內可以利用若干試驗點處的函數(shù)值來構造低次多項式，用它作為函數(shù)的近似表達式，并用這個多項式的極小點作為原函數(shù)極小點的近似。常用的插值多項式為二次多項式。 牛頓法（切線法） 利用一點的函數(shù)值、一階導數(shù)值和二階導數(shù)值來構造二次函數(shù)。 二次插值法（拋物線法） 利用三個點的函數(shù)值形成一個拋物線來構造二次函數(shù)。q牛頓法（切線法） 對于一維搜索函數(shù) ， 假定已給出極小點的一個較好的近似點 ，因為一個連續(xù)可微的函數(shù)在極小點附近與一個二次

12、函數(shù)很接近，所以可在 點附近用一個二次函數(shù) 來逼近函數(shù) ，即在 點將 進行泰勒展開并保留到二次項，有 然后以二次函數(shù) 的極小點作為 極小點的一個新近似點 。根據(jù)極值必要條件 ： 即 得 依此繼續(xù)下去，可得牛頓法迭代公式右圖是對牛頓法所作的幾何解釋 的極小點 應滿足極值必要條件 。所以求 的極小點也就是求解 方程的根。故在 處用一拋物線 代替曲線 相當于用一斜線 代替曲線 。拋物線頂點 作為第一個近似點應處于斜線 與 軸的交點處。這樣各個近似點是通過對 作切線求得與 軸的交點而找到的，所以牛頓法又稱作切線法。牛頓法的計算步驟是：給定初始點 ，控制誤差 ，并令 。 計算 。 求 。 若 則求得近似

13、解 ，停止計算，否則作4。 令 轉1。 牛頓法的特點 牛頓法最大的優(yōu)點是收斂速度快。 但是在每一點處都要計算函數(shù)的二階導數(shù)，因而增加了每次迭代的工作量。 特別是用數(shù)值微分代替二階導數(shù)時，舍人誤差會影響牛頓法的收斂速度。 另外，牛頓法要求初始點選得比較好（離極小點不能太遠），否則有可能使極小化序列發(fā)散或收斂到非極小點。q二次插值法（拋物線法） 二次插值法是利用 在單谷區(qū)間中的三點 的相應函數(shù)值 ，作出如下的二次插值多項式 則它應滿足條件 則多項式 的極值點可從極值的必要條件求得 為了確定這個極值點，只需計算出系數(shù) 和 。其方法法是利用 的聯(lián)立方程組中相鄰兩個方程消去 ，從而得到關于 的方程組 解

14、得 所以 如果令 則 這樣就得到了 極小點 的近似解 。 如果區(qū)間長度 足夠小，則由 便得出所要求的 的足夠精確的極小點 。如果區(qū)間長度 不是足夠小，則必須縮小區(qū)間 。根據(jù)區(qū)間消去法原理，需要已知區(qū)間內兩點的函數(shù)值。其中點 的函數(shù)值 已知，另外一點可取 點并計算其函數(shù)值 。當 時取 為縮短后的搜索區(qū)間（如右圖）。當 時取 為縮短后的搜索區(qū)間。在縮短后的新區(qū)間內再用二次插值法插人新的極小點近似值 （如右圖）。如此不斷進行下去，直到滿足迭代精度要求為止。 程序設計技巧為了在每次計算插入點的坐標時能應用同一計算公式，新區(qū)間端點的坐標及函數(shù)值名稱需換成原區(qū)間端點的坐標及函數(shù)值名稱。在每個新區(qū)間上仍取

15、三點及其相應函數(shù)值 。這樣當計算插入點（即拋物線極小點 ）位置時仍可以應用原來的計算公式。根據(jù) 與 的相對位置， 與 的大小以及正向搜索（ ）或反向搜索（ ）的不同，具體換名有如下表所示的八種情況。（P56)上表中的中的 就是在進行外推法時求初始搜索區(qū)間過程中所形成的最后步長， 可正可負，分別對應于沿 正向或反向進行的一維搜索。分析上述八種換名情況可知，如果乘積 的符號相同，那么正向搜索和反向搜索將采取同樣的換名方式，從而可將上述八種情況合并成四種情況，從而可將程序框圖簡化。二維插值法的程序框圖（P57）q插值法和試探法的比較 試探法中試驗點位置是由某種給定的規(guī)律確定的，它不考慮函數(shù)值的分布。例如，黃金分割法是按等比例0.618縮短率確定的。插值法中，試驗點位置是按函數(shù)值近似分布的極小點確定的。試探法僅僅利用了試驗點函數(shù)值大小的比較，而插值法還要利用函數(shù)值本身或者其導數(shù)信息。 試探法僅對試驗點函數(shù)值的大小進行比較，而函數(shù)值本身的特性沒有得到充分利用，這樣即使對一些簡單的函數(shù)，例如二次函數(shù)，也不得不象一般函數(shù)那樣進行同樣多的函數(shù)值計算。插值法是利用