求解非光滑优化问题的修正HS三项共轭梯度法

黎勇 王松华

摘要：为了提高大规模非光滑优化问题的求解效率，克服其他方法存储需求大、算法复杂等缺点，提出求解非光滑优化问题的一种修正HS共轭梯度算法。在经典HS三项共轭梯度法的基础上提出一种新的搜索方向，并利用MoreauYosida正则化技术和Armijotype线搜索技术进行设计。新算法满足充分下降条件，搜索方向属于信赖域，在适当条件下证明了新算法全局收敛。初步的数值实验表明新算法在求解非光滑无约束优化问题方面比LMBM方法更有效。新算法不仅具有较好的收敛性质，而且数值表现良好，为更加高效地求解非光滑优化问题提供了新的方法。

关键词：最优化；非光滑优化；共轭梯度法；充分下降条件；信赖域；全局收敛性

中图分类号：O224MSC（2010）主题分类：49J25文献标志码：A

收稿日期：20170821；修回日期：20171210；责任编辑：张军

基金项目：国家自然科学基金（11661001，11661009）；广西教育厅科研项目（YB2014389）；广西中青年教师能力提升项目（KY2016YB417）

第一作者简介：黎勇（1973—），男，广西靖西人，副教授，硕士，主要从事最优化理论与方法方面的研究。

Email：liyong3922@163.com

黎勇，王松华.求解非光滑优化问题的修正HS三项共轭梯度法[J].河北科技大学学报，2018，39（2）：142148.

LI Yong，WANG Songhua.A modified threeterm HS conjugate gradient method for solving nonsmooth minimizations[J].Journal of Hebei University of Science and Technology，2018，39（2）：142148.A modified threeterm HS conjugate gradient method

for solving nonsmooth minimizations

LI Yong，WANG Songhua

（School of Mathematics and Statistics， Baise University， Baise， Guangxi 533000， China）

Abstract：To improve the efficiency for largescale nonsmooth optimization problems and overcome the large storage requirements and complex computation of other algorithms， a modified HS conjugate gradient algorithm for nonsmooth optimization problems is proposed. A new search direction based on the classical HS conjugate gradient method is given， then the MoreauYosida regularization technique and the Armijotype line search technique are used to design the algorithm. The sufficient descent condition and the trust region are satisfied for this algorithm. Under suitable conditions， the global convergence of the new algorithm is proved. The preliminary numerical experiments show that the new algorithm is more efficient than the LMBM method for nonsmooth unconstrained optimization problems. The presented algorithm is efficiently for solving nonsmooth optimization problems since it has good convergence property and good numerical performance.

Keywords：optimization； nonsmooth optimization； conjugate gradient method； sufficient descent； trust region； global convergence

非線性共轭梯度法被广泛应用于最优化问题的求解方面，该算法简单、存储需求小。在长期的研究过程中，学者们设计出了PRP[12]，HS[3]，LS[4]，FR[5]等一批经典的共轭梯度算法。研究结果表明，充分下降条件是共轭梯度法的一个重要性质，对算法的全局收敛等性质的影响非常关键[610]。近年来共轭梯度法的研究新成果不断出现，如WEI等[11]提出的WYL共轭梯度法，该算法不仅收敛性质较好，而且数值方面的表现也比较出色。 YAO等[12]对WYL算法做了进一步推广，提出了一种修正的HS共轭梯度法，其公式定义河北科技大学学报2018年第2期黎勇，等：求解非光滑优化问题的修正HS三项共轭梯度法 如下：βMHSk=gTk（gk-‖gk‖‖gk-1‖gk-1）（gk-gk-1）Tdk-1。ZHANG等[13]为了保证搜索方向自动具有充分下降性质，提出了一种三项PRP共轭梯度法，该算法的搜索方向定义如下：dk=-gk，if k=0，-gk+βPRPkdk-1-θkyk-1，if k≥1，式中θk=gTkdk-1‖gk-1‖2，yk-1=gk-gk-1，迭代公式为xk+1=xk+tkdk， tk是步长。这样建立的算法能自动满足充分下降条件，因而具有良好的收敛性质。

