張穎

共軛梯度方法是解決大規(guī)模無(wú)約束優(yōu)化問(wèn)題的重要方法，從不同角度來(lái)研究共軛梯度法有著重要意義.本文在非單調(diào)線搜索技術(shù)[1]基礎(chǔ)之上，提出的一種新的非單調(diào)譜共軛梯度方法，并證明該方法具有充分下降性和全局收斂性.

【關(guān)鍵詞】Armijo線搜索；無(wú)約束最優(yōu)化；譜共軛梯度法；全局收斂性

【中圖分類號(hào)】O241.5 【文獻(xiàn)標(biāo)識(shí)碼】A

引 言

在1998年Barzilai與Borwein[2]提出譜梯度法.在2001年Birgin與Martinez[3]把譜梯度法與共軛梯度法結(jié)合提出一類新的譜共軛梯度法.譜共軛梯度法數(shù)值試驗(yàn)結(jié)果與收斂情況表明，與相應(yīng)的共軛梯度法相比，譜共軛梯度法更有效[4].

對(duì)于無(wú)約束優(yōu)化問(wèn)題

minx∈Rnf（x）

其中f：Rn→R是連續(xù)可微的.

本文構(gòu)造了一種新的譜共軛梯度法：

xk+1=xk+αkdk，（1）

dk=-gk，k=1；-1δkgk+βkdk-1，k≥2.（2）

βk=δk-1uk（‖gk-gk-1‖2）δk（‖gk‖·‖dk-1‖+dTk-1gk-1），0其中

δk=sTk-1yk-1‖sk-1‖2，（sk=xk+1-xk，yk=gk+1-gk）（4）

在線搜索條件的選擇上，在本文中將選擇由Grippo等人提出的一種Armijo型的非單調(diào)線搜索技術(shù)[1]：令β>0，γ∈（0，1），取一正的整數(shù)M，并且取步長(zhǎng)為αk=βγmk，我們要求mk是滿足下面不等式的最小的非整數(shù)

f（xk+βλmkdk）≤max0≤j≤m（k）{fk-1}+σβγmkgkTdk，（5）

其中要求0<σ<1，并且

m（0）=0，0≤m（k）≤min{m（k-1）+1，M}.

利用Armijo型的非單調(diào)線搜索技術(shù)構(gòu)造的譜共軛梯度法的優(yōu)點(diǎn)在于，數(shù)值試驗(yàn)表明該算法具有良好計(jì)算效能，也能用于維數(shù)較高的無(wú)約束優(yōu)化問(wèn)題[5-6].本文證明了新算法不僅具有充分下降性，并在Armijo線搜索下具有全局收斂性.

1.充分下降性及新的譜共軛梯度算法

為了證明充分下降性，我們首先假設(shè)：

（a）目標(biāo)函數(shù)f（x）在如下水平集中有界，

L={x∈Rn|f（x）≤f（x0）}.

其中x0為初始點(diǎn).

（b）f在水平集L的開凸集U連續(xù)可微，并且它的梯度向量g滿足Lipschitz條件，即存在一個(gè)常數(shù)τ，使得：

‖g（x）-g（y）‖≤τ‖x-y‖，x，y∈U

根據(jù)假設(shè)（a）和（b），我們?nèi)菀字来嬖谝粋€(gè)常數(shù)ν，滿足：

‖g（x）‖≤ν，x∈L..

定理1.1 考慮迭代方法（1）-（4），步長(zhǎng)因子ak滿足了非單調(diào)步長(zhǎng)規(guī)則（5），

βk=δk-1uk（‖gk-gk-1‖）δk（‖gk‖·‖dk‖+dTk-1gk-1），0

‖dk‖≤H‖gk‖.

證明 （ⅰ）當(dāng)k=l時(shí)，由于d1=-g1，所以我們有‖d1‖=‖g1‖，結(jié)論顯然成立，

