一維搜尋，又稱一維最佳化，是指求解一維目標函式 f(X) 最優解的過程。
基本介紹
- 中文名：一維搜尋
- 外文名：One-dimensional search
- 拼音：Yī wéi sōu suǒ
- 學科：運籌學
- 隸屬：非線性規劃
- 別稱：一維最佳化
內容介紹,搜尋區間,區間消去,方法,套用,
內容介紹
求解一維目標函式 f(X) 最優解的過程，稱為一維最佳化(一維搜尋)，所使用的方法稱為一維最佳化方法。
求某目標函式的最優值時，疊代過程每一步的格式都是從某一定點
出發，沿著某一使目標函式下降的規定方向
搜尋，以找出此方向的極小點
。這一過程是各種最最佳化方法的一種基本過程。
一維搜尋方法一般分兩步進行：
- 首先確定一個包含函式極小點的初始區間，即確定函式的搜尋區間，該區間必須是單峰區間；
- 然後採用縮小區間或插值逼近的方法得到最優步長，最終求出該搜尋區間內的一維極小點。
搜尋區間
根據函式的變化情況，可將區間分為單峰區間和多峰區間。所謂單峰區間，就是在該區間內的函式變化只有一個峰值，即函式的極小值。
目前在一維最佳化搜尋中確定單峰區間常用的方法是進退試算法。進退試算法的基本思想為：
- 按照一定的規律給出若干試算點；
- 依次比較各試算點的函式值的大小；
- 直到找到相鄰三點函式值按“高-低-高”變化的單峰區間為止。
區間消去
搜尋區間確定之後，採用區間消去法逐步縮短搜尋區間，找到極小點的數值近似解。
假定在搜尋區間內[a，b] 任取兩點
、
，且
，
。
1.若
，新區間為
；
2.若
，新區間為
；
3.若
，新區間為 。
對於上述縮短後的新區間，可在其內再取一個新點，然後將此點和該區間內剩下的那一點進行函式值大小的比較，以再次按照上述方法，進一步縮短區間，這樣不斷進行下去，直到所保留的區間縮小到給定的誤差範圍內，而得到近似最優解。
方法
斐波那契法：在區間[a，b]內取兩個不同點，並算出它們的函式值加以比較，就可以把搜尋區間[a，b]縮小成 或 (縮小後的區間仍需包含極小點)。現在如果要繼續縮小搜尋區間 (或 )，就只需在上述區間內再取一點算出其函式值，並與
或
加以比較即可。
黃金分割法：適用於[a，b]區間上的任何單谷函式求極小值問題。對函式除要求“單峰”外不作其他要求，甚至可以不連續。適應面相當廣。黃金分割法還要求在保留下來的區間內再插入一點所形成的區間新三段，與原來區間的三段具有相同的比例分布。
黃金分割法插入兩點的計算公式如下：
這個方法可以看成是斐波那契法的近似，實現起來比較容易，效果也相當好，因而易於為人們所接受。
牛頓法：把非線性函式
在
處展開成泰勒級數，取其線性部分，作為非線性方程的近似方程如下：
可得
，依此類推可得牛頓疊代公式：
。
在 處用一拋物線
代替曲線
，相當於用一斜直線
代替曲線
。這樣各個近似點是通過對作 切線求得與軸的交點找到的，所以有時牛頓法又稱作切線法。牛頓法收斂速度快，但牛頓法要求初始點離極小點不太遠，否則可能使極小化序列發散或收斂到非極小點。
