凸約束方程組的新型無導數算法及在信號重構中的應用

摘要： 提出一種新型無導數算法， 以解決凸約束非線性方程組問題. 該算法利用改進的共軛參數設計搜索方向， 以確保算法的充分下降性和信賴域特性. 在適當的假設下， 該算法具有全局收斂性. 數值仿真結果表明， 該算法在處理凸約束非線性方程組問題和信號重構問題時具有高效性和魯棒性.

關鍵詞： 凸約束非線性方程組； 無導數； 全局收斂性； 信號重構

中圖分類號： O224""文獻標志碼： A""文章編號： 1671-5489（2024）06-1345-07

Novel Derivative-Free Algorithm for Convex Constrained Equations and Its Application in Signal Reconstruction

XIA Yan1， LI Yuanfei1， WANG Songhua2， LI Dandan1

（1. Department of Applied Mathematics， Guangzhou Huashang College， Guangzhou 511300， China;

2. School of Mathematics and Statistics， Baise University， Baise 533000， Guangxi Zhuang Autonomous Region， China）

Abstract： We "proposed a novel derivative-free algorithm "to solve convex constrained nonlinear equation systems. The "algorithm utilized improved conjugate parameters

to design a search direction， ensuring sufficient descent and trust region characteristics of the algorithm. Under appropriate assumptions， the "algorithm had "global convergence.

Numerical simulation results show that the "algorithm has high "efficiency and robustness in handling convex constrained nonlinear equation systems and signal reconstruction problems.

Keywords： convex constrained nonlinear "equation systems; derivative-free; global convergence; signal reconstruction

0"引"言

考慮下列具有凸約束的非線性方程組問題：

Ω（a）=0，""a∈En，（1）其中函數Ω：n→n是連續的. 形如問題（1）的非線性方程組在科學、 工程、 社會科學、 管理科學等領域應用廣泛^［1-4］.

因此， 研究求解問題（1）的數值方法有一定的理論意義. 由于牛頓法和擬牛頓法在每次迭代中需使用Jacobi矩陣或其近似值求解線性方程組， 因此其通常不適合解決大規模問題. 本文主要研究不依賴于Jacobi矩陣或其近似值的數值方法， 從而能有效處理大規模非線性方程組， 同時保持較低的存儲需求和計算復雜度.

近年來， 為適應求解大規模非線性方程組的要求， 對基于共軛梯度方法進行擴展的研究備受關注^［5-13］. "例如， 文獻［5］將原用于二次優化問題的譜梯度方法進行擴展， 使其適用于求解非線性方程組； 文獻［6］結合譜梯度方法和投影技術， 提出了一種新的譜梯度投影方法， 用于解決具有凸約束的非線性方程組； 文獻［7］利用最速下降法研究了一類共軛梯度法， 旨在高效處理大規模非線性方程組； 文獻［8］對經典的PRP（Polak-Ribière-Polyak） 共軛梯度法進行擴展， 在非單調線搜索的框架下， 構建了一種無導數PRP算法， 以適應大規模非線性方程組的求解； 結合RMIL（Rivaie-Mustafa-Ismail-Leong）共軛梯度法和一種新的非單調線搜索方法， 文獻［9］研究了一種新的無導數共軛梯度法， 用于解決大規模非線性方程組.

受文獻［14］工作的啟發， 并結合上述討論的共軛梯度法以及投影技術， 本文提出一種新的無導數算法（novel derivative-free， NDF）， 用于求解凸約束非線性方程組. 新算法具有以下特性： 1） 無需計算函數的Jacobi矩陣或其近似值； 2） 搜索方向具有充分下降性并具有信賴域特點； 3） 在較弱的假設下， 新算法具有全局收斂性. 數值仿真實驗結果表明， 新算法適用于解決大規模凸約束非線性方程組問題， 并且在壓縮感知領域的信號重構問題中效果顯著.

1"算"法

記投影算子為PE［·］， 其定義如下：

PE［a］=argmin{‖a-b‖， b∈E}，""a∈n，

其中PE： n→E且 E為非空閉凸集. 此外， 投影算子具有非擴張性質， 即對任意的a∈n， 滿足‖PE［a］-b‖≤‖a-b‖， b∈E. 受文獻［14］的啟發， 本文提出一種新的無導數算法，

用于求解凸約束非線性方程組問題. 新算法的搜索方向和共軛參數分別定義如下：

dk=-Ωk，k=0，

-Ωk+βkdk-1，k≥1，（2）

βk=minΩTkΩk-μ

1（ΩTkdk-1）2‖Ωk‖‖Ω