共轭梯度法目前主要被应用于光滑优化问题的求解，特别是对大规模优化问题，其效果相对于牛顿法、拟牛顿法、信赖域法等优化方法更为明显。针对大规模非光滑凸优化问题，如金融、图形图像、生物工程、最优控制、信息技术等方面研究，能否充分利用共轭梯度法的特点来有效解决非光滑优化问题，研究成果还比较少。文献＼[14＼]和文献＼[15＼]分别提出了新的修正PolakRibièrePolyak和修正HestenesStiefel共轭梯度法，这些算法通过利用MoreauYosida正则化技术，并结合Armijotype线搜索，能够有效解决非光滑凸优化问题。胡亚萍[16]结合MoreauYosida正则化技术、邻近点算法提出求解无约束非光滑凸优化问题的修正LS算法和修正WYL算法。本研究将在文献＼[12＼]和文献＼[13＼]基础上，利用文献＼[14-16＼]的思想设计一种新的修正HestenesStiefel共轭梯度算法，讨论其在求解大规模非光滑凸优化问题中的收敛性质和数值表现。

1预备知识

为方便后面的讨论，给出非光滑凸优化问题的相关理论知识。

针对非光滑无约束优化问题：min{f（x）|x∈Rn}， （1）其中目标函数f：Rn→R是非光滑凸函数。

对目标函数f施行MoreauYosida正则化后得到新函数F：Rn→R，F（x）=minz∈Rn{f（z）+12μ‖z-x‖2}，（2）这里‖·‖指欧几里得范数，参数μ>0。令Q（z，x）=f（z）+12μ‖z-x‖2，且令h（x）=arg minzQ（z，x），由于Q（z，x）对每一个固定的x强凸，故h（x）唯一。因此F（x）=f（h（x））+12μ‖h（x）-x‖2。

由文献＼[17—19＼]可知F（x）具有以下性質：

i）F（x）是有界凸函数，且处处可微。令：g（x）=ΔF（x）=x-h（x）μ ，（3）则g（x） Lipschitz连续，即‖g（x）-g（y）‖≤1μ‖x-y‖，x，y∈Rn。（4）ii）x是问题（1）的最优解，当且仅当ΔF（x）=0时，有h（x）=x。

从上述讨论容易知道，只要求出arg minzQ（z，x）的最优解，F（x）和g（x）就可以确定下来。然而求出arg minzQ（z，x）=h（x）的精确解是非常困难的，甚至是不可能完成的任务。因此在实际计算中不可能用精确的h（x）去定义F（x）和g（x）。文献＼[20＼]给出了如下近似替换的思路与方法。

对x∈Rn，ε>0，存在向量hα（x，ε）∈Rn，使得：f（hα（x，ε））+12μ‖hα（x，ε）-x‖2≤F（x）+ε，（5）当ε充分小时可用hα（x，ε）近似定义F（x）和g（x）表示如下：Fα（x，ε）=f（hα（x，ε））+12μ‖hα（x，ε）-x‖2，（6）

gα（x，ε）=x-hα（x，ε）μ。 （7）从文献＼[20＼]可知，Fα（x，ε）和gα（x，ε）具有以下性质。

命题1假设式（5）—式（7）成立，则有：F（x）≤Fα（x，ε）≤F（x）+ε，（8）

‖hα（x，ε）-h（x）‖≤2με，（9）

‖gα（x，ε）-g（x）‖≤2ε/μ。（10） 命题说明，当ε充分小，Fα（x，ε）和gα（x，ε）可以无限接近F（x）和g（x）。其证明详见文献＼[20＼]。

2修正HS三项共轭梯度法

在文献＼[12-15＼]基础上，笔者提出一种求解非光滑无约束凸优化问题（1）的修正HS三项共轭梯度法，其搜索方向定义如下：dk+1=-gα（xk+1，εk+1）+gα（xk+1，εk+1）Ty*kdk-dTkgα（xk+1，εk+1）y*kmax{2c‖dk‖‖y*k‖，|dTkyk|}，if k≥1，-gα（xk+1，εk+1），if k=0，（11）式中：dk是搜索方向，且y*k=gα（xk+1，εk+1）-‖gα（xk+1，εk+1）‖‖gα（xk，εk）‖gα（xk，εk），yk=gα（xk+1，εk+1）-gα（xk，εk），常数c>0。在此基础上提出新算法。

算法1

Step1选择初始值x0∈Rn，取σ∈（0，1），c>0，s>0，μ>0，d0=-gα（x0，ε0），γ∈[0，1]，令k=0。

Step2如果‖gα（xk，εk）‖<γ，则停止运算，否则进行下一步。

