李雙安，陳鳳華，程慧燕

（河南理工大學萬方科技學院 公共基礎教學部，河南 鄭州 450026）

教學教育研究

一個新的超記憶梯度法及全局收斂性

李雙安，陳鳳華，程慧燕

（河南理工大學萬方科技學院 公共基礎教學部，河南 鄭州 450026）

文章提出了一個新的超記憶梯度法解決無約束優(yōu)化問題.該算法沿著目標函數(shù)的下降方向進行搜索，每步迭代提出的算法都充分地利用了前面多步迭代信息，避免目標函數(shù)海瑟陣的儲存和計算，因此它適合解決大規(guī)模無約束優(yōu)化問題.在適當?shù)募僭O條件下，證明了所提出的算法具有全局收斂性.數(shù)值實驗表明此算法的可行性.

無約束優(yōu)化；超記憶梯度法；非單調線搜索；全局收斂性；數(shù)值實驗

本文考慮如下優(yōu)化問題：

其中f∶Rn→R為連續(xù)可微函數(shù).

求解問題（1）有很多迭代方法，如線搜索和信賴域方法，見文獻[1].線搜索方法迭代公式如下：

這里dk是f（x）在xk處的搜索方向，αk為搜索步長.

為方便，記（fxk）為fk，?f(xk)為gk.

在線搜索方法中，每一步迭代只用當前迭代信息生成下一步迭代，前面幾步的迭代信息被忽略.這對于設計一個高效算法而言是信息的浪費.共軛梯度法用前一步的迭代信息生成下一步的迭代，搜索方向定義如下：

共軛梯度法的優(yōu)勢是避免了牛頓型方法中矩陣的計算和存儲，因此它適合解決大規(guī)模優(yōu)化問題[2].

記憶梯度和超記憶梯度是共軛梯度法的推廣，因此它們和共軛梯度法有相同的性質.與共軛梯度法相比，記憶梯度法和超記憶梯度法充分利用前幾步迭代的信息生成一個新的迭代，這對于設計一個快速收斂的算法十分有效[3].

基于無約束優(yōu)化問題的牛頓方法，Grippo等人提出了非單調線搜索技術[4]，搜索步長αk滿足下面的條件：

這里σ∈(0,1)，m（0）=0，0≤m（k）≤min{m（k-1）+ 1，M}，M是預設非負整數(shù).

非單調技術或結合共軛梯度法，記憶梯度法的變化形式甚至被推廣到信賴域方法，它可以用來解無約束優(yōu)化問題，見文獻[5-6].此外，戴彧虹給出了非單調線搜索策略的理論證明.文獻[7]中指出，非單調性方法增加了找到全局最優(yōu)解的可能性，大量的數(shù)值實驗已表明非單調方案是有效的，尤其對于較困難的優(yōu)化問題.

盡管基于（3）式的非單調技術在大多數(shù)情況下性能良好，但是它也有一些缺點，許多情況下數(shù)值效果取決于M值的選取.

受到前面方法的啟發(fā)，本文提出了一個修正的非單調策略超記憶梯度法解無約束優(yōu)化問題（1）.在每一步迭代，提出的方法充分利用前面多步信息，避免了目標函數(shù)海瑟陣的存儲和計算，因此它適合解決大規(guī)模無約束優(yōu)化問題.在某些條件下，證明提出的算法具有全局收斂性，且數(shù)值實驗表明本文提出的算法是可行的.

1 新的超記憶梯度法

由前m步迭代信息構造搜索方向dk（m為一給定正整數(shù)）：

修正非單調線搜索技術計算步長αk如下，αk= βmk，其中mk是滿足下列不等式的最小非負整數(shù)：

修正非單調線搜索（6）下超記憶梯度算法步驟如下：

算法1 新的超記憶梯度算法：

步驟1：計算gk.若，算法停止；否則轉下一步；

步驟2：計算（4）式定義的搜索方向dk；

步驟3：確定滿足（6）式的步長αk；

步驟4：令xk+1=xk+αkdk；

步驟5：循環(huán).令k?k+1，轉步驟1.

下面給出修正非單調線搜索超記憶梯度算法的兩個性質如下：

引理1 對任一線搜索，搜索方向由（4）式定義，則有

引理1表明搜索方向dk是目標函數(shù)f（x）在xk處的下降方向.

引理2 對任意的k，有

故對任意的k，結論得證.

顯然，由（7）和（8）式有

2 全局收斂性分析

為保證全局收斂性，對問題（1）作如下基本假設：

（H1）目標函數(shù)f（x）在水平集

有界.

