劉麗敏
中國石油大學勝利學院基礎科學學院
關于一類記憶梯度算法收斂速度的研究
劉麗敏
中國石油大學勝利學院基礎科學學院
本文研究基于稀疏對角擬牛頓技術的Gu N.Z.非單調曲線搜索的記憶梯度算法,給出了算法的線性收斂性分析。
記憶梯度算法;線性收斂速度;無約束
文獻[1]中提出了一種基于對角稀疏擬牛頓技術,結合曲線搜索步長規(guī)則、Gu N.Z。非單調技術,建立的一種新的求解無約束最優(yōu)化問題的記憶梯度算法,同時,給出了算法的全局收斂性分析。數值例子表明:算法是有效的,適合求解大規(guī)模問題。
性質1若xk不是問題(p)的穩(wěn)定點,則有:
性質2若xk不是問題(p)的穩(wěn)定點,則:
性質3設{}xk是由算法NMDSMG產生的序列,則有:
1)f(xk+1)≤Dk,?k;2)f(xk)≤Dk,?k;3){Dk}是單調不增序列。
線性收斂速度分析需要以下假設條件:
(H1)目標函數f(x)在Rn上有下界。
(H2)目標函數的梯度g(x)=?f(x)在包含水平集L(x0)={x∈Rn|f(x)≤f(x0)}的開凸集B上Lipschitz連續(xù),即存在L〉0滿足:‖g(x)-g(y)‖≤L‖x-y‖,?x,y∈B。
(H3)f(x)是強凸函數,即存在常數r〉0滿足:
定理1設{xk,αk,gk} 是由算法產生的序列,假設(H1)~(H3)成立,如果有界,則存在θ∈()0,1滿足:
f(xk)-f(x?)≤θk(f(x0)-f(x?)),?k.即{fk}R-線性收斂于f(x?)。
設x?是f的惟一最優(yōu)解,在式(2)中令y=x?得
由f()xk+1≤Dk,?k和{}Dk是單調不增序列知{}xk?L()x0
再有Cauchy-Schwarz不等式、性質1、性質2及式(6)可得
由假設(H2)及式(7)可知:
由假設條件知:
其中D0=hˉ..因此
其中b0=1+LD0.
事實上,如果‖gk‖2≥b1(Dk-f(x?)),則
故有Dk+1-f(x*)=ηkDk+(1-ηk)f(xk+1)-f(x*)
再由性質3,知f(xk)-f(x?)≤Dk-f(x?)=θk(f(x0)-f(x?)).定理得證。
記憶梯度法是共軛梯度法[3]的一種變形,相比較而言,它的收斂速度更快。與其他需要計算梯度的無約束優(yōu)化方法相比,它能充分利用前面迭代點的一些信息,從而避免了信息浪費,且能有效避免存貯和計算矩陣,適合求解大規(guī)模無約束優(yōu)化問題[4]。除此之外,該算法還增加了參數選擇的自由度,由此更有利于構造快速穩(wěn)定的收斂算法。從理論上分析,該算法不僅具有全局收斂性,而且在一定條件下還具有線性收斂速度。
[1]劉麗敏,吳玉敏.基于對角稀疏擬牛頓技術的非單調曲線搜索的記憶梯度算法[J].中國石油大學勝利學院學報,2015,29(3):28-31
[2]孫清瀅,徐琳琳,劉麗敏,等.基于稀疏對角擬牛頓方向的非單調超記憶梯度算法[J].工程數學學報,2012,29(3)∶375-385
[3]Cohen A.I..Stepsize analysis for descent methods[J].JOTA,1981,33(2):187-205
[4]Cantrell,J.W..Relation between the memory gradient method and the Fletcher-Reeves method[J].Journal of Optimization Theory and Applications,1969,4(1)∶67-71