求解绝对值方程的多元谱梯度投影方法

2022-03-31马昌凤

井冈山大学学报(自然科学版) 2022年2期

关键词：算例收敛性梯度

华瑜，马昌凤

求解绝对值方程的多元谱梯度投影方法

华瑜，*马昌凤

（福建师范大学数学与统计学院，福建，福州 350007）

绝对值方程；多元谱梯度投影算法；全局收敛性；数值实验

0 引言

本文考虑如下绝对值方程(AVE)

绝对值方程是由O.L. Mangasarian等人[1]提出的特殊且不可微的优化问题。在文献[2]中证明了确定AVE(1) 的解的存在是NP-hard 问题。由于绝对值方程广泛分布于优化领域，一般的线性互补问题，线性规划问题，凸二次规划等数学规划问题，见文献[3-5]都可以等效的以AVE(1) 的形式重新表述，于是如何求解绝对值方程引起了许多研究者的关注。

求解绝对值方程AVE(1) 的方法有很多，不同的角度提出了不同的方法，许多研究者提出了数值迭代法求解AVE(1)。在文献[6]中D.K. Salkuyeh 提出Picard-Hss 迭代法求解，在文献[7-8]中Ke等人和Guo等人提出求解绝对值方程(AVE)的SOR 类迭代方法，该方法是通过将AVE 等效地重新表述为2×2块非线性方程而获得。在文献[3]中M.Zamani等人提出一种基于凹极小化方法的新方法，通过将绝对值方程AVE 等价于最小化问题进行求解。

许多求解绝对值方程的数值方法，主要基于非线性优化技术，例如：文献[11-12]中将谱梯度方法应用到无约束的非线性方程组。谱梯度方法的主要特点是搜索方向不需要雅克比矩阵，每次迭代只需要较低的计算量而受到广泛关注。在文献[13]中，L.Grippo 等人提出经典的谱梯度方法。根据谱梯度方法的原理，L.Han 等人在文献[14]中引入多元谱梯度算法。

基于超平面投影的思想，将求解无约束优化问题的多元谱梯度方法推广到求解大规模的单调非线性方程组，该方法的优点是算法不需要方程组的梯度信息，因而可以用于求解非光滑方程组,无需假设可微的条件下，也能建立算法的全局收敛性，算法不需要计算和存储矩阵,因而适合求解大规模问题。在假设1 不是A的特征值的基础上，AVE 可以简化为无约束的非线性单调方程组求解，值得一提的是，在文献[15]中，L. Grippo等人将多元谱梯度投影方法用于求解绝对值方程。

以下介绍谱梯度算法[13]和多元谱梯度投影算法[15]迭代形式：

对于无约束最优化问题：

其中

2）多元谱梯度投影方法迭代形式：

其中

本文后续部分安排如下：第2节介绍预备知识，提出求解绝对值方程的多元谱梯度投影算法；第3 节全局收敛性分析；第4节引用绝对值方程的例子进行数值比较；第5节结论。

1 预备知识和算法

令

将问题(1) 转化为(9)，根据多元谱梯度方法求解绝对值方程的思想，提出改进的多元谱梯度投影算法如下：

算法1（MMSGP算法）

步2 计算搜索方向：

计算

步4 通过超平面投影更新的迭代点：

其中

3）由步（2.c）化简可得，

2 收敛性分析

一方面：

注意到，

因此，

另一方面，

以下引理证明算法1是适定的。

和

以下证明算法1的全局收敛性。

和

证明：

由(8)和(12)得

根据(20)-(22)可得：

根据(23) 和(24) 有

从而

以下将讨论两种可能的情况：

另一方面，

其中，

于是根据(15)，(28)，(29)，有

综上，算法1的全局收敛性证明完毕。

3 数值实验

表1 符号说明

Table 1 Symbol description.

算例测试的维数迭代次数算法终止的时间

算例1[8]考虑绝对值方程(1)

表2 算例1的数值结果

算例2[18]绝对值方程(1)矩阵由MATLAB命令随机产生，

表3 算例2的数值结果

Table 3 Numerical results of calculation example 2

10330.0039.08e - 07230.0015.43e - 07260.0023.82e - 07

算例3[19]绝对值方程(1)矩阵由以下形式得到，

表4 算例3的数值结果

Table 4 Numerical results of calculation example 3

