数学物理学报, 2022, 42(6): 1886-1897 doi:

论文

非线性伪单调方程组的谱LS型投影算法

张宁,, 刘金魁,

重庆三峡学院数学与统计学院 重庆 404100

Spectral LS-type Projection Algorithm for Solving Nonlinear Pseudo-Monotone Equations

Zhang Ning,, Liu Jinkui,

School of Mathematics and Statistics, Chongqing Three Gorges University, Chongqing 404100

通讯作者: 刘金魁, E-mail: liujinkui2006@126.com

收稿日期: 2022-03-22  

基金资助: 重庆市自然科学基金.  cstc2021jcyj-msxmX0233
重庆三峡学院研究生科研创新项目.  YJSKY22058

Received: 2022-03-22  

Fund supported: the Chongqing Research Program of Basic Research and Frontier Technology.  cstc2021jcyj-msxmX0233
the Chongqing Three Gorges University Graduate Research Innovation Project.  YJSKY22058

作者简介 About authors

张宁,E-mail:zhangning19990405@126.com , E-mail:zhangning19990405@126.com

Abstract

Based on the structures of the spectral gradient method and the famous LS conjugate gradient method, in this paper we establish an spectral LS-type derivative-free projection algorithm to solve nonlinear pseudo-monotone equations with convex constraints. By using the spectral parameter, the proposed method can generate the descent direction in each iterate, which is independent of any line search. Under some usual assumptions, the global convergence of the proposed method is proved by using the classical derivative-free line search condition. Numerical experiments show that the proposed method inherits the excellent computational performance of the LS conjugate gradient method and improves its stability.

Keywords: Nonlinear equations ; Derivative-free projection method ; Derivative-free line search ; Global convergence

PDF (431KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

张宁, 刘金魁. 非线性伪单调方程组的谱LS型投影算法. 数学物理学报[J], 2022, 42(6): 1886-1897 doi:

Zhang Ning, Liu Jinkui. Spectral LS-type Projection Algorithm for Solving Nonlinear Pseudo-Monotone Equations. Acta Mathematica Scientia[J], 2022, 42(6): 1886-1897 doi:

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矩阵. 由于实际问题中存在的非线性方程问题不一定是光滑的, 于是广大研究者建立了拟牛顿型算法[25], 这类算法利用了近似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 投影算法

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

$ \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 $的一个非空闭凸子集. 该算子具有非扩张性, 即

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

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

$ \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 $满足

$ \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 $时, 可得

$ \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\} $满足下式

$ \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 $, 则停止; 否则, 计算下一迭代点

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

其中

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

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

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

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

3 算法的收敛性

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

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

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

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

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

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

$ \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(ⅱ)可得

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

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

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

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

$ \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 $

于是, 根据(3.4)式可得

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

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

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

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

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

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

$ \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} $满足

$ \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(ⅲ), 可得

$ \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} $

整理可得

结论(3.6)得证.证毕.

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

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

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

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

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

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

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

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

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

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

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

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

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

4 数值试验

为了检验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 $. 测试问题格式为:

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

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

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

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

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

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

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

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

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

为了检测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算法在每次实验中都能成功解决测试问题.

表 1   算法对问题1的测试结果

IntpDimSLSDFHSDFLJJCGPM
NI/time/$\|F_k\|$NI/time/$\|F_k\|$NI/time/$\|F_k\|$
$x_0^1$1000010/0.27/8.35775E-069/0.05/7.69126E-0610/0.13/6.24219E-06
10000011/0.54/5.36400E-0610/0.35/4.40940E-0613/0.44/3.06195E-06
$x_0^2$1000011/0.07/3.95144E-0610/0.05/2.24586E-0611/0.42/2.52040E-06
10000012/0.59/2.53604E-0610/0.35/7.10203E-0611/0.36/1.95314E-06
$x_0^3$1000014/0.15/5.38909E-0618/0.27/8.08404E-0613/0.09/2.45327E-06
10000015/0.63/3.45872E-0619/0.84/8.64032E-0613/0.48/7.75972E-06
$x_0^4$1000010/0.07/3.16713E-0616/0.16/8.47098E-0610/0.08/5.68024E-06
10000011/0.62/1.47420E-0617/0.74/9.05390E-0611/0.35/7.97022E-06
$x_0^5$1000011/0.06/4.81393E-0611/0.05/5.31729E-0612/0.07/4.65517E-06
10000012/0.52/3.08958E-0612/0.45/3.04840E-0611/0.32/4.10582E-06
$x_{rd}$100018/0.46/5.95037E-0623/0.02/7.65046E-0618/0.02/7.26018E-06
100014/0.01/2.53885E-0617/0.02/2.36570E-0617/0.01/3.03249E-06
100018/0.01/2.69658E-0616/0.01/9.89883E-0619/0.01/4.60776E-06
1000016/0.25/3.56274E-0619/0.1/8.93693E-0620/0.07/2.70993E-06
1000017/0.09/8.58381E-0616/0.06/8.76281E-0624/0.08/3.85628E-06
1000016/0.08/2.41299E-0621/0.08/3.38577E-0620/0.06/4.22776E-06

