基于對角稀疏擬牛頓技術(shù)的非單調(diào)曲線搜索的記憶梯度算法

劉麗敏, 吳玉敏

(中國石油大學(xué)勝利學(xué)院 基礎(chǔ)科學(xué)學(xué)院,山東 東營 257000)

基于對角稀疏擬牛頓技術(shù)的非單調(diào)曲線搜索的記憶梯度算法

劉麗敏, 吳玉敏

(中國石油大學(xué)勝利學(xué)院 基礎(chǔ)科學(xué)學(xué)院,山東 東營 257000)

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

非線性規(guī)劃;對角稀疏擬牛頓算法;非單調(diào)技術(shù);曲線搜索;記憶梯度算法;收斂

1 技術(shù)手段

20世紀60年代末,Miele和Cantrell首先提出的記憶梯度法[1]可以有效利用前面迭代點的信息。2006年,時貞軍[2]基于擬牛頓方程,通過限制Hk為對角稀疏正定矩陣,提出了對角稀疏擬牛頓算法,算法存儲量降為O(n),使其利于求解大規(guī)模問題。根據(jù)目標(biāo)函數(shù)f(x)的Taylor展開式,Wei Z X[3]給出了非擬牛頓方程,并且給出了Ak的兩種取法:

(1)

(2)

其中,vk=2(fk-fk+1)+(gk+1+gk)Tsk。2012年,孫清瀅[4]給出了另外一種新的取法:

(3)

同時,提出Hk如下修正形式:

設(shè)Hk為對角稀疏正定矩陣,令Hk+1=Hk+ΔHk,其中,ΔHk為對角矩陣。這時Hk+1為對角矩陣且要求近似滿足非擬牛頓條件:

(4)

近年來,曲線搜索技術(shù)應(yīng)用到優(yōu)化算法中,使算法在曲線上搜索下一個迭代點,在確定步長的同時確定下降方向,得到了一些收斂效果好的算法[5]。非單調(diào)線搜索技術(shù)具有使算法快速收斂和便于求解全局最優(yōu)解的優(yōu)點,最近,Gu和Mo[6]提出了一種新的非單調(diào)線搜索技術(shù),在新的非單調(diào)線搜索技術(shù)中改進了傳統(tǒng)非單調(diào)技術(shù)中的參考值的選取。

本文在修正擬牛頓方程的基礎(chǔ)上,結(jié)合了對角稀疏擬牛頓技術(shù)、記憶梯度算法的思想,用前一次迭代方向去修正-Hkgk得到算法的迭代方向,結(jié)合Gu N.Z.非單調(diào)技術(shù)和曲線搜索步長規(guī)則,建立求解無約束最優(yōu)化問題的新的記憶梯度算法,并給出了算法的全局收斂性分析。給出數(shù)值例子驗證算法的有效性,確實適合求解大規(guī)模問題。

2 算 法

基于稀疏對角擬牛頓技術(shù)的Gu N.Z.非單調(diào)曲線搜索的記憶梯度算法(NMDSMG):

步驟2令

(5)

步驟3令xk+1=xk+αkdk(αk),選取步長αk為{1,ω,ω2,…}中滿足下式的最大者

(6)

其中,

(7)

其中,Hk由式(4)確定。

步驟4通過某種規(guī)則給出ηk∈[ηmin,ηmax],令

Dk+1=ηkDk+(1-ηk)f(xk+1).

(8)

令k:=k+1,轉(zhuǎn)步驟1。

證明 由dk的定義和Hk的取法易證。

證明 由式(7)和Hk的構(gòu)造知

引理3 設(shè){xk}是由算法NMDSMG產(chǎn)生的序列,則有

1)f(xk+1)≤Dk,?k;

2)f(xk)≤Dk,?k;

3){Dk}是單調(diào)不增序列。

證明 見文獻[4]中引理3的證明。

3 全局收斂性

設(shè)算法NMDSMG產(chǎn)生的點列為{xk},如果存在某個k使得f(xk)=0,那么xk就是問題(p)的穩(wěn)定點。下面假設(shè)算法中產(chǎn)生的點列{xk}為無窮點列,全局收斂結(jié)果如下:

定理1 假設(shè)目標(biāo)函數(shù)f(x)在水平集L0={x∈Rn|f(x)≤f(x0)}上有下界,算法產(chǎn)生無窮點列{xk},如果目標(biāo)函數(shù)f(x)的梯度f(x)在包含L0的某開凸集上一致連續(xù),那么點列{xk}的任一極限點都是問題(p)的穩(wěn)定點。

