新Armijo線搜索下的PRP共軛梯度法及其收斂性分析

韋春妙　龐建華　黃李韋　羅杰明

摘??? 要：優化算法研究，主要工作是給迭代點尋求可接受且有效的步長及可行的下降方向.在求解大規模無約束優化問題時，共軛梯度法被廣泛應用.其中， Polak-Ribiere-Polyak方法（簡稱：PRP方法）是眾多共軛梯度法中數值表現相對較好的，但它在許多線搜索下并不具備全局收斂性，如何發揮PRP方法數值優良，而克服其收斂性差，是學者們致力探索的熱點課題.本文提出新的PRP參數公式，并對Armijo線搜索方法進行修正，建立了新Armijo線搜索下的PRP共軛梯度算法，證明算法滿足充分下降條件，并證明算法在適當條件下具有全局收斂性.

關鍵詞：無約束優化; PRP共軛梯度法;新Armijo線搜索;全局收斂性

中圖分類號： O224??????????? DOI：10.16375/j.cnki.cn45-1395/t.2019.02.016

0??? 引言

諸多領域如工業、農業、經濟等很多最優化問題，都可以歸結為大規模的無約束優化問題.本文考慮無約束優化問題：

[min f（x） ， x∈Rn]??? []??????????????????????????????????????????????????????????????? （1）

其中[f]：[Rn→R]為連續可微函數.

求解式（1）的方法有很多， 共軛梯度法是最為常用的方法之一. 共軛梯度法的研究已有五十多年的歷史， 由于其具有較低的存儲量與較小的計算量等特性，被學者們廣泛研究.著名數學家Beale等，把該方法應用到非線性優化問題中并取得了顯著性成果.經典的共軛梯度法有Fletcher-Reeves方法[1]（簡稱[FR]法）、Hestenses-Stiefel方法[2]（簡稱[HS]法）、Dai-Yuan方法[3]（簡稱[DY]法）、Polak-Ribiere-Polyak方法[4]（簡稱[PRP]法），這些方法中，[FR]法收斂速度慢，數值計算不理想;[HS]法采用精確線搜索時，若目標函數是非凸函數，此方法通常不具有全局收斂性.而[DY]法在特定的線搜索下，不能完全使得算法滿足充分下降條件， Al-Baali[[5]]，Gilbert等[[6]]證明了在某些線搜索下，除了滿足基本條件，[DY]法需具備更多條件才具有全局收斂性.[PRP]方法是當今眾多方法中，公認的數值表現較優的共軛梯度法.當運用[PRP]共軛梯度法在極小點附近產生小步長時，它后續所生成的搜索方向[dk]會自動向負梯度方向靠近，從而有效地避免[FR]方法中出現不斷產生小步長的問題.不僅如此，[PRP]方法同時可以有效解決存儲空間過大的問題.但是在非精確線搜索下，即使[PRP]方法有比較好的數值結果，在全局收斂性上卻并不優良.許多學者不斷探究，獲得了可喜的結論，韋增欣等[7]提出了一個非精確[Armijo]線搜索的[PRP]算法，并證明了非凸無約束優化問題在所提算法下具有全局收斂性.本研究將[Armijo]線搜索進一步修正，建立一個新的共軛梯度算法，并證明了在此線搜索下算法具有全局收斂性.

共軛梯度法的通常迭代格式為：

[xk+1=xk+ikdk， k=0，? 1，? 2，? 3，? 4，? …]????????????????????????????????????????? （2）

其中，[xk]表示第[k]次迭代，[ik]為第[k]次的步長，[dk]表示第[k]次搜索的方向，一般共軛梯度法的搜索方向定義為：

[dk=-gk， ???????????????? k=0 ;-gk+βkdk-1， k>0;]???????????????????????????? （3）

其中，[gk=?f（xk）]， [βk]是調控參數. [βk]由于有不同的取法，因而產生了不同方法.