8450.0055.52e-07280.0019.39e-07 128900.376.33e-07240.0238.80e-07 200710.0999.63e-07500.0349.91e-07 1500123118.60e-0710399.98e-07

本算例给出的是对角线为4n，次对角线相等，其余元素都为0.5的矩阵，表4可以看出，加入松弛因子后的迭代次数少于文献[15]中的方法（MMSGP）的迭代次数，且CPU时间更短。

4 结论

通过以上的数值结果，可以得出结论，本文所改进的算法优于文献[15]中的方法（MMSGP），在迭代次数和CPU时间上表现明显，关于改进多元谱梯度投影算法的方法有很多，下降方向的选取对迭代效果也有一定的影响，之后将继续研究如何对下降方向进行改进，实现更好的迭代效果。

[1] Mangasarian O L , Meyer R R . Absolute value equations[J]. Linear Algebra Appl,2006,419(2-3): 359-367.

[2] Mangasarian O L . Absolute value programming[J]. Comput. Optim. Appl, 2007, 36(1): 43-53.

[3] Zamani M, Hladík M. A new concave minimization algorithm for the absolute value equation solution[J]. Optimization Letters, 2021: 1-14.

[4] Bai Z Z. Modulus-based matrix splitting iteration methods for linear complementarity problems[J]. Numer. Linear Algebr, 2010, 17(6): 917-933.

[5] Mangasarian O L. A hybrid algorithm for solving the absolute value equation[J].Optim.Lett., 2015,9(7): 1469-1474.

[6] Salkuyeh D K.The picard-HSS iteration method for absolute value equations[J].Optim.Lett., 2014,8:2191-2202.

[7] Ke Y F, Ma C F. SOR-like iteration method for solving absolute value equations[J]. Appl. Math. Comput, 2017, 311: 195-202.

[8] Guo P, Wu S L, Li C X. On the SOR-like iteration method for solving absolute value equations [J].Appl. Math. Lett, 2019,97: 107-113.

[9] Mangasarian O L. Absolute value equation solution via concave minimization[J]. Optim. Lett, 2007, 1(1): 3-8.

[10] Mangasarian O L. A generalized Newton method for absolute value equations[J]. Optim. Let.,2009, 3: 101-108.

[11] Cruz W La, Raydan M. Nonmonotone spectral methods for large-scale nonlinear systems[J]. Optim. Methods Softw, 2003: 583-599.

[12] Cruz W La, Martínez J M , Raydan M. Spectral residual method without gradient information for solving large-scale nonlinear systems of equations[J].Math. Comput., 2006,75: 1449-1466.

[13] Grippo L, Lampariello F, Lucidi S. A nonmonotone line search technique for Newton’s method[J]. SIAM J. Numer. Anal., 1986, 23: 707-716.

[14] Han L, Yu G, Guan L, Multivariate spectral gradient method for unconstrained optimization[J]. Appl. Math. Comput.,2008,201 (1): 621-630.

[15] Yu Z, Li L, Yuan Y. A modified multivariate spectral gradient algorithm for solving absolute value equations[J]. Applied Mathematics Letters, 2021: 107-461.

[16] Amini K, Kamandi A. A new line search strategy for finding separating hyperplane in projection-based methods[J]. Numerical Algorithms, 2015,70(3): 559-570.

[17] Rohn J. A theorem of the alternatives for the equation Ax+B|x|=b[J].Linear Multilinear Algebra,2004,52(6):421-426.

[18] Wang A , Wang H ,Deng Y. Interval algorithm for absolute value equations[J]. Cent. Eur. J. Math.,2011,9: 1171-1184.

[19] Noor M A, Iqbal J, Noor K I, et al. On an iterative method for solving absolute value equations[J]. Optim. Lett.,2012,6: 1027-1033.

[20] Yu Z, Sun J, Qin Y. A multivariate spectral projected gradient method for bound constrained optimization[J]. Comput.Appl. Math. 2011, 235(8): 2263-2269.

[21] Yu G, Niu S, Ma J. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints[J].Ind.Manag.Optim.,2013,9(1): 117-129.

MULTIVARIATE SPECTRAL GRADIENT PROJECTION METHOD FOR SOLVING ABSOLUTE VALUE EQUATION

HUA Yu,*MA Chang-feng

（School of Mathematics and Statistics, Fujian Normal University, Fuzhou, Fujian 350007, China）