求解絕對值方程的多元譜梯度投影方法

華 瑜，馬昌鳳

求解絕對值方程的多元譜梯度投影方法

華 瑜，*馬昌鳳

（福建師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，福建，福州 350007）

絕對值方程；多元譜梯度投影算法；全局收斂性；數(shù)值實驗

0 引言

本文考慮如下絕對值方程(AVE)

絕對值方程是由O.L. Mangasarian等人[1]提出的特殊且不可微的優(yōu)化問題。在文獻(xiàn)[2]中證明了確定AVE(1) 的解的存在是NP-hard 問題。由于絕對值方程廣泛分布于優(yōu)化領(lǐng)域，一般的線性互補(bǔ)問題，線性規(guī)劃問題，凸二次規(guī)劃等數(shù)學(xué)規(guī)劃問題，見文獻(xiàn)[3-5]都可以等效的以AVE(1) 的形式重新表述，于是如何求解絕對值方程引起了許多研究者的關(guān)注。

求解絕對值方程AVE(1) 的方法有很多，不同的角度提出了不同的方法，許多研究者提出了數(shù)值迭代法求解AVE(1)。在文獻(xiàn)[6]中D.K. Salkuyeh 提出Picard-Hss 迭代法求解，在文獻(xiàn)[7-8]中Ke等人和Guo等人提出求解絕對值方程(AVE)的SOR 類迭代方法，該方法是通過將AVE 等效地重新表述為2×2塊非線性方程而獲得。在文獻(xiàn)[3]中M.Zamani等人提出一種基于凹極小化方法的新方法，通過將絕對值方程AVE 等價于最小化問題進(jìn)行求解。

許多求解絕對值方程的數(shù)值方法，主要基于非線性優(yōu)化技術(shù)，例如：文獻(xiàn)[11-12]中將譜梯度方法應(yīng)用到無約束的非線性方程組。譜梯度方法的主要特點是搜索方向不需要雅克比矩陣，每次迭代只需要較低的計算量而受到廣泛關(guān)注。在文獻(xiàn)[13]中，L.Grippo 等人提出經(jīng)典的譜梯度方法。根據(jù)譜梯度方法的原理，L.Han 等人在文獻(xiàn)[14]中引入多元譜梯度算法。

基于超平面投影的思想，將求解無約束優(yōu)化問題的多元譜梯度方法推廣到求解大規(guī)模的單調(diào)非線性方程組，該方法的優(yōu)點是算法不需要方程組的梯度信息，因而可以用于求解非光滑方程組,無需假設(shè)可微的條件下，也能建立算法的全局收斂性，算法不需要計算和存儲矩陣,因而適合求解大規(guī)模問題。在假設(shè)1 不是A的特征值的基礎(chǔ)上，AVE 可以簡化為無約束的非線性單調(diào)方程組求解，值得一提的是，在文獻(xiàn)[15]中，L. Grippo等人將多元譜梯度投影方法用于求解絕對值方程。

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

對于無約束最優(yōu)化問題：

其中

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

其中

本文后續(xù)部分安排如下：第2節(jié)介紹預(yù)備知識，提出求解絕對值方程的多元譜梯度投影算法；第3 節(jié)全局收斂性分析；第4節(jié)引用絕對值方程的例子進(jìn)行數(shù)值比較；第5節(jié)結(jié)論。

1 預(yù)備知識和算法

令

將問題(1) 轉(zhuǎn)化為(9)，根據(jù)多元譜梯度方法求解絕對值方程的思想，提出改進(jìn)的多元譜梯度投影算法如下：

算法1（MMSGP算法）

步2 計算搜索方向：

計算

步4 通過超平面投影更新的迭代點：

其中

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

2 收斂性分析

一方面：

注意到，

因此，

另一方面，

以下引理證明算法1是適定的。

和

以下證明算法1的全局收斂性。

和

證明：

由(8)和(12)得

根據(jù)(20)-(22)可得：

根據(jù)(23) 和(24) 有

從而

以下將討論兩種可能的情況：

另一方面，

其中，

于是根據(jù)(15)，(28)，(29)，有

綜上，算法1的全局收斂性證明完畢。

3 數(shù)值實驗

表1 符號說明

Table 1 Symbol description.

算例測試的維數(shù) 迭代次數(shù) 算法終止的時間

算例1[8]考慮絕對值方程(1)

表2 算例1的數(shù)值結(jié)果

算例2[18]絕對值方程(1)矩陣由MATLAB命令隨機(jī)產(chǎn)生，

表3 算例2的數(shù)值結(jié)果

Table 3 Numerical results of calculation example 2

10330.0039.08e - 07230.0015.43e - 07260.0023.82e - 07

算例3[19]絕對值方程(1)矩陣由以下形式得到，

表4 算例3的數(shù)值結(jié)果

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可以看出，加入松弛因子后的迭代次數(shù)少于文獻(xiàn)[15]中的方法（MMSGP）的迭代次數(shù)，且CPU時間更短。

4 結(jié)論

通過以上的數(shù)值結(jié)果，可以得出結(jié)論，本文所改進(jìn)的算法優(yōu)于文獻(xiàn)[15]中的方法（MMSGP），在迭代次數(shù)和CPU時間上表現(xiàn)明顯，關(guān)于改進(jìn)多元譜梯度投影算法的方法有很多，下降方向的選取對迭代效果也有一定的影響，之后將繼續(xù)研究如何對下降方向進(jìn)行改進(jìn)，實現(xiàn)更好的迭代效果。

[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）

absolute value equation; multivariate spectral gradient projection algorithm; global convergence; numerical experiment

1674-8085（2022）02-0001-07

O224.2

A

10.3969/j.issn.1674-8085.2022.02.001

2021-11-19；

2021-12-29

國家自然科學(xué)基金項目(11901098)；福建省自然科學(xué)基金項目(2020J05034)

華 瑜(1996-），女，福建三明人，碩士生，主要從事數(shù)值代數(shù)研究(E-mail: 806162057@qq.com)；

*馬昌鳳(1962-)，男，湖南邵陽人，教授，博士生導(dǎo)師，主要從事數(shù)值代數(shù)及其應(yīng)用研究(E-mail:macf@fjnu.edu.cn).