k-1‖‖dk-1‖2Ωk-1，‖Ωk

‖2max{μ2‖Ωk‖‖dk-1‖，dTk

（Ωk-Ωk-1）}，（3）

其中Ω（ak）縮寫為Ωk， μ1gt;0， μ2gt;1. 基于式（2）和式（3）， 下面給出新的NDF算法流程如下.

給定初始點a0∈n， l∈（0，2）， δ，σ，ξgt;0， ρ∈（0，1）， μ1gt;0， μ2gt;1， 令k∶=0；

步驟1） 計算Ωk， 若‖Ωk‖≤δ， 則算法停止， 否則轉步驟2）；

步驟2） 根據式（2）和式（3）計算搜索方向dk；

步驟3） 計算試探點bk∶=ak+tkdk， 其中tk∶=max{ξρi： i=0，1，…}， 使得下式成立：

-Ω（ak+ξρidk）Tdk≥σξρ

i‖Ω（ak+ξρidk）‖‖dk‖2；（4）

步驟4） 若‖Ω（bk）‖≤δ， 則算法停止， 否則通過下式計算下一個迭代點：

ak+1=PEak-lΩ

（bk）T（ak-bk）‖Ω（bk）‖2Ω（bk）；

步驟5） 令k∶=k+1， 轉步驟1）.

2"算法性質與全局收斂性

為建立NDF算法的全局收斂性， 需進行以下假設：

（H1） 函數Ω（a）是Lipschitz連續的， 即存在正常數L， 使得

‖Ω（a）-Ω（b）‖≤L‖a-b‖，""a，b∈n.

（H2） 問題（1）的解集非空.

引理1"搜索方向dk由式（2）和式（3）產生， 則dk滿足充分下降性質，

即ΩTkdk≤-1-1μ2‖Ωk‖2.

證明： 當k=0時， ΩT0d0=-‖Ω0‖2≤-（1-1/μ2）‖Ω0‖2. 當k≥1時， 將式（2）兩邊左乘ΩTk并結合式（3）， 得

ΩTkdk= "ΩTk（-Ωk+

βkdk-1）=-‖Ωk‖2+βkΩTkdk-1≤

-‖Ωk‖2+‖Ωk‖2μ2‖Ωk‖‖dk-1‖‖Ωk‖‖dk-1‖=-1-1μ2‖Ωk‖2.

證畢.

引理1表明， NDF算法的搜索方向dk滿足充分下降性質.

引理2"假設搜索方向dk由式（2）和式（3）產生， 則dk滿足：

（1-1/μ2）‖Ωk‖≤‖dk‖≤（1+1/μ2）‖Ωk‖.

證明： 一方面， 由引理1得-‖Ωk‖‖dk‖≤ΩT

kdk≤-（1-1/μ2）‖Ωk‖2， 整理得‖dk‖≥（1-1/μ2）‖Ωk‖. 另一方面， 由式（2）和式（3）得

‖dk‖=‖-Ωk+βkdk-1‖≤‖Ω

k‖+‖Ωk‖2μ2‖Ωk‖‖dk-1‖

‖dk-1‖=1+1μ2‖Ωk‖.

證畢.

引理2表明， 該算法的搜索方向dk滿足信賴域性質.

引理3"假設序列{ak}由NDF算法產生且假設條件（H1），（H2）成立， 則下列結論成立：

1） {ak}和{bk}是有界的; 2） limk→∞ tk‖dk‖=0.

證明： 類似于文獻［10］的引理3.3可證明結論成立.

引理4"在假設條件（H1），（H2）下， 下式成立：

tk≥minξ，ρ（μ2-1）（1+1/μ2）2μ2（L+σC），

其中C=LM+Lξρ^-11+1μ2N.

證明： 若tk≠ξ， 則式（4）結合tkρ^-1得

-Ω（ak+tkρ^-1dk）Tdklt;σ

tkρ^-1‖Ω（ak+tkρ^-1dk）‖‖dk‖2.

此外， 記a∈E使得Ω（a）=0. 由序

列{ak}的有界性可推出‖ak-a‖≤M， Mgt;0. 于是有

‖Ω（ak+tkρ^-1dk）‖=‖Ω（ak+tkρ^-1

dk）-Ω（a）‖≤L‖ak+tkρ^-1dk

-a‖≤ "L（‖ak-a‖+tkρ^-1‖dk‖）≤LM+Ltkρ^-1‖dk‖.（5）

由引理3可知序列{ak}的有界性和函數Ω（a）的連續性， 于是有‖Ωk‖≤N， Ngt;0， 結合式（5）以及引理2， 得

