求解非光滑優(yōu)化問題的修正HS三項共軛梯度法

黎勇 王松華

摘要：為了提高大規(guī)模非光滑優(yōu)化問題的求解效率，克服其他方法存儲需求大、算法復(fù)雜等缺點，提出求解非光滑優(yōu)化問題的一種修正HS共軛梯度算法。在經(jīng)典HS三項共軛梯度法的基礎(chǔ)上提出一種新的搜索方向，并利用MoreauYosida正則化技術(shù)和Armijotype線搜索技術(shù)進行設(shè)計。新算法滿足充分下降條件，搜索方向?qū)儆谛刨囉?，在適當條件下證明了新算法全局收斂。初步的數(shù)值實驗表明新算法在求解非光滑無約束優(yōu)化問題方面比LMBM方法更有效。新算法不僅具有較好的收斂性質(zhì)，而且數(shù)值表現(xiàn)良好，為更加高效地求解非光滑優(yōu)化問題提供了新的方法。

關(guān)鍵詞：最優(yōu)化；非光滑優(yōu)化；共軛梯度法；充分下降條件；信賴域；全局收斂性

中圖分類號：O224MSC（2010）主題分類：49J25文獻標志碼：A

收稿日期：20170821；修回日期：20171210；責任編輯：張軍

基金項目：國家自然科學(xué)基金（11661001，11661009）；廣西教育廳科研項目（YB2014389）；廣西中青年教師能力提升項目（KY2016YB417）

第一作者簡介：黎勇（1973—），男，廣西靖西人，副教授，碩士，主要從事最優(yōu)化理論與方法方面的研究。

Email：liyong3922@163.com

黎勇，王松華.求解非光滑優(yōu)化問題的修正HS三項共軛梯度法[J].河北科技大學(xué)學(xué)報，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

非線性共軛梯度法被廣泛應(yīng)用于最優(yōu)化問題的求解方面，該算法簡單、存儲需求小。在長期的研究過程中，學(xué)者們設(shè)計出了PRP[12]，HS[3]，LS[4]，F(xiàn)R[5]等一批經(jīng)典的共軛梯度算法。研究結(jié)果表明，充分下降條件是共軛梯度法的一個重要性質(zhì)，對算法的全局收斂等性質(zhì)的影響非常關(guān)鍵[610]。近年來共軛梯度法的研究新成果不斷出現(xiàn)，如WEI等[11]提出的WYL共軛梯度法，該算法不僅收斂性質(zhì)較好，而且數(shù)值方面的表現(xiàn)也比較出色。 YAO等[12]對WYL算法做了進一步推廣，提出了一種修正的HS共軛梯度法，其公式定義河北科技大學(xué)學(xué)報2018年第2期黎勇，等：求解非光滑優(yōu)化問題的修正HS三項共軛梯度法 如下：βMHSk=gTk（gk-‖gk‖‖gk-1‖gk-1）（gk-gk-1）Tdk-1。ZHANG等[13]為了保證搜索方向自動具有充分下降性質(zhì)，提出了一種三項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是步長。這樣建立的算法能自動滿足充分下降條件，因而具有良好的收斂性質(zhì)。

共軛梯度法目前主要被應(yīng)用于光滑優(yōu)化問題的求解，特別是對大規(guī)模優(yōu)化問題，其效果相對于牛頓法、擬牛頓法、信賴域法等優(yōu)化方法更為明顯。針對大規(guī)模非光滑凸優(yōu)化問題，如金融、圖形圖像、生物工程、最優(yōu)控制、信息技術(shù)等方面研究，能否充分利用共軛梯度法的特點來有效解決非光滑優(yōu)化問題，研究成果還比較少。文獻＼[14＼]和文獻＼[15＼]分別提出了新的修正PolakRibièrePolyak和修正HestenesStiefel共軛梯度法，這些算法通過利用MoreauYosida正則化技術(shù)，并結(jié)合Armijotype線搜索，能夠有效解決非光滑凸優(yōu)化問題。胡亞萍[16]結(jié)合MoreauYosida正則化技術(shù)、鄰近點算法提出求解無約束非光滑凸優(yōu)化問題的修正LS算法和修正WYL算法。本研究將在文獻＼[12＼]和文獻＼[13＼]基礎(chǔ)上，利用文獻＼[14-16＼]的思想設(shè)計一種新的修正HestenesStiefel共軛梯度算法，討論其在求解大規(guī)模非光滑凸優(yōu)化問題中的收斂性質(zhì)和數(shù)值表現(xiàn)。

