INTERIOR-POINT METHODS FOR P*(κ)-LINEAR
COMPLEMENTARITY PROBLEM BASED ON
GENERALIZED TRIGONOMETRIC BARRIER FUNCTION
M. El Ghami1, G.Q. Wang2
1Mathematics Section
Faculty of Education and Arts
Nord University
Nesna 8700, NORWAY
2College of Fundamental Studies
Shanghai University of Engineering Science
Shanghai, 201620, P.R. CHINA

Abstract

Recently, M. Bouafoa, et al. [#!Bouafia2016!#] investigated a new kernel function which differs from the self-regular kernel functions. The kernel function has a trigonometric Barrier Term. In this paper we generalize the analysis presented in the above paper for P*(κ) Linear Complementarity Problems (LCPs). It is shown that the iteration bound for primal-dual large-update and small-update interior-point methods based on this function is as good as the currently best known iteration bounds for these type methods. The analysis for LCPs deviates significantly from the analysis for linear optimization. Several new tools and techniques are derived in this paper.

Citation details of the article



Journal: International Journal of Applied Mathematics
Journal ISSN (Print): ISSN 1311-1728
Journal ISSN (Electronic): ISSN 1314-8060
Volume: 30
Issue: 1
Year: 2017

DOI: 10.12732/ijam.v30i1.2

Download Section



Download the full text of article from here.

You will need Adobe Acrobat reader. For more information and free download of the reader, please follow this link.

References

  1. [1] Y.Q. Bai, M. El Ghami, and C. Roos, A new efficient large-update primaldual interior-point method based on a finite barrier, SIAM Journal on Optimization, 13, No 3 (2003), 766–782.
  2. [2] Y.Q. Bai, M. El Ghami, and C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization, SIAM Journal on Optimization, 15, No 1 (2004), 101–128.
  3. [3] M. Bouafia, D. Benterki, and A. Yassine, An efficient primal-dual interior point method for linear programing problems based on a new kerne function with a trigonometric barrier term, J. of Optimization Theory and Applications, 170, No 2 (2016), 528–545; doi: 10.1007/s10957-016-0895-0.
  4. [4] E. M. Cho, Log-barrier method for two-stagequadratic stochastic programming, Applied Mathematics and Computation, 164 (2005), 45–69.
  5. [5] Gyeong-Mi Cho, and Min-Kyung Kim, A new large-update interior point algorithm for P∗(κ) LCPs based on kernel functions, Applied Mathematics and Computation, 182 (2006), 1169–1183.
  6. [6] R. Cottle, J.S. Pang, and R.E. Stone, The Linear Complementarity Problem, Academic Press, Boston, 1992.
  7. [7] M. El Ghami, Z. A. Guennoun, S. Bouali and T. Steihaug, Primal-dual interior-point methods for linear optimization based on a kernel function with trigonometric barrier term, J. of Computational and Applied Mathematics, 236, No 15 (2012), 3613–3623.
  8. [8] M. El Ghami, and T. Steihaug, Kernel-function based primal-dual algorithms for P∗ (κ) linear complementarity problems, International J. RAIRO-Operations Research, 44, No 3 (2010), 185–205.
  9. [9] M. El Ghami, Primal-dual algorithms for P (κ) linear complementarity ∗problems based on kernel-function with trigonometric barrier term, Optimization Theory, Decision Making, and Operations Research Applications 2013 (2013), 331–349.
  10. [10] T. Illés doiand M. Nagy, The Mizuno-Todd-Ye predictor-corrector algorithm for sufficient matrix linear complementarity problem, Alkalmaz. Mat. Lapok 22, No 1 (2005), 41–61, doi: 10.1016/j.ejor.2005.08.031.
  11. [11] M. Kojima, N. Megiddo, T. Noma, and A. Yoshise, A primal-dual interior point algorithm for linear programming, In: N. Megiddo (Ed.), Progress in Mathematical Programming; Interior Point Related Methods, 10 (1989), Springer Verlag, New York, 29–47.
  12. [12] M. Kojima, N. Megiddo, T. Noma, and A. Yoshise, A unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Volume 538 of Lecture Notes in Computer Science, Springer Verlag, Berlin, 1991.
  13. [13] J. Miao, A quadratically convergent o((1 + k)√ nl-iteration algorithm for the p (k)-matrix linear complementarity problem, Mathematical Program∗ming, 69 (1995), 355–368.
  14. [14] R.D.C. Monteiro and I. Adler, Interior path following primal-dual algorithms. Part I: Linear programming, Mathematical Programming, 44 (1989), 27–41.
  15. [15] J. Peng, C. Roos, and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization, Mathematical Programming, 93 (2002), 129–171.
  16. [16] J. Peng, C. Roos, and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, 2002.
  17. [17] C. Roos, T. Terlaky, and J.-Ph. Vial, Theory and Algorithms for Linear Optimization. An Interior-Point Approach, Springer Science, 2005.
  18. [18] S. J. Wright, Primal-Dual Interior-Point Methods, SIAM, Philadelphia, USA, 1997.