求解無(wú)約束優(yōu)化問(wèn)題的一種新的譜共軛梯度法

汪丹戎，陳忠，張毅 （長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州434023）

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

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

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

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

式中，‖·‖ 為歐式范數(shù)，yk－1＝gk－gk－1。

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

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

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

1 算法描述

改進(jìn)的譜系數(shù)βk的表達(dá)式如下：

算法描述如下：

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

步2 利用Wolfe線搜索準(zhǔn)則求得αk：

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

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

步5 令k＝k＋1，轉(zhuǎn)步2。

2 充分下降性

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

證明 利用數(shù)學(xué)歸納法：

1）當(dāng)k＝1時(shí)，有d1＝－g1，gT1d1＝－‖g1‖2＜0。

2）假設(shè)n＝k－1時(shí)，式（11）恒成立，即：

由式（10）知：

當(dāng)n＝k時(shí)，由式（7）有：

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

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

由定理1知，算法在標(biāo)準(zhǔn)Wolfe線性搜索條件，能滿足充分下降性。

3 全局收斂性

為證明全局收斂性，假定目標(biāo)函數(shù)f（x）滿足以下條件（A）：

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

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

引理1［9］設(shè)f（x）和初始點(diǎn)x1滿足假設(shè)（A），對(duì)于式（2）和式（3）產(chǎn)生的迭代，其中dk為下降方向滿足gkTdk＜0，步長(zhǎng)因子αk應(yīng)滿足式（4），則有：

定理2 設(shè)f（x）和初始點(diǎn)x1滿足假設(shè)（A），對(duì)于式（2）和式（3）產(chǎn)生的迭代，步長(zhǎng)因子αk應(yīng)滿足式（4），βk由式（6）產(chǎn)生，有：

證明 用反證法。假設(shè)結(jié)論不成立，則必存在常數(shù)c＞0，使得：

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

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

即可得：

由式（20）可知：

即：

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

4 結(jié)語(yǔ)

對(duì)于無(wú)約束優(yōu)化問(wèn)題，設(shè)計(jì)出一種修正的譜共軛梯度算法，證明了該算法產(chǎn)生的搜索方向是充分下降方向，最后還結(jié)合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.