劉麗敏, 吳玉敏

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

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

劉麗敏, 吳玉敏

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

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

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

1 技術(shù)手段

20世紀(jì)60年代末,Miele和Cantrell首先提出的記憶梯度法[1]可以有效利用前面迭代點(diǎn)的信息。2006年,時(shí)貞軍[2]基于擬牛頓方程,通過(guò)限制Hk為對(duì)角稀疏正定矩陣,提出了對(duì)角稀疏擬牛頓算法,算法存儲(chǔ)量降為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)

同時(shí),提出Hk如下修正形式:

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

(4)

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

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

2 算 法

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

步驟2令

(5)

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

(6)

其中,

(7)

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

步驟4通過(guò)某種規(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)不增序列。

證明 見文獻(xiàn)[4]中引理3的證明。

3 全局收斂性

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

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

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

(14)

(15)

4 數(shù)值實(shí)驗(yàn)

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

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

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

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

5 結(jié)束語(yǔ)

本文在對(duì)角稀疏擬牛頓技術(shù)的基礎(chǔ)上,結(jié)合了Gu和Mo非單調(diào)曲線搜索規(guī)則,建立了求解無(wú)約束最優(yōu)化問題的新的記憶梯度算法,給出了算法的全局收斂性。數(shù)值例子表明算法是有效的,確實(shí)適合求解大規(guī)模問題。在傳統(tǒng)算法中,Hk是用BFGS公式和DFP公式校正,而在新算法中,Hk是用公式(4)校正。新算法更適用于計(jì)算大規(guī)模問題,因?yàn)樗拇鎯?chǔ)量小、計(jì)算量小,并且迭代時(shí)間短、迭代次數(shù)少,目標(biāo)函數(shù)值更接近于最優(yōu)值,而且所要解決問題的規(guī)模越大、維數(shù)越高,新算法優(yōu)勢(shì)就越明顯。對(duì)有些數(shù)值例子來(lái)說(shuō),非單調(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] 時(shí)貞軍,孫國(guó).無(wú)約束優(yōu)化問題的對(duì)角稀疏擬牛頓法[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] 孫清瀅,徐琳琳,劉麗敏,等.基于稀疏對(duì)角擬牛頓方向的非單調(diào)超記憶梯度算法[J].工程數(shù)學(xué)學(xué)報(bào),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é)任編輯] 藍(lán)若水

2015-06-06

劉麗敏(1987—),女,山東濰坊人,中國(guó)石油大學(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