On the Solution of the Linear Complementarity Problem by the Generalized Accelerated Overrelaxation Iterative Method

详细信息    查看全文

• 作者：Apostolos Hadjidimos (1)
  Michael Tzoumas (2)
  
  1. Department of Electrical & Computer Engineering ; University of Thessaly ; 382聽21聽 ; Volos ; Greece
  2. c/o Department of Mathematics ; University of Ioannina ; 451聽10聽 ; Ioannina ; Greece
  
• 关键词：Linear complementarity problem ; $$H_+ ; $$ H + ; matrices ; Strictly diagonally dominant (SDD) matrices ; Projected methods ; Modulus algorithms ; Generalized accelerated overrelaxation ; Primary 65F10
• 刊名：Journal of Optimization Theory and Applications
• 出版年：2015
• 出版时间：May 2015
• 年：2015
• 卷：165
• 期：2
• 页码：545-562
• 全文大小：266 KB
• 参考文献：1. Berman, A, Plemmons, RJ (1994) Nonnegative Matrices in the Mathematical Sciences. Classics in Applied Mathematics. SIAM, Philadelphia CrossRef
  2. Cottle, RW, Pang, J-S, Stone, RE (1992) The Linear Complementarity Problem. Computer Science and Scientific Computing. Academic Press, Boston
  3. Murty K. G.: Linear Complementarity, Linear and Nonlinear Programming. Internet (Ed.) (1997).
  4. Hildreth, C (1954) Point estimates of ordinates of concave function. J. Am. Stat. Assoc. 49: pp. 598-619 CrossRef
  5. Christopherson, DG (1941) A new mathematical method for the solution of film lubrication problems. Inst. Mech. Eng. Proc. 146: pp. 126-135 CrossRef
  6. Cryer, CW (1971) The method of Christopherson for solving free boundary problems for infinite journal bearings by means of finite differences. Math. Comput. 25: pp. 435-443 CrossRef
  7. Cryer, CW (1971) The solution of a quadratic programming problem using systematic over-relaxation. SIAM J. Control 9: pp. 385-392 CrossRef
  8. Rainondi, AA, Boyd, J (1958) A solution for the finite journal bearing and its application to analysis and design, III. Trans. Am. Soc. Lubric. Eng. 1: pp. 194-209
  9. Fridman, VM, Chernina, VS (1967) An iteration process for the solution of the finite dimensional contact problem. USSR Comput. Math. Math. Phys. 8: pp. 210-214 CrossRef
  10. Varga, RS (2000) Matrix Iterative Analysis (Revised and Expanded). Springer, Berlin CrossRef
  11. Young, DM (1971) Iterative Solution of Large Linear Systems. Academic Press, New York
  12. Mangasarian, OL (1977) Solution of symmetric linear complementarity problems by iterative methods. J. Opt. Theory Appl. 22: pp. 465-485 CrossRef
  13. Ahn, BH (1981) Solution of nonsymmetric linear complementarity problems by iterative methods. J. Opt. Theory Appl. 33: pp. 175-185 CrossRef
  14. Pang, JS (1984) Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem. J. Opt. Theory Appl. 42: pp. 1-17 CrossRef
  15. Pantazopoulos K.: Numerical methods and software for the pricing of American financial derivatives. PhD Thesis, Department of Computer Sciences, Purdue University, West Lafayette (1998).
  16. Koulisianis, MD, Papatheodorou, TS (2003) Improving projected successive overrelaxation method for linear complementarity problems. Appl. Numer. Math. 45: pp. 29-40 CrossRef
  17. Yuan, D, Song, Y (2003) Modified AOR methods for linear complementarity problem. Appl. Math. Comput. 140: pp. 53-67 CrossRef
  18. Lj, Cvetkovi膰, Rapaji膰, S (2005) How to improve MAOR method convergence area for linear complementarity problems. Appl. Math. Comput. 162: pp. 577-584 CrossRef
  19. Li, Y, Dai, P (2007) Generalized AOR for linear complementarity problem. Appl. Math. Comput. 188: pp. 7-18 CrossRef
  20. Saberi Najafi, H, Edalatpanah, SA (2013) On the convergence regions of generalized accelerated overrelaxation method for linear complementarity problems. J. Optim. Theory Appl. 156: pp. 859-866 CrossRef
  21. Saberi Najafi, H, Edalatpanah, SA (2013) Modification of iterative methods for solving linear complementarity problems. Eng. Comput. 30: pp. 910-923 CrossRef
  22. Herceg, D, Lj, Cvetkovi膰 (1990) On an iterative method for a system of equations. Zb. Rad. Prir.- Mat. Fac. Ser. Mat. 20: pp. 11-15
  23. Saberi Najafi, H, Edalatpanah, SA (2013) Iterative methods with analytical preconditioning technique to linear complementarity problems. RAIRO-Oper. Res. 47: pp. 59-71 CrossRef
  24. van Bokhoven, W.M.G.: A class of linear complementarity problems is solvable in polynomial time. Department of Electrical Engineerig, University of Technology, Eindhoven, Netherlands (1980)
  25. Kappel, NW, Watson, LT (1986) Iterative algorithms for the linear complementarity problems. Int. J. Comput. Math. 19: pp. 273-297 CrossRef
  26. Hadjidimos, A, Tzoumas, M (2009) Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem. Linear Algebra Appl. 431: pp. 197-210 CrossRef
  27. Bai, Z-Z (2010) Modulus-based matrix splitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 17: pp. 917-933 CrossRef
  28. Dong, J-L, Jiang, M-Q (2009) A modified modulus method for symmetric positive-definite linear complementarity problems. Numer. Linear Algebra Appl. 16: pp. 129-143 CrossRef
  29. Zhang, L-L (2011) Two-step modulus based matrix splitting iteration method for linear complementarity problems. Numer. Algor. 57: pp. 83-99 CrossRef
  30. Hadjidimos, A, Lapidakis, M, Tzoumas, M (2012) On iterative solution for the linear complementarity problem with an $$H_+-$$ H + - matrix. SIAM J. Matrix Anal. 33: pp. 97-110 CrossRef
  31. Bai, Z-Z, Zhang, L-L (2013) Modulus-based synchronous multisplitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 20: pp. 425-439 CrossRef
  32. Bai, Z-Z, Zhang, L-L (2013) Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems. Numer. Algorithms 62: pp. 59-77 CrossRef
  33. Cvetkovi膰 Lj., Kosti膰 V.: A note on the convergence of the MSMAOR method for linear complementarity problems. Numer. Linear Algebra Appl. (2013) (/DOIurl:10.1002/nla.1896).
  34. Cvetkovi膰 Lj., Hadjidimos A., Kosti膰 V.: On the choice of parameters in MAOR type splitting methods for the linear complementarity problem. Numer. Algor. (2014) (/DOIurl: 10.1007/s11075-014-9824-1).
  35. Hadjidimos, A (1978) Accelerated overrelaxation method. Math. Comput. 32: pp. 149-157 CrossRef
  36. Hadjidimos, A.: Successive overrelaxation (SOR) and related methods. J. Comput. Appl. Math. 123, 177鈥?99 (2000) (Also, in 鈥淣umerical Analysis 2000, Vol. 3, Linear Algebra鈥擫inear Systems and Eigenvalues鈥? van Dooren, P. M., Hadjidimos, A., van der Vorst, H. A. (Eds), North Holland, Amsterdam (2000)).
  37. Ortega, JM, Rheinboldt, W (2000) Iterative Solution of Nonlinear Equations in Several Space Variables. Classics in Applied Mathematics. SIAM, Philadelphia CrossRef
  38. Alanelli, M, Hadjidimos, A (2006) A new iterative criterion for $$H-$$ H - matrices. SIAM J. Matrix Anal. Appl. 29: pp. 160-176 CrossRef
  39. Bru Garcia, R, Gim茅nez, I, Hadjidimos, A (2012) Is $$A \in {C}^{n, n}$$ A 鈭C n , n a general $$H-$$ H - matrix?. Linear Algebra Appl. 436: pp. 364-380 CrossRef
  
• 刊物主题：Calculus of Variations and Optimal Control; Optimization; Optimization; Theory of Computation; Applications of Mathematics; Engineering, general; Operations Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2878

文摘

In the present work, we determine intervals of convergence for the various parameters involved for what is known as the generalized accelerated overrelaxation iterative method for the solution of the linear complementarity problem. The convergence intervals found constitute sufficient conditions for the generalized accelerated overrelaxation method to converge and are better than what have been known so far.