關于一類記憶梯度算法收斂速度的研究

劉麗敏

中國石油大學勝利學院基礎科學學院

關于一類記憶梯度算法收斂速度的研究

劉麗敏

中國石油大學勝利學院基礎科學學院

本文研究基于稀疏對角擬牛頓技術的Gu N.Z.非單調曲線搜索的記憶梯度算法，給出了算法的線性收斂性分析。

記憶梯度算法；線性收斂速度；無約束

1　引言

文獻［1］中提出了一種基于對角稀疏擬牛頓技術，結合曲線搜索步長規則、Gu N.Z。非單調技術，建立的一種新的求解無約束最優化問題的記憶梯度算法，同時，給出了算法的全局收斂性分析。數值例子表明：算法是有效的，適合求解大規模問題。

性質1若xk不是問題（p）的穩定點，則有：

性質2若xk不是問題（p）的穩定點，則：

性質3設｛｝xk是由算法NMDSMG產生的序列，則有：

1）f（xk+1）≤Dk，?k；2）f（xk）≤Dk，?k；3）｛Dk｝是單調不增序列。

2　收斂速度

線性收斂速度分析需要以下假設條件：

（H1）目標函數f（x）在Rn上有下界。

（H2）目標函數的梯度g（x）=?f（x）在包含水平集L（x0）=｛x∈Rn|f（x）≤f（x0）｝的開凸集B上Lipschitz連續，即存在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的惟一最優解，在式（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　結論

記憶梯度法是共軛梯度法［3］的一種變形，相比較而言，它的收斂速度更快。與其他需要計算梯度的無約束優化方法相比，它能充分利用前面迭代點的一些信息，從而避免了信息浪費，且能有效避免存貯和計算矩陣，適合求解大規模無約束優化問題［4］。除此之外，該算法還增加了參數選擇的自由度，由此更有利于構造快速穩定的收斂算法。從理論上分析，該算法不僅具有全局收斂性，而且在一定條件下還具有線性收斂速度。

［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