求解無約束優化問題的一種新的譜共軛梯度法

汪丹戎，陳忠，張毅 （長江大學信息與數學學院，湖北 荊州434023）

考慮求解無約束優化問題：

這里f（x）：Rn→R為連續可微函數。求解共軛梯度算法的迭代格式如下：

其中，gk＝▽f（xk）為f（x）在xk處的梯度；dk搜索方向；αk≥0為步長因子；βk為譜系數。

不同的βk與αk構成不同的共軛梯度法，如FR方法［1］、HS方法［2］、PRP方法［3］、 CD方法［4］、LS方法［5］、DY方法［6］的參數βk的表達式分別為：

式中，‖·‖ 為歐式范數，yk－1＝gk－gk－1。

在上述幾種方法中，PRP、HS和LS方法數值性能良好，但不具有很好的全局收斂性，而FR、CD和DY方法具有良好的收斂性，但數值表現卻一般。不少研究者將βk作出改進，設計出了不同效果的算法［7，8］。2001年，Birgin和Martinez［7］將譜共軛梯度和共軛梯度第一次結合起來，提出了譜共軛梯度算法。譜共軛梯度的迭代公式如下：

2007年，YAO，WEI和HUANG［8］對βLSk進行改進，提出了一種的新的βk公式：

該算法每次迭代都可以產生一個充分下降方向，并且在Wolfe線搜索下全局收斂。下面，筆者在文獻［8］的基礎上，對譜系數βk進行改進，并采用譜共軛梯度算法的的迭代格式，提出了一種新的譜共軛梯度法。

1 算法描述

改進的譜系數βk的表達式如下：

算法描述如下：

步1 給定x∈Rn，ε＞0，0＜ρ＜σ＜1，若 ‖gk‖≤ε，則停止；否則令d1＝－g1，k＝1；

步2 利用Wolfe線搜索準則求得αk：

步3 計算xk＋1＝xk＋αkdk；如果 ‖gk＋1‖ ≤ε， 則停止；

步4 由式 （7）計算βk＋1， 由式 （8）計算θk，由式（6）計算dk；

步5 令k＝k＋1，轉步2。

2 充分下降性

定理1 按照βk的新公式（7）和式（8）時，對于所有的k≥1，則有：

證明 利用數學歸納法：

1）當k＝1時，有d1＝－g1，gT1d1＝－‖g1‖2＜0。

2）假設n＝k－1時，式（11）恒成立，即：

由式（10）知：

當n＝k時，由式（7）有：

由式（5）知dk＝－θkgk＋βkdk－1兩端與gk作內積，并由（15）可得：

由此可知對于所有的k≥1，gTkdk＜0都成立。

由定理1知，算法在標準Wolfe線性搜索條件，能滿足充分下降性。

3 全局收斂性

為證明全局收斂性，假定目標函數f（x）滿足以下條件（A）：

1）f（x）在水平集Ω＝｛x∈Rn｜f（x）≤f（x1）｝上有下界；

2）f（x）連續可微且其導數▽f（x）滿足Lipschitz條件，即存在常數L＞0，使得：

引理1［9］設f（x）和初始點x1滿足假設（A），對于式（2）和式（3）產生的迭代，其中dk為下降方向滿足gkTdk＜0，步長因子αk應滿足式（4），則有：

定理2 設f（x）和初始點x1滿足假設（A），對于式（2）和式（3）產生的迭代，步長因子αk應滿足式（4），βk由式（6）產生，有：

證明 用反證法。假設結論不成立，則必存在常數c＞0，使得：

對所有的k≥1成立，由式（3）知dk＋θkgk＝βkdk－1，兩邊取平方模并移項可得：

上式兩邊除以（gkTdk）2，由式（7）和式（8）可知：

即可得：

由式（20）可知：

即：

這與引理1矛盾，故式 （19）成立，定理2得證。

4 結語

對于無約束優化問題，設計出一種修正的譜共軛梯度算法，證明了該算法產生的搜索方向是充分下降方向，最后還結合Wolfe線搜索及梯度滿足Lipschitz條件，證明了算法具有全局收斂性。

［1］ Fletcher R，Reeves C M.Function minimization by conjugate gradients ［J］.The Computer Journal，1964，7 （2）：149～154.

［2］ Hestenes M R，Stieffel E L.Method of conjugate gradient for solving linear systems ［J］.Research Nat Bur Standards，1952，49 （1952）：409～436.

［3］ Polyak B T.The conjugate gradient method in extremal problems ［J］.USSR Computational Mathematics and Mathematical Physics，1969，9 （4）：94～112.

［4］ Fletcher R.Practical Methods of Optimization：Vol.2：Constrained Optimization ［M］.John Wiley﹠Sons，Inc，1987.

［5］ Liu Y，Storey C.Efficient Generalized Conjugate Gradient Algorithms，Part 1：Theory ［J］.Journal of Optimization Theroy and Applications，1991，69 （1）：129～137.

［6］ Dai Y H，Yuan Y.A Nonlinear Conjugate Gradient Method with a strong global convergence property ［J］.SIAM Journal on optimization，1999，10 （1）：177～182.

［7］ Birgin E G，Martimez J M.A spectral conjugate gradient method for unconstrained optimization ［J］.Appl Math optim，2001，43 （2）：117～128.

［8］ Yao S W，Wei Z X，Huang H.A note about WYL’s conjugate gradient method and its apptications ［J］.Appl Math Comput，2007，191 （2）：381～388.

［9］ Zoutendijk G.Nonlinear programming，Computational Methods，in integer and Nonlinear Programming ［M］.North－Holland，Amsterdam，1970.