（ⅱ）當(dāng)k≥2時(shí)，由βk的定義和（7）我們有

‖dk‖≤1δk‖gk‖+βk‖dk-1‖

=1δk‖gk‖+dk-1‖gk-gk-1‖2dk（‖gk‖·‖dk-1‖+|dTk-1gk-1|）‖dk-1‖

≤1ρmin‖gk‖+ρmax（1+m）2‖gk‖2ρmin（‖gk‖·‖dk-1‖）‖dk-1‖

≤1+ρmax（1+m）2ρmin‖gk‖.

設(shè)H=1+ρmax（1+m）2ρmin，則結(jié)論成立.

引理3.2 [7]假設(shè)（a）和（b）成立，考慮迭代（1）-（4），為本文算法產(chǎn)生的序列，則有，

limk→∞αk‖dk‖=0

定理3.3 假設(shè)（a）和（b）成立，考慮方法（1）-（2），由式（3）與（4）定義，由單調(diào)線搜索條件（5）決定，則有

limk→∞inf‖gk‖=0

證明 假設(shè)結(jié)論不成立，那么存在著一個(gè)常數(shù)c>0，使得

‖gk‖2≥c，k=1，2，……

如若limk→∞infαk>0，由引理3.2證明的最后，我們知道limk→∞αkgTkdk=0，并且由定理1.1可知limk→∞‖gk‖=0，產(chǎn)生矛盾，

如若limk→∞infαk=0，那么一定存在著無(wú)窮子列I滿足條件：

limk→∞，k∈Iαk=0. （8）

由αk的定義以及γ∈（0，1），我們有αkγ不滿足非單調(diào)線搜索（5），也就是：

fxk+akγdk≥max0≤j≤m（k）{fk-j}+σakγgTkdk≥f（xk）+σakγgTkdk.（9）

由微分中值定理，Lipchitz條件以及引理3.1可知，存在一個(gè)常數(shù)θ，滿足

f（xk+αkγdk）-f（xk）=αkγgxk+θαkγdkTdk

=αkγgTkdk+αkγgxk+θαkγdkTdk-αkγgTkdk

=αkγgTkdk+αkγgxk+θαkγdk-gkTdk

≤αkγgTkdk+Lθα2kγ2‖dk‖2

≤αkγgTkdk+Lθα2kγ2H2‖gk‖2 （10）

由式（9）、（10），我們知道可以得到對(duì)任意的k∈I有

akγgTkdk+Lθa2kγ2H2‖gk‖2≥σakγgTkdk（11）

又由假設(shè)（a）與（b），我們?nèi)菀字来嬖谝粋€(gè)常數(shù)ν，滿足：

‖g（x）‖≤ν，x∈L

整理式（11）我們有

（1-σ）akγgTkdk≥-Lθα2kγ2H2‖gk‖2

≥-Lθα2kγ2H2ν2（12）

由定理1.1，我們知道gTkdk<-N‖gk‖2，由上式我們有

‖gk‖2≤LθH2ν2Hγ（1-σ）αk（13）

由引理3.2與（13），我們可以得到 limk→∞inf‖gk‖=0.與假設(shè)產(chǎn)生矛盾.

綜上，結(jié)論成立.

4.結(jié) 論

本文結(jié)合Grippo等人提出的非單調(diào)線搜索技術(shù)，給出了一種新的非單調(diào)譜共軛梯度法，證明了這種方法在不依賴于線搜索條件的情況下，具有著充分的下降性，并且證明新算法具有全局收斂性.

【參考文獻(xiàn)】

[1]孫中波，段復(fù)建.一類無(wú)約束優(yōu)化的非單調(diào)共軛梯度法[J].河北師范大學(xué)學(xué)報(bào)，38（1）：12–15，2010.

[2]莫利柳，洪玲，韋增欣.一類無(wú)約束優(yōu)化問(wèn)題的非單調(diào)譜共軛梯度方法[J].廣西科學(xué).