解非線性方程組的雜交修正共軛梯度法及其應(yīng)用*

李丹丹, 王松華

(1.廣州華商學(xué)院 應(yīng)用數(shù)學(xué)系,廣東 廣州 511300；2.百色學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院,廣西 百色 533000)

非線性單調(diào)方程組廣泛應(yīng)用于壓縮感知領(lǐng)域中的信號恢復(fù)和圖像處理等問題[1-2]，是許多工程技術(shù)應(yīng)用的重要工具，其表達式如下：

g(x)=0,x∈Rn，

(1)

-g(xk+αkdk)Tdk≥σαk‖dk‖2，

(2)

其中αk=max{s,ρs,ρ2s,…},σ>0,s>0,ρ∈(0,1);而搜索方向dk的優(yōu)劣取決于共軛參數(shù)的構(gòu)造形式，在一定程度上決定了算法的收斂速度.

1 算法基礎(chǔ)與設(shè)計

1.1 投影技術(shù)介紹

在共軛梯度投影算法中所使用的投影技術(shù)是利用函數(shù)g(x)的單調(diào)性來構(gòu)造一個隔離當(dāng)前迭代點xk與問題(1)的最優(yōu)解x*的超平面，然后將當(dāng)前迭代點xk投影到該超平面上，從而產(chǎn)生下一個迭代點xk+1.

對于經(jīng)典的投影技術(shù)[10]，首先尋找一個搜索方向dk，利用線搜索方法產(chǎn)生一個步長αk，使得g(zk)T(xk-zk)>0成立，其中zk=xk+αkdk.由g(x)的單調(diào)性，對于問題(1)的任意最優(yōu)解x*，得g(zk)T(x*-zk)≤0，超平面集合Hk={x∈Rn|g(zk)T(x-zk)=0}，嚴格分離當(dāng)前迭代點xk與問題(1)的最優(yōu)解x*，于是下一個迭代點的更新公式為

(3)

1.2 LCGP算法設(shè)計

為了改進HS算法與PRP算法的理論性質(zhì)，使得所構(gòu)造的算法同時具備良好的充分下降性與信賴域性質(zhì)，設(shè)計了一個新的雜交搜索方向

(4)

其中共軛參數(shù)

(5)

式中,μ>1，yk-1=gk-gk-1.

基于以上論述，給出求解問題(1)的LCGP算法步驟：

步驟1：給定初始點x0∈Rn，正常數(shù)s,σ>0,ε,ρ∈(0,1),μ>1.令k∶=0；

步驟2：若‖g(xk)‖≤ε，則算法停止；否則轉(zhuǎn)步驟3；

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

步驟4：步長αk是由式(2)所決定且令zk=xk+αkdk；

步驟5：若‖g(zk)‖≤ε，則算法停止，并令xk+1=zk；否則，通過式(3)計算新的迭代點xk+1；

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

2 充分下降性和信賴域特性

引理1由式(4)和式(5)所定義的搜索方向dk，具有充分下降性

(6)

和信賴域特性

(7)

當(dāng)k≥1時，有

故有

結(jié)合式(5),有:

故

(8)

由式(4)和式(8)得

綜上所述，式(6)得證.

(ⅱ)當(dāng)k=0時，式(7)顯然成立.

故式(7)成立.

3 全局收斂性分析

作一般性假設(shè)A：

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

(A2)函數(shù)g:Rn→Rn是Lipschitz連續(xù)的，即?M>0，使得

‖g(x)-g(y)‖≤M‖x-y‖，?x,y∈Rn.

(9)

引理2在假設(shè)A條件下，序列{xk}和{zk}是由算法LCGP產(chǎn)生的，那么式(2)產(chǎn)生的步長αk存在下界，即

(10)

引理3的證明類似于文獻[11]引理4的證明，故省略.

定理1在假設(shè)A條件下，算法LCGP產(chǎn)生的序列{xk}滿足以下等式

4 數(shù)值試驗

使用MATLAB(2014a)編寫程序，運行環(huán)境為:Windows 10(64bite)，RAM:8 G，CPU3.60 GHz.

4.1 求解非線性單調(diào)方程組

在算法LCGP的步驟 2 中，分別采用DFPB1[12]和M3TFR1[13]產(chǎn)生搜索方向，其余步驟與算法LCGP一致，得到算法DFPB1和算法M3TFR1.采用這三種算法求解非線性單調(diào)方程組問題.參數(shù)設(shè)置：s=1,ρ=0.43,σ=0.092,μ=1.96.終止準則為‖gk‖≤10-5，設(shè)置算法的迭代次數(shù)上限為1 000，維數(shù)為3 000，6 000，30 000，60 000，90 000.測試問題來自文獻[14]，具體問題和初始點見表1.

表1 測試函數(shù)

選用曲線比較法[15]，對三種算法在求解過程中產(chǎn)生的迭代次數(shù)、目標函數(shù)計算次數(shù)和運行時間的數(shù)據(jù)繪制性能圖(如圖1).

圖1 迭代次數(shù)、目標函數(shù)計算次數(shù)和運行時間性能圖

在圖1中算法LCGP所對應(yīng)的曲線均位于算法DFPB1和算法M3TFR1對應(yīng)的曲線之上，表明LCGP算法在求解大規(guī)模非線性單調(diào)方程組問題上更加高效與穩(wěn)定，具有較強的魯棒性.

4.2 圖像恢復(fù)問題

表2 算法LCGP和算法DFPB1的恢復(fù)圖像時間(s)

從左到右分別為20%椒鹽噪聲圖像、算法LCCP恢復(fù)的圖像和算法DFPB1恢復(fù)的圖像.

從左到右分別為50%椒鹽噪聲圖像、算法LCCP恢復(fù)的圖像和算法DFPB1恢復(fù)的圖像

由表2可知，算法LCGP在CPU時間方面比算法DFPB1有競爭力.此外，由圖2和圖3可知，算法LCGP和算法DFPB1能夠在合理的時間內(nèi)恢復(fù)不同程度受椒鹽噪聲污染的圖像.從而驗證了新算法的可行性與實用性.

5 結(jié)語

在修正HS算法和修正PRP算法的基礎(chǔ)上，設(shè)計一個新的雜交搜索方向，結(jié)合超平面投影技術(shù)和高效的線搜索方法，提出了一個雜交修正共軛梯度算法.該算法具有以下優(yōu)良的性質(zhì)：信賴域特性、充分下降性和全局收斂性.采用大規(guī)模(維數(shù)3 000-90 000)問題進行數(shù)值檢驗，結(jié)果表明算法LCGP比算法M3TFR1和算法DFPB1效果更好，具有較強的魯棒性.此外，將新算法LCGP應(yīng)用于圖像恢復(fù)問題，能成功恢復(fù)圖像，證明新算法具有實際應(yīng)用價值.