（H2）（fx）的梯度函數(shù)g（x）在閉凸集B?L(x0)上是Lipschitz連續(xù)的，即存在某一常數(shù)L>0滿足

引理3 若假設條件（H1）、（H2）成立，則算法1是良定的，即存在一個步長αk使得（6）式成立.

證明 由（6）式有

即證.

引理4 若假設條件（H1）、（H2）成立，γ∈（0，1-mp），則存在一常數(shù)η>0使得

由中值定理，存在θk∈[0,1]使得

由（12）、（13）式有

由假設條件（H2）及柯西-施瓦茲不等式，有

又由（14）、（15）式有

上式結合（9）式有

由（6）、（7）式有

定理1 若假設條件（H1）、（H2）成立，γ∈（0，1-mρ），則對某一k有gk=0或

證明 由引理3，引理4及文獻[8]定理8的證明即證得結論.

3 數(shù)值實驗

為進一步從數(shù)值計算的角度分析算法的可行性，通過Matlab編程將算法進行數(shù)值實驗，實驗結果表明本文提出的新的超記憶梯度法是可行的.算法中m=5，β=0.5，σ=0.2.

表1 問題1的數(shù)值實驗結果Tab.1 Numerical results for question 1

表2 問題2的數(shù)值實驗結果Tab.2 Numerical results for question 2

4 結論

本文提出了一個新的超記憶梯度法，該算法的特點：

1）搜索方向總是目標函數(shù)的下降方向，且不依賴于使用何種線搜索；

表3 問題3-8的數(shù)值實驗結果Tab.3 Numerical results for question 3-8

2）每步迭代，充分利用前面多步迭代信息，避免了目標函數(shù)海瑟陣的存儲和計算，算法適合解大規(guī)模無約束優(yōu)化問題.

在適當?shù)募僭O條件下，本文證明了提出的新的超記憶梯度法具有全局收斂性，且數(shù)值實驗結果表明本文提出的算法是可行的.

[1]Sun W Y,Yuan Y S.Optimization theory and methods[M]. New York:Springer,2006.

[2]Dai Y.Nonlinear conjugate gradient methods[M].Wiley En?cyclopedia of Operations Research and Management Science, 2011.

[3]Zheng Y,Wan Z.A new variant of the memory gradient method for unconstrained optimization[J].Optimization Letters,2012,6(8):1643-1655.

[4]Grippo L,Lampariello S,Lucidi F.A nonmonotone line search technique for newton's method[J].SIAM Journal on Numerical Analysis,1986,23(4):707-716.

[5]Liu H G,Jing L L,Han X,et al.A class of nonmonotone conjugate gradient methods for unconstrained optimization [J].Journal of optimization theory and applications,1999,101 (1):127-140.

[6]Shi Z,Wang S,Xu Z.The convergence of conjugate gradi?ent method with nonmonotone line search[J].Applied Mathematics and Computation,2010,217(5):1921-1932.

[7]Dai Y H.On the nonmonotone line search[J].J of Optim Theory and Appl,2002,112(2):315-330.

[8]Ou Y,Liu Y.A nonmonotone supermemory gradient algo?rithm for unconstrained optimization[J].Journal of Applied Mathematics and Computing,2014,46(2):215-235.

[9]房明磊,張聰,陳鳳華.一種新的Wolfe線搜索技術及全局收斂性[J].桂林電子科技大學學報,2008,28(1):62-65.

[10]陳鳳華,張聰,房明磊.曲線搜索下的新的記憶擬牛頓法[J].廣西科學,2008,15(3):254-256.

責任編輯：劉 紅

A New Supermemory Gradient Method and the Global Convergence

LI Shuang’an，CHEN Fenghua，CHENG Huiyan
（Wanfang Institute of Science and Technology，Henan Polytechnic University，Zhengzhou 450026，China）

In this paper,we propose a new supermemory gradient method for unconstrained optimization.An attractive prop?erty of the proposed method is that the direction generated by the method is always a descent for the objective function.The proposed method sufficiently uses the previous multi-step iterative information at each iteration and avoids the storage and computation of matrices associated with the Hessian of objective functions.Therefore,it is suitable to solve large-scale un?constrained optimization problems.Under appropriate conditions,we show that the new supermemory gradient method with nonmonotone line search is globally convergent.Numerical experiments show that the proposed algorithm is effective.

unconstrained optimization；supermemory gradient method；nonmonotone line search；global convergence；nu?merical experiments

O 224

A

1674-4942（2015）03-0237-05

2015-06-09

國家自然科學基金（11361018）；廣西杰出青年基金（2012GXSFFA060003）；河南省教育廳科學技術研究重點項目（12B110011）；高等學校重點科研項目（15B110008）