解凸約束非線性方程組的修正WYL投影算法

李丹丹，李遠飛

(廣州華商學院 應用數(shù)學系，廣東 廣州 511300)

考慮帶凸約束的非線性單調(diào)方程組問題：

H(z)=0，z∈Ζ，

(1)

其中函數(shù)H:Rn→Rn是連續(xù)且具有單調(diào)性質，Ζ?Rn是非空閉凸集.單調(diào)性指的是對于任意z1,z2∈Rn，有 (H(z1)-H(z2))T(z1-z2)≥0成立.

非線性方程組問題具有廣泛的應用，如壓縮感知的稀疏信號恢復和圖像恢復、化學均衡系統(tǒng)等[1-3].因此研究求解非線性方程組的數(shù)值算法具有一定的實際意義.目前，在眾多數(shù)值算法中，共軛梯度法因具有結構簡單、低存儲特點，而被廣泛應用于大規(guī)模非線性方程組問題中[4].求解帶約束的非線性方程組引起了學者們的關注，文獻[5]提出了一種求解帶凸約束非線性方程組問題的投影算法，該算法在沒有可微的假設下?lián)碛腥质諗啃再|，并且數(shù)值結果體現(xiàn)了該算法是穩(wěn)定與有效的.文獻[6]提出了一個Wei-Yao-Liu(WYL)共軛梯度投影算法，隨后文獻[7]將WYL共軛梯度法推廣到求解帶凸約束非線性方程組問題中，該算法具有以下良好性質：1) 因沒有可微的假設，該算法是一種無導數(shù)型算法，可以求解非光滑非線性方程組問題；2) 全局收斂性質的證明不依賴于方程組的可微假設也不依賴于某種效益函數(shù)；3) 該算法無需計算和存儲矩陣信息，只需要較低的存儲內(nèi)存，從而適合于求解大規(guī)模非線性方程組問題.

受文獻[7]的啟發(fā)，本文中，筆者對文獻[6]搜索方向作出修正，修正后所得到的搜索方向不僅具有充分下降性，還滿足信賴域性質，并且新算法擁有全局收斂性和較好的數(shù)值效果.

1 預備知識

2 算 法

共軛梯度算法的一般迭代公式為zk+1=zk+αkdk，其中步長αk由某一線搜索方法決定.

文獻[6]提出了一種WYL共軛方向為

(2)

(3)

(4)

(5)

基于以上闡述，下面給出求解問題(1)的算法步驟(MWYL算法)：

步驟2 計算H(zk)，若‖H(zk)‖≤ε，則算法停止；

步驟3 通過(4)和(5)計算搜索方向dk；

步驟4 令wk=zk+αkdk，其中步長αk=max{βkρi|i=0,1,2,…}滿足

-H(zk+αkdk)Tdk≥σαk‖H(zk+αkdk)‖‖dk‖2；

(6)

步驟5 計算H(wk)，若‖H(wk)‖≤ε，則算法停止，否則計算新的迭代點wk+1，即

步驟6 選擇βk+1使得βk+1∈[βmin,βmax]，令k:=k+1，轉步驟2.

3 充分下降性與信賴域特征

本節(jié)主要分析搜索方向dk的良好性質.下面引理說明搜索方向dk具有充分下降性和信賴域特征.

引理1假設搜索方向dk是由(4)和(5)決定，那么以下不等式成立：

(7)

(8)

因此，(7)成立.利用Cauchy-Schwarz不等式得

(9)

另外，由(4)和(5)可得

結合(9)得(8)成立.

4 全局收斂性

本節(jié)主要討論算法MWYL的全局收斂性質，為了方便后續(xù)的證明，先給出如下的假設S：

S1) 問題(1)的解集非空;

S2) 函數(shù)H:Rn→Rn是利普希茨連續(xù)的，即存在正常數(shù)η>0，有

(10)

下面證明算法MWYL是有意義的.

引理2在假設S成立下，?k存在步長αk使得(6)成立.更進一步，假設算法MWYL產(chǎn)生序列{zk}，{wk}，{αk}和{dk}，那么有

(11)

由(7)，(10)及上式得

因此

證類似于文獻[8]中的引理4可以證明結論成立.

定理1在假設S成立下，算法MWYL產(chǎn)生的序列{zk}，{αk}，{dk}，{wk}使得如下式子成立：

證假設存在ξ>0，對于任意的k≥0，有‖Hk‖≥ξ，再結合引理1得

(12)

另外，由引理3可知，序列{zk}和{wk}是有界的，于是存在η1>0，使得

‖H(zk)‖≤η1，‖H(wk)‖≤η1.

(13)

由引理1,(11)～(13)得

這與引理3矛盾，故定理1得證.

5 數(shù)值試驗

算法DF-LSTT和算法SPPRP的參數(shù)設置保持不變.所有算法的終止準則為‖Hk‖≤10-5且迭代次數(shù)上限為300.3種算法的數(shù)值效果見表1，其中各種符號的含義為：P(problem)為問題序號；D(dimension)為維數(shù)；NI(number of iterations)為迭代次數(shù)；NF(number of function)為函數(shù)計算次數(shù)；T為CPU時間.

從表1中可以清楚地看到，算法MWYL在迭代次數(shù)、函數(shù)計算次數(shù)和CPU時間方面總體上比算法DF-LSTT和算法SPPRP更具有競爭力.為了更直觀地比較3種算法的性能表現(xiàn)，采用曲線計算法[16]繪制性能圖，見圖1～3，其中曲線越靠上，說明其算法性能越好.算法MWYL的曲線整體上都在算法DF-LSTT和算法SPPRP的曲線之上，這在某種程度上說明了算法MWYL是有效與穩(wěn)定的.

表1 各類算法數(shù)值結果Tab.1 Numerical Results of Various Algorithms

續(xù)表

圖1 各類算法總迭代次數(shù)性能Fig.1 Performance Profiles of Various Methods Iterations

圖2 各類算法函數(shù)計算總次數(shù)性能Fig.2 Performance Profiles of the Number of Various Methods Objective Function

圖3 各類算法總運行時間性能Fig.3 Performance Profiles of Various Methods CPU Time

6 結 論

提出了一種求解大規(guī)模凸約束非線性單調(diào)方程組問題的無導數(shù)修正WYL共軛梯度投影算法.新算法在不基于某種線搜索方法上自動擁有充分性下降性和信賴域特征.在合理的假設下，證明了新算法的全局收斂性質.由于繼承了共軛梯度法的優(yōu)點，新算法十分適合于求解大規(guī)模非光滑方程組問題.數(shù)值試驗結果充分表明了新算法是高效與穩(wěn)定的.