‖Ω（ak+tkρ^-1dk）‖≤LM+Ltkρ^-11+1μ2‖Ωk‖≤LM+Ltkρ^-11+1μ2NC.

再結合Cauchy-Schwarz不等式， 由引理1得

1-1μ2‖Ωk‖2≤-ΩTkdk=（Ω（a

k+tkρ^-1dk）-Ωk）Td

k-Ω（ak+tkρ^-1dk）Tdk≤

Ltkρ^-1‖dk‖2+σtkρ^-1C‖dk‖2=

tkρ^-1C‖dk‖2（L+σC）≤tkρ^-1（L+σC）1+1μ22‖Ωk‖2，

整理得tk≥ρ（μ2-1）（1+1/μ2）2μ2（L+σC）.

證畢.

定理1"在假設條件（H1），（H2）下， limk→∞ inf‖Ωk‖=0成立.

證明： 反證法. 假設結論不成立， 則存在vgt;0使得‖Ωk‖≥v， 結合引理2得

‖dk‖≥（1-1/μ2）‖Ωk‖≥（1-1/μ2）v.

由引理3可知 limk→∞ tk=0， 與引理4矛盾， 故原結論成立， 證畢.

3"數值仿真

3.1"凸約束非線性方程組問題

為評估NDF算法的數值性能， 本文將其與DFPRPMHS（derivative-free Polak-Ribière-Polyak and modified Hestenes-Stiefel）算法^［15］和CGD（conjugate gradie

nt descent）算法^［16］進行比較. 所選的測試問題來自文獻［10-11］， 每個測試問題的維數設為［1 000，5 000，10 000，50 000，100 000］， 不同維數設置不同的初始點， 以確保測試的全面性， 即

a1=［0，1］n，"a2=1-1n

，1-2n，…，0T，"a3=13，132，…，13nT，

a4=1n，2n，…，nnT，

a5=1，12，…，1nT，"a6=（1，1，…，1）T，"a7=

12，122，…，12nT，"a8=0，1n，…，n-1nT.

3種算法的代碼均在Ubuntu 20.04.2 LTS 64位系統上運行， 所用處理器為Intel（R） Xeon（R） Gold 5115， 主頻為2.40 GHz. 在執行過程中， NDF算法的參數設為l=1.5，

δ=10^-5， σ=10^-4， ρ=0.74， μ1=0.78， μ2=2.4， 其余兩種算法的參數設置與原文獻相同.

為更全面地比較NDF算法、 DFPRPMHS算法和CGD算法的性能， 采用常用于評估數值方法的標準工具^［17］繪制算法性能圖， 其中橫坐標τ表示該算法在解決特定問題時的性能與所有算法中最佳性能的比值倒數， 縱坐標ρ（τ）表示當該算法的性能比率低于參數τ時， 所能成功求解的問題數量占總問題數量的比值， 性能圖中越靠上的曲線表示該算法對應的性能越有優勢. 圖1～圖3分別為3種算法在迭代次數、 函數計算次數和運行時間（CPU時間）上的性能比較結果. 由圖1～圖3可見， NDF算法性能最優. 因此， 在處理大規模凸約束非線性方程組問題時， NDF算法顯示出了更高的效率和穩定性.

3.2"信號重構問題

實驗考慮從k個觀測信號中重構一個大小為n的稀疏信號. 原始信號包含r個隨機非零元素， 觀測信號v含有隨機噪聲， 即v=Qa+κ， 其中Q是隨機生成的高斯矩陣， a是原始信號， 而κ是均值為0、 方差為10^-4的正態分布的高斯噪聲. 將NDF算法與DFPRPMHS算法和CGD算法進行比較， 比較算法的迭代次數、 運行時間和均方誤差（MSE）. MSE用于衡量恢復的受干擾信號相對于原始信號的質量， 即MSE=‖a-a*‖2/n， 其中a*為恢復的信號.

考慮兩種問題規模設置， 即（n，k，r）=（4 096，1 024，128）和（n，k，r）=（8 192，2 048，256）. 實驗結果分別如圖4～圖7所示.

由圖4和圖6可見， 3種算法都能成功重構受噪聲干擾的信號， 且NDF算法以更少的迭代次數和運行時間實現了信號的還原， 信號恢復能力更高效. 為更直觀地展示這些算

法的性能， 針對不同的問題規模設置， 繪制不同指標下的收斂性結果， 如圖5和圖7所示.

