考虑如下形式的非线性方程组问题

(1.1) $ \begin{equation} F(x)=0, x\in\Omega, \end{equation} $

其中$ F: {{\mathbb R}}^n\rightarrow {{\mathbb R}}^n $是一个连续映射, $ \Omega\subseteq R^{n} $是一个非空闭凸集. 该问题广泛应用于工程技术、管理学、经济学、自然科学等领域, 其数值解法受到了研究者的广泛关注.

非线性方程组问题数值解法中的经典方法之一是牛顿法^[1], 其优点是当选择的初始点靠近极小点时, 算法具有二次收敛速度; 但当初始点远离极小点时, 牛顿法不一定收敛, 并且牛顿法需要计算和存储Jacobian矩阵. 由于实际问题中存在的非线性方程问题不一定是光滑的, 于是广大研究者建立了拟牛顿型算法^[2−5], 这类算法利用了近似Jacobian矩阵, 继承了牛顿法的快速收敛性, 但是它们仍然要计算和存储矩阵. 因此, 这两类算法在求解大规模非线性方程组问题时受到一定的制约.

共轭梯度法、谱梯度法和谱共轭梯度法等一阶最优化方法在求解最优化问题方面受到了研究者的广泛关注, 这类方法迭代结构简单, 存储量小, 具有良好的局部和全局收敛性, 适合求解大规模问题. 近年来, 广大研究者热衷于利用一阶最优化方法的结构, 借助投影算子和无导数线搜索条件求解大规模非光滑的非线性方程组问题, 这类算法避免了计算和存储Jacobian矩阵. 如Cheng^[6]在著名PRP共轭梯度法和超平面投影技术的基础上建立了求解无约束单调方程组问题的PRP型投影算法. Yu等^[7]将改进的谱梯度法与投影法相结合建立了求解凸约束单调方程组的谱梯度投影算法. 受Livieris等^[9]利用无记忆BFGS混合共轭梯度方法求解无约束优化问题的启发, Koorapetse和Kaelo^[8]基于著名的HS和DY两种共轭梯度法, 借助投影算子, 建立了一种求解凸约束单调方程组问题的混合共轭梯度型投影算法. Liu等人^[10]建立了一种求解凸约束单调方程组问题的修正无导数投影算法, 并在自适应无导数线搜索条件下证明了算法的全局收敛性. 基于PRP共轭梯度法与投影法, 刘金魁、孙悦和赵永祥^[11]研究了一种求解凸约束伪单调方程组问题的无导数投影算法, 该算法在不需要假设方程组满足Lipschitz条件下具有全局收敛性和R-线收敛速度.

受上述文献的启发, 基于著名LS共轭梯度法和谱梯度法的结构, 借助投影算子, 本文进一步研究求解凸约束非线性伪单调方程组问题的谱LS型无导数投影算法, 其在不需要线搜索条件下能够保证搜索方向在每次迭代中满足充分下降性. 在常规假设和经典无导数线搜索条件下, 算法具有全局收敛性. 通过大量的数值实验和分析, 新算法对于给定的大规模问题是有效的和稳定的.

为了建立约束问题的迭代算法, 本文需要借助投影算子, 即

(2.1) $ \begin{equation} P_{\Omega}[x]=\arg\min\limits_{y\in\Omega}||x-y||, \forall x\in {{\mathbb R}}^n, \end{equation} $

其中$ P_{\Omega}:{{\mathbb R}}^n\rightarrow \Omega $是一个映射, $ \Omega $为$ {{\mathbb R}}^n $的一个非空闭凸子集. 该算子具有非扩张性, 即

(2.2) $ \begin{equation} ||P_{\Omega}[x]-y||\leq||x-y||, \forall x\in {{\mathbb R}}^n, y\in \Omega. \end{equation} $

基于LS共轭梯度法与谱梯度法, 本文建立新的搜索方向, 即

