常用一維搜索算法

1、常用一維搜索算法無約束優(yōu)化：不對定義域或值域做任何限制的情況下，求解目標函數(shù)的最小值。這是因為實際應用中，許多情形被抽象為函數(shù)形式后均為凸函數(shù)，對于凸函數(shù)來說局部最小值點即為全局最小值點，因此只要能求得這類函數(shù)的一個最小值點，該點一定為全局最小值。（直接法：又稱數(shù)值方法，它只需計算目標函數(shù)駐點的函數(shù)數(shù)值，而不是求其倒數(shù)，如坐標輪換法，單純型法等。間接法：又稱解析法，是應用數(shù)學極值理論的解析方法。首先計算出目標函數(shù)的一階或一階、二階導數(shù)，然后根據(jù)梯度及海賽矩陣提供的信息，構(gòu)造何種算法，從而間接地求出目標函數(shù)的最優(yōu)解，如牛頓法、最速下降法共軛梯度法及變尺度法。）在優(yōu)化算法中保證整體收斂的重要方法就

2、是線搜索法與信賴域法,這兩種算法既相似又有所不同。根據(jù)不同的線搜索準則就延伸出不同的線搜索算法,譬如比較常見和經(jīng)典的最速下降法,牛頓法,擬牛頓法以及共輒梯度法等。一維搜索又稱線性搜索(Line Search),就是指單變量函數(shù)的最優(yōu)化,它是多變量函數(shù)最優(yōu)化的基礎,是求解無約束非線性規(guī)劃問題的基本方法之一。一維搜索技術既可獨立的用于求解單變量最優(yōu)化問題,同時又是求解多變量最優(yōu)化問題常用的手段,雖然求解單變量最優(yōu)化問題相對比較簡單,但其中也貫穿了求解最優(yōu)化問題的基本思想。由于一維搜索的使用頻率較高,因此努力提高求解單變量問題算法的計算效率具有重要的實際意義。 在多變量函數(shù)的最優(yōu)化中,迭代格式Xk+

3、1=Xk+akdk其關鍵就是構(gòu)造搜索方向dk和步長因子ak設(a)=f(xk+adk)這樣從凡出發(fā),沿搜索方向dk,確定步長因子ak,使(a)0)則稱這樣的一維搜索為最優(yōu)一維搜索,或精確一維搜索,ak叫最優(yōu)步長因子;如果選取ak使目標函數(shù)f得到可接受的下降量,即使得下降量f (xk)一f (xk+akdk)0是用戶可接受的,則稱這樣的一維搜索為近似一維搜索,或不精確一維搜索,或可接受一維搜索。由于在實際計算中,一般做不到精確的一維搜索,實際上也沒有必要做到這一點,因為精確的一維搜索需要付出較高的代價,而對加速收斂作用不大,因此花費計算量較少的不精確一維搜索方法受到了廣泛的重視和歡迎。精確一維搜

4、索,作為一種理想的狀態(tài),雖然在實際計算中被采用的概率較之不精確一維搜索要小,但有關精確一維搜索技術的研究歷史悠久成果相當豐富,方法眾多,其理論體系也相對比較完備,對其進行進一步的研究仍有著重要的理論意義和現(xiàn)實意義。通常我們根據(jù)算法中有無使用導數(shù)的情況,將精確一維搜索算法分為兩大類:一類是不用函數(shù)導數(shù)的方法,這其中就包括二分法(又稱作對分法或中點法)、法(黃金分割腳、Fibonacci法(分數(shù)法)、割線法、成功一失敗法等;另一類是使用函數(shù)導數(shù)的方法,包括經(jīng)典的Newton法、拋物線法以及各種插值類方法等。（1）在不用導數(shù)的方法中,二分法、法(黃金分割法)以及Fibonacci法均是分割方法,其基

5、本思想就是通過取試探點和進行函數(shù)值比較,使包含極小點的搜索區(qū)間不斷縮短,當區(qū)間長度縮短到一定程度時,區(qū)間上各點的函數(shù)值均接近函數(shù)的極小值,從而各點均可看作極小點的近似。分割類方法僅需計算函數(shù)值,因此使用的范圍較廣,尤其適用于非光滑及導數(shù)表達式復雜或?qū)懖怀龅惹樾?。二分法是一種最簡單的分割方法,每次迭代都將搜索區(qū)間縮短一半,故二分法的收斂速度是線性的,收斂比為,收斂速度較慢。其優(yōu)勢就是每一步迭代的計算量都相對較小,程序簡單,而且總能收斂到一個局部極小點。黃金分割法是一種針對目標函數(shù)是單峰函數(shù)亦即目標函數(shù)為凸的情形的分割類方法,因其不要求函數(shù)可微,且每次迭代只需計算一個函數(shù)值,程序簡單容易實現(xiàn)而被廣

