關(guān)于一類記憶梯度算法收斂速度的研究

劉麗敏

中國(guó)石油大學(xué)勝利學(xué)院基礎(chǔ)科學(xué)學(xué)院

關(guān)于一類記憶梯度算法收斂速度的研究

劉麗敏

中國(guó)石油大學(xué)勝利學(xué)院基礎(chǔ)科學(xué)學(xué)院

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

記憶梯度算法；線性收斂速度；無(wú)約束

1　引言

文獻(xiàn)［1］中提出了一種基于對(duì)角稀疏擬牛頓技術(shù)，結(jié)合曲線搜索步長(zhǎng)規(guī)則、Gu N.Z。非單調(diào)技術(shù)，建立的一種新的求解無(wú)約束最優(yōu)化問(wèn)題的記憶梯度算法，同時(shí)，給出了算法的全局收斂性分析。數(shù)值例子表明：算法是有效的，適合求解大規(guī)模問(wèn)題。

性質(zhì)1若xk不是問(wèn)題（p）的穩(wěn)定點(diǎn)，則有：

性質(zhì)2若xk不是問(wèn)題（p）的穩(wěn)定點(diǎn)，則：

性質(zhì)3設(shè)｛｝xk是由算法NMDSMG產(chǎn)生的序列，則有：

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

2　收斂速度

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

（H1）目標(biāo)函數(shù)f（x）在Rn上有下界。

（H2）目標(biāo)函數(shù)的梯度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）是強(qiáng)凸函數(shù)，即存在常數(shù)r〉0滿足：

定理1設(shè)｛xk，αk，gk｝ 是由算法產(chǎn)生的序列，假設(shè)（H1）～（H3）成立，如果有界，則存在θ∈（）0，1滿足：

f（xk）-f（x?）≤θk（f（x0）-f（x?）），?k.即｛fk｝R-線性收斂于f（x?）。

設(shè)x?是f的惟一最優(yōu)解，在式（2）中令y=x?得

由f（）xk+1≤Dk，?k和｛｝Dk是單調(diào)不增序列知｛｝xk?L（）x0

再有Cauchy-Schwarz不等式、性質(zhì)1、性質(zhì)2及式（6）可得

由假設(shè)（H2）及式（7）可知：

由假設(shè)條件知：

其中D0=hˉ..因此

其中b0=1+LD0.

事實(shí)上，如果‖gk‖2≥b1（Dk-f（x?）），則

故有Dk+1-f（x*）=ηkDk+（1-ηk）f（xk+1）-f（x*）

再由性質(zhì)3，知f（xk）-f（x?）≤Dk-f（x?）=θk（f（x0）-f（x?））.定理得證。

3　結(jié)論

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

［1］劉麗敏，吳玉敏.基于對(duì)角稀疏擬牛頓技術(shù)的非單調(diào)曲線搜索的記憶梯度算法［J］.中國(guó)石油大學(xué)勝利學(xué)院學(xué)報(bào)，2015，29（3）：28-31

［2］孫清瀅，徐琳琳，劉麗敏，等.基于稀疏對(duì)角擬牛頓方向的非單調(diào)超記憶梯度算法［J］.工程數(shù)學(xué)學(xué)報(bào)，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