一種改進(jìn)的DY共軛梯度法及其全局收斂性

王安平 （長江大學(xué)工程技術(shù)學(xué)院基礎(chǔ)教學(xué)部，湖北 荊州434020）

馬 爍 （荊州理工職業(yè)學(xué)院基礎(chǔ)課部，湖北 荊州434000）

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

式中，f：Rn→R連續(xù)可微。共軛梯度法是求解該問題的一類有效算法。一般的共軛梯度法迭代公式為：

式中，x1為初始點；dk為搜索方向；αk是由某種線性搜索或由特定公式計算出的步長因子；βk為標(biāo)量；g（x）＝ ▽f（x），gk＝ ▽f（xk）。共軛梯度法的關(guān)鍵是選取αk和βk，不同的αk和βk決定了不同的共軛梯度算法。常用選取αk的線搜索是標(biāo)準(zhǔn)Wolfe線搜索，即選取αk＞0滿足：

式中，δ和σ是滿足0＜δ＜σ＜1的常數(shù)。而βk的選取公式常用的有：

對應(yīng)的共軛梯度法依次為FR方法［1］、PRP方法［2］、HS方法［3］、CD方法［4］、LS方法［5］和 DY 方法［6］。

在眾多共軛梯度法中，為了保證下降方向，許多學(xué)者都做了深入的研究。文獻(xiàn) ［7］提出了一種改進(jìn)的DY共軛梯度法，參數(shù)βk的計算公式為：

受文獻(xiàn)［7］的啟發(fā)，筆者在MDY方法的基礎(chǔ)上，給出了一個新的參數(shù)βk的取法，即：

1 改進(jìn)的DY算法及其充分下降性

改進(jìn)的DY算法如下：

步1 給定初始點x1∈Rn，ε＞0，d1＝－g1，令k＝1；

步2 若‖gk‖≤ε，則停止迭代；否則轉(zhuǎn)入步3；

步3 由式（3）求得αk；

步4 計算xx＋1＝xk＋αkdk，若 ‖gk＋1‖ ≤ε，則算法停止，否則轉(zhuǎn)步5；

步5 利用式（4）計算βk＋1。計算dk＋1＝－gk＋1＋βk＋1dk，置k＝k＋1，轉(zhuǎn)步2。

定理1 設(shè)迭代方向由：

證明 當(dāng)k＝0時，dT0g0＝－‖g0‖2，結(jié)論成立。

當(dāng)k≥0時，dk＝－gk＋βNMDYkdk－1兩邊與gk做內(nèi)積：

2 算法的全局收斂性

下面筆者將在一定的假設(shè)條件下證明NMDY算法的全局收斂性。假設(shè)條件（A）如下：

（1）水平集L1＝ ｛x∈Rn｜f（x）≤f（x1）｝有界，其中x1為初始點；

（2）在水平集L1的一個鄰域U內(nèi)，f（x）是連續(xù)可微的，其梯度g（x）是lipschitz連續(xù)的，即存在常數(shù)L＞0使：

‖g（x）－g（y）‖ ≤L‖x－y‖ ?x，y∈U引理1 設(shè)目標(biāo)函數(shù)f（x）滿足假設(shè)A，序列｛xk｝由式（2）產(chǎn)生，其中βk由（4）計算，αk滿足式（3），則。此關(guān)系式稱為Zoutendijk條件。

證明 由定理1及式（3），則有：

則式（6）說明了函數(shù)列｛fk｝有界。再由定理1及式（3）和假設(shè)條件（A）中的第2個條件，則有：

再聯(lián)合式（3）可以得到：

又因為函數(shù)列｛fk｝有界，所以有：

定理2 設(shè)目標(biāo)函數(shù)f（x）滿足假設(shè)條件A，序列｛xk｝由式（2）產(chǎn)生，其中βk由式（4）計算，αk由式（3）確定。假設(shè)存在一個正數(shù)α＊，滿足αk≥α＊，則有：

證明 由假設(shè)A中的（1），則存在一個常數(shù)M＞0使得：

由式（8）和αk≥α＊，可以得到：

由式（9）及引理1和定理1的結(jié)論，可以得到式（7），即定理2得證。