求解非光滑問題的修正HS共軛梯度法

胡亞萍，王玉杰，劉麗英

(天津科技大學(xué)理學(xué)院，天津 300457)

考慮無約束優(yōu)化問題min{ f(x) |x ∈?n}，其中f: ?n→?為非光滑凸函數(shù)．非光滑問題中的目標(biāo)函數(shù)是連續(xù)不可微函數(shù)，傳統(tǒng)的優(yōu)化算法不能直接用于求解該問題．與非光滑凸優(yōu)化問題緊密相關(guān)的是目標(biāo)函數(shù)Moreau-Yosida正則化[1]，正則化函數(shù)F(x)是定義在整個(gè)空間n?上的可微的凸函數(shù)，并且與原非光滑優(yōu)化問題擁有相同的解集合．求解非光滑優(yōu)化問題的常用算法有Bundle法和信賴域法[2-4]．近年來，Yuan等[5-6]和Hu[7-8]提出的梯度類算法在求解非光滑問題時(shí)表現(xiàn)較好．其中文獻(xiàn)[6]基于BFGS修正技術(shù)提出的修正PRP共軛梯度法需要較大的存儲(chǔ)空間和計(jì)算量，它每步迭代時(shí)的計(jì)算量和內(nèi)存需求均大于共軛梯度類算法．本文結(jié)合Moreau-Yosida正則化和非單調(diào)線搜索技術(shù)，提出了修正的HS共軛梯度算法求解非光滑優(yōu)化問題．新算法具有滿足共軛性條件、自動(dòng)具有充分下降性、給出近似參數(shù)選取方式、克服存儲(chǔ)需求大與算法復(fù)雜等特點(diǎn)．?dāng)?shù)值結(jié)果表明，與文獻(xiàn)[6]的算法相比，新算法具有收斂速度快、精度高的優(yōu)點(diǎn)．

1 算 法

記p(x) =argmin {θ(z ) |z ∈?n}，且定義θ(z)=f(z)+ ‖z -x‖2/(2λ)，由于θ(z)是一個(gè)強(qiáng)凸函數(shù)，極小值點(diǎn)p(x)存在且唯一．于是非光滑凸函數(shù)f(x)的Moreau-Yosida正則函數(shù)F(x)表示為

正則化函數(shù)F(x)是連續(xù)可微的凸函數(shù)，但同時(shí)注意到F(x)未必二次可微．F(x)在點(diǎn)x處的梯度為g(x) =?F (x) = ( x - p(x) )/λ．然而θ(z)的極小值點(diǎn)p(x)一般很難甚至不可能精確求解，這便不能直接利用p(x)的精確值來確定函數(shù)值F(x)和梯度值g(x)．但是對(duì)任意 x∈?n和任意的近似參數(shù)ε＞0，存在近似值 pα(x,ε) ∈?n滿足

于是，可以利用pα( x,ε)來確定F(x)和g(x)的近似值，即

一些用于求解近似極小值點(diǎn)pα( x,ε)的算法見文獻(xiàn)[9]，近似值Fα( x,ε)和gα( x,ε)滿足下面的性質(zhì)[9]：

本文提出修正HS共軛梯度算法，簡(jiǎn)記為MHS算法，令

算法MHS的步驟如下：

步驟0：令k=0，給定初始點(diǎn) x0∈?n，s＞0，ξ∈ (0,1)，σ∈ (0,1)，λ＞0，ρ＞0，E0=1，一個(gè)嚴(yán)格下降的正序列{τk}滿足τ0≤1且，ε0=τ0，J0= Fa(x0,ε0)，d0=- gα(x0,ε0)．

步驟2：選取εk1+滿足

由非單調(diào)Armijo-型線搜索確定步長(zhǎng) kα：

其中，αk=s 2-ik，ik∈{ 1,2,…}．

步驟3：令 xk+1= xk+αkdk．若則算法停止．

步驟4：由下面公式更新Jk1+

步驟5：由式(8)計(jì)算搜索方向dk1+．

步驟6：令k=k+1，轉(zhuǎn)步驟1．

