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

李丹丹，李遠飛

（廣州華商學(xué)院 數(shù)據(jù)科學(xué)學(xué)院，廣東 廣州511300）

0 引言

考慮如下非線性單調(diào)方程組

其中θ：Rn→Rn是連續(xù)可微函數(shù)且單調(diào)，即θ(x)－θ(y)，x－y≥0，?x，y∈Rn。

非線性單調(diào)方程組可廣泛運用于壓縮感知中的信號恢復(fù)、圖像處理、經(jīng)濟等跨學(xué)科領(lǐng)域［1－3］。若干具有快速局部收斂性質(zhì)的迭代算法可高效求解問題（1），如牛頓法、擬牛頓法和LM 算法等［4］。上述算法需計算和存儲矩陣信息，不適用于求解大規(guī)模非線性單調(diào)方程組問題。共軛梯度法［5－6］因算法結(jié)構(gòu)簡單、易操作、儲存量小等優(yōu)點被推廣到求解大規(guī)模非線性方程組，并驗證了其優(yōu)良性質(zhì)。

式（3）中βk為共軛參數(shù)，θ(xk) 簡寫為θk，而搜索方向dk與線搜索方法決定了共軛梯度法的優(yōu)劣性，且在一定的程度上體現(xiàn)算法收斂效果。

Wei 等［7］給出了一個修正HS 算法，其共軛參數(shù)為

其中yk－1＝θk－θk－1。Sun 等［8］提出了一個雜交共軛梯度投影方法，該方法的搜索方向具有良好的信賴域特性，其中共軛參數(shù)為

其中μ ＞1，yk－1＝θk－ θk－1。基于Wei 等［7］和Sun 等［8］的良好性質(zhì)，受此啟發(fā)，本文設(shè)計出一個新的修正搜索方向，其共軛參數(shù)為

本文借鑒Wei 等［7］的修正HS 算法與Sun 等［8］的雜交共軛梯度投影算法思想，設(shè)計出一個新的搜索方向，再結(jié)合Dai 等［11］的線搜索方法和Solodov 等［12］經(jīng)典的超平面投影技術(shù)，提出了一個無導(dǎo)數(shù)型的修正共軛梯度算法。新算法的搜索方向滿足充分下降性和信賴域特性，保證了算法的有效性。在適當(dāng)?shù)募僭O(shè)下，證明了新算法的全局收斂性。此外，在數(shù)值試驗中，利用新算法求解非線性正規(guī)方程組和稀疏信號重構(gòu)問題，結(jié)果闡明了新算法的高效性、可行性及實用性。

1 算法描述

建立求解非線性單調(diào)方程組問題（1）的修正共軛梯度算法（MHSN）：

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

證明算法MHSN 具有充分下降性和信賴域特性，這為分析算法的全局收斂性起到積極的作用。

引理1由式（3）和式（4）所確定的搜索方向dk滿足以下性質(zhì)：

3 全局收斂性分析

本節(jié)分析算法MHSN 的全局收斂性質(zhì)，需作假設(shè)B：

（B1）非線性單調(diào)方程組問題（1）的解集非空；

（B2）函數(shù)θ (x) 在Rn上是Lipschitz 連續(xù)的，即存在常數(shù)L ＞0，有

下面給出算法MHSN 的適定性引理，即證明算法是有意義的。

引理2在假設(shè)B 條件下，算法MHSN 是有意義的。

4 數(shù)值試驗

4.1 非線性正規(guī)方程組

在算法MHSN 的步驟2 中，采用Fang［14］中算法MRMIL3 產(chǎn)生搜索方向dk，其余步驟與算法MHSN一致，得到的算法記為算法MRMIL3。

相關(guān)參數(shù)：β＝1，ρ＝0.5，σ＝0.096，μ＝1.81。

運行環(huán)境：采用MATLAB（2014a）實現(xiàn)，Windows10（64 bite），RAM：8 GB，CPU：3.60 GHz。

終止準則：‖θk‖≤10－5，迭代次數(shù)上限為1 000，維數(shù)為［4 500，12 000，24 000，30 000，45 000］。

