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