周國玲，曹名圓，楊月婷

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

0 引 言

考慮無約束優(yōu)化問題

minf(x)，x∈n，

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

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

(1)

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

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

(2)

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

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

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

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

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

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

我們在二維子空間Ωk=span{-gk+1，sk}上構造如下優(yōu)化問題

(3)

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

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

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

(4)

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

(5)

(6)

dk+1=-gk+1

(7)

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

算法1

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

步2 由Wolfe線搜索準則

計算步長αk.

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

證明：1)當dk+1由式(5)計算時，則

2)當dk+1由式(6)計算時，則

3)當dk+1由式(7)計算時，則

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

2 收斂性分析

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

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

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

(8)

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

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

則

(9)

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

(10)

則式(9)成立.

證明：從假設(H2)，有

(11)

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

(12)

1)當dk+1由式(5)計算時，可得

因此

2) 當dk+1由式(6)計算時，可得

因此

3) 當dk+1由式(7)計算時，可得

3 數(shù)值實驗

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

圖1 算法性能對比Fig.1 Comparison of algorithm performance

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

4 結 論

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