非單調ARMIJO型線搜索下的新譜共軛梯度法

張穎

共軛梯度方法是解決大規模無約束優化問題的重要方法，從不同角度來研究共軛梯度法有著重要意義.本文在非單調線搜索技術[1]基礎之上，提出的一種新的非單調譜共軛梯度方法，并證明該方法具有充分下降性和全局收斂性.

【關鍵詞】Armijo線搜索；無約束最優化；譜共軛梯度法；全局收斂性

【中圖分類號】O241.5 【文獻標識碼】A

引 言

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

對于無約束優化問題

minx∈Rnf（x）

其中f：Rn→R是連續可微的.

本文構造了一種新的譜共軛梯度法：

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型的非單調線搜索技術[1]：令β>0，γ∈（0，1），取一正的整數M，并且取步長為αk=βγmk，我們要求mk是滿足下面不等式的最小的非整數

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型的非單調線搜索技術構造的譜共軛梯度法的優點在于，數值試驗表明該算法具有良好計算效能，也能用于維數較高的無約束優化問題[5-6].本文證明了新算法不僅具有充分下降性，并在Armijo線搜索下具有全局收斂性.

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

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

（a）目標函數f（x）在如下水平集中有界，

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

其中x0為初始點.

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

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

根據假設（a）和（b），我們容易知道存在一個常數ν，滿足：

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

定理1.1 考慮迭代方法（1）-（4），步長因子ak滿足了非單調步長規則（5），

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

‖dk‖≤H‖gk‖.

證明 （ⅰ）當k=l時，由于d1=-g1，所以我們有‖d1‖=‖g1‖，結論顯然成立，

（ⅱ）當k≥2時，由β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‖.

設H=1+ρmax（1+m）2ρmin，則結論成立.

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

limk→∞αk‖dk‖=0

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

limk→∞inf‖gk‖=0

證明 假設結論不成立，那么存在著一個常數c>0，使得

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

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

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

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

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

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

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

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），我們知道可以得到對任意的k∈I有

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

又由假設（a）與（b），我們容易知道存在一個常數ν，滿足：

‖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.與假設產生矛盾.

綜上，結論成立.

4.結 論

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

【參考文獻】

[1]孫中波，段復建.一類無約束優化的非單調共軛梯度法[J].河北師范大學學報，38（1）：12–15，2010.

[2]莫利柳，洪玲，韋增欣.一類無約束優化問題的非單調譜共軛梯度方法[J].廣西科學.