新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