1預(yù)備知識

為方便后面的討論，給出非光滑凸優(yōu)化問題的相關(guān)理論知識。

針對非光滑無約束優(yōu)化問題：min{f（x）|x∈Rn}， （1）其中目標函數(shù)f：Rn→R是非光滑凸函數(shù)。

對目標函數(shù)f施行MoreauYosida正則化后得到新函數(shù)F：Rn→R，F(xiàn)（x）=minz∈Rn{f（z）+12μ‖z-x‖2}，（2）這里‖·‖指歐幾里得范數(shù)，參數(shù)μ>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）具有以下性質(zhì)：

i）F（x）是有界凸函數(shù)，且處處可微。令：g（x）=ΔF（x）=x-h（x）μ ，（3）則g（x） Lipschitz連續(xù)，即‖g（x）-g（y）‖≤1μ‖x-y‖，x，y∈Rn。（4）ii）x是問題（1）的最優(yōu)解，當且僅當ΔF（x）=0時，有h（x）=x。

從上述討論容易知道，只要求出arg minzQ（z，x）的最優(yōu)解，F(xiàn)（x）和g（x）就可以確定下來。然而求出arg minzQ（z，x）=h（x）的精確解是非常困難的，甚至是不可能完成的任務(wù)。因此在實際計算中不可能用精確的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(xiàn)α（x，ε）和gα（x，ε）具有以下性質(zhì)。

命題1假設(shè)式（5）—式（7）成立，則有：F（x）≤Fα（x，ε）≤F（x）+ε，（8）

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

‖gα（x，ε）-g（x）‖≤2ε/μ。（10） 命題說明，當ε充分小，F(xiàn)α（x，ε）和gα（x，ε）可以無限接近F（x）和g（x）。其證明詳見文獻＼[20＼]。

2修正HS三項共軛梯度法

在文獻＼[12-15＼]基礎(chǔ)上，筆者提出一種求解非光滑無約束凸優(yōu)化問題（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），常數(shù)c>0。在此基礎(chǔ)上提出新算法。

算法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，通過非單調(diào)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）兩邊同取范數(shù)得：

‖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說明搜索方向具有有界性，即搜索方向具有信賴域性質(zhì)。

3全局收斂性

以下是算法1的全局收斂性討論中需要用到的假設(shè)。

假設(shè)Ai）對ξk∈[xk，xk+1]和k∈N，存在一個正的常數(shù)ρ，使得：‖Δ2F（ξk）‖≤ρ，（15）其中F是目標函數(shù)f經(jīng)MoreauYosida正則化后所得到的函數(shù)。

ii）函數(shù)F有下界。

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

引理3設(shè)序列{xk}由算法1產(chǎn)生，假設(shè)A成立，如果εk=o（t2k‖dk‖2），則對充分大的k，存在一個正的常數(shù)l，使tk≥l。 （16）證明反證法。

假設(shè)結(jié)論不成立，則存在t′k=tk2，使式（12）不成立，即：

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

根據(jù)式（8）和假設(shè)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）出發(fā)，根據(jù)式（10）、式（13）和式（14）及εk+1≤εk，結(jié)合ε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≥+∞，

矛盾，故結(jié)論成立。

定理1設(shè)序列{xk}，{tk}由算法1產(chǎn)生，假設(shè)A成立，εk=o（t2k‖dk‖2），則limk→∞‖g（xk）‖=0，且序列{xk}的聚點是問題（1）的最優(yōu)解。