6、泛采用。由于黃金分割法是以等比例=分割縮小區(qū)間的,因此它是一種近似最優(yōu)方法。針對在實際中遇到的目標函數(shù)往往不是單峰函數(shù)的情況,HPonfiger(1976)提出了.0618法的改進形式,即在縮小區(qū)間時,不只是比較兩個內(nèi)點處的函數(shù)值,而是對兩內(nèi)點及其兩端點處的函數(shù)值進行綜合比較,以避免搜索得到的函數(shù)值反而比初始區(qū)間端點處的函數(shù)值大的情況。經(jīng)過這樣的修改,算法比.0618法要更加可靠。Fibonacci法是另一種與.0618法相類似的分割類方法,兩者的主要區(qū)別在于Fibonacci法搜索區(qū)間的縮短比率不是采用黃金分割數(shù),而是采用Fibonacci數(shù)列。在使用Fibonacci法時,通常是由用戶給定

7、最終區(qū)間長度的上限,從而確定探索點的個數(shù),逐步進行搜索。通過對Fibonacci數(shù)列進行分析表明,在迭代次數(shù)n趨于無窮的情形。Fibonacci法與.0618法的區(qū)間縮短率相同,因而Fibonacci法的收斂速度也是線性的,收斂比也是黃金分割數(shù)?？梢宰C明,Fibonacci法是分割方法求解一維極小化問題的最優(yōu)策略,而法只是近似最優(yōu)的,但因法不必預先知道探索點的個數(shù),程序?qū)崿F(xiàn)更加容易,因而應用也更加廣泛。拋物線法也可稱作三點二次插值法,其基本思想與下面要敘述的牛頓法相同,也是用二次函數(shù)近似目標函數(shù),并以其極小點去近似目標函數(shù)的極小點,不同之處是牛頓法是利用目標函數(shù)fx()在x0處的二階Tyalo

8、r展式來逼近f(x),而拋物線法則是利用目標函數(shù)fx()在三個點x0,xl,xZ處的函數(shù)值構(gòu)造一個二次函數(shù)作為其近似。一般地,拋物線法并不能保證算法一定收斂,在迭代過程中有可能會出現(xiàn)相鄰迭代點xk，xk+1充分接近且xk+1并非函數(shù)近似極小點的退化情況。但在己知迭代點列收斂到目標函數(shù)極小點的情況,可以證明:在一定的條件下,拋物線法是超線性收斂的,收斂的階約為。割線法與分割法類似,也是通過取試探點和進行函數(shù)值比較,使包含所求點的搜索區(qū)間縮小,但試探點的取法與分割法不同,它是選取連接兩個端點的線段與橫軸的交點作為試探點。割線法不能保證每次都使搜索區(qū)間縮小一定的比例,因而不具有全局線性收斂性,但是它

9、卻利用了函數(shù)的一些性質(zhì)。在函數(shù)接近線性時,它是非?？斓摹Ｈ绻瘮?shù)本身是線性函數(shù)時,它可以一步找到解。(ii)一般地,使用導數(shù)的方法通常包括牛頓法、插值法等,其中插值法又有一點二次插值法(牛頓法)、二點二次插值法)、三點二次插值法以及三次插值法、有理插植法等常用方法。求一維無約束極小化問題的牛頓法是從計算方法中方程求根的牛頓法演化而來的,其基本思想是用目標函數(shù)f (x)在己知點x0處的二階Tylor展式g (x)來近似代替目標函數(shù),用g (x)的極小點作為f (x)的近似極小點,迭代公式是xk+1=xk=f(xk)f(xk)牛頓法的優(yōu)點是收斂速度快,具有局部二階收斂速度;缺點是要在每個迭代點處計

10、算函數(shù)的二階導數(shù)值,增加了每次迭代的工作量,而且它要求迭代初始點要選的好,也就是說初始點不能離極小值太遠,在極小點未知的情況下,做到這一點是很困難的,這就限制了算法的應用范圍,導致算法不實用。事實上,牛頓法也是插值類方法的一種。插值法是一類重要的一維搜索方法,其基本思想是在搜索區(qū)間內(nèi)不斷用低次(通常不超過三次)多項式來逼近目標函數(shù),并用插值多項式的極小點去近似目標函數(shù)的極小點。實踐表明,在目標函數(shù)具有較好的解析性質(zhì)時,插值方法比直接方法(如.0618或Fibonacci法)效果更好。所謂不精確一維搜索方法是指應用各種可接受的步長選擇律的線性搜索方法。常用的不精確一維搜索算法包括利用簡單準則的后

11、退方法、經(jīng)典的Armijo-Goldstein方法、Wolfe-Powell方法和強Wolfe-Powell方法、以及其后發(fā)展起來的利用Curry-Altman步長律、改進的Curry-Altman步長律、Danilin-Pshenichuyi步長律、De Leone-Grippo步長律、Backtracking步長律等的各種方法（P19-24）方法 特點可靠性有效性簡便性備注程度特點程度特點程度特點問題大小直接法坐標輪換法中對背脊穩(wěn)問題舍入誤差低不具有收斂性高程序簡單，內(nèi)存少n10鮑威爾法高Si(k)有較高的共軛程度高近似二次收斂性中程序較繁，內(nèi)存量較大n1020間接法梯度法中舍入誤差低不具有二次收斂性高結(jié)構(gòu)簡單，內(nèi)存少低維牛頓法低函數(shù)二次性要求嚴高具有二次收斂性低程序復雜，內(nèi)存大低維變尺度法高對函數(shù)要求低高高二次收斂性中程序較繁，內(nèi)存