周國(guó)玲，曹名圓，楊月婷

(北華大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，吉林 吉林 132013)

0 引 言

考慮無(wú)約束優(yōu)化問(wèn)題

minf(x)，x∈n，

其中f(x)是n→上的連續(xù)可微函數(shù).共軛梯度算法具有迭代格式簡(jiǎn)單、儲(chǔ)存量小等優(yōu)點(diǎn)，因而特別適用于求解大規(guī)模無(wú)約束優(yōu)化問(wèn)題，其基本迭代格式為

xk+1=xk+αkdk，k≥0，

(1)

這里的gk=?f(xk)是f(x)在xk點(diǎn)的梯度，步長(zhǎng)αk可通過(guò)精確線搜索方法或非精確線搜索方法求得，共軛參數(shù)βk-1的不同選取方式對(duì)應(yīng)了不同的共軛梯度法[1-4].

Masoud Fatem[5]考慮用精確線搜索求解強(qiáng)凸二次函數(shù)極小時(shí)，線性共軛梯度法具有充分下降性、正交性以及共軛性等顯著特性.利用式(1)構(gòu)造如下關(guān)于共軛參數(shù)的一維優(yōu)化模型

(2)

通過(guò)求解問(wèn)題(2)確定共軛參數(shù)βk，這里的yk=gk+1-gk，sk=xk+1-xk.

另一方面，子空間技術(shù)因其可以減小計(jì)算成本和存儲(chǔ)規(guī)模而被廣泛關(guān)注[6-10].例如Stoer和Yuan[11]將二維子空間與共軛梯度法相結(jié)合提出了二維子空間極小化共軛梯度法，其搜索方向dk+1由當(dāng)前梯度和最近一次搜索方向生成，即

dk+1=μk+1gk+1+νk+1sk，

其中μk+1和νk+1是標(biāo)量參數(shù).Yang等[12]提出一種子空間三項(xiàng)共軛梯度法，該方法在子空間Ωk={-gk+1，sk，sk-1}上構(gòu)造目標(biāo)函數(shù)的近似二次模型，再確定搜索方向.

受文獻(xiàn)[5，12]啟發(fā)，本文結(jié)合子空間技術(shù)，考慮算法的充分下降性和共軛性，構(gòu)造一個(gè)帶有懲罰參數(shù)的優(yōu)化模型，通過(guò)極小化該模型確定搜索方向，進(jìn)而提出新子空間共軛梯度法.

1 子空間共軛梯度法的提出

我們?cè)诙S子空間Ωk=span{-gk+1，sk}上構(gòu)造如下優(yōu)化問(wèn)題

(3)

其中：d=-μgk+1+νsk是待定搜索方向，這里的μ、ν是待定參數(shù)；Mk為懲罰參數(shù)，當(dāng)Mk較大時(shí)，增加搜索方向滿足共軛性的機(jī)會(huì)，反之，搜索方向的下降性更強(qiáng).將待定搜索方向d代入φk+1(d)得

這是關(guān)于μ、ν的二次函數(shù)，易見(jiàn)φk+1(d)關(guān)于μ、ν的Hessian陣

是半正定的.因此令φk+1(d)的梯度為0，即

(4)

則上式的解即為優(yōu)化模型(3)的解.考慮以下3種情況：

(5)

(6)

dk+1=-gk+1

(7)

由此，建立如下子空間共軛梯度算法.

算法1

步0 給定初始點(diǎn)x0∈n，參數(shù)ε>0，0

步2 由Wolfe線搜索準(zhǔn)則

計(jì)算步長(zhǎng)αk.

下面證明搜索方向dk+1在不依賴任何線搜索的條件下，具有充分下降性.

證明：1)當(dāng)dk+1由式(5)計(jì)算時(shí)，則

2)當(dāng)dk+1由式(6)計(jì)算時(shí)，則

3)當(dāng)dk+1由式(7)計(jì)算時(shí)，則

令c=1/2，引理得證.證畢.

2 收斂性分析

本節(jié)證明算法1的全局收斂性.首先作如下假設(shè)：

(H1)f(x)在水平集L0={x∈nf(x)

由假設(shè)(H1)～(H2)可知，存在一個(gè)常數(shù)Γ>0，使得

(8)

下面引理給出著名的Zoutendijk條件[13].

引理3假設(shè)(H1)～(H2)成立，序列{xk}由算法1生成，如果

則

(9)

定理1假設(shè)(H1)～(H2)成立，序列{xk}由算法1生成，如果f是一致凸函數(shù)，即存在正常數(shù)γ使得

(10)

則式(9)成立.

證明：從假設(shè)(H2)，有

(11)

又根據(jù)式(10)可得

(12)

1)當(dāng)dk+1由式(5)計(jì)算時(shí)，可得

因此

2) 當(dāng)dk+1由式(6)計(jì)算時(shí)，可得

因此

3) 當(dāng)dk+1由式(7)計(jì)算時(shí)，可得

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

采用Dolan等[14]的評(píng)價(jià)準(zhǔn)則，對(duì)算法1的迭代次數(shù)和CPU運(yùn)行時(shí)間的性能進(jìn)行評(píng)估，我們以迭代次數(shù)為例說(shuō)明性能圖上橫縱坐標(biāo)的物理意義.用τ>1表示最佳比值因子，用函數(shù)ρν(τ)表示某算法在迭代次數(shù)與所有算法中最小迭代次數(shù)的比值不超過(guò)τ時(shí)所求解問(wèn)題個(gè)數(shù)占問(wèn)題總數(shù)的比率，它反映了所測(cè)算法在迭代次數(shù)方面的性能.因此，本文對(duì)算法1(SC算法)、HS算法、DY算法，以τ為橫坐標(biāo)、ρν(τ)為縱坐標(biāo)作圖，圖中曲線越高表明算法的數(shù)值性能越好.三個(gè)算法的性能評(píng)估結(jié)果如圖1所示.

圖1 算法性能對(duì)比Fig.1 Comparison of algorithm performance

從圖1 a中可以看出，在迭代次數(shù)方面，算法1的性能曲線都在DY、HS的曲線之上，說(shuō)明算法1在求解大規(guī)模無(wú)約束優(yōu)化問(wèn)題時(shí)能夠使用更少的迭代次數(shù)，求解效率更高；圖1 b表明算法1在CPU時(shí)間上也優(yōu)于HS和DY方法.

4 結(jié) 論

本文研究了求解大規(guī)模無(wú)約束優(yōu)化問(wèn)題的新子空間共軛梯度法，且搜索方向滿足充分下降性條件.在適當(dāng)假設(shè)條件下，證明了算法的全局收斂性.數(shù)值結(jié)果表明，該算法在求解大規(guī)模無(wú)約束優(yōu)化問(wèn)題時(shí)具有較高效率，特別在迭代次數(shù)上明顯優(yōu)于HS和DY方法.