求解凸约束非线性方程组的无导数DY投影算法

李丹丹，王松华

(1. 广州华商学院应用数学系，广州 511300；2. 百色学院数学与统计学院，百色 533000)

凸约束非线性方程组广泛应用于压缩感知中的信号恢复、图像处理、等离子体物理学、非线性光学等问题[1-4]，因此，研究求解带有凸约束非线性方程组问题的高效数值算法具有重要的理论价值与实际应用意义．于是本文考虑如下带凸约束的非线性方程组问题：

其中，φ: A → Rn是连续非线性函数，且 A ⊆ Rn是一个非空闭凸集．

目前在求解问题(1)的众多数值方法中，梯度类方法[5-6]表现较好，考虑到共轭梯度法的低存储需求与迭代框架简单等优点，学者们试图将共轭梯度法与投影技术结合应用于求解问题(1)，如文献[7-9]．文献[10]研究了共轭梯度法的进展，提到经典的共轭梯度法(如HS算法、LS算法、DY算法等)不能同时满足收敛效果好、数值效果佳的事实，并讨论了三项共轭梯度方法的构造形式．文献[11]在经典HS方法的基础上研究一种求解问题(1)的修正三项共轭梯度投影算法．文献[12]对经典LS方法进行修正，提出了一种新的三项共轭梯度投影算法来求解凸约束非线性单调方程组问题．文献[13]建立了一个高效求解无约束优化问题的新型三项共轭梯度法，该方法的搜索方向在不依赖于任意线搜索的情况下自动满足充分下降性且数值效果显著．文献[14]将其推广到带简单凸约束的非线性方程组问题．考虑到经典DY算法具有较强的收敛性，但数值效果欠佳的情况，受文献[14]构造思想的启发，对DY算法的搜索方向进行修正，提出了一种无导数修正DY三项共轭梯度投影算法用于求解凸约束非线性方程组问题．

1 算法描述

文献[10]总结的三项共轭梯度方向构造形式为

式中：参数βk为共轭参数；为了方便描述，φ(xk)记为φk；pk可定义为φk、dk-1或γk-1=φk-φk-1等任一形式．

一般共轭梯度法的迭代式为 zk+1=zk+αkdk，其中αk为确定的步长，dk为搜索方向．

文献[14]设计了一个三项共轭梯度方向，其定义为

其中：σ1,σ2＞0,符号·代表Euclidean范数，

最后，引入投影算子，其定义为从集合 Rn到非空闭凸集A的映射，即

该算子具有以下良好性质：

综上所述，下面给出求解带凸约束的非线性方程组算法描述．

算法MLLY的步骤：

(1)给出参数β,σ＞0,ρ∈ (0,1),σ1,σ2＞0,ε≥0，初始点 x0∈ Rn，令k=0；

(2)计算φ(xk)，若φ(xk)≤ε，则算法停止；

(3)搜索方向dk是由式(4)计算而得；

(4)令 vk=zk+αkdk，其中步长满足如下不等式：

(5)计算φ(vk)，若φ(vk)≤ε，则算法停止，否则通过如下方法计算下一个迭代点zk+1，即

(6)令k:=k+1，转步骤(2)．

2 收敛性分析

本节先分析算法MLLY产生的搜索方向拥有充分下降性，再证明由式(5)产生步长的存在性，最后讨论算法MLLY具有全局收敛的性质．下面给出合理的假设．

假设S

(S1) 映射 :φRn→Rn是单调连续的，即

(S2) 问题(1)的解集非空；

(S3) 映射 :φn→nR R是Lipschitz连续的，即存在常数ζ＞0，有

引理1假定序列{ xk}和{dk}是由算法MLLY产生的，若σ1-(1 +σ2)28σ1＞0和 0＜σ1≤1，则存在正常数χ使得如下不等式成立：

证明：当k=0时，令那么式(8)显然成立．当k≥1时，令利 用 不 等 式得

引理2若假设S条件成立，对于∀k，存在步长kα满足式(5)．

证明：类似于文献[15]中的引理2.2可以证明结论成立．

引理3若假设S条件成立，算法MLLY产生序列{zk}和{vk}，那么对于问题(1)的最优解z*，有

证明：类似于文献[9]中的引理2可以证明此结论成立．

定理1若假设S条件成立，算法MLLY产生的序列成立．

上式联合式(7)、式(8)和Cauchy-Schwarz不等式得

整理上式得

上式两边对k取极限，由式(10)推得

故结论成立．证毕．

3 数值实验

为了检测算法MLLY的性能表现，本节将其与算法ACGD[16]和算法MFRM[17]进行比较．算法ACGD和算法MFRM保持原有的参数设置，算法MLLY的参数设置为β=1，ρ=0.55，σ=0.001，σ1=0.7，σ2=0.3，ε=10-5．所 有 算 法 都 采 用MATLAB2014a软件编写并运行，运行环境为Windows10(64bite)，RAM：8GB，CPU3.60GHz．测试问题共10个，分别来自文献[1，17-20]，对每个测试问题选取不同的维数且设置维数为[1000 5000 10000 50000 100000]，迭代次数上限为800．

计算出3种算法在求解过程中的3个指标(总迭代次数、函数计算总次数、CPU运行总时间)的数据，采用曲线计算方法[21]绘制性能图，进而更直观地分析对比3种算法的性能效果，结果如图1所示．图1从3个角度(迭代次数、函数计算次数和CPU运行时间)进行评价，曲线越靠上，表明算法越稳定与有效．

图1中横坐标的t指的是给定的数值比率，纵坐标的计算公式为

图1 不同算法的比较Fig. 1 Comparison profile of different algorithms

从图1可看出，算法MLLY的曲线在图中均位于其他两个算法之上，这表明在3个指标上算法MLLY均优于算法ACGD和算法MFRM，具有较好的鲁棒性．

4 结 语

在修正经典DY共轭参数及文献[14]搜索方向的基础上，本文提出了求解一类带凸约束大规模非线性方程组问题的无导数修正DY共轭梯度投影算法．新方法拥有充分下降性和全局收敛的良好性质．数值结果表现了新算法的有效性，更适合求解大规模非线性方程组问题．同时，也可进一步研究新算法在处理信号恢复与图像处理等问题上的实用性．