(2.3) $ \begin{equation} d_k =\left\{ {{\begin{array}{ll} -F(x_k), & k=0, \\ { } -\tau_kF(x_k)-\frac{F(x_k)^{T}y_{k-1}}{F(x_{k-1})^{T}d_{k-1}}s_{k-1}, \ & k\geq1. \end{array} }} \right. \end{equation} $

其中$ y_{k-1}=F(x_k)-F(x_{k-1}) $, $ s_{k-1}=x_k-x_{k-1} $, $ \tau_k $为谱参数.

为了克服LS算法下降性弱的缺点, 我们选取适当的$ \tau_k $满足

(2.4) $ \begin{equation} F_k^Td_k\leq -c||F_k||^2, \forall k\geq0, \end{equation} $

其中$ c>0 $, $ F_k=F(x_k) $. 注意, 为了书写简便, 后面将$ F(x_k) $缩写为$ F_k $.

当$ k\geq 1 $时, 可得

$ \begin{eqnarray} F_k^Td_k&&=-\tau_k||F_k||^2-\frac{F_k^Ty_{k-1}F_k^Ts_{k-1}}{F_{k-1}^Td_{k-1}} \\ &&\leq-\tau_k||F_k||^2+\frac{||F_k||^2\cdot||y_{k-1}||\cdot||s_{k-1}||}{|F_{k-1}^Td_{k-1}|} \\ &&=-\left(\tau_k-\frac{||y_{k-1}||\cdot||s_{k-1}||}{|F_{k-1}^Td_{k-1}|}\right)||F_k||^2. \end{eqnarray} $

取$ \tau_k=c+\frac{||y_{k-1}||\cdot||s_{k-1}||}{|F_{k-1}^Td_{k-1}|} $, (2.4)式成立. 又$ F_0^Td_0=-||F_0||^2 $, 显然取$ c=1 $, (2.4)式仍然成立.

下面根据投影算子及新的搜索方向, 借助经典的无导数型线搜索技术, 本文建立求解凸约束伪单调方程组问题的谱LS型无导数投影算法, 其在每一步迭代均满足充分下降性质.

算法2.1 (SLSDF)

步骤0: 选取初始点$ x_0\in {{\mathbb R}}^n $, 加速参数$ \gamma>0 $, 误差参数$ \varepsilon>0 $, $ \sigma>0 $与$ \beta\in(0, 1) $, $ k:=0 $.

步骤1: 若$ ||F_k||\leq\varepsilon $, 算法终止; 否则转步骤2.

步骤2: 利用(2.3)计算搜索方向$ d_k $.

步骤3: 计算$ z_k=x_k+\alpha_kd_k $, 其中步长$ \alpha_k=\max\{\beta^i:i=0, 1, 2\cdots\} $满足下式

(2.5) $ \begin{equation} -F(x_k+\alpha_kd_k)^Td_k\geq\sigma\alpha_k||d_k||^2. \end{equation} $

步骤4: 若$ z_k\in\Omega $, 且$ ||F(z_k)||\leq\varepsilon $, 则停止; 否则, 计算下一迭代点

(2.6) $ \begin{equation} x_{k+1}=P_{\Omega}[x_k-\gamma\lambda_kF(z_k)], \end{equation} $

其中

$ \lambda_k=\frac{F(z_k)^T(x_k-z_k)}{||F(z_k)||^2}. $

步骤5: 设$ k:=k+1 $, 转步骤1.

下面定理在证明迭代算法的收敛性方面具有重要作用, 其证明参考谱参数的构造.

定理2.1   设序列$ \{d_k\} $和$ \{F_k\} $由SLSDF算法产生, 则对任意非负参数$ c $有

(2.7) $ \begin{equation} F_k^Td_k\leq-c||F_k||^2, \forall k\geq0. \end{equation} $

为了证明SLSDF算法对伪单调方程组问题的全局收敛性, 本文需要下面的假设条件.

假设3.1   (ⅰ) 问题(1.1)的解集$ S $是非空的.

(ⅱ) $ F $满足伪单调性, 即对任意的$ x, y\in {{\mathbb R}}^n $, 有

$ \langle F(x), y-x\rangle\geq0 \Rightarrow \langle F(y), y-x\rangle\geq0. $

(ⅲ) $ F $是Lipschitz连续的, 即存在一个常数$ L>0 $, 使得

$ \|F(x)-F(y)\|\leq L\|x-y\|, \forall x, y\in {{\mathbb R}}^n. $

引理3.1   设$ F $满足假设3.1(ⅰ)–(ⅲ). 若序列$\{ x_{k}\} $和$ \{z_{k}\} $由SLSDF算法生成, 则序列$ \{x_k\} $有界, 进一步有

(3.1) $ \begin{equation} \lim\limits_{k\rightarrow +\infty}||z_k-x_k||=0, \end{equation} $

(3.2) $ \begin{equation} \lim\limits_{k\rightarrow +\infty}||x_{k+1}-x_k||=0. \end{equation} $

证   设$ x^{*}\in S $, 则$ F(x^*)^T(z_k-x^*)\geq0 $. 利用假设3.1(ⅱ)可得

(3.3) $ \begin{equation} F(z_k)^T(z_k-x^*)\geq0, \forall k\geq0. \end{equation} $

根据(2.5)和(3.3)式可得

$ \begin{eqnarray} F(z_k)^T(x_k-x^{*})&&=F(z_k)^T(x_k-z_k)+F(z_k)^T(z_k-x^{*}) \\ &&\geq F(z_k)^T(x_k-z_k) \\ &&\geq\sigma||\alpha_kd_k||^2\geq0. \end{eqnarray} $

利用上述不等式、(2.2)式和参数$ \lambda_k $的定义, 可得

$ \begin{eqnarray} \|x_{k+1}-x^{*}\|^2&&=||P_\Omega[x_k-\gamma\lambda_kF(z_k)]-x^*||^2 \\ &&\leq||x_k-\gamma\lambda_kF(z_k)-x^{*}||^2 \\ &&=||x_k-x^{*}||^2-2\gamma\lambda_kF(z_k)^T(x_k-x^{*})+\gamma^2||\lambda_kF(z_k)||^2 \\ &&\leq||x_k-x^{*}||^2-2\gamma\lambda_kF(z_k)^T(x_k-z_{k})+\gamma^2||\lambda_kF(z_k)||^2 \\ &&=||x_k-x^*||^2-\frac{(2\gamma-\gamma^2)(F(z_k)^T(x_k-z_{k}))^2}{||F(z_k)||^2} \\ &&\leq||x_k-x^*||^2-\frac{\sigma^2(2\gamma-\gamma^2)||\alpha_kd_k||^4}{||F(z_k)||^2} \\ &&=||x_k-x^*||^2-\frac{\sigma^2(2\gamma-\gamma^2)||x_k-z_k||^4}{||F(z_k)||^2}. \end{eqnarray} $

由于$ \gamma\in(0, 2) $, 则上述不等式表明序列$ \{||x_k-x^*||\} $是单调递减的. 对上述不等式进行递推可得

(3.4) $ \begin{equation} ||x_{k+1}-x^*||^2\leq||x_0-x^*||^2-\sigma^2(2\gamma-\gamma^2)\sum\limits_{i=0}^{k}\frac{||x_i-z_i||^4}{||F(z_i)\|^2}, \end{equation} $

故序列$ \{||x_k-x^*||\} $有界. 因此, 序列$ \{||x_k-x^*||\} $收敛, 进而序列$ \{x_k\} $是有界的.

根据假设3.1(ⅲ)及序列$ \{||x_k-x^*||\} $的单调递减性, 对$ x^*\in S $有

$ \begin{eqnarray*} ||F(z_k)||&=&||F(z_k)-F(x^*)||\leq L||z_k-x^*||\leq L||x_k-z_k||+L||x_k-x^*||\\ &\leq& L||x_k-z_k||+L||x_0-x^*||. \end{eqnarray*} $

于是, 根据(3.4)式可得

$ \frac{\sigma^2(2\gamma-\gamma^2)}{L^2}\sum\limits_{k=0}^{+\infty}\frac{||x_k-z_k||^4}{(||z_k-x_k||+||x_0-x^*||)^2}\leq\sigma^2(2\gamma-\gamma^2)\sum\limits_{k=0}^{+\infty}\frac{||x_k-z_k||^4}{||F(z_k)||^2}\leq||x_0-x^*||^2. $

进一步利用收敛级数的性质可知

$ \lim\limits_{k\rightarrow +\infty}\frac{||x_k-z_k||^4}{(||z_k-x_k||+||x_0-x^*||)^2}=0. $

这意味着结论(3.1)成立. 根据(2.2)式及参数$ \lambda_k $的定义可得

$ \begin{eqnarray*} ||x_{k+1}-x_{k}||&&=||P_\Omega[x_k-\gamma\lambda_kF(z_k)]-x_k|| \leq||x_k-\gamma\lambda_kF(z_k)-x_{k}||\nonumber \\ &&\leq\frac{\gamma||F(z_k)||\cdot||x_k-z_k||}{||F(z_k)||^2}||F(z_k)||\nonumber =\gamma||x_k-z_k||.\nonumber \end{eqnarray*} $

于是, 利用(3.1)式及上述不等式, 可得(3.2)式成立. 证毕.

注3.1  根据序列$ \{x_k\} $的有界性和$ F $的连续性, 可知序列$ \{F_k\} $是有界的, 即存在一个正常数$ M $满足

(3.5) $ \begin{equation} ||F_k||\leq M, \forall k\geq0. \end{equation} $

引理3.2   设$ F $满足假设3.1(ⅰ)–(ⅲ), 步长$ \alpha_k $由SLSDF算法产生, 则

(3.6) $ \begin{equation} \alpha_k\geq\max\left\{1, \frac{c\beta||F_k||^2}{(L+\sigma)||d_k||^2}\right\}, \forall k\geq0. \end{equation} $

证   根据(2.5)式可知, $ \alpha_k\beta^{-1} $满足

(3.7) $ \begin{equation} -F(x_k+\alpha_k\beta^{-1}d_k)^Td_k<\sigma\alpha_k\beta^{-1}||d_k||^2. \end{equation} $

于是, 根据(2.7)、(3.7)式及假设3.1(ⅲ), 可得

(3.8) $ \begin{eqnarray} c||F_k||^2&&\leq-F_k^Td_k \\ &&=(F(x_k+\alpha_k\beta^{-1}d_k)-F_k)^Td_k-F(x_k+\alpha_k\beta_k^{-1}d_k)^Td_k \\ &&\leq(L+\sigma)\alpha_k\beta^{-1}||d_k||^2. \end{eqnarray} $

整理可得

$ \alpha_k\geq\frac{c\beta||F_k||^2}{(L+\sigma)||d_k||^2}. $

结论(3.6)得证.证毕.

下面利用定理2.1和引理3.1–3.2证明SLSDF算法对凸约束伪单调方程组问题具有全局收敛性.

定理3.1   设$ F $满足假设3.1(ⅰ)–(ⅲ), 序列$ \{F_k\} $由SLSDF算法产生，则

(3.9) $ \begin{equation} \lim\limits_{k\rightarrow +\infty}\inf||F_k||=0. \end{equation} $

证   反证法证明. 假设(3.9)式不成立, 则存在一个正数$ \upsilon $使得

(3.10) $ \begin{equation} ||F_k||\geq \upsilon, \forall k\geq0. \end{equation} $

根据引理3.1可知, 序列$ \{x_k\} $有界, 则存在一个正常数$ \Gamma $满足

(3.11) $ \begin{equation} ||x_k||\leq\Gamma, \forall k\geq0. \end{equation} $

根据(2.7)和(3.10)式可得

(3.12) $ \begin{equation} ||d_k||\geq c\upsilon, \forall k\geq0. \end{equation} $

根据(2.3)、(2.7)、(3.5)和(3.11)式可知

$ \begin{eqnarray} ||d_k||&&=\left\|-\left(c+\frac{||y_{k-1}||\cdot||s_{k-1}||}{|F_{k-1}^Td_{k-1}|}\right)F_k-\frac{F_k^Ty_{k-1}}{F_{k-1}^Td_{k-1}}s_{k-1}\right\| \\ &&\leq c||F_k||+2\frac{||F_k||\cdot||y_{k-1}||\cdot||s_{k-1}||}{c||F_{k-1}||^2} \\ &&\leq c||F_k||+2\frac{||F_k||(||F_k||+||F_{k-1}||)(||x_k||+||x_{k-1}||)}{c||F_{k-1}||^2} \\ &&\leq cM+\frac{8M^2\Gamma}{c\upsilon^2}\triangleq \hat{M}. \end{eqnarray} $

于是，利用(3.6)和(3.12)式有

$ \begin{eqnarray} \alpha_k||d_k|| &&\geq \max\left\{1, \frac{c\beta||F_k||^2}{(L+\sigma)||d_k||^2}\right\}||d_k|| \\ &&=\max\left\{||d_k||, \frac{c\beta||F_k||^2}{(L+\sigma)||d_k||}\right\} \\ &&\geq \max\left\{c\upsilon, \frac{c\beta\upsilon^2}{(L+\sigma)\hat{M}}\right\}. \end{eqnarray} $

又利用(3.1)式和$ z_k $的定义, 可得

$ \lim\limits_{k\rightarrow +\infty}||z_k-x_k||=\lim\limits_{k\rightarrow +\infty}||\alpha_kd_k||=0. $

这显然产生矛盾. 因此, 假设命题(3.10)不成立, 结论(3.9)成立.

为了检验SLSDF算法的有效性和稳定性, 本节利用SLSDF算法对给定的测试问题进行数值测试, 并与LJJCGPM算法^[10]以及HSDF算法^[11]进行数值比较. SLSDF算法中的参数取值分别为$ \sigma=10^{-4} $, $ \beta=0.6 $, $ c=2 $, $ \gamma=1.1 $; LJJCGPM算法与HSCG算法的参数选取来源于原文献. 程序代码由MATLAB2016a编写, 运行环境为PC 3.20 GHz CPU处理器、8.0 GB内存和Windows 10操作系统.

算法终止条件为$ ||F(x_k)||\leq1.0\times10^{-5} $, 或者$ ||F(z_k)||\leq1.0\times10^{-5} $，$ z_k\in\Omega $. 测试问题格式为:

$ F(x)=(f_1(x), f_2(x), \cdots, f_n(x))^T. $

问题1. 该问题来自文献[12], 并增加约束条件$ \Omega=\{x\in {{\mathbb R}}^n | x\geq-5\} $.

$ f_i(x)={\rm e}^{x_i^2}+3\sin(x_i)\cos(x_i)-1, \; i=1, 2, \cdots, n. $

问题2. 该问题来自文献[13], 其约束条件为$ \Omega=\{x\in {{\mathbb R}}^n | x\geq-1\} $.

$ \begin{eqnarray} f_1(x)&&=4x_1-x_2+{\rm e}^{x_1}-5, \\ f_i(x)&&=-x_{i-1}+4x_i-x_{i+1}+{\rm e}^{x_i}-5, \; i=2, 3, \cdots, n-1, \\ f_n(x) &&=-x_{n-1}+4x_n+{\rm e}^{x_n}-5. \end{eqnarray} $

问题3. Tridiagonal exponential问题^[14], 并增加约束条件$ \Omega={{\mathbb R}}^n_+ $.

$ \begin{eqnarray} f_1(x)&&=x_1-{\rm e}^{\cos(h(x_1+x_2))}, \\ f_i(x)&&=x_i-{\rm e}^{\cos(h(x_{i-1}+x_i+x_{i+1}))}, \; i=2, 3, \cdots, n-1, \\ f_n(x) &&=x_n-{\rm e}^{\cos(h(x_{n-1}+x_n))}, \end{eqnarray} $

其中$ h=\frac{1}{n+1} $.

问题4. ENGVAL函数^[15]的梯度, 并增加约束条件$ \Omega={{\mathbb R}}^n_+ $.

$ \begin{eqnarray} f_1(x)&&=4x_1(x_1^2+x_2^2)-4, \\ f_i(x)&&=4x_i(x_{i-1}^2+x_i^2)+4x_i(x_i^2+x_{i+1}^2)-4, \; i=2, 3, \cdots, n-1, \\ f_n(x) &&=4x_{n}(x_{n-1}^2+x_n^2). \end{eqnarray} $

问题5. Discrete boundry value问题^[16], 并增加约束条件$ \Omega=\{x\in {{\mathbb R}}^n | x\geq-1\} $.

$ \begin{eqnarray} f_1(x)&&=2x_1+0.5h^2(x_1+h)^3-x_2, \\ f_i(x)&&=2x_i+0.5h^2(x_i+hi)^3-x_{i-1}+x_{i+1}, \; i=2, 3, \cdots, n-1, \\ f_n(x) &&=2x_{n}+0.5h^2(x_n+hn)^3-x_{n-1}, \end{eqnarray} $

其中$ h=\frac{1}{n+1} $.

问题6. 该问题来自文献[17], 并增加了约束条件$ \Omega={{\mathbb R}}^n_+ $.

$ f_i(x)=(1-x_i^2)+x_i(1+x_ix_{n-2}x_n)-2, \; i=1, 2, \cdots, n. $

问题7. 该问题来自文献[17], 并增加了约束条件$ \Omega=\{x\in {{\mathbb R}}^n | x\geq-5\} $.

$ f_i(x)=x_i-3x_i\left(\frac{\sin(x_i)}{3}-0.66\right)+2, \; i=1, 2, \cdots, n. $

为了检测SLSDF算法对大规模问题的有效性和适应性, 本文取测试问题的维数为$ n=10000 $和$ n=100000 $, 取定5个初始点: $ x_0^1=(0.1, 0.1, \cdots, 0.1)^T $, $ x_0^2=(0.3, 0.3, \cdots, 0.3)^T $, $ x_0^3=(-2, -2, \cdots, -2)^T $, $ x_0^4=(3, 3, \cdots, 3)^T $, $ x_0^5=(-0.5, -0.5, \cdots, -0.5)^T $; 另外, 本文也选择测试问题的维数为$ n=1000 $和$ n=10000 $, 然后利用"rand"函数在区间$ (-1, 1) $内随机产生初始点, 对测试问题在相同维数下计算3次. 计算结果见表 1–表 7, 其中"Intp"为初始点, "Dim"为问题维数, "NI"为迭代次数, "time"为运行时间(秒), "$ \|F_k\| $"为算法终止时$ F $的2 -范数, "$ x_{rd} $"表示在$ (-1, 1) $内随机产生的初始点. 表 1–表 7表明SLSDF算法与LJJCGPM算法以及HSDF算法在每次实验中都能成功解决测试问题.

为了综合比较算法的整体有效性, 本文采用Dolan和Moré^[18]提出的性能曲线图对三种算法进行了比较, 见图 1, 2. 根据Dolan和Moré 的评价规则, 对给定的测试问题, 图 1, 2表明SLSDF算法在迭代次数和计算时间方面整体上均优于LJJCGPM算法以及HSDF算法.