由NDF算法在大規模凸約束非線性方程組問題和信號重構問題上的實驗結果可見， 新算法具有較好的潛力和競爭力.

參考文獻

［1］"李丹丹， 李遠飛， 王松華. 一種修正三項Hestenes-Stiefel共軛梯度投影算法及其應用 ［J］. 吉林大學學報（理學版）， 2022， 60（1）： 64-72. （LI D D， LI Y F， WANG

S H. A Modified Three Terms Hestenes-Stiefel Conjugate Gradient Projection Algorithm and Its Application ［J］. Journal of Jilin University （Science Edition）， 2022， 60（1）： 64-72.）

［2］"CHOROWSKI J， ZURADA J M. Learning Understandable Neural Networks with Nonne

gative Weight Constraints ［J］. IEEE Transactions on Neural Networks and Learning Systems， 2015， 26（1）： 62-69.

［3］"DIRKSE S P， FERRIS M C. MCPLIB： A Collection of Nonl

inear Mixed Complementarity Problems ［J］. Optimization Methods and Software， 1995， 5（4）： 319-345.

［4］"MEINTJES K， MORGAN A P. A Methodology for Solving Chemical Equilibrium Systems ［J］. Applied Mathematics and Computation， 1987， 22（4）： 333-361.

［5］"LA CRUZ W， MARTNEZ J， RAYDAN M. Spectral Resid

ual Method without Gradient Information for Solving Large-Scale Nonlinear Systems of Equations ［J］. Mathematics of Computation， 2006， 75： 1429-1448.

［6］"YU Z S， LIN J， SUN J， et al. Spectral Gradient Projection Method for Monotone Nonlinear Equations with Convex Cons

traints ［J］. Applied Numerical Mathematics， 2009， 59（10）： 2416-2423.

［7］"CHENG W Y， XIAO Y H， HU Q J. A Family of Derivative-Free Conjugate Gradien

t Methods for Large-Scale Nonlinear Systems of Equations ［J］. Journal of Computational and Applied Mathematics， 2009， 224（1）： 11-19.

［8］"LI M. A Derivative-Free PRP Method for Solving Large-Scale Nonlinear Syste

ms of Equations and Its Global Convergence ［J］. Optimization Methods and Software， 2014， 29（3）： 503-514.

［9］"FANG X W， NI Q. A New Derivative-Free Conjugate Gradient Method for Large-

Scale Nonlinear Systems of Equations ［J］. Bulletin of the Australian Mathematical Society， 2017， 95（3）： 500-511.

［10］"LI D D， WU J Q， LI Y， et al. A Modified Spectral Gradient Projection-Based Algorithm for Large-Scale Constrained Nonlinear Equ

ations with Applications in Compressive Sensing ［J］. Journal of Computational and Applied Mathematics， 2023， 424： 115006-1-115006-21.

［11］"LI D D， WANG S H， LI Y， et al. A Projection-Based Hybrid PRP-DY Type Conj

ugate Gradient Algorithm for Constrained Nonlinear Equations with Applications ［J］. Applied Numerical Mathematics， 2024， 195： 105-125.

［12］"MA G D， JIN J C， JIAN J B， et al. A Modified Inertial Three-Te

rm Conjugate Gradient Projection Method for Constrained Nonlinear Equations with Applications in Compressed Sensing ［J］. Numerical Algorithms， 2023， 92（3）： 1621-1653.

［13］"WAZIRI M Y， KIRI A I， KIRI A A， et al. A Modified Conjugate

Gradient Parameter via Hybridization Approach for Solving Large-Scale Systems of Nonlinear Equations ［J］. SeMA Journal， 2023， 80（3）： 479-501.

［14］"MEHANDIA A E， CHAIB Y， BECHOUAT T. Two Modified Con

jugate Gradient Methods for Solving Unconstrained Optimization and Application ［J］. RAIRO Operations Research， 2023， 57（2）： 333-350.

［15］"IBRAHIM A H， KUMAM P， KUMAM W. A Family of Derivati

ve-Free Conjugate Gradient Methods for Constrained Nonlinear Equations and Image Restoration ［J］. IEEE Access， 2020， 8： 162714-162729.

［16］"XIAO Y H， ZHU H. A Conjugate Gradient Method to Solve Convex Constrained Monotone Equations with Applications in Compressive Sensin

g ［J］. Journal of Mathematical Analysis and Applications， 2013， 405（1）： 310-319.

［17］"DOLAN E D， MOR J J. Benchmarking Optimization Software with Performance Profiles ［J］. Mathematical Programming， 2001， 91（2）： 201-213.

（責任編輯： 趙立芹）