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

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