新窗口打开| 下载CSV


表 2   算法对问题2的测试结果

IntpDimSLSDFHSDFLJJCGPM
NI/time/$\|F_k\|$NI/time/$\|F_k\|$NI/time/$\|F_k\|$
$x_0^1$1000014/0.11/2.28152E-0622/0.13/6.86367E-0649/0.24/6.82665E-06
10000016/1.03/2.10679E-0625/1.44/6.43402E-0654/2.08/6.77842E-06
$x_0^2$1000012/0.08/2.04626E-0621/0.14/9.39860E-0652/0.24/7.26662E-06
10000019/1.16/1.76761E-0624/1.23/5.72030E-0651/1.87/7.03466E-06
$x_0^3$1000012/0.09/8.92636E-0627/0.17/7.87962E-0649/0.25/6.42977E-06
10000015/0.92/4.24272E-0624/1.43/7.22225E-0653/2.02/6.98044E-06
$x_0^4$1000014/0.12/8.31650E-0622/0.15/8.32467E-0649/0.2/6.63369E-06
10000023/1.57/3.13326E-0629/1.64/9.69912E-0659/2.12/8.06344E-06
$x_0^5$1000020/0.17/9.18226E-0622/0.13/7.27369E-0651/0.27/9.47091E-06
10000018/1.75/5.89499E-0623/1.16/5.15380E-0654/1.98/7.31554E-06
$x_{rd}$100013/0.02/9.55053E-0625/0.03/9.45970E-0668/0.04/7.64093E-06
100013/0.01/6.91733E-0626/0.02/6.77331E-0658/0.03/7.69436E-06
100014/0.01/3.27047E-0622/0.01/9.13867E-0658/0.02/7.50824E-06
1000016/0.1/4.89654E-0642/0.28/5.62731E-0664/0.28/9.72200E-06
1000019/0.13/5.67477E-0640/0.22/8.89704E-0664/0.26/9.52940E-06
1000018/0.12/4.61617E-0627/0.16/7.33332E-0663/0.31/9.64623E-06

新窗口打开| 下载CSV


表 3   算法对问题3的测试结果

IntpDimSLSDFHSDFLJJCGPM
NI/time/$\|F_k\|$NI/time/$\|F_k\|$NI/time/$\|F_k\|$
$x_0^1$1000017/0.07/2.81228E-0616/0.06/8.52110E-0657/0.24/9.14599E-06
10000016/0.39/8.13031E-0620/0.49/6.11814E-0644/0.81/8.87728E-06
$x_0^2$1000015/0.06/9.95448E-0616/0.06/3.98212E-0658/0.14/9.11972E-06
10000015/0.39/4.47081E-0618/0.42/4.45220E-0645/0.81/8.73945E-06
$x_0^3$1000014/0.06/5.53121E-0612/0.05/1.99091E-0623/0.08/8.77438E-06
10000015/0.36/5.62202E-0615/0.37/9.14178E-0640/0.73/7.49943E-06
$x_0^4$1000016/0.12/4.56086E-0613/0.05/1.27684E-0653/0.16/9.12098E-06
10000018/0.41/9.53202E-0618/0.42/2.94888E-0640/0.73/9.09379E-06
$x_0^5$1000014/0.05/6.46989E-0617/0.06/3.78712E-0656/0.14/9.14812E-06
10000017/0.41/8.76135E-0615/0.34/7.77275E-0641/0.72/8.76429E-06
$x_{rd}$100015/0.02/5.12728E-0614/0.02/6.96159E-0670/0.03/6.06227E-06
100016/0.01/3.31604E-0615/0.01/5.33449E-0671/0.02/6.04804E-06
100015/0.01/8.42411E-0617/0.01/3.22741E-0667/0.02/9.92832E-06
1000017/0.06/3.04681E-0617/0.07/1.89898E-0657/0.15/9.11084E-06
1000017/0.06/3.77356E-0617/0.05/3.52052E-0657/0.12/9.21500E-06
1000017/0.05/3.04315E-0616/0.04/6.01119E-0653/0.12/9.08530E-06

