求解非光滑優化問題的修正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