International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 3, No. 2, 8 Mar. 2011
Cover page and Table of Contents: PDF (size: 142KB)
Two SAOR Iterative Formats for Solving Linear Complementarity Problems
Full Text (PDF, 142KB), PP.38-45
Views: 0 Downloads: 0
Author(s)
Xian-li Han
1,*
Dong-jin Yuan
1
Shan Jiang
1
Index Terms
SAOR method, linear complementarity problem, convergence, H-matrix, M-matrix, monotone
Abstract
In this paper, we propose two new iterative SAOR methods to solve the linear complementarity problem. Some sufficient conditions for the convergence of two new iterative methods are presented, when the system matrix M is an M-matrix. Moreover, when M is an L-matrix, we discuss the monotone convergence of the new methods. And in the numerical experiments we report some computational results with the two proposed SAOR formats.
Cite This Paper
Xian-li Han, Dong-jin Yuan, Shan Jiang, "Two SAOR Iterative Formats for Solving Linear Complementarity Problems", International Journal of Information Technology and Computer Science(IJITCS), vol.3, no.2, pp.38-45, 2011. DOI: 10.5815/ijitcs.2011.02.06
Reference
[1] A. Berman and R.J. Plemmons, Nonnegative Matrix in the Mathematical Sciences, Academic Press, New York, 1979.
[2] K. G. Murty, Algorithm for finding all the feasible complementary bases for a linear complementarity problem, IE Dept., University of Michigan, Ann Arbor, 1972 .
[3] S. C. Billups, “K. G. Murty, Complementarity problems,” J. Comput. Appl. Math., vol. 124, pp. 303–318, 2000.
[4] R. W. Cottle and G. B. Dantzig, “Complementarity pivot theory of mathematical programming,” Linear Algebra Appl., vol. 1, pp, 103–125, 1968.
[5] R. W. Cottle, G. H. Golub and R. S. Sacher, “On the solution of large structured linear complementarity problems,” vol. III, Technical Report STAN-CS-74 439, Stanford University, Stanford, CA, 1974.
[6] R. W. Cottle and R. S. Sacher, “On the solution of large structured linear complementarity problems: The tridiagonal case,” Appl. Math. Optim., vol. 3, pp. 321–341, 1976.
[7] R. W. Cottle, G. H. Golub and R. S. Sacher, “On the solution of large structured linear complementarity problems: The block partitioned case,” Appl. Math. Optim., vol. 4, pp. 347–363, 1978.
[8] O. L. Mangasarian, “Solution of general linear complementarity problems via nondifferentiable concave minimization,” Acta Math. Vietnam., vol. 22, pp. 199–205, 1997.
[9] O. L. Mangasarian, “The linear complemenarity problem as a separable bilinear program,” J. Global Optim., vol. 6, pp. 153–161, 1995.
[10] K. G. Murty, “On the number of solutions to the complementarity problem and spanning properties of complementary cones,” Linear Algebra Appl., vol. 5, pp. 65–108, 1972.
[11] K. G. Murty, “Note on a Bard-type scheme for solving the complementarity problem,” Opsearch, vol. 11, pp. 123–130, 1974.
[12] K. G. Murty, On the linear complementarity problem, in: Third Symposium on Operations Research, Univ. Mannheim, Mannheim, 1978, Section I, pp. 425–439, Operations Res. Verfahren, 31, Hain, Konigstein/Ts., 1979.
[13] S. Wang and X. Yang, “A power penalty method for linear complementarity problems,” Oper. Res. Lett., vol. 36, pp. 211–214, 2008.
[14] M. D. Koulisianis and T. S. Papatheodorou, “Improving projected successive overrelaxation method for linear complementarity problems.” Appl. Numer. Math., vol. 45, pp. 29–40, 2003.
[15] D. J. Yuan and Y. Song, “Modified AOR Methods for linear complementarity problem,” Appl. Math. Comput., vol. 140, pp. 53–67, 2003.
[16] Y. Li and P. Dai, “Generalized AOR methods for linear complementarity problem,” Appl. Math. Comput., vol. 88, pp. 7–18, 2007.
[17] Z. Z. Bai and D. J. Evans, “Matrix multisplitting relaxation methods for the linear complementarity problem,” SIAM J. Matrix Anal. Appl., vol. 21, pp. 309–326, 1997.
[18] Z. Z. Bai, “On the convergence of the multisplitting methods for the linear complementarity problem,” SIAM J. Matrix Anal. Appl., vol. 21, pp. 67–78, 1999.
[19] Z. Z. Bai and D. J. Evans, “Matrix multisplitting relaxation methods for the linear complementarity problem,” SIAM J. Matrix Anal. Appl., vol. 21, pp. 309–326, 1997.
[20] M. Wu, L. Wang and Y. Song, “Preconditioned AOR iterative method for linear systems,” Appl. Numer. Math., vol. 57, pp. 672–685, 2007.
[21] Z. Z. Bai and D. J. Evans, “Matrix multisplitting relaxation methods for linear complementarity problems,” Int. J. Comput. Math., vol. 63, pp. 309–326, 1997.
[22] A. Berman and R. J. Plemmons, Non-Negative Matrices in the Mathematical Sciences, 3rd ed., SIAM, Philadelphia, 1994.
[23] R. S. Varga, Matrix iterative Analysis, Springer-Verlag, New York, 2000.
[24] B. H. Ahn, “Solution of nonsymmetric linear complementarity problems by iterative methods,” J. Optim. Theory Appl., vol. 33, pp. 185–197, 1981.
[25] O. L. Mangasarian, “Solution of symmetric linear complementarity problems by iterative methods,” J. Optim. Theory Appl., vol. 22, pp. 465–485, 1977.