新窗口打开| 下载CSV


表 4   算法对问题4的测试结果

IntpDimSLSDFHSDFLJJCGPM
NI/time/$\|F_k\|$NI/time/$\|F_k\|$NI/time/$\|F_k\|$
$x_0^1$1000034/0.15/6.71745E-0622/0.08/9.64604E-0658/0.17/8.00695E-06
10000040/1.33/5.98689E-0630/0.88/4.99211E-0656/1.22/6.92717E-06
$x_0^2$1000033/0.12/6.46636E-0626/0.11/9.37117E-0661/0.17/7.19919E-06
10000033/1.04/8.47901E-0631/0.96/4.23145E-0658/1.3/9.11678E-06
$x_0^3$1000037/0.15/5.39551E-0631/0.12/6.05411E-0665/0.19/8.18695E-06
10000040/1.32/7.67252E-0633/1.01/6.90460E-0662/1.39/7.08876E-06
$x_0^4$1000030/0.13/4.75619E-0630/0.11/6.52395E-0670/0.17/7.42661E-06
10000040/1.31/6.29701E-0637/1.17/4.36692E-0668/1.48/7.09583E-06
$x_0^5$1000030/0.12/8.35595E-0628/0.12/8.82222E-0657/0.14/9.92298E-06
10000037/1.12/7.90263E-0626/0.73/7.80168E-0655/1.21/8.54528E-06
$x_{rd}$100042/0.03/7.25125E-0637/0.03/6.49794E-0684/0.03/7.28839E-06
100050/0.02/8.09325E-0631/0.01/8.94628E-0670/0.02/9.50344E-06
100050/0.02/8.03816E-0638/0.01/7.83207E-0679/0.02/8.27614E-06
1000045/0.19/4.45461E-0647/0.16/4.26260E-06104/0.23/9.05904E-06
1000055/0.19/5.31741E-0640/0.12/7.73662E-0692/0.19/8.53725E-06
1000056/0.18/5.93166E-0642/0.14/7.89234E-0690/0.2/9.27884E-06

新窗口打开| 下载CSV


表 5   算法对问题5的测试结果

IntpDimSLSDFHSDFLJJCGPM
NI/time/$\|F_k\|$NI/time/$\|F_k\|$NI/time/$\|F_k\|$
$x_0^1$1000015/0.2/9.30794E-0624/0.26/8.99460E-0653/0.41/7.45327E-06
10000025/2.93/6.43615E-0619/1.78/8.38742E-0655/4.19/9.53306E-06
$x_0^2$1000017/0.25/8.73580E-0626/0.29/9.71544E-0657/0.46/8.26386E-06
10000034/3.94/6.56639E-0621/2.03/8.86982E-0660/4.54/6.42017E-06
$x_0^3$1000037/0.45/6.52915E-0631/0.35/6.52281E-06199/1.46/9.56048E-06
10000054/6.35/7.12462E-0626/2.58/9.96656E-06200/13.6/8.85841E-06
$x_0^4$1000033/0.41/3.86804E-0629/0.34/4.86781E-0663/0.5/8.09248E-06
10000049/5.59/6.35406E-0629/2.91/9.44800E-0662/4.71/7.91238E-06
$x_0^5$1000019/0.25/7.35353E-0627/0.3/7.77302E-0659/0.5/8.37336E-06
10000032/3.82/6.28651E-0623/2.34/5.85602E-0655/4.19/6.79479E-06
$x_{rd}$100023/0.04/9.62598E-0631/0.05/8.91162E-06201/0.15/8.25980E-06
100025/0.03/5.50717E-0634/0.04/9.17404E-06197/0.14/7.45662E-06
100024/0.03/3.32316E-0634/0.04/7.69712E-0664/0.05/9.94895E-06
1000033/0.4/3.16616E-0634/0.47/8.97918E-0667/0.49/7.79202E-06
1000037/0.43/8.07076E-0633/0.33/8.94202E-0667/0.49/7.33025E-06
1000028/0.38/5.46344E-0638/0.42/5.74752E-0669/0.49/7.27176E-06

