非線性方程組的修正共軛梯度法及其應用

李丹丹，李遠飛

（廣州華商學院 數據科學學院，廣東 廣州511300）

0 引言

考慮如下非線性單調方程組

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

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

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

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

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

其中μ ＞1，yk－1＝θk－ θk－1?；赪ei 等［7］和Sun 等［8］的良好性質，受此啟發，本文設計出一個新的修正搜索方向，其共軛參數為

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

1 算法描述

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

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

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

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

3 全局收斂性分析

本節分析算法MHSN 的全局收斂性質，需作假設B：

（B1）非線性單調方程組問題（1）的解集非空；

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

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

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

4 數值試驗

4.1 非線性正規方程組

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

相關參數：β＝1，ρ＝0.5，σ＝0.096，μ＝1.81。

運行環境：采用MATLAB（2014a）實現，Windows10（64 bite），RAM：8 GB，CPU：3.60 GHz。

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

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

表1 各類算法數值結果Tab.1 Numerical results of various methods

續表1 各類算法數值結果Continued Tab.1 Numerical results of various methods

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

圖1 迭代次數性能圖Fig.1 Performance profiles of iterations

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

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

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

4.2 稀疏信號重構問題

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

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

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

表2 稀疏信號恢復結果Tab.2 Results of sparse signal recovery

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

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

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

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

5 結論

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