凸約束方程組的新型無導(dǎo)數(shù)算法及在信號重構(gòu)中的應(yīng)用

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

關(guān)鍵詞： 凸約束非線性方程組； 無導(dǎo)數(shù)； 全局收斂性； 信號重構(gòu)

中圖分類號： O224""文獻標(biāo)志碼： 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）其中函數(shù)Ω：n→n是連續(xù)的. 形如問題（1）的非線性方程組在科學(xué)、 工程、 社會科學(xué)、 管理科學(xué)等領(lǐng)域應(yīng)用廣泛^［1-4］.

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

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

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

1"算"法

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

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

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

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

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‖≤δ， 則算法停止， 否則轉(zhuǎn)步驟2）；

步驟2） 根據(jù)式（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， 轉(zhuǎn)步驟1）.

2"算法性質(zhì)與全局收斂性

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

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

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

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

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

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

證明： 當(dāng)k=0時， ΩT0d0=-‖Ω0‖2≤-（1-1/μ2）‖Ω0‖2. 當(dāng)k≥1時， 將式（2）兩邊左乘ΩTk并結(jié)合式（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滿足充分下降性質(zhì).

引理2"假設(shè)搜索方向dk由式（2）和式（3）產(chǎn)生， 則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滿足信賴域性質(zhì).

引理3"假設(shè)序列{ak}由NDF算法產(chǎn)生且假設(shè)條件（H1），（H2）成立， 則下列結(jié)論成立：

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

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

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

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

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

證明： 若tk≠ξ， 則式（4）結(jié)合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}的有界性和函數(shù)Ω（a）的連續(xù)性， 于是有‖Ωk‖≤N， Ngt;0， 結(jié)合式（5）以及引理2， 得

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

再結(jié)合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"在假設(shè)條件（H1），（H2）下， limk→∞ inf‖Ωk‖=0成立.

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

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

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

3"數(shù)值仿真

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

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

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

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位系統(tǒng)上運行， 所用處理器為Intel（R） Xeon（R） Gold 5115， 主頻為2.40 GHz. 在執(zhí)行過程中， NDF算法的參數(shù)設(shè)為l=1.5，

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

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

3.2"信號重構(gòu)問題

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

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

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

法的性能， 針對不同的問題規(guī)模設(shè)置， 繪制不同指標(biāo)下的收斂性結(jié)果， 如圖5和圖7所示.

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

參考文獻

［1］"李丹丹， 李遠飛， 王松華. 一種修正三項Hestenes-Stiefel共軛梯度投影算法及其應(yīng)用 ［J］. 吉林大學(xué)學(xué)報（理學(xué)版）， 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.

（責(zé)任編輯： 趙立芹）