On the preconditioned projective iterative methods for the linear complementarity problems

Edalatpanah, Seyyed Ahmad

RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 2, pp. 341-349.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

This paper aims to propose the new preconditioning approaches for solving linear complementarity problem (LCP). Some years ago, the preconditioned projected iterative methods were presented for the solution of the LCP, and the convergence of these methods has been analyzed. However, most of these methods are not correct, and this is because the complementarity condition of the preconditioned LCP is not always equivalent to that of the un-preconditioned original LCP. To overcome this shortcoming, we present a new strategy with a new preconditioner that ensures the solution of the same problem is correct. We also study the convergence properties of the new preconditioned iterative method for solving LCP. Finally, the new approach is illustrated with the help of a numerical example.

[1] K.G. Murty, Linear Complementarity, Linear and Nonlinear Programming. Heldermann Verlag, Berlin (1988). | MR | Zbl

[2] M.S. Bazaraa, H.D. Sheral and C.M. Shetty, Nonlinear Programming, Theory and Algorithms, 3rd edition. Wiley-Interscience, Hoboken, NJ (2006). | MR | Zbl

[3] R.W. Cottle, J.S. Pang and R.E. Stone, The Linear Complementarity Problem. Academic Press, London (1992). | MR | Zbl

[4] Z.Z. Bai and D.J. Evans, Matrix multisplitting relaxation methods for linear complementarity problems. Int. J. Comput. Math. 63 (1997) 309–326. | DOI | MR | Zbl

[5] D. Yuan and Y.Z. Song, Modified AOR methods for linear complementarity problem. Appl. Math. Comput. 140 (2003) 53–67. | MR | Zbl

[6] L. Cvetković, S. Rapajić, How to improve MAOR method convergence area for linear complementarity problems. Appl. Math. Comput. 162 (2005) 577–584. | MR | Zbl

[7] Y. Li and P. Dai, Generalized AOR methods for linear complementarity problem. Appl. Math. Comput. 188 (2007) 7–18. | MR | Zbl

[8] M.H. Xu and G.F. Luan, A rapid algorithm for a class of linear complementarity problems. Appl. Math. Comput. 188 (2007) 1647–1655. | MR | Zbl

[9] M. Dehghan and M. Hajarian, Convergence of SSOR methods for linear complementarity problems. Oper. Res. Lett. 37 (2009) 219–223. | DOI | MR | Zbl

[10] H. Saberi, S. Najafi, A. Edalatpanah, On the two SAOR iterative formats for solving linear complementarity problems. I.J. Inf. Technol. Comput. Sci. 3 (2011) 19–24.

[11] H. Saberi, S. Najafi and A. Edalatpanah, A kind of symmetrical iterative methods to solve special class of LCP (#). Int. J. Appl. Math. App. 4 (2012) 183–189.

[12] H. Saberi, S. Najafi and A. Edalatpanah, On the convergence regions of generalized accelerated overrelaxation method for linear complementarity problems. J. Optim. Theory Appl. 156 (2013) 859–866. | DOI | MR | Zbl

[13] L.T. Zhang, X.Y. Zuo, T.X. Gu and X.P. Liu, Improved convergence theorems of multisplitting methods for the linear complementarity problem. Appl. Math. Comput. 243 (2014) 982–987. | MR | Zbl

[14] A. Hadjidimos and M. Tzoumas, On the solution of the linear complementarity problem by the generalized accelerated overrelaxation iterative method. J. Optim. Theory Appl. 165 (2015) 545–562. | DOI | MR | Zbl

[15] A. Hadjidimos and M. Tzoumas, The solution of the linear complementarity problem by the matrix analogue of the accelerated overrelaxation iterative method. Numer. Algor. 73 (2016) 665–684. | DOI | MR | Zbl

[16] A. Hadjidimos and L.L. Zhang, Comparison of three classes of algorithms for the solution of the linear complementarity problem with an $H_{+}$-matrix. J. Comput. Appl. Math. 336 (2018) 175–191. | DOI | MR | Zbl

[17] W.M.G. Van Bokhoven, A Class of Linear Complementarity Problems is Solvable in Polynomial Time. Department of Electrical Engineering, University of Technology, Eindhoven, Netherlands (1980).

[18] J.-L. Dong and M.-Q. Jiang, A modified modulus method for symmetric positive-definite linear complementarity problems. Numer. Linear Algebra Appl. 16 (2009) 129–143. | DOI | MR | Zbl

[19] Z.-Z. Bai, Modulus-based matrix splitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 17 (2010) 917–933. | DOI | MR | Zbl

[20] L.-L. Zhang and Z.-R. Ren, Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems. Appl. Math. Lett. 26 (2013) 638–642. | DOI | MR | Zbl

[21] L.-L. Zhang, Y.-P. Zhang and Z.-R. Ren, New convergence proofs of modulus-based synchronous multisplitting iteration methods for linear complementarity problems. Linear Algebra Appl. 481 (2015) 83–93. | DOI | MR | Zbl

[22] S. Liu, H. Zheng and W. Li, A general accelerated modulus-based matrix splitting iteration method for solving linear complementarity problems. Calcolo 53 (2016) 189–199. | DOI | MR | Zbl

[23] H. Zheng, W. Li and S. Vong, A relaxation modulus-based matrix splitting iteration method for solving linear complementarity problems. Numer. Algorithms 74 (2017) 137–152. | DOI | MR | Zbl

[24] H. Saberi Najafi and S.A. Edalatpanah, Verification of iterative methods for the linear complementarity problem: verification of iterative methods for LCPs, edited by P. Vasant, G. Weber and V. Dieu. In: Handbook of Research on Modern Optimization Algorithms and Applications in Engineering and Economics. IGI Global, Hershey, PA (2016) 545–580. | Zbl

[25] C.Y. Liu and C.L. Li, A new preconditioned Generalized AOR methods for the Linear complementarity problem based on a generalized Hadjidimos preconditioner. East Asian J. Appl. Math. 2 (2012) 94–107. | DOI | MR | Zbl

[26] B.X. Duan, W.Y. Zeng and X.P. Zhu, A preconditioned Gauss-Seidel iterative method for linear complementarity problem in intelligent materials system. Adv. Mater. Res. 340 (2012) 3–8. | DOI

[27] Y. Liu, R. Zhang, Y. Wang and X. Huang, Comparison analysis on preconditioned GAOR method for linear complementarity problem. J. Inf. Comput. Sci. 9 (2012) 4493–4500.

[28] H. Saberi Najafi and S.A. Edalatpanah, Iterative methods with analytical preconditioning technique to linear complementarity problems: application to obstacle problems. RAIRO-Oper. Res. 47 (2013) 59–71. | DOI | Numdam | MR | Zbl

[29] C. Liu and C.L. Li, A preconditioned multisplitting and Schwarz method for linear complementarity problem. J. Appl. Math. 519017 (2014) 6. | MR | Zbl

[30] R.S. Varga, Matrix Iterative Analysis, 2nd edition. Springer, Berlin (2000). | MR | Zbl

[31] A. Berman and R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences. Academic Press, New York, NY (1979). | MR | Zbl

[32] M. Hazewinkel, Monomial Representation. Encyclopedia of Mathematics, Springer (2001).

[33] O. Ore, Theory of monomial groups. Trans. Am. Math. Soc. 51 (1942) 15–64. | DOI | JFM | MR