《線搜索準(zhǔn)則分析綜述》2300字

線搜索準(zhǔn)則分析綜述在完成下降方向的確定后，需要通過線搜索過程以選取步長。線搜索方法設(shè)計的優(yōu)劣在很大程度上會對算法的性能產(chǎn)生直接影響?？梢栽O(shè)想，最為理想的線搜索結(jié)果應(yīng)是選取出能夠使下一迭代值在既定的下降方向上最小化的步長，即可表示為：α實現(xiàn)了上述思想的算法被稱為精確線搜索方法。盡管能達(dá)到最速下降的理想目的，但它在每次迭代時均須完成一次最小值問題的求解，這將帶來及其繁重的計算量進(jìn)而大大提升了問題的計算難度，在實際計算中很少被采用。也正因此非精確線搜索的研究受到了優(yōu)化學(xué)者們廣泛的重視與討論。常用的非精確線搜索規(guī)則有如下幾種：Armijo線搜索準(zhǔn)則：引入?yún)?shù)δ,σ∈0,1,s>0。令αk=sσ? fxk+Wolfe線搜索準(zhǔn)則：引入?yún)?shù)0<δ<σ<1。選擇 fxGoldstein線搜索準(zhǔn)則：引入?yún)?shù)σ∈(0,1/2)。選擇能夠滿足式（1.2.3）的 σ≤fx上述列舉的三類非精確線搜索準(zhǔn)則在產(chǎn)生迭代步長時，均會受到常數(shù)參數(shù)σ,δ,s的影響，因此在實際應(yīng)用時需要對參數(shù)選擇進(jìn)行審慎的考慮。以上三種線搜索準(zhǔn)則具有一個共同特性，其產(chǎn)生的迭代值是單調(diào)下降的，即滿足：f因此我們稱這樣的線搜索方法為單調(diào)線搜索方法。盡管它們能在局部迭代時獲得令人滿意的下降，但在處理某些目標(biāo)函數(shù)非線性程度較高，在可行域中存在狹長的彎曲谷底的無約束優(yōu)化問題時，這種目標(biāo)函數(shù)的迭代值嚴(yán)格下降的性質(zhì)將會極大地降低搜索算法的收斂速度——一旦函數(shù)迭代進(jìn)入了狹長的彎曲峽谷，就只能被迫沿著谷底緩慢前進(jìn)。在此過程中相鄰迭代點之間的前進(jìn)距離將極為微小，甚至可能出現(xiàn)鋸齒現(xiàn)象使得算法陷入低效困境中。為了解決此類單調(diào)線搜索方法的局限性，Grippo、Lampariello和Lucidi在1986年首次提出了非單調(diào)線搜索方法。非單調(diào)線搜索方法的核心思想在于它并不要求迭代過程中產(chǎn)生的迭代值始終下降，而是在保證算法的全局收斂性的前提下，通過給出一些更為寬容的迭代條件，以期提高找到最優(yōu)解的可能性及算法收斂速率。在某些應(yīng)用單調(diào)線搜索方法會出現(xiàn)迭代點被迫沿著狹長谷底緩慢爬行情形的問題中，它可以有效地提高算法的收斂速度，避免無意義的重復(fù)迭代。數(shù)值試驗的結(jié)果表明非單調(diào)線搜索方法在解決一些困難的非線性問題時能夠表現(xiàn)出良好的數(shù)值效果，也正因此成為了數(shù)值優(yōu)化領(lǐng)域經(jīng)久不衰的研究熱點之一。Grippo、Lampariello和Lucidi以Armijo線搜索方法為基礎(chǔ)，在此之上實施改良，最早提出了一類關(guān)于牛頓法的非單調(diào)線搜索方法框架。該方法可以概述為：引入?yún)?shù)λ1,λ2,σ,δ，滿足0<λ1<λ2<1fxk+其中，gk是目標(biāo)函數(shù)在第k次迭代點xk處的梯度，“內(nèi)存”mk顯然當(dāng)M=0時，該非單調(diào)線搜索方法將退化為Armijo線搜索方法。Grippo、Lampariello和Lucidi在此后的研究中進(jìn)一步證明，當(dāng)目標(biāo)函數(shù)存在下界且下降方向ppkT嵌入了該非單調(diào)框架的牛頓類算法具有全局收斂性。式（1.2.4）中引入的最大值函數(shù)使得下一迭代點的選擇與生成將不再僅依賴上一相鄰迭代點，而是由內(nèi)存中相鄰一組迭代點共同決定。該設(shè)計旨在增強(qiáng)算法的全局性，能夠避免陷入迭代過程在局部徘徊不前的困境，顯著提高了算法收斂速度。此后眾多學(xué)者展開了對于該非單調(diào)線搜索框架的研究，試圖將其與各類不同的優(yōu)化算法相整合以期提高算法的整體性能，并對其在不同條件下的收斂性質(zhì)進(jìn)行了更為深入、廣泛的探討。例如，Zhou和Tits將該非單調(diào)線搜索框架延伸至極小化極大問題，并證明該框架能有效克服Maratos效應(yīng)；Raydn首次實現(xiàn)其與Barazilai-Borwein梯度法的交叉結(jié)合，在較弱的條件下證明了該新型Barazilai-Borwein梯度法的全局收斂性；Birgin、Martinez和Raydan應(yīng)用該非單調(diào)線搜索作為步長策略，對經(jīng)典的投影梯度法做出更新與擴(kuò)展。值得一提的是，他們創(chuàng)新性地設(shè)計出一種非單調(diào)線搜索步長策略與譜步長選擇策略的結(jié)合方案，成功實現(xiàn)了收斂過程的加速。此外，對于該非單調(diào)線搜索框架本身的改良亦是學(xué)者們不懈努力的研究方向——Han和Liu提出了一種非單調(diào)Wolfe線搜索方法，并給出了在凸優(yōu)化問題中，結(jié)合該框架的BFGS算法在一定條件下具有良好的全局收斂性的證明。該方法核心思想即在于用Wolfe線搜索準(zhǔn)則替換框架中的Armijo準(zhǔn)則，其步長需滿足式（1.2.6）及（1.2.7）fx?f其中δ∈(0,1)，σ∈(0,1/2)，p∈(?∞,1)盡管該非單調(diào)線搜索框架與多類優(yōu)化方法的結(jié)合算法在眾多數(shù)值案例中均表現(xiàn)出良好的計算性能，其仍然存在不可忽視的缺點。首先，最大值函數(shù)的引入使得過程中所產(chǎn)生的任一理想函數(shù)值在經(jīng)歷足夠多次迭代后基本上都會被丟棄。其次，在某些情況下，該方法的數(shù)值性能十分依賴于固定上界M的選擇。此外，Dai指出在目標(biāo)函數(shù)f為一致凸