基于平均值的非單調(diào)線搜索方法綜述目錄TOC\o"1-2"\h\u17137基于平均值的非單調(diào)線搜索方法綜述 113871.1基于平均值的非單調(diào)線搜索方法的相關定義及算法概述 1265291.2算法全局收斂性的證明 2174561.3R?線性收斂性的證明 41.1基于平均值的非單調(diào)線搜索方法的相關定義及算法概述為了克服Grippo等三位學者所提出的非單調(diào)線搜索方法的局限性，Zhang和Hager圍繞前者提出了一類新型的非單調(diào)線搜索方法。其中最為核心亦最具有突破性的改變即是用一系列函數(shù)值的平均值替換了式（1.2.4）中的最大值函數(shù)。修正后的線搜索方法包括以下兩部分核心內(nèi)容。1）線搜索更新過程。線搜索過程要求得到的步長αfxk+α?fxk+或能滿足Armijo搜索準則，即令αk=αkρ?k，?k是能使式（1.2）代價更新過程。Qk+1=ηkQ Ck+1=ηkQ其中各參數(shù)須滿足：0≤ηmin≤ηmax≤1，ηk∈ηmin,ηmax，0<δ<σ<1<ρ。Ck和Qk事實上，ηk的選擇將在很大程度上影響此方法的非單調(diào)程度。當ηk取0時，Ck與fxkCk+1=i=0kf1.2算法全局收斂性的證明Zhang和Hager已經(jīng)證明在適當條件下，該非單調(diào)線搜索方法在適當假設成立前提下，對非凸目標函數(shù)均具有良好的全局收斂性。為證明該方法的全局收斂性，我們首先需要證明引理1。引理1:當目標函數(shù)fx在水平集L=x∈R?fx且下降方向始終滿足方向假設（1.2.5）時，在該非單調(diào)線搜索的每次迭代過程中，均有fxk≤Ck成立。更進一步地，當目標函數(shù)fx有下界且下降方向證明：定義函數(shù)Dkt我們對其進行求導，得到導數(shù)Dk'又因為?fxkTpk≤0，代入步長更新公式（fk=D根據(jù)Wolfe規(guī)則及Armijo規(guī)則的定義可知，當?fxkTdk<0且目標函數(shù)有下界時，必然能搜索到滿足標準Wolfe規(guī)則、標準Armijo規(guī)則的αk。又結合式（2.2.4事實上，太小的步長更可能導致算法陷入下降速率緩慢的困境中。Zhang和Hager提出的這種非單調(diào)線搜索框架能夠有效規(guī)避這種風險，他們在文章中證明了由該方法生成的步長是具有下界的。引理2：當該算法采用的迭代方向始終為下降方向，即滿足?fxkαk≥對于采用Armijo線搜索準則的步長，αk≥證明：我們需要對上述兩種情形進行分類討論。當αk?fx又因為梯度?fLipschitz連續(xù)?fxk+結合式（2.2.7）及（2.2.8）并運用Cauchy-Schwarz不等式，式（2.2.5）即可得證。對于αk滿足Armijo準則的情況，我們進行進一步地分類。若ραk≥μ，顯然此時有α≥μ/ρf又因為梯度?fLipschitz連續(xù)，易得整理上式后可得，(δ?1)?基于引理1、引理2，Zhang和Hager證明了該單調(diào)非線搜索方法的全局收斂性，即由該算法生成的迭代序列xlim證明：首先分情形討論。當αkα結合（1.1）式及方向假設，我們可以寫出f當ρf當αk滿足Wolfe準則時，代入Wolfe情形下對應的α令w=min?fk+1≤再將式（2.2.9）代入代價更新公式，可得C因為Ck≥fk且f又因為Q假設limk→∞?f(xk)k=0因此假設不成立。limk→∞1.3R?線性收斂性的證明當目標函數(shù)為強凸函數(shù)時，該非單調(diào)線搜索方法被證明在適當條件下能夠R?線性收斂到最小值。假設fx為強凸函數(shù)，在x?處具有唯一最小值f?，函數(shù)梯度?fx在有界集上Lipschitz連續(xù)，下降方向pk始終滿足方向假設（1.2.5）。fx證明：由梯度的Lipschitz連續(xù)性可得?又根據(jù)方向假設及α?再結合三角不等式，我們可以得到?f(x代價更新公式可以被寫為Ck+1?f結合（2.2.9）式，可得C又因為Q所以有C在接下來的證明中，我們需要引入未知常數(shù)b作為衡量梯度大小的尺度。當Ck+1?f?已知fx?fx??其中μ'>0是凸性量度。又因為x?μ根據(jù)凸函數(shù)的性質(zhì)，可知gt=fx?f結合式（2.3.4），可以寫出f當?f將上