Improvement of Convergence of One- and Two-Step MSM Iteration Methods for Nondifferentiable Nonlinear Complementarity Problems

doi:10.1007/s42967-024-00378-x

摘要/Abstract

摘要： Our goal is to improve the convergence theory of the one-step modulus-based synchronous multisplitting (MSM) and the two-step modulus-based synchronous multisplitting (TMSM) iteration methods for a class of nondifferentiable nonlinear complementarity problems (NCPs) with H₊-matrices. The analysis is developed and the results are renewed under some conditions weakened than before.

关键词: Nonlinear complementarity problem (NCP), Modulus-based, Multisplitting, H₊-matrix, H-splitting, Convergence

Abstract: Our goal is to improve the convergence theory of the one-step modulus-based synchronous multisplitting (MSM) and the two-step modulus-based synchronous multisplitting (TMSM) iteration methods for a class of nondifferentiable nonlinear complementarity problems (NCPs) with H₊-matrices. The analysis is developed and the results are renewed under some conditions weakened than before.

Key words: Nonlinear complementarity problem (NCP), Modulus-based, Multisplitting, H₊-matrix, H-splitting, Convergence

中图分类号:

Gui-Lin Yan, Yu-Jiang Wu, Bo Deng. Improvement of Convergence of One- and Two-Step MSM Iteration Methods for Nondifferentiable Nonlinear Complementarity Problems[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 733-758.

参考文献

1. Bai, Z.-Z.: On the monotone convergence of the projected iteration methods for linear complementarity problems. Numer. Math. J. Chinese Univ. 5, 228–233 (1996)
2. Bai, Z.-Z.: On the convergence of the multisplitting methods for the linear complementarity problem. SIAM J. Matrix Anal. Appl. 21, 67–78 (1999)
3. Bai, Z.-Z.: Experimental study of the asynchronous multisplitting relaxation methods for the linear complementarity problems. J. Comput. Math. 20, 561–574 (2002)
4. Bai, Z.-Z.: Modulus-based matrix splitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 17, 917–933 (2010)
5. Bai, Z.-Z., Huang, Y.-G.: A class of asynchronous parallel multisplitting relaxation methods for large sparse linear complementarity problems. J. Comput. Math. 21, 773–790 (2003)
6. Bai, Z.-Z., Zhang, L.-L.: Modulus-based synchronous multisplitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 20, 425–439 (2013)
7. Bai, Z.-Z., Zhang, L.-L.: Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems. Numer. Algorithms 62, 59–77 (2013)
8. Berman, A., Plemmons, R.J.: Nonnegative Matrices in Mathematical Sciences. Academic Press, Cambridge (1979)
9. Cottle, R.W., Dantzig, G.B.: Complementary pivot theory of mathematical programming. Linear Algebra Appl. 1, 103–125 (1968)
10. Cryer, C.W.: The solution of a quadratic programming problem using systematic overrelaxation. SIAM J. Control 9, 385–392 (1971)
11. Dong, J.-L.: Inexact multisplitting methods for linear complementarity problems. J. Comput. Appl. Math. 223, 714–724 (2009)
12. Dong, J.-L., Jiang, M.-Q.: A modified modulus method for symmetric positive-definite linear complementarity problems. Numer. Linear Algebra Appl. 16, 129–143 (2009)
13. Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
14. Ferris, M.C., Pang, J.-S.: Engineering and economic applications of complementarity problems. SIAM Review 39, 669–713 (1997)
15. Formmer, A., Mayer, G.: Convergence of relaxed parallel multisplitting methods. Linear Algebra Appl. 119, 141–152 (1989)
16. Hadjidimos, A., Lapidakis, M., Tzoumas, M.: On iterative solution for the linear complementarity problem with an H⁺-matrix. SIAM J. MAtrix Anal 33, 97–110 (2012)
17. Hadjidimos, A., Tzoumas, M.: Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem. Linear Algebra Appl. 431, 197–210 (2009)
18. Hu, J.-G.: Estimates of B-1 A ∞ and their applications. Math. Numer. Sinica 4, 272–282 (1982)
19. Hu, J.-G.: Scaling transformation and convergence of splittings of a matrix. Math. Numer. Sinica 5, 72–78 (1983)
20. Huang, N., Ma, C.-F.: The modulus-based matrix splitting algorithms for a class of weakly nonlinear complementarity problems. Numer. Linear Algebra Appl. 23, 558–569 (2016)
21. Li, R., Wang, Y., Yin, J.-F.: On the convergence of two-step modulus-based matrix splitting iteration methods for a restricted class of nonlinear complementarity problems with H+-matrices. Numer. Math. Theory Methods Appl. 11, 128–139 (2018)
22. Li, W.: A general modulus-based matrix splitting method for linear complementarity problems of Hmatrices. Appl. Math. Lett. 26, 1159–1164 (2013)
23. Ma, C.-F., Jiang, L.-H., Wang, D.-S.: The convergence of a smoothing damped Gauss-Newton method for nonlinear complementarity problem. Nonlinear Anal. Real World Appl. 10, 2072–2087 (2009)
24. Machida, N., Fukushima, M., Ibaraki, T.: A multisplitting method for symmetric linear complementarity problems. J. Comput. Appl. Math. 62, 217–227 (1995)
25. Murty, K.G.: Linear Complementarity, Linear and Nonlinear Programming. Heldermann, Berlin (1988)
26. O’Leary, D.P., White, R.E.: Multisplittings of matrices and parallel solution of linear systems. SIAM J. Algebraic Discrete Methods 6, 630–640 (1985)
27. Pardalos, P.M.: The Linear Complementarity Problem. Springer, Netherlands (1995)
28. Sun, Z., Zeng, J.-P.: A monotone semismooth Newton type method for a class of complementarity problems. J. Comput. Appl. Math. 235, 1261–1274 (2011)
29. van Bokhoven, W.M.G.: Piecewise-Linear Modelling and Analysis. Proefschrift, Eindhoven (1981)
30. Varga, R.S.: Matrix Iterative Analysis. Prentice Hall, New Jersey (1962)
31. Wu, Y.-J., Yan, G.-L., Yang, A.-L.: Modulus-based synchronous multisplitting iteration methods for a restricted class of nonlinear complementarity problems. Numer. Math. Theor. Meth. Appl. 12(3), 709–726 (2019)
32. Wu, Y.-J., Zhang, W.-H., Yang, A.-L.: Modulus-based inexact non-alternating preconditioned splitting method for linear complementarity problems. Linear Multilinear Algebra 70, 7414–7432 (2022)
33. Xia, Z.-C., Li, C.-L.: Modulus-based matrix splitting iteration methods for a class of nonlinear complementarity problem. Appl. Math. Comput. 271, 34–42 (2015)
34. Xie, S.-L., Xu, H.-R., Zeng, J.-P.: Two-step modulus-based matrix splitting iteration method for a class of nonlinear complementarity problems. Linear Algebra Appl. 494, 1–10 (2016)
35. Xu, W.-W., Liu, H.: A modified general modulus-based matrix splitting method for linear complementarity problems of H-matrices. Linear Algebra Appl. 458, 626–637 (2014)
36. Yan, G.-L., Wu, Y.-J., Yang, A.-L., Jomah, S.A.S.: Two-step modulus-based synchronous multisplitting iteration methods for nonlinear complementarity problems. East Asian J. Appl. Math. 12(2), 449–469 (2022)
37. Yang, H.-J., Li, Q.-G., Xu, H.-R.: A multiplicative Schwarz iteration scheme for solving the linear complementarity problem with an H-matrix. Linear Algebra Appl. 430, 1085–1098 (2009)
38. Zhang, L.-L.: Two-step modulus-based matrix splitting iteration method for linear complementarity problems. Numer. Algorithms 57, 83–99 (2011)
39. Zhang, L.-L.: Two-step modulus-based synchronous multisplitting iteration methods for linear complementarity problems. J. Comput. Math. 33, 100–112 (2015)
40. Zhang, L.-L., Ren, Z.-R.: Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems. Appl. Math. Lett. 26, 638–642 (2013)
41. Zheng, H., Vong, S.W.: Improved convergence theorems of the two-step modulus-based matrix splitting and synchronous multisplitting iteration methods for solving linear complementarity problems. Linear Multilinear Algebra 67, 1773–1784 (2019)
42. Zheng, N., Yin, J.-F.: Accelerated modulus-based matrix splitting iteration methods for linear complementarity problem. Numer. Algorithms 64, 245–262 (2013)
43. Zheng, N., Yin, J.-F.: Convergence of accelerated modulus-based matrix splitting iteration methods for linear complementarity problem with an H₊-matrix. J. Comput. Appl. Math. 260, 281–293 (2014)
44. Zhou, C.-C., Cao, Y., Shi, Q., Qiu, J.: A robust two-step modulus-based matrix splitting iteration method for mixed-size cell circuit legalization problem. J. Circuits Syst. Comput. 32(8), 2350129 (2023)
45. Zhou, C.-C., Qiu, J., Cao, Y., Yang, G.-C., Shen, Q.-Q., Shi, Q.: An accelerated modulus-based matrix splitting iteration method for mixed-size cell circuits legalization. Integr. VLSI J. 88(1), 20–31 (2023)

[1]	Shipeng Mao, Jiaao Sun. Error Estimates of Finite Element Method for the Incompressible Ferrohydrodynamics Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 485-535.
[2]	Mengfei Wang, Yan Xu. Superconvergence of UWLDG Method for One-Dimensional Linear Sixth-Order Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 771-795.
[3]	Ren Liu, Lifei Wu. Numerical Approach for Solving Two-Dimensional Time-Fractional Fisher Equation via HABC-N Method[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 315-346.
[4]	Pavel Bakhvalov, Mikhail Surnachev. On the Order of Accuracy of Edge-Based Schemes: a Peterson-Type Counter-Example[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 372-391.
[5]	Jieying Zhang, Caixia Ou, Zhibo Wang, Seakweng Vong. An Order Reduction Method for the Nonlinear Caputo-Hadamard Fractional Diffusion-Wave Model[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 392-408.
[6]	Mária Lukáčová-Medvid'ová, Yuhuan Yuan. Convergence of a Generalized Riemann Problem Scheme for the Burgers Equation[J]. Communications on Applied Mathematics and Computation, 2024, 6(4): 2215-2238.
[7]	Hua Zheng, Xiaoping Lu, Seakweng Vong. A Two-Step Modulus-Based Matrix Splitting Iteration Method Without Auxiliary Variables for Solving Vertical Linear Complementarity Problems[J]. Communications on Applied Mathematics and Computation, 2024, 6(4): 2475-2492.
[8]	Michel Bergmann, Afaf Bouharguane, Angelo Iollo, Alexis Tardieu. High Order ADER-IPDG Methods for the Unsteady Advection-Diffusion Equation[J]. Communications on Applied Mathematics and Computation, 2024, 6(3): 1954-1977.
[9]	Yifan Chen, Thomas Y. Hou, Yixuan Wang. Exponentially Convergent Multiscale Finite Element Method[J]. Communications on Applied Mathematics and Computation, 2024, 6(2): 862-878.
[10]	Wes Whiting, Bao Wang, Jack Xin. Convergence of Hyperbolic Neural Networks Under Riemannian Stochastic Gradient Descent[J]. Communications on Applied Mathematics and Computation, 2024, 6(2): 1175-1188.
[11]	Xuechun Liu, Haijin Wang, Jue Yan, Xinghui Zhong. Superconvergence of Direct Discontinuous Galerkin Methods: Eigen-structure Analysis Based on Fourier Approach[J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 257-278.
[12]	Changpin Li, Dongxia Li, Zhen Wang. L1/LDG Method for the Generalized Time-Fractional Burgers Equation in Two Spatial Dimensions[J]. Communications on Applied Mathematics and Computation, 2023, 5(4): 1299-1322.
[13]	Liang Li, Jun Zhu, Chi-Wang Shu, Yong-Tao Zhang. A Fixed-Point Fast Sweeping WENO Method with Inverse Lax-Wendroff Boundary Treatment for Steady State of Hyperbolic Conservation Laws[J]. Communications on Applied Mathematics and Computation, 2023, 5(1): 403-427.
[14]	Xiaoying Han, Habib N. Najm. Modeling Fast Diffusion Processes in Time Integration of Stiff Stochastic Differential Equations[J]. Communications on Applied Mathematics and Computation, 2022, 4(4): 1457-1493.
[15]	Xiaozhou Li. How to Design a Generic Accuracy-Enhancing Filter for Discontinuous Galerkin Methods[J]. Communications on Applied Mathematics and Computation, 2022, 4(3): 759-782.