2 全局收斂性

本節(jié)討論修正HS共軛梯度算法用于求解非光滑凸優(yōu)化問題時(shí)的收斂性．為此，需要文獻(xiàn)[5-7]中的假設(shè)條件．

假設(shè)A．序列{Vk}有界，即存在常數(shù)M ＞0使得

其中矩陣 Vk∈?Bg (xk)．

假設(shè) B．正則化函數(shù)F有下界．

引理1由式(8)的定義，搜索方向滿足性質(zhì)

證明:當(dāng)k=0時(shí)，d0=- gα(x0,ε0)，式(11)、式(12)顯然成立．

當(dāng)k≥1時(shí)

故(12)成立．

故(13)成立．證畢．

根據(jù)假設(shè)B和修正HS算法中的步驟5，提出下面的引理．引理表明該搜索是適定的，證明方法與文獻(xiàn)[10]中的引理1類似，故省略．

引理2若假設(shè)B成立．序列{xk}由算法MHS產(chǎn)生，則 Fa(xk,εk)≤ Jk≤ Ck對(duì)每一個(gè)k成立，其中另外，存在kα滿足線搜索中Armijo條件．

由假設(shè)A，類似于文獻(xiàn)[5]中的引理4.2，可以得到下面的引理．

引理3若假設(shè)A成立．序列{(xk,εk)}由算法MHS產(chǎn)生．假設(shè)成立．則存在常數(shù)m0＞ 0，滿足αk≥ m0．

定理1若假設(shè)A，假設(shè)B和引理3的條件成立，序列{xk}由算法MHS產(chǎn)生，則有，且序列{xk}的每一個(gè)聚點(diǎn)都是非光滑凸優(yōu)化問題(1)的最優(yōu)解．

證明：先用反證法證明假設(shè)存在常數(shù)?0＞0和k0＞0使得‖ gα(xk,εk‖)≥?0對(duì)所有的 k＞k0成立．由式(5)和假設(shè)B，知 Fa(xk,εk)有下界．結(jié)合引理2，得到Jk有下界，且

另一方面，由式(9)和引理3，有

因此，上式結(jié)合式(10)可推出

由{εk}的定義和式(7)，有．令 x*是序列{xk}的一個(gè)聚點(diǎn)，不妨設(shè)存在一個(gè)子列{xk}K，使得

由正則化函數(shù)F(x)的定義，有

式中令k→∞，有 x*=p(x*)成立．因此x*是非光滑優(yōu)化問題(1)的最優(yōu)解．證畢．

3 數(shù)值實(shí)驗(yàn)

算法MHS、MPRP[6]和BT[11]的數(shù)值結(jié)果見表1.非光滑測(cè)試函數(shù)信息可參考文獻(xiàn)[5]的表1．在實(shí)驗(yàn)中，取參數(shù)s=λ=1，ρ=0.75，σ=0.9，εk= 1/( k +1)2，終止準(zhǔn)則為‖ ga(x,ε)‖ ≤ 10-5．表1中f(x)表示算法終止時(shí)的函數(shù)值；fops(x)表示目標(biāo)函數(shù)的最優(yōu)值．

從表1中迭代次數(shù)、函數(shù)值計(jì)算次數(shù)和算法終止時(shí)的函數(shù)值三方面綜合來看，修正HS共軛梯度算法對(duì)求解非光滑問題是有效的．

表1 不同算法的數(shù)值結(jié)果 Tab. 1 Numerical results of different algorithms

4 結(jié) 語

非光滑優(yōu)化問題是最優(yōu)化理論與方法的重要分支，其求解也是優(yōu)化領(lǐng)域的難題之一．本文結(jié)合Moreau-Yosida正則化和非單調(diào)線搜索技術(shù)提出了非線性修正HS共軛梯度算法用于求解非光滑優(yōu)化問題．在適當(dāng)條件下，證明了該算法具有全局收斂性．?dāng)?shù)值結(jié)果表明新算法在求解非光滑優(yōu)化問題方面是有效的．