求解凸約束非線性方程組的無導數(shù)DY投影算法

李丹丹，王松華

(1. 廣州華商學院應用數(shù)學系，廣州 511300；2. 百色學院數(shù)學與統(tǒng)計學院，百色 533000)

凸約束非線性方程組廣泛應用于壓縮感知中的信號恢復、圖像處理、等離子體物理學、非線性光學等問題[1-4]，因此，研究求解帶有凸約束非線性方程組問題的高效數(shù)值算法具有重要的理論價值與實際應用意義．于是本文考慮如下帶凸約束的非線性方程組問題：

其中，φ: A → Rn是連續(xù)非線性函數(shù)，且 A ? Rn是一個非空閉凸集．

目前在求解問題(1)的眾多數(shù)值方法中，梯度類方法[5-6]表現(xiàn)較好，考慮到共軛梯度法的低存儲需求與迭代框架簡單等優(yōu)點，學者們試圖將共軛梯度法與投影技術結合應用于求解問題(1)，如文獻[7-9]．文獻[10]研究了共軛梯度法的進展，提到經(jīng)典的共軛梯度法(如HS算法、LS算法、DY算法等)不能同時滿足收斂效果好、數(shù)值效果佳的事實，并討論了三項共軛梯度方法的構造形式．文獻[11]在經(jīng)典HS方法的基礎上研究一種求解問題(1)的修正三項共軛梯度投影算法．文獻[12]對經(jīng)典LS方法進行修正，提出了一種新的三項共軛梯度投影算法來求解凸約束非線性單調(diào)方程組問題．文獻[13]建立了一個高效求解無約束優(yōu)化問題的新型三項共軛梯度法，該方法的搜索方向在不依賴于任意線搜索的情況下自動滿足充分下降性且數(shù)值效果顯著．文獻[14]將其推廣到帶簡單凸約束的非線性方程組問題．考慮到經(jīng)典DY算法具有較強的收斂性，但數(shù)值效果欠佳的情況，受文獻[14]構造思想的啟發(fā)，對DY算法的搜索方向進行修正，提出了一種無導數(shù)修正DY三項共軛梯度投影算法用于求解凸約束非線性方程組問題．

1 算法描述

文獻[10]總結的三項共軛梯度方向構造形式為

式中：參數(shù)βk為共軛參數(shù)；為了方便描述，φ(xk)記為φk；pk可定義為φk、dk-1或γk-1=φk-φk-1等任一形式．

一般共軛梯度法的迭代式為 zk+1=zk+αkdk，其中αk為確定的步長，dk為搜索方向．

文獻[14]設計了一個三項共軛梯度方向，其定義為

其中：σ1,σ2＞0,符號·代表Euclidean范數(shù)，

最后，引入投影算子，其定義為從集合 Rn到非空閉凸集A的映射，即

該算子具有以下良好性質(zhì)：

綜上所述，下面給出求解帶凸約束的非線性方程組算法描述．

算法MLLY的步驟：

(1)給出參數(shù)β,σ＞0,ρ∈ (0,1),σ1,σ2＞0,ε≥0，初始點 x0∈ Rn，令k=0；

(2)計算φ(xk)，若φ(xk)≤ε，則算法停止；

(3)搜索方向dk是由式(4)計算而得；

(4)令 vk=zk+αkdk，其中步長滿足如下不等式：

(5)計算φ(vk)，若φ(vk)≤ε，則算法停止，否則通過如下方法計算下一個迭代點zk+1，即

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

2 收斂性分析

本節(jié)先分析算法MLLY產(chǎn)生的搜索方向擁有充分下降性，再證明由式(5)產(chǎn)生步長的存在性，最后討論算法MLLY具有全局收斂的性質(zhì)．下面給出合理的假設．

假設S

(S1) 映射 :φRn→Rn是單調(diào)連續(xù)的，即

(S2) 問題(1)的解集非空；

(S3) 映射 :φn→nR R是Lipschitz連續(xù)的，即存在常數(shù)ζ＞0，有

引理1假定序列{ xk}和{dk}是由算法MLLY產(chǎn)生的，若σ1-(1 +σ2)28σ1＞0和 0＜σ1≤1，則存在正常數(shù)χ使得如下不等式成立：

證明：當k=0時，令那么式(8)顯然成立．當k≥1時，令利 用 不 等 式得

引理2若假設S條件成立，對于?k，存在步長kα滿足式(5)．

證明：類似于文獻[15]中的引理2.2可以證明結論成立．

引理3若假設S條件成立，算法MLLY產(chǎn)生序列{zk}和{vk}，那么對于問題(1)的最優(yōu)解z*，有

證明：類似于文獻[9]中的引理2可以證明此結論成立．

定理1若假設S條件成立，算法MLLY產(chǎn)生的序列成立．

上式聯(lián)合式(7)、式(8)和Cauchy-Schwarz不等式得

整理上式得

上式兩邊對k取極限，由式(10)推得

故結論成立．證畢．

3 數(shù)值實驗

為了檢測算法MLLY的性能表現(xiàn)，本節(jié)將其與算法ACGD[16]和算法MFRM[17]進行比較．算法ACGD和算法MFRM保持原有的參數(shù)設置，算法MLLY的參數(shù)設置為β=1，ρ=0.55，σ=0.001，σ1=0.7，σ2=0.3，ε=10-5．所 有 算 法 都 采 用MATLAB2014a軟件編寫并運行，運行環(huán)境為Windows10(64bite)，RAM：8GB，CPU3.60GHz．測試問題共10個，分別來自文獻[1，17-20]，對每個測試問題選取不同的維數(shù)且設置維數(shù)為[1000 5000 10000 50000 100000]，迭代次數(shù)上限為800．

計算出3種算法在求解過程中的3個指標(總迭代次數(shù)、函數(shù)計算總次數(shù)、CPU運行總時間)的數(shù)據(jù)，采用曲線計算方法[21]繪制性能圖，進而更直觀地分析對比3種算法的性能效果，結果如圖1所示．圖1從3個角度(迭代次數(shù)、函數(shù)計算次數(shù)和CPU運行時間)進行評價，曲線越靠上，表明算法越穩(wěn)定與有效．

圖1中橫坐標的t指的是給定的數(shù)值比率，縱坐標的計算公式為

圖1 不同算法的比較Fig. 1 Comparison profile of different algorithms

從圖1可看出，算法MLLY的曲線在圖中均位于其他兩個算法之上，這表明在3個指標上算法MLLY均優(yōu)于算法ACGD和算法MFRM，具有較好的魯棒性．

4 結 語

在修正經(jīng)典DY共軛參數(shù)及文獻[14]搜索方向的基礎上，本文提出了求解一類帶凸約束大規(guī)模非線性方程組問題的無導數(shù)修正DY共軛梯度投影算法．新方法擁有充分下降性和全局收斂的良好性質(zhì)．數(shù)值結果表現(xiàn)了新算法的有效性，更適合求解大規(guī)模非線性方程組問題．同時，也可進一步研究新算法在處理信號恢復與圖像處理等問題上的實用性．