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

胡亞萍，王玉杰，劉麗英

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

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

1 算 法

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

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

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

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

本文提出修正HS共軛梯度算法，簡記為MHS算法，令

算法MHS的步驟如下：

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

步驟2：選取εk1+滿足

由非單調Armijo-型線搜索確定步長 kα：

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

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

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

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

步驟6：令k=k+1，轉步驟1．

2 全局收斂性

本節討論修正HS共軛梯度算法用于求解非光滑凸優化問題時的收斂性．為此，需要文獻[5-7]中的假設條件．

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

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

假設 B．正則化函數F有下界．

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

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

當k≥1時

故(12)成立．

故(13)成立．證畢．

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

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

由假設A，類似于文獻[5]中的引理4.2，可以得到下面的引理．

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

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

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

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

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

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

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

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

3 數值實驗

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

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

表1 不同算法的數值結果 Tab. 1 Numerical results of different algorithms

4 結 語

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