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

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.

Keywords

Nonlinear complementarity problem (NCP) / Modulus-based / Multisplitting / $H_{+}$-matrix / H-splitting / Convergence / 90C33 / 65K05 / 65F10

References

[1] Bai Z-Z. On the monotone convergence of the projected iteration methods for linear complementarity problems. Numer. Math. J. Chinese Univ.. 1996, 5: 228-233

[2] Bai Z-Z. On the convergence of the multisplitting methods for the linear complementarity problem. SIAM J. Matrix Anal. Appl.. 1999, 21: 67-78

[3] Bai Z-Z. Experimental study of the asynchronous multisplitting relaxation methods for the linear complementarity problems. J. Comput. Math.. 2002, 20: 561-574

[4] Bai Z-Z. Modulus-based matrix splitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl.. 2010, 17: 917-933

[5] Bai Z-Z, Huang Y-G. A class of asynchronous parallel multisplitting relaxation methods for large sparse linear complementarity problems. J. Comput. Math.. 2003, 21: 773-790

[6] Bai Z-Z, Zhang L-L. Modulus-based synchronous multisplitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl.. 2013, 20: 425-439

[7] Bai Z-Z, Zhang L-L. Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems. Numer. Algorithms. 2013, 62: 59-77

[8] Berman A, Plemmons RJ. Nonnegative Matrices in Mathematical Sciences. 1979, Cambridge, Academic Press

[9] Cottle RW, Dantzig GB. Complementary pivot theory of mathematical programming. Linear Algebra Appl.. 1968, 1: 103-125

[10] Cryer CW. The solution of a quadratic programming problem using systematic overrelaxation. SIAM J. Control. 1971, 9: 385-392

[11] Dong J-L. Inexact multisplitting methods for linear complementarity problems. J. Comput. Appl. Math.. 2009, 223: 714-724

[12] Dong J-L, Jiang M-Q. A modified modulus method for symmetric positive-definite linear complementarity problems. Numer. Linear Algebra Appl.. 2009, 16: 129-143

[13] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)

[14] Ferris MC, Pang J-S. Engineering and economic applications of complementarity problems. SIAM Review. 1997, 39: 669-713

[15] Formmer A, Mayer G. Convergence of relaxed parallel multisplitting methods. Linear Algebra Appl.. 1989, 119: 141-152

[16] Hadjidimos A, Lapidakis M, Tzoumas M. On iterative solution for the linear complementarity problem with an $H_{+}$-matrix. SIAM J. MAtrix Anal. 2012, 33: 97-110

[17] Hadjidimos A, Tzoumas M. Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem. Linear Algebra Appl.. 2009, 431: 197-210

[18] Hu J-G. Estimates of $\Vert {B}^{-1}{A}\Vert _{\infty }$ and their applications. Math. Numer. Sinica. 1982, 4: 272-282

[19] Hu J-G. Scaling transformation and convergence of splittings of a matrix. Math. Numer. Sinica. 1983, 5: 72-78

[20] Huang N, Ma C-F. The modulus-based matrix splitting algorithms for a class of weakly nonlinear complementarity problems. Numer. Linear Algebra Appl.. 2016, 23: 558-569

[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.. 2018, 11: 128-139

[22] Li W. A general modulus-based matrix splitting method for linear complementarity problems of $H$-matrices. Appl. Math. Lett.. 2013, 26: 1159-1164

[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.. 2009, 10: 2072-2087

[24] Machida N, Fukushima M, Ibaraki T. A multisplitting method for symmetric linear complementarity problems. J. Comput. Appl. Math.. 1995, 62: 217-227

[25] Murty, K.G.: Linear Complementarity, Linear and Nonlinear Programming. Heldermann, Berlin (1988)

[26] O’Leary DP, White RE. Multisplittings of matrices and parallel solution of linear systems. SIAM J. Algebraic Discrete Methods. 1985, 6: 630-640

[27] Pardalos PM. The Linear Complementarity Problem. 1995, Netherlands, Springer

[28] Sun Z, Zeng J-P. A monotone semismooth Newton type method for a class of complementarity problems. J. Comput. Appl. Math.. 2011, 235: 1261-1274

[29] van Bokhoven WMG. Piecewise-Linear Modelling and Analysis. 1981, Eindhoven, Proefschrift

[30] Varga RS. Matrix Iterative Analysis. 1962, New Jersey, Prentice Hall

[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.. 2019, 12(3): 709-726

[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. 2022, 70: 7414-7432

[33] Xia Z-C, Li C-L. Modulus-based matrix splitting iteration methods for a class of nonlinear complementarity problem. Appl. Math. Comput.. 2015, 271: 34-42

[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.. 2016, 494: 1-10

[35] Xu W-W, Liu H. A modified general modulus-based matrix splitting method for linear complementarity problems of $H$-matrices. Linear Algebra Appl.. 2014, 458: 626-637

[36] Yan G-L, Wu Y-J, Yang A-L, Jomah SAS. Two-step modulus-based synchronous multisplitting iteration methods for nonlinear complementarity problems. East Asian J. Appl. Math.. 2022, 12(2): 449-469

[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.. 2009, 430: 1085-1098

[38] Zhang L-L. Two-step modulus-based matrix splitting iteration method for linear complementarity problems. Numer. Algorithms. 2011, 57: 83-99

[39] Zhang L-L. Two-step modulus-based synchronous multisplitting iteration methods for linear complementarity problems. J. Comput. Math.. 2015, 33: 100-112

[40] Zhang L-L, Ren Z-R. Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems. Appl. Math. Lett.. 2013, 26: 638-642

[41] Zheng H, Vong SW. Improved convergence theorems of the two-step modulus-based matrix splitting and synchronous multisplitting iteration methods for solving linear complementarity problems. Linear Multilinear Algebra. 2019, 67: 1773-1784

[42] Zheng N, Yin J-F. Accelerated modulus-based matrix splitting iteration methods for linear complementarity problem. Numer. Algorithms. 2013, 64: 245-262

[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.. 2014, 260: 281-293

[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.. 2023, 32(8): 2350129

[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.. 2023, 88(1): 20-31

Funding

National Natural Science Foundation of China(12161030)

RIGHTS & PERMISSIONS

Shanghai University