Glodstein條件下的一種修正CD共軛梯度法

黎小林

（重慶師范大學(xué)數(shù)學(xué)學(xué)院，重慶 401331）

1 引言

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

其中Rn是n維歐幾里得空間，f:Rn→R是一個(gè)連續(xù)可微的函數(shù)［1］.

眾所周知，共軛梯度法是求解該類問題的一種重要方法，它具有如下的迭代格式

其中αk是某種線搜索下的步長(zhǎng)，dk滿足

其中βk是共軛參數(shù)，不同的βk的取法會(huì)產(chǎn)生不同的共軛梯度法，常見的βk有如下定義

對(duì)應(yīng)的方法分別叫做 FR（Fletcher-Revees），PRP（Polak-Ribiere-Polyak），HS（Hestenes-Stiefel），LS（Liu-Storey），CD（Conjugate Descent）和DY（Dai-Yuan）共軛梯度法.

共軛梯度法是求解大規(guī)模無約束優(yōu)化問題的一種方法，它存儲(chǔ)量小、計(jì)算簡(jiǎn)單.該方法由Hestenes和Stiefel在求解對(duì)稱正定線性方程時(shí)提出，并由Fletcher和Revees在求解無約束極小化問題中發(fā)展起來，它在控制論、工程、管理科學(xué)和優(yōu)化研究中有廣泛應(yīng)用.

受文獻(xiàn)［2］啟發(fā)，主要對(duì) Conjugate Descent法進(jìn)行了修正，得到了一個(gè)新的修正 Conjugate Descent（MCD）算法，并證明了新算法在一個(gè)Goldstein線搜索準(zhǔn)則下的全局收斂性.

采用的Glodstein線搜索準(zhǔn)則［3］為

戴彧虹（文獻(xiàn)［4］）對(duì)非線性共軛梯度法的收斂性進(jìn)行了分析，并且在文獻(xiàn)［5］中提出了一種具有強(qiáng)全局收斂性的共軛梯度法.另外，張麗等提出了幾種3項(xiàng)共軛梯度法（文獻(xiàn)［6，7］），它們?cè)诓灰蕾嚾魏尉€搜索的條件下滿足充分下降性，同時(shí)在適當(dāng)條件下也具有較好的全局收斂性，這些在文獻(xiàn)的數(shù)值算例中得到很好的體現(xiàn).

2 算法

給出的MCDCG算法［6］的迭代格式為式（2）和

其中

顯然，由式（5）（6）和βCD的公式知，對(duì)于任意的k≥0，有

MCDCG 算法:初始步:給定 x0∈Rn，ε≥0，令 d0=－g0，k:=0.

第1步:若‖g0‖≤ε，則停止.

第2步:求出滿足Glodstein準(zhǔn)則的步長(zhǎng)αk.

第 3 步:計(jì)算 xk+1=xk+αkdk，若‖gk+1‖≤ε，則停止.

第4步:通過式（5），求得dk+1;令k:=k+1，轉(zhuǎn)第2步.

3 MCDCG算法的收斂性

作如下假設(shè)［4］:

（A）水平集Ω={x∈Rn|f（x）≤f（x0）}有下界，其中x0∈Rn為初始點(diǎn).

（B）f在水平集Ω的一個(gè)領(lǐng)域N內(nèi)連續(xù)可微，且其梯度g滿足Lipschitz連續(xù)，即存在常數(shù)L＞0，使得

顯然，在上述假設(shè)下，存在某個(gè)γ1＞0，使得

引理1 如果存在常數(shù)ε＞0，使得‖gk‖≥ε對(duì)任意k≥0成立，則必存在常數(shù)M＞0，使得‖dk‖≤M對(duì)任意k≥0成立.

證明 當(dāng)k=0時(shí)，‖d0‖=‖－g0‖=‖g0‖≤γ1，此時(shí)令 γ1=M，結(jié)論成立.

證明 用反證法.假設(shè)定理1的結(jié)論不成立，則存在常數(shù)ε＞0，使得‖gk‖≥ε對(duì)任意k成立.下面分兩種情況進(jìn)行討論.

由式（11）和式（4）的左邊不等式知，當(dāng)k∈Κ充分大時(shí)，有

整理可得

［1］張霞.一個(gè)新的光滑低階精確罰函數(shù)［J］.重慶工商大學(xué)學(xué)報(bào):自然科學(xué)版，2013，30（8）:15-18

［2］ZHANG L，ZHOU W J，LI D H.A Descent Modified Polar-Ribiere and Polyak Conjugate Gradient Method with Armijo-type Line Search［J］.IMA Journal of Numerical Analysis，2006（26）:629-640

［3］孟繼東，杜學(xué)武.Armijo型線搜索一個(gè)修正LS共軛梯度法的全局收斂性［J］.重慶師范大學(xué)學(xué)報(bào):自然科學(xué)版，2012（6）:6-8

［4］DAI Y H.Convergence Properties of Nonlinear Conjugate Gradient Methods［J］.SIAM Journal on Optimization，1999（10）:345-358

［5］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

［6］ZHANG L，ZHOU W，LI D.Some Descent Three-term Conjugate Gradient Methods and Their Global Convergence［J］.Optim Methods Softw，2007（22）:697-711

［7］ZHANG L，ZHOU W，LI D.Global Convergence of a Modified Fletcher-reeves Conjugate Gradient Method with Armijo-type Line Search［J］.Numerische Mathematik，2006（104）:561-572