新窗口打开| 下载CSV


表 6   算法对问题6的测试结果

IntpDimSLSDFHSDFLJJCGPM
NI/time/$\|F_k\|$NI/time/$\|F_k\|$NI/time/$\|F_k\|$
$x_0^1$1000012/0.04/3.53915E-0610/0.04/1.82363E-0626/0.05/7.73313E-06
10000013/0.28/2.65924E-0610/0.19/5.76683E-0628/0.4/6.73508E-06
$x_0^2$1000013/0.04/3.17492E-0610/0.04/4.73744E-0623/0.05/7.15729E-06
10000014/0.32/2.38556E-0611/0.21/1.76149E-0625/0.42/6.23357E-06
$x_0^3$100009/0.03/1.67451E-0611/0.04/1.43408E-0623/0.05/6.28294E-06
1000009/0.18/5.29525E-0611/0.19/4.53495E-0625/0.39/5.47206E-06
$x_0^4$1000011/0.03/6.75249E-0611/0.03/1.44773E-0625/0.05/6.65329E-06
10000012/0.24/5.07367E-0611/0.21/4.57811E-0627/0.41/5.79461E-06
$x_0^5$1000012/0.04/7.54576E-0611/0.03/1.80320E-0626/0.05/9.15601E-06
10000013/0.27/5.66971E-0611/0.19/5.70223E-0628/0.42/7.97432E-06
$x_{rd}$100015/0.01/4.65847E-0621/0.02/8.13107E-0630/0.02/8.92921E-06
100062/0.01/5.37181E-06124/0.04/9.46999E-06376/0.05/9.07041E-06
100036/0.01/6.96704E-06114/0.03/8.90380E-06283/0.04/9.54975E-06
1000067/0.13/8.04304E-0638/0.07/8.47795E-06254/0.33/7.17963E-06
1000029/0.06/7.79403E-0628/0.05/9.51788E-06142/0.18/7.03547E-06
1000030/0.05/7.67295E-0632/0.06/8.66574E-06371/0.43/7.84702E-06

新窗口打开| 下载CSV


表 7   算法对问题7的测试结果

IntpDimSLSDFHSDFLJJCGPM
NI/time/$\|F_k\|$NI/time/$\|F_k\|$NI/time/$\|F_k\|$
$x_0^1$100006/0.03/3.45393E-0717/0.06/5.54564E-0618/0.05/5.65483E-06
1000006/0.2/1.09223E-0618/0.44/6.05833E-0619/0.38/6.55944E-06
$x_0^2$100006/0.03/6.20504E-0716/0.05/4.33525E-0618/0.05/8.39471E-06
1000006/0.2/1.96221E-0617/0.52/4.73604E-0619/0.4/9.73760E-06
$x_0^3$100007/0.03/4.59950E-0717/0.06/8.08326E-0617/0.05/5.97154E-06
1000007/0.24/1.45449E-0618/0.44/8.83056E-0618/0.35/6.92680E-06
$x_0^4$100005/0.02/4.07959E-0617/0.06/6.42071E-0618/0.05/6.74412E-06
1000006/0.18/2.53313E-0718/0.43/7.01431E-0619/0.39/7.82298E-06
$x_0^5$100005/0.03/3.42253E-0714/0.05/9.48173E-0615/0.05/8.28338E-06
1000005/0.16/1.08230E-0616/0.42/3.57842E-0616/0.33/9.60847E-06
$x_{rd}$100014/0.01/8.67102E-0717/0.02/5.33128E-0617/0.02/8.07045E-06
100013/0.01/9.50521E-0617/0.01/5.32577E-0617/0.01/8.23321E-06
100015 0.01/7.80850E-0617/0.01/5.27943E-0617/0.01/7.88612E-06
1000014/0.05/6.96719E-0618/0.05/5.81512E-0618/0.05/9.32633E-06
1000014/0.04/5.16981E-0618/0.06/5.81045E-0618/0.04/9.52345E-06
1000014/0.04/6.15402E-0618/0.04/5.82664E-0618/0.03/9.36081E-06

新窗口打开| 下载CSV


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