如何沿著搜索方向[dk]找到一個適合的步長因子[ik]是很重要的，比較常用的線搜索方法有：Wolfe-Powell型線搜索，Armijo-Goldstein型線搜索等.韋增欣等[7]運用上述準則研究[PRP]方法的全局收斂性，并且提出一種線搜索Armijo-Type [line] [search]（ATLS）方法.方法如下：

令[α∈[0，12）]，[c∈（0，1）]，[μ>0].令[tk]=[ρjk]，則：

[f（xk+ρjdk）-f（xk）≤αρjgTkdk-μ2（ρj）2dk2]

上式中，[α]、c、p為介于0和1之間的常數，[μ]為非負常數，[jk]是使得式子成立的最小非負整數[j]，且

[g（xk+ρjdk）TQPRPk（j）≤-cg（xk+ρjdk）2]

其中T表示轉置，[QPRPk（j）]定義為：

[QPRPk（j）=-g（xk+ρjdk）+g（xk+ρjdk）Tg（xk+ρjdk）-gkgk2dk]

證明了[PRP]方法在此線搜索下，滿足充分下降條件：

[gTkdk≤-cgk2]，[c∈（0，1）]?????????????????????????? （4）

本文嘗試了一個新的線搜索Armijo-Type [line] [search]（簡記ATLS*），對于搜索方向，基于經典的[βPRPk]，本文提出新的[PRP]參數公式：

[β*k=gTk2gk-1-gkgkgk-gk-1gTkgk-1].??????????????????????? （5）

1??? 算法描述

1.1?? ATLS*線搜索與算法

首先，令[ik=ρjk]，[ik]為步長因子，[jk]是使下列式子成立的最小的非負整數[j]，

[f（xk+ρjdk）-f（xk）≤αρjgTkdk-μ2（ρj）2dk2]????????????????? （6）

且有

[g（xk+ρjdk）TQ*k（j）≤-cg（xk+ρjdk）2]???????????????????? （7）

其中[Q*k（j）]定義為：

[Q*k（j）=-g（xk+ρjdk）+g（xk+ρjdk）T2gk-g（xk+ρjdk）g（xk+ρjdk）g（xk+ρjdk）-gkgk2dk]??? （8）

其次，對目標函數[f（x）]進行如下假設：

假設1?? [φ={x∈Rn：? f（x）≤f（x1）}]是一個有界的水平集.

假設2?? [f（x）]是連續可微的函數，[f（x）]的梯度[Lipschitz]連續.即存在常數[L>0]，使得對[?x，y∈φ]都有[g（x）-g（y）≤Lx-y].

引理1? 若對于[?k∈N，? gTkdk<0]，就存在一個非負整數[jk]，使[ik=ρjk]滿足新的[ATLS*]線搜索算法（6）—?????? 算法（8），其中[α∈[0， 12） ，? μ>0].

證明? 首先證明有[j0].對于所有[j>j0]，使得式（6）成立.用反證法證明.

假設對于任意[j]：

[f（xk+ρjdk）-f（xk）>αρjgTkdk-μ2（ρj）2dk2].

由泰勒展開式有：

[ρjgTkdk+ο（ρj）>αρjgTkdk-μ2（ρj）2dk2].

不等式兩邊除以[ρj]并且令[j→∞]，得到：

[gTkdk≥αgTkdk].

因此，由[gTkdk<0]，可得[α>1].與[α∈[0，1/2）]相違背.

其次，證明存在[j1∈（j0，+∞）]使得式（7）成立.假設結論不成立，對于任意[j>j0]，有：

[g（xk+ρjdk）TQ*k（j）>-cg（xk+ρjdk）2]?????????????????? （9）

將[Q*k（j）]代入式（9），即：

[g（xk+ρjdk）TQ*k（j）=-g（xk+ρjdk）2+g（xk+ρjdk）T2gk-g（xk+ρjdk）g（xk+ρjdk）g（xk+ρjdk）-gkgk2g（xk+ρjdk）Tdk>-cg（xk+ρjdk）2]

令[j∈（j0，+∞）]且[j→∞]，又由[g]的連續性可得：

[-gk2≥-cgk2]

由[gk≠0]（0——零向量）知[c>1].與[c∈（0， 1）]相矛盾.

綜上所述，存在一個[jk]使得式（6）和式（7）成立.

1.2?? 新ATLS*線搜索下的PRP算法（簡稱新ATLS*算法）

Step 1? 給定初值[x1∈χn， α∈[0， 1/2） ， c∈（0， 1） ， μ>0.]令[d1=-g1， k=1.]若[g1=0]，則停止，否則轉Step 2.

Step 2? 求出滿足新[ATLS*]線搜索式（6）—式（8）的步長[ik>0].

Step 3? 迭代公式為：[xi+1=xi+ikdk， gk+1=g（xk+1）.]若[gk+1=0]，則停止，否則轉Step 4.

Step 4? 由式（5）計算[βk+1]，由式（3）計算[dk+1].

Step 5? 令[k=k+1]，轉Step 2.

2??? 算法的收斂性分析

引理2? 考慮上述算法，對于[?k∈N]，若[gTkdk<0]，則：

[gTk+1dk+1≤-cgk+12].??????????;????????????????? （10）

證明 根據引理1，由新[ATLS*]線搜索產生的步長，并由上列算法可以得到迭代點[xk+1]，[gk+1]，[βk+1]，[dk+1].

所以

[gTk+1dk+1=-gk+12+β*k+1gTk+1dk=- gk+12+gTk+12gk-gk+1gk+1gk+1-gkgk2gTk+1dk=]

[-g（xk+ikdk）2+g（xk+ikdk）T2gk-g（xk+ikdk）g（xk+ikdk）g（xk+ikdk）-gkgk2g（xk+ikdk）Tdk=g（xk+ρjdk）TQ*k（j）]

因為[ik]滿足式（7），所以

[gTk+1dk+1][=g（xk+ρjdk）TQ*k（j）][≤-cgk+12]

即式（10）成立.

定理1? 對新ATLS*線搜索下的PRP算法，如果[gk≠0]，則對[?k>0]，有[gTkdk≤-cgk2]，[c∈（0，1）]，即算法充分下降.

證明? 假設[g1≠0]，因為[d1=-g1]，那么[gT1d1=-g12≤-cg12].如果[gk≠0]，則有[gTkdk≤-cgk2<0]，且[c∈（0，1）]，有引理2可得：

[gTk+1dk+1≤-cgk+12]

通過數學歸納法便可推出定理1.

引理3?? 當假設1成立時，有：

[limk→∞ikdk=0 ，]?????????????????????????? （11）

與

[limk→∞-ikgTkdk=0 .]????????????????????????? （12）

證明?? 因為[{f（xk）}]是遞減序列，而由新ATLS*算法產生的序列[xk]包含于[φ]，由假設1，存在一常數[f1]使得

[limk→∞f（xk）=f1 .]

那么，

[k=1∞（f（xk）-f（xk+1））=limk→∞k=1∞（f（xk）-f（xk+1））]

[limN→∞（f（x1）-f（xN+1））=f（x1）-f1]

則：

[k=1∞（f（xk）-f（xk+1））<+∞].

又由式（6）得：

[f（xk+ikdk）-f（xk）≤αikgTkdk-μ2（ik）2dk2]，

所以，[k=1∞i2kdk2<∞且 k=1∞-ikgTkdk<∞]，因此，式（11）與式（12）成立.

引理4? 如果假設1和假設2均成立，[xk]由新ATLS*算法得到，存在一個常數[M1>0]使得對[?k]，有

[ik≥M1gk2dk2].

證明?? 分成如下情形證明：

情形1?? [ik=1]時有：

[gk2≤1cgTkdk≤1cgkdk]

由式（10），有：

[gk≤1cdk]

由[ik=1]有：

[gk2≤1c2dk2=ikc2dk2]

所以

[ik≥c2gk2dk2]

情形2?? [ik<1]時，有[jk-1]是一個非負整數，從對[ik]的定義（6）不能都滿足[ikρ=ρjk-1].

因為[ikρ]不滿足式（6），有：

[f（xk+（ikρ）dk）-f（xk）>α（ikρ）gTkdk-μ2（ikρ）2dk2].

運用中值定理得到[θk∈（0，1）]，有：

[（ikρ）?g（xk+θk（ikρ）dk）Tdk>α（ikρ）gTkdk-μ2（ikρ）2dk2]

兩邊除以[ikρ]，有：

[g（xk+θk（ikρ）dk）Tdk>αgTkdk-μ2（ikρ）dk2]

不等式兩邊減去[gTkdk]，有：

[（g（xk+θk（ikρ）dk）-gk）Tdk>-（1-α）gTkdk-μ2（ikρ）dk2，]

結合假設2有：

[Lθk（ikρ）dk2>-（1-α）gTkdk-μ2（ikρ）dk2].

因此，

[ik>2（1-α）ρ2Lθk+μ（-gTkdk）dk2].

故由式（4）與[θk∈（0，1）]，有：

[ik>2c（1-α）ρ2Lθk+μgTk2dk2≥2c（1-α）ρ2L+μgTk2dk2]

綜上情形1和情形2得證.

令：????????????????????????????????????????????????? [M1=minc2， 2（1-α）ρ2L+μ]，

引理4? 得證.

引理5? 如果假設1和假設2均成立，且對于[?k，?ε>0，]使得

[gk≥ε]&nbsp;???????????????????????????????? （13）

即有常數[M2>0]，對[?k]有：

[dk≤M2]????????????????????????????????????? （14）

證明? 運用Cauchy-schwartz不等式，由式（3）有：

[dk≤gk+β*kdk-1≤gk+gTk2gk-1-gkgkgk-gk-1gk-12dk-1≤gk+gk?2gk-1-gkgkgk-gk+gk-gk-1gk-12?dk-1≤gk+gk2gk-1-gkgkgk-gk+gk-gk-1gk-12?dk-1≤gk+（2gk-1-gk）gk-（gk）gk+gkgk-gk-1gk-12?dk-1≤gk+2（gk-1-gk）gk+gkgk-gk-1gk-12?dk-1≤gk+2gk-1-gkgk+gkgk-gk-1gk-12?dk-1≤gk+3gk?gk-gk-1gk-12 dk-1]

再由假設2和式（13）可得：

[dk≤gk+3L gk?xk-xk-1gk-12 dk-1≤gk+ gk 3Lik-1dk-1ε2 dk-1]???????? （15）

由于[xk]是有界序列，結合假設2有，存在[M3>0]，使得對[?k]，

[gk≤M3]?????????????????????????????????? （16）

所以由式（15）和式（16）有：

[dk≤M3+3M3Lε2ik-1dk-12=M3+3M3Lε2ik-1dk-1dk-1]????????????? （17）

又由引理[3]的式（11）可推出：存在一個常數[q∈（0，1）]與一個整數[k0]，對[?k≥k0]時，有[3M3Lε2ik-1dk-1≤q].因此對于[?k>k0]，由式（17）得：

[dk≤M3+qdk-1≤M3（1+q+q2+…+qk-k0-1）+qk-k0dk0≤?????????? M31-q+qk-k0dk0≤M31-q+dk0]

令[M2=maxd1 ，? d2 ，…，? dk0 ，? M31-q+dk0]，那么式（14）對[?k]成立.

定理2?? 若上述假設1和假設2均成立，那么有：

[limk→∞infgk=0].?????????????????????????????? （18）

證明?? 首先，假設定理2不成立，則存在一個常數[ε>0]，對[?k]，有

[gk≥ε.]????????;??????????????????????? （19）

結合引理4，即存在一個常數[M1≥0]，對于[?k， ik≥M1gk2dk2]，再由引理5有[gk2≤M2M1ikdk]，令[k→∞]，結合式（11）與該不等式可以得到和式（19）相矛盾的結論，所以式（18）成立，即證明了全局收斂性.

3??? 討論

構造有效的全局優化算法[8-9]， 通常是在已有算法的基礎上不斷改進和創新.如何選取有效的非精確線搜索使得[PRP]共軛梯度法具有全局收斂性，是研究[PRP]法理論部分的難點所在，與之相關研究結果相對較少，本文所構造的新ATLS*線搜索，其形式比較復雜，但并不影響算法的全局收斂性，在一定程度上豐富了[PRP]共軛梯度法的理論研究.

4??? 結論

[PRP]共軛梯度法的優良數值效果獲得了大家的青睞， 然而，優化算法的理論研究是最優化理論與算法的一個重要內容，遺憾的是，[PRP]共軛梯度法的全局收斂性在眾多的非精確線搜索下卻沒有全局收斂性.本文在韋增欣教授等研究基礎上，努力尋找并構建合適的線搜索，使[PRP]共軛梯度法具有優良的收斂性，雖然其線搜索的形式較為復雜，但最終證明[PRP]共軛梯度法在新構建的線搜索下具有全局收斂性.

參考文獻

[1]???? FLETCHER R，REEVES C M.Function minimization by conjugate gradients[J].Computer Journal，1964（7）：149-154.

[2]???? HESTENES M R，STIEFEL E. Method of conjugate gradient for solving linear equations[J].Journal of Research National? Bureau of Standards，1952（49）：409-436.

[3]???? DAI Y H，YUAN Y.Convergence properties of the conjugate descent method[J].Advances in Mathematics，1996，25：552-562.

[4]???? POLYAK P T. The conjugate gradient method in extremal problems[J].Ussr Computation Mathematics and Mathematical? physics，1969（9）：94-112.

[5]???? AL-BAALI M. Descent property and global convergence of the Fletcher-Reeves method with inexact line search[J].Ima???? Journal and Numerical Analysis，1985（5）：121-124.

[6]???? GILBERT J C，NOCEDAL J. Global convergence properties of conjugate gradient methods for optimization[J].SIAM Journal of Optimization，1992，2（1）：21-42.

[7]???? WEI Z X， LI G Y ， QI L Q. Global convergence of the Polak-Ribiere-Polyak conjugate method with an Armijo-type inexact line search for nonconvex unconstrained optimization problems[J].Mathematics of Computation，2008，77（264）：2173-2193.

[8]???? 吳慶軍.一個全局收斂的共軛梯度法[J].廣西工學院學報，2004，15（3）：89-92.

[9]???? 朱孝晶，周圓兀，龔熠，等.基于多樣性優化策略的粒子群算法[J].廣西工學院學報，2001，22（1）：74-77.

Global convergence analysis of the Polak-Ribiere-Polyak conjugate gradient method with a new Armijo-type line search

WEI Chunmiao， PANG Jianhua， HUANG Liwei， LUO Jieming

（Science College， Guangxi University of Science and Technology， Liuzhou 545006， China）

Abstract： The optimization algorithm research focuses on finding an acceptable and effective step size and feasible descent direction. The conjugate gradient methods are widely used in solving the???????? large-scale unconstrained optimization problems. Among them， Polak-Ribiere-Polyak method （PRP） has better numerical effect than other conjugate gradient methods. However，the global convergence has not been established for the PRP method with some inexact linear line search . How proposed new line search condition which was designed to get convergence theory to ensure the PRP method is????? globally convergent. At the same time， it remains its excellent numerical effect. In this paper， a new Armijo line searching method with a new parameter formula is proposed. The PRP conjugate gradient algorithm under the new Armijo line search is established. It is proved that the algorithm satisfies the sufficient descent condition and that the algorithm has global convergence under appropriate conditions.

Key words： unconstrained optimization; PRP conjugate gradient method; new Armijo line search;? global convergence