Step3选择一个εk+1，满足0<εk+1<εk，通过非单调Armijotype线搜索[21]确定步长tk：Fα（xk+tkdk，εk+1）-Fα（xk，εk）≤σtkgα（xk，εk）Tdk，（12）其中tk=s2-ik，ik∈{0，1，2，…}。

Step4定义xk+1=xk+tkdk，如果‖gα（xk+1，εk+1）‖<γ，则停止运算；否则，进行下一步。

Step5利用式（11）计算dk+1。

Step6令k：=k+1，返回Step2。

引理1对所有k∈N∪{0}，有：gα（xk，εk）Tdk=-‖gα（xk，εk）‖2。（13）证明

当k=0时，d0=-gα（x0，ε0），命题成立。

当k≥1时，式（11）两边同时乘以gα（xk+1，εk+1）得：

dTk+1gα（xk+1，εk+1）=-‖gα（xk+1，εk+1）‖2+

[gα（xk+1，εk+1）Ty*kdk-dTkgα（xk+1，εk+1）y*kmax{2c‖dk‖‖y*k‖，|dTkyk|}]Tgα（xk+1，εk+1）=

-‖gα（xk+1，εk+1）‖2。

命题成立。

综上所述，命题对所有k∈N∪{0}都成立。

引理2对k∈N∪{0}，有：

‖dk‖≤（1+1c）‖gα（xk，εk）‖。（14）

证明由于max{2c‖dk‖‖y*k‖，|dTkyk|}≥2c‖dk‖‖y*k‖，所以式（11）两边同取范数得：

‖dk+1‖=-gα（xk+1，εk+1）+gα（xk+1，εk+1）Ty*kdk-dTkgα（xk+1，εk+1）y*kmax{2c‖dk‖‖y*k‖，|dTkyk|}≤

‖gα（xk+1，εk+1）‖+gα（xk+1，εk+1）Ty*kdk-dTkgα（xk+1，εk+1）y*kmax{2c‖dk‖‖y*k‖，|dTkyk|}≤

‖gα（xk+1，εk+1）‖+‖gα（xk+1，εk+1）‖‖y*k‖‖dk‖+‖dk‖‖gα（xk+1，εk+1）‖‖y*k‖max{2c‖dk‖‖y*k‖，|dTkyk|}≤

‖gα（xk+1，εk+1）‖+‖gα（xk+1，εk+1）‖‖y*k‖‖dk‖+‖dk‖‖gα（xk+1，εk+1）‖‖y*k‖2c‖dk‖‖y*k‖≤

（1+1c）‖gα（xk+1，εk+1）‖。

引理1说明本研究所提出的算法不需要线搜索即可满足充分下降条件。引理2说明搜索方向具有有界性，即搜索方向具有信赖域性质。

3全局收敛性

以下是算法1的全局收敛性讨论中需要用到的假设。

假设Ai）对ξk∈[xk，xk+1]和k∈N，存在一个正的常数ρ，使得：‖Δ2F（ξk）‖≤ρ，（15）其中F是目标函数f经MoreauYosida正则化后所得到的函数。

ii）函数F有下界。

iii）序列{εk}收敛于0。

引理3设序列{xk}由算法1产生，假设A成立，如果εk=o（t2k‖dk‖2），则对充分大的k，存在一个正的常数l，使tk≥l。 （16）证明反证法。

假设结论不成立，则存在t′k=tk2，使式（12）不成立，即：

Fα（xk+t′kdk，εk+1）-Fα（xk，εk）>σt′kgα（xk，εk）Tdk。

根据式（8）和假设A，并利用泰勒展开式，有：

σt′kgα（xk，εk）Tdk

F（xk+t′kdk）+εk+1-Fα（xk，εk）≤

F（xk+t′kdk）-F（xk）+εk+1=

F（xk）+t′kdTkg（xk）+ΔF2（ξk）（t′kdk）22-F（xk）+εk+1=

t′kdTkg（xk）+（t′k）2dTkΔF2（ξk）dk2+εk+1≤

t′kdTkg（xk）+ρ2（t′k）2‖dk‖2+εk+1，（17）

式中ξk=xk+at′kdk，a∈（0，1）。从式（17）出发，根据式（10）、式（13）和式（14）及εk+1≤εk，结合εk=o（t2k‖dk‖2），有：

tk2=t′k≥σgα（xk，εk）Tdk-dTkg（xk）-εk+1t′kρ2‖dk‖2>

[（gα（xk，εk）-g（xk））Tdk-（1-σ）gα（xk，εk）Tdk-εk+1t′k‖dk‖2]2ρ≥

[（1-σ）‖gα（xk，εk）‖2-2εkμ‖dk‖-εkt′k‖dk‖2]2ρ=

[（1-σ）‖gα（xk，εk）‖2‖dk‖2-o（tk）μ-o（tk）]2ρ，

两边同时除以tk，并取极限得：

12≥limk→∞ （2（1-σ）ρ（1+1c）2-o（tk））1tk≥+∞，

矛盾，故结论成立。

定理1设序列{xk}，{tk}由算法1产生，假设A成立，εk=o（t2k‖dk‖2），则limk→∞‖g（xk）‖=0，且序列{xk}的聚点是问题（1）的最优解。

证明要证明limk→∞ ‖g（xk）‖=0，只需證明limk→∞‖gα（xk，εk）‖=0（18）即可，采用反证法。假设式（18）不成立，则存在正的常数η0和k0，使得对k>k0，有：‖gα（xk，εk）‖≥η0。（19）从式（12）出发，利用式（13）、式（16）、式（19），得：

Fα（xk+1，εk+1）-Fα（xk，εk）≤σtkgα（xk，εk）Tdk=-σtk‖gα（xk，εk）‖2≤-σlη0，k>k0，

所以有：∑k>k0（Fα（xk，εk）-Fα（xk+1，εk+1））≥∑k>k0σlη0，由此易知，当k→∞时，Fα（xk，εk）→∞，与假设A中条件ii）矛盾。因此式（18）成立。

下面证明第2个结论。

由式（10）有：

‖gα（xk，εk）-g（xk）‖≤2εkμ，

根据假设A中条件iii），可得：

limk→∞ ‖g（xk）‖=0。 （20）

令x*是序列{xk}的聚点，则存在子序列{xk}K满足：

limk∈K，k→∞ xk=x*。 （21）

根据式（3）以及F（x）的性质易知g（xk）=xk-h（xk）μ，因此由式（20）和式（21）可知x*=h（x*）成立，故x*是问题（1）的最优解。

4数值结果

笔者通过数值试验来考查本研究所提出的算法解决非光滑优化问题的有效性。试验的计算机环境为Windows7+Fortran90，内存2.0 GB，各参数选取为s=μ=1，σ=0.8，εk=1/（k+2）2；终止条件为‖gα（x，ε）‖≤10-15或者迭代次数Ni>104。测试问题选自文献＼[12＼]，测试程序是利用Fortran语言在文献＼[12＼]所提供程序基础上修改而得，新方法的实验结果将与文献＼[22＼]所提出的LMBM（limited memory bundle method）方法从Ni，Nf和f（x）等几方面进行比较。其中Ni为迭代次数，Nf表示函数值的计算次数，f（x）为近似最优点的函数值。

測试问题名称及初始点在表1中列出，2种方法数值试验的结果在表2中列出，其中Problem表示测试问题的名称，x0表示初始点，Dim表示维数。

分别对6个测试函数的4种不同维数进行测试比较，从表2可以看出，本研究所提出的新算法与求解非光滑问题的传统LMBM算法相比较优势明显。综上所述，新算法不仅具有较好的收敛性质，而且数值表现良好，因此可以认为它能够有效求解非光滑优化问题。

5结论

非线性共轭梯度法算法简单，存储需求小，是一种重要的优化方法，HS方法是其中被广泛讨论和运用的一种方法。本文针对非光滑优化问题的求解，在经典HS共轭梯度法的基础上，通过利用MoreauYosida正则化技术和文献＼[21＼]所提出的Armijotype线搜索技术，设计了一种修正HS共轭梯度算法。笔者所设计的算法不仅可以自动具有充分下降性，而且相应的搜索方向属于信赖域。在适当条件下，证明了新算法是全局收敛的。初步的数值试验表明新算法在求解非光滑无约束优化问题方面是有效的。

在接下来的工作中，还有很多相关问题值得做进一步的思考和讨论，如新算法的收敛速度，各种参数的不同选择对算法效率的影响等，以及新算法在解决金融、图形图像、生物工程、最优控制、信息技术等实际问题所蕴含的非光滑问题时的效果，这些都有待在以后工作中继续检验和测试。

参考文献/References：