由式(6)和式(8)知

Dk+1=ηkDk+(1-ηk)f(xk+1)≤

(9)

由ηmin<1、式(9)和引理2知

(10)

由引理3知

(11)

根據(jù)中值定理,可得

(12)

由Cauchy-Schwarz不等式、引理1、引理2及式(12)可得

(13)

因為{xk}k∈K有界,g(x)連續(xù),因而{gk}k∈K有界,設(shè)其界為M>0,則由式(13)可知

(14)

(15)

4 數(shù)值實驗

從文獻[5,7]中選擇2個數(shù)值例子,利用Matlab7.0在電腦上編制程序?qū)Ρ疚乃惴ㄟM行數(shù)值實驗,同時與其單調(diào)算法進行比較。

當(dāng)Ak取式(1)、式(2)、式(3)及Ak=0時,算法NMDSMG對應(yīng)的算法為NMDSMG(1)、NMDSMG(2)、NMDSMG(3)及NMDSMG(0);當(dāng)ηk≡0時,算法NMDSMG(1)、NMDSMG(2)、NMDSMG(3)及NMDSMG(0)分別對應(yīng)其單調(diào)算法,記為MMG(1)、MMG(2)、MMG(3)及MMG(0)。當(dāng)Bk≡In時,記為NGM;當(dāng)ηk≡0時,算法NGM對應(yīng)其單調(diào)算法,記為GM。當(dāng)Bk用DFP公式修正時,算法記為DMMG;當(dāng)Bk用BFGS公式修正時,算法記為BMMG;在算法DMMG、BMMG中取η≡0時,分別對應(yīng)其單調(diào)算法,分別記為MDMMG、MBMM。

初始點x0=(-2,-2,…,-2)T,最優(yōu)值。

表1 例1、2的計算結(jié)果

5 結(jié)束語

本文在對角稀疏擬牛頓技術(shù)的基礎(chǔ)上,結(jié)合了Gu和Mo非單調(diào)曲線搜索規(guī)則,建立了求解無約束最優(yōu)化問題的新的記憶梯度算法,給出了算法的全局收斂性。數(shù)值例子表明算法是有效的,確實適合求解大規(guī)模問題。在傳統(tǒng)算法中,Hk是用BFGS公式和DFP公式校正,而在新算法中,Hk是用公式(4)校正。新算法更適用于計算大規(guī)模問題,因為它的存儲量小、計算量小,并且迭代時間短、迭代次數(shù)少,目標(biāo)函數(shù)值更接近于最優(yōu)值,而且所要解決問題的規(guī)模越大、維數(shù)越高,新算法優(yōu)勢就越明顯。對有些數(shù)值例子來說,非單調(diào)算法的數(shù)值表現(xiàn)要優(yōu)于單調(diào)算法。

[1] MIELE A,CANTRELL J W.Memory gradient method for the minimization of functions[J].Journal of Optimization Theory and Applications,1969,3(6):459- 470.

[2] 時貞軍,孫國.無約束優(yōu)化問題的對角稀疏擬牛頓法[J].系統(tǒng)科學(xué)與數(shù)學(xué),2006,26(1):101-112.

[3] WEI Z X, LI G Y, QI L Q. New quasi-Newton methods for uncon- strained optimization problems[J].Applied Mathematics and Computation,2006,175(2):1156-1188.

[4] 孫清瀅,徐琳琳,劉麗敏,等.基于稀疏對角擬牛頓方向的非單調(diào)超記憶梯度算法[J].工程數(shù)學(xué)學(xué)報,2012,29(3):375-385.

[5] SHI Z J,SHEN J.A new descent algorithm with curve search rule[J].Applied Mathematics and Computation,2005,161(3):753-768.

[6] GU N Z,MO J T.Incorporating nonmonotone strategies into the trust region method for unconstrained optimization[J].Computers and Mathematics with Applications,2008,55(9):2158-2172.

[7] TOUATI-AHMED D,STOREY C.Efficient hybrid conjugate gradient techniques[J].Journal of Optimization Theory and Applications,1990,64(2):379-397.

[責(zé)任編輯] 藍若水

2015-06-06

劉麗敏(1987—),女,山東濰坊人,中國石油大學(xué)勝利學(xué)院基礎(chǔ)科學(xué)學(xué)院助教,碩士,主要從事數(shù)學(xué)教學(xué)與研究。

10.3969/j.issn.1673-5935.2015.03.009

O224

A

1673-5935(2015)03- 0028- 04