图 1


图 2


参考文献

Dennis J E , Schnabel R B . Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Philadelphia: SIAM, 1983

[本文引用: 1]

Solodov M V , Svaiter B F . A Globally Convergent Inexact Newton Method for Systems of Monotone Equations. Kluwer: Kluwer Academic Publisher, 1988

[本文引用: 1]

Zhou G , Toh K C .

Superline convergence of a Newton-type algorithm for monotone equations

Journal of Optimization Theory and Applications, 2005, 125, 205- 221

DOI:10.1007/s10957-004-1721-7     

Li D H , Fukushima M .

A globally and superlinearly convergent Gauss-Newton based BFGS method for symmetric equations

SIAM Journal on Numerical Analysis, 1999, 37, 152- 172

DOI:10.1137/S0036142998335704     

Zhou W J .

A modified BFGS type quasi-Newton method with line search for symmetric nonlinear equations problems

Journal of Computational and Applied Mathematics, 2020, 367, 112454

DOI:10.1016/j.cam.2019.112454      [本文引用: 1]

Cheng W Y .

A PRP type method for systems of monotone equations

Mathematical and Computer Modelling, 2009, 50, 15- 20

DOI:10.1016/j.mcm.2009.04.007      [本文引用: 1]

Yu Z S , Ji L , Sun J , et al.

Spectral gradient projection method for monotone nonlinear equations with convex constraints

Applied Numerical Mathematics, 2009, 59, 2416- 2423

DOI:10.1016/j.apnum.2009.04.004      [本文引用: 1]

Koorapetse M , Kaelo P .

A derivative-free conjugate gradient projection method based on the memoryless BFGS update

Malaya Journal of Matematik, 2020, 8, 502- 509

DOI:10.26637/MJM0802/0031      [本文引用: 1]

Livieris I E , Tampakas V , Pintelas P .

A descent hybrid conjugate gradient method based on the memoryless BFGS update

Numerical Algorithms, 2018, 79, 1169- 1185

DOI:10.1007/s11075-018-0479-1      [本文引用: 1]

Liu P J , Jian J B , Jiang X Z .

A new conjugate gradient projection method for convex constrained nonlinear equations

Complexity, 2020, 2020, 1- 14

[本文引用: 2]

刘金魁, 孙悦, 赵永祥.

凸约束伪单调方程组的无导数投影算法

计算数学, 2021, 43, 388- 400

DOI:10.12286/jssx.j2020-0659      [本文引用: 2]

Liu J K , Sun Y , Zhao Y X .

A derivative-free projection algorithm for solving pseudo-monotone equations with convex constraints

Mathematica Numerica Sinica, 2021, 43, 388- 400

DOI:10.12286/jssx.j2020-0659      [本文引用: 2]

Gao P T , He C J .

An efficient three-term conjugate gradient method for nonlinear monotone equations with convex constraints

Calcolo, 2018, 55, 1- 17

DOI:10.1007/s10092-018-0244-9      [本文引用: 1]

Liu J K , Lu Z L , Xu J L , et al.

An efficient projection-based algorithm without Lipschitz continuity for large-scale nonlinear pseudo-monotone equations

Journal of Computational and Applied Mathematics, 2021, 403, 113822

[本文引用: 1]

Bing Y , Lin G .

An efficient implementation of Merrill's method for sparse or partially separable systems of nonlinear equations

SIAM Journal on Optimization, 1991, 2, 206- 221

[本文引用: 1]

Conn A R , Gould N I M , Toint Ph L .

CUTEr: constrained and unconstrained testing enviroment

ACM Transactions on Mathematical Software, 1995, 21, 123- 160

DOI:10.1145/200979.201043      [本文引用: 1]

Moŕe J J , Garbow B S , Hillström K E .

Testing uncosntrained optimization software

ACM Transactions on Mathematical Software, 1981, 7, 17- 41

DOI:10.1145/355934.355936      [本文引用: 1]

Waziri M Y , Muhammad H U , Halilu A S , Ahmed K .

Modified matrix-free methods for solving system of nonlinear equations

Optimization, 2021, 71, 2321- 2340

[本文引用: 2]

Dolan E D , Moŕe J J .

Benchmarking optimization software with performance profiles

Mathematical Programming, 2002, 91, 201- 213

DOI:10.1007/s101070100263      [本文引用: 1]

/