[1]POLAK E， RIBIERE G. Note surla convergence de method de directions conjugees[J]. Rev Francaise informat Recherche Opèrationelle， 3e Annèe， 1969， 16（16）： 3543.

[2]POLYAK B T. The conjugate gradient method in extremal problems[J]. Ussr Computational Mathematics and Mathematical Physics， 1969， 9（4）： 94112.

[3]HESTENES M R， STIEFEL E. Method of conjugate gradient for solving linear systems[J]. Journal of Research of the National Bureau of Standards， 1952， 49（6）： 409436.

[4]LIU Y， STOREY C. Efficient generalized conjugate gradient algorithms， part 1： Theory[J]. Journal of Optimization Theory and Applications， 1991， 69（1）： 129137.

[5]FLETCHER R， REEVES C. Function minimization by conjugate gradients[J]. Computer Journal， 1964， 7（2）： 149154.

[6]GILBERT J C， NOCEDAL J. Global convergence properties of conjugate gradient methods for optimization[J]. Siam Journal on Optimization， 1992， 2（1）： 2142.

[7]HU Y F， STOREY C. Global convergence result for conjugate gradient methods[J]. Journal of Optimization Theory & Applications， 1991， 71（2）： 399405.

[8]ZENG X W， GUO Y L， LI Q Q. Global convergence of the PolakRibièrePolyak conjugate gradient methods with inexact line search for nonconvex unconstrained optimization problems[J]. Mathematics of Computation， 2008， 77（264）： 21732193.

[9]TOUATIAHMED D， STOREY C. Efficient hybrid conjugate gradient techniques[J]. Journal of Optimization Theory & Applications，1990， 64 （2）： 379397.

[10]ALBAALI M. Descent property and global convergence of the FlecherReves method with inexact line search[J]. Ima Journal of Numerical Analysis， 1985， 5（1）： 121124.

[11]WEI Z X， YAO S W， LIU L Y. The convergence properties of some new conjugate gradient methods[J]. Applied Mathematics and Computation， 2006， 183（2）： 13411350.

[12]YAO S W， WEI Z X， HUANG H. A note about WYLs conjugate gradient method and its applications[J]. Applied Mathematics and Computation， 2007， 191（2）： 381388.

[13]ZHANG L， ZHOU W J， LI D H. A descent modified PolakRibièrePolyak conjugate gradient method and its global convergence[J]. Ima Journal of Numerical Analysis， 2006， 26（4）： 629640.

[14]YUAN G L， WEI Z X， LI G Y. A modified PolakRibièrePolyak conjugate gradient algorithm for nonsmooth covex programs[J]. Journal of Computational and Applied Mathematics， 2014， 255（1）： 8696.

[15]YUAN G L， MENG Z H， LI Y. A modified Hestenes and Stiefel conjugate gradient algorithm for largescale nonsmooth minimizations and nonlinear equations[J]. Journal of Optimization Theory and Applications， 2016， 168（1）： 129152.

[16]胡亞萍.非线性单调方程组和非光滑优化问题的算法研究[D]. 上海：华东理工大学，2014.

HU Yaping. Numerical Methods for Nonlinear Monotone Equations and Nonsmooth Optimization Problems[D]. Shanghai： East China University of Science and Technology， 2014.

[17]BONNAN J F， GILBERT J C， LEMARECHAL C，et al. A family of variable metric proximal methods[J]. Mathematical Programming， 1995， 68（1）： 1547.

[18]CORREA R， LEMARCHAL C. Convergence of some algorithms for convex minimization[J]. Mathematical Programming， 1993， 62（1/2/3）： 261273.

[19]HIRIARTURRUTY J B， LEMARECHAL C. Convex Analysis and Minimization Algorithms Ⅱ[M]. Berlin：Springer， 1993.

[20]FUKUSHIMA M， QI L. A globally and superlinearly convergent algorithm for nonsmooth convex minimization[J]. Siam Journal on Optimization， 1996， 6（4）： 11061120.

[21]ZHANG H C， HARGER W W. A nonmonotone line search technique and its application to unconstrained optimization[J]. Siam Journal on Optimization， 2006， 14（4）： 10431056.

[22]HAARALA M， MIETTINEN K， MKEL M M. New limited memory bundle method for largescale nonsmooth optimization[J]. Optimization Methods & Software， 2004， 19（6）： 673692.第39卷第2期河北科技大学学报Vol.39，No.2

2018年4月Journal of Hebei University of Science and TechnologyApr. 2018