測試問題共10 個［10，15－17］，數(shù)值結(jié)果如表1 所示，其中Pro 為問題序號，Dim 為維數(shù)，Iter 為迭代次數(shù)，NF為函數(shù)計算次數(shù)，Time 為程序運行時間（單位：秒）。

表1 各類算法數(shù)值結(jié)果Tab.1 Numerical results of various methods

續(xù)表1 各類算法數(shù)值結(jié)果Continued Tab.1 Numerical results of various methods

為了更直觀反映三種算法的性能指標（迭代次數(shù)、函數(shù)計算次數(shù)和運行時間），采用Dolan［18］的評價方式，描繪了迭代次數(shù)性能圖、函數(shù)計算次數(shù)性能圖和運行時間性能圖，如圖1 至圖3。

圖1 迭代次數(shù)性能圖Fig.1 Performance profiles of iterations

圖2 目標函數(shù)計算次數(shù)性能圖Fig.2 Performance profiles of the number of objective function

圖3 運行時間性能圖Fig.3 Performance profiles of CPU time

從表1 可知，算法MHSN 和算法MRMIL3 都在有限迭代次數(shù)內(nèi)成功求解非線性正規(guī)方程組。同時，在同等條件下，數(shù)值結(jié)果表1 說明了算法LCGP 總體上比算法M3TFR 更優(yōu)，各類指標數(shù)值更少。性能圖1－3 顯示算法MHSN 總體上比算法MRMIL3 更好，具有更好的魯棒性，故驗證了算法MHSN 是有效的且適合于求解大規(guī)模非線性單調(diào)方程組。

4.2 稀疏信號重構(gòu)問題

本小節(jié)主要考慮壓縮感知中的稀疏信號重構(gòu)問題［19］。使用算法MHSN 和算法MRMIL3 求解稀疏信號恢復(fù)問題。

在測試中，信號的相關(guān)參數(shù)為n＝212，k＝210，原始信號只包含27個隨機非零元素，其余為0。 此外，觀測值y＝Bx?＋η是帶有噪聲的高斯分布，其中x?為原始信號B的隨機高斯分布矩陣，η是均值為0 和方差為10－4的高斯噪聲。采用均方誤差（MSE）作為恢復(fù)信號的評判標準，即其中x*為恢復(fù)信號。程序終止準則為

由于觀察值含有隨機噪聲，將程序運行10 次，其結(jié)果如表2 所示，顯然，從運行時間和迭代次數(shù)的角度來看，算法MHSN 比算法MRMIL3 效率更高。

表2 稀疏信號恢復(fù)結(jié)果Tab.2 Results of sparse signal recovery

圖4 為算法MHSN 和算法MRMIL3 在處理稀疏信號恢復(fù)的對比圖，在圖4 中由上到下分別表示為原始信號、觀測值、由算法MHSN 和MRMIL3 恢復(fù)的信號。圖5 為兩種算法效果對比圖，其中MSE 表示均方誤差值，Iterations 表示迭代次數(shù)，CPU time 表示運行時間。

圖4 稀疏信號恢復(fù)對比圖Fig.4 Comparison of the sparse signal recovery

圖5 算法MHSN 和算法MRMIL3 的比較結(jié)果Fig.5 Comparison of the MHSN and MRMIL3 algorithms

從圖4 可知，算法MHSN 和算法MRMIL3 都成功地恢復(fù)信號。由圖5 可知，從迭代次數(shù)和運行時間來看，兩種算法的均方誤差都收斂于0，且算法MHSN 效果更好。從而驗證了新算法具有實際應(yīng)用價值。

5 結(jié)論

本文在雜交共軛梯度投影方法和修正HS 算法的基礎(chǔ)上，設(shè)計出一個新的修正搜索方向，結(jié)合經(jīng)典投影方法和最新的線搜索方法，提出了一個新的修正共軛梯度投影算法。證明了新算法具有優(yōu)良的理論性質(zhì)，通過對非線性正規(guī)方程組和稀疏信號重構(gòu)問題進行求解，驗證了新算法的有效性與實用性。同時還可將新算法推廣到圖像恢復(fù)問題的應(yīng)用中。