證明要證明limk→∞ ‖g（xk）‖=0，只需證明limk→∞‖gα（xk，εk）‖=0（18）即可，采用反證法。假設(shè)式（18）不成立，則存在正的常數(shù)η0和k0，使得對k>k0，有：‖gα（xk，εk）‖≥η0。（19）從式（12）出發(fā)，利用式（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(xiàn)α（xk，εk）→∞，與假設(shè)A中條件ii）矛盾。因此式（18）成立。

下面證明第2個結(jié)論。

由式（10）有：

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

根據(jù)假設(shè)A中條件iii），可得：

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

令x*是序列{xk}的聚點，則存在子序列{xk}K滿足：

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

根據(jù)式（3）以及F（x）的性質(zhì)易知g（xk）=xk-h（xk）μ，因此由式（20）和式（21）可知x*=h（x*）成立，故x*是問題（1）的最優(yōu)解。

4數(shù)值結(jié)果

筆者通過數(shù)值試驗來考查本研究所提出的算法解決非光滑優(yōu)化問題的有效性。試驗的計算機環(huán)境為Windows7+Fortran90，內(nèi)存2.0 GB，各參數(shù)選取為s=μ=1，σ=0.8，εk=1/（k+2）2；終止條件為‖gα（x，ε）‖≤10-15或者迭代次數(shù)Ni>104。測試問題選自文獻＼[12＼]，測試程序是利用Fortran語言在文獻＼[12＼]所提供程序基礎(chǔ)上修改而得，新方法的實驗結(jié)果將與文獻＼[22＼]所提出的LMBM（limited memory bundle method）方法從Ni，Nf和f（x）等幾方面進行比較。其中Ni為迭代次數(shù)，Nf表示函數(shù)值的計算次數(shù)，f（x）為近似最優(yōu)點的函數(shù)值。

測試問題名稱及初始點在表1中列出，2種方法數(shù)值試驗的結(jié)果在表2中列出，其中Problem表示測試問題的名稱，x0表示初始點，Dim表示維數(shù)。

分別對6個測試函數(shù)的4種不同維數(shù)進行測試比較，從表2可以看出，本研究所提出的新算法與求解非光滑問題的傳統(tǒng)LMBM算法相比較優(yōu)勢明顯。綜上所述，新算法不僅具有較好的收斂性質(zhì)，而且數(shù)值表現(xiàn)良好，因此可以認為它能夠有效求解非光滑優(yōu)化問題。

5結(jié)論

非線性共軛梯度法算法簡單，存儲需求小，是一種重要的優(yōu)化方法，HS方法是其中被廣泛討論和運用的一種方法。本文針對非光滑優(yōu)化問題的求解，在經(jīng)典HS共軛梯度法的基礎(chǔ)上，通過利用MoreauYosida正則化技術(shù)和文獻＼[21＼]所提出的Armijotype線搜索技術(shù)，設(shè)計了一種修正HS共軛梯度算法。筆者所設(shè)計的算法不僅可以自動具有充分下降性，而且相應(yīng)的搜索方向?qū)儆谛刨囉?。在適當條件下，證明了新算法是全局收斂的。初步的數(shù)值試驗表明新算法在求解非光滑無約束優(yōu)化問題方面是有效的。

在接下來的工作中，還有很多相關(guān)問題值得做進一步的思考和討論，如新算法的收斂速度，各種參數(shù)的不同選擇對算法效率的影響等，以及新算法在解決金融、圖形圖像、生物工程、最優(yōu)控制、信息技術(shù)等實際問題所蘊含的非光滑問題時的效果，這些都有待在以后工作中繼續(xù)檢驗和測試。

參考文獻/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]胡亞萍.非線性單調(diào)方程組和非光滑優(yōu)化問題的算法研究[D]. 上海：華東理工大學(xué)，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期河北科技大學(xué)學